MATH 302 Lecture 8

« previous | Wednesday, September 21, 2011 | next »

Sets (cont'd)

Power Set

$P(A)$ the set of all subsets of A

$X\in P(A)\equiv X\subseteq A$

$|A|=n\rightarrow |P(A)|=2^{n}$

Collection of Sets

Universal Union

Similar to existential quantifier.

$\bigcup _{i=1}^{\infty }A_{i}=\{x\in U|\exists i(x\in A_{i})\}$

Universal Intersection

Similar to universal quantifier.

$\bigcap _{i=1}^{\infty }A_{i}=\{x\in U|\forall i(x\in A_{i})\}$

Function

Mapping of elements in set $A$ (domain) to elements in set $B$ (codomain)

each element $a$ in the domain is the initial point for exactly one mapping

for all $a\in A$ there is assigned a unique value in the codomain $B$

$f:A\rightarrow B$

f (	a	) =	b
	preimage of b		image of a

Properties of Functions

one-to-one (injective)

every element in the codomain must have at most one arrow pointing to it. (Two domain elements cannot be mapped to the same codomain element)

$\forall x,y\in A(x\neq y\rightarrow f(x)\neq f(y))$

prove injectivity using the contrapositive (assume that there is an $x$ and a $y$ so that $f(x)=f(y)$ and prove that $x$ must equal $y$)

onto (surjective)

every element in the codomain must have at least one arrow pointing to it.

$\forall b\in B\exists a\in A(f(a)=b)$

bijective

both injective and bijective

function can be inverted by changing the direction of the arrows