Review of Discrete Math

Sets, Relations, Set Operations, Cartesian Product, Functions

$A^* = \bigcup_{k=1}^{\infty} A^k$ (set of all finite types of $A$)

if $S\cap T = \empty$, then $|S\cup T| = |S| + |U|$.

Exercise: show that $|S\cup T| = |S| + |T| - |S\cap T|$

$S\cup T = S\cup (T - S)$

$= (S-T) \cup (S\cap T) \cup (T - S)$

$|S\cup T| = |S-T| + |S\cap T| + |T-S|$

$=(|S-T| + |S\cap T|) + (|T-S| + |S\cap T|) - |S\cap T|$

$= |S| + |T| - |S\cap T|$

Functions

$f: S\rightarrow T \:\mathrm{if}\: \forall s\in S \:\exists t\in T \:\mathrm{s.t.}\: f(s) = t$

$S$ domain of $f$

$T$ codomain of $f$

$f(S) = \{t\in T : \exists s\in S, f(s) = t\}$

(image or range of $f$)

$f$ is injective iff $\forall s_1,s_2 \in S \:\mathrm{if}\: s_1\neq s_2,\, f(s_1) \neq f(s_2)$

$f$ is surjective iff $\forall t\in T,\, \exists s\in S \:\mathrm{s.t.}\: f(s) = t$