MATH 302 Lecture 8

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

Sets (cont'd)

Power Set

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A)} the set of all subsets of A

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \in P(A) \equiv X \subseteq A}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|=n \rightarrow |P(A)|=2^n}

Collection of Sets

Universal Union

Similar to existential quantifier.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall x, y \in A ( x \ne y \rightarrow f(x) \ne f(y) )}

prove injectivity using the contrapositive (assume that there is an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} so that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = f(y)} and prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} must equal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} )

onto (surjective)

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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