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\to |P(A)|=2^n$

Collection of Sets

Universal Union

Similar to existential quantifier.

$\bigcup _{i=1}^{\mathrm{\infty }}{A}_i=\{x\in U|\mathrm{\exists }i(x\in A_i)\}$

Universal Intersection

Similar to universal quantifier.

$\bigcap _{i=1}^{\mathrm{\infty }}{A}_i=\{x\in U|\mathrm{\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\to 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)

$\mathrm{\forall }x,y\in A(x\ne y\to f(x)\ne 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.

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

bijective

both injective and bijective

function can be inverted by changing the direction of the arrows