Sets and Functions

1 Sets

1.1 Special Sets

$$\begin{array}{rlrlrl}& \mathbb{N}& & \text{Natural numbers}& & \left\{0,1,2\dots \right\}\\ & \mathbb{Z}& & \text{Integers}& & \left\{\dots ,-1,0,1,\dots \right\}\\ & \mathbb{Q}& & \text{Rational numbers}& & \\ & \mathbb{R}& & \text{Real numbers}& & \end{array}$$

1.2 Empty Set and Singleton Set

• Empty set ($\varnothing$ or $\{\}$) is a set with no elements
• Singleton set is a set with one element

$\varnothing \ne \left\{\varnothing \right\}$

1.3 Set Equality

$$\forall x(x\in A\leftrightarrow x\in B)$$

1.4 Proper Subset

$$(A\subset B)\leftrightarrow (A\subseteq B\wedge A\ne B)$$

1.5 Power Set

$P(S)$ is the set of all subsets of $S$

There will be $2^n$ elements, including the empty set
Since for $n$ elements, number of subsets = the number of ways to permute the $n$ elements, just like the number of combination for a $n$ bit binary number when each element is represented by either 1 or 0

1.6 Ordered Tuple

$$(a_1,a_2,\dots ,a_n)$$

Ordered 2-tuple is an ordered pair

Two ordered n-tuples are equal if and only if $m=n$ and $a_i=b_i$ for all $i=1,2,\dots ,n$

1.7 Cartesian Product

$$\begin{array}{rl}& A\times B=\left\{(a,b)\mid a\in A\wedge b\in B\right\}\\ & \\ & A_1\times A_2\times \cdots \times A_n=\left\{(a_1,a_2,\dots ,a_n)\mid a_i\in A_i\text{ for }i=1,2,\dots ,n\right\}\end{array}$$

1.8 Relation

$$R\subset A\times B$$

1.9 Union

${\cup }_{i=1}^n{A}_i$ is the set that contains elements from at least one set in the collection

1.10 Intersection

${\cap }_{i=1}^n{A}_i$ is the set that contains elements from all the sets in the collection

1.11 Cardinality

$|S|$ is the number of distinct elements in $S$

$$|A\cup B|=|A|+|B|-|A\cap B|$$ $$\begin{array}{rl}|A\cup B\cup C|& =|A|+|B|+|C|\\ & -|A\cap B|-|A\cap C|-|B\cap C|\\ & +|A\cap B\cap C|\end{array}$$

Two sets have same cardinality if and only if there is a one-to-one correspondence from $A$ to $B$

1.11.1 Cardinality of natural number

$$|\mathbb{N}|={\aleph }_0$$

1.11.2 Countability

$$\begin{array}{rlrl}& \text{Finite}& & |S|=n\text{ for some }n\in \mathbb{N}\\ & \text{Infinitely Countable}& & |S|={\aleph }_0\\ & \text{Otherwise uncountable}& & \end{array}$$

1.12 Difference and Complement

$A-B$ is the set that contains elements in $A$ but not in $B$

$$\overline{A}=U-A$$

1.13 Set Identities

• Associative Laws

$$\begin{array}{r}A\cup (B\cup C)=(A\cup B)\cup C\\ A\cap (B\cap C)=(A\cap B)\cap C\end{array}$$

• Distributive Laws

$$\begin{array}{r}A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\\ A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\end{array}$$

• De Morgan’s Laws

$$\begin{array}{r}\overline{A\cup B}=\overline{A}\cap \overline{B}\\ \overline{A\cap B}=\overline{A}\cup \overline{B}\end{array}$$

• Absorption Laws

$$\begin{array}{r}A\cup (A\cap B)=A\\ A\cap (A\cup B)=A\end{array}$$

• Complement Laws

$$\begin{array}{rl}& A\cup \overline{A}=U\\ & A\cap \overline{A}=\varnothing \end{array}$$

2 Functions

2.1 Domain Codomain Range

If $f$ is a function from $A$ to $B$ and $f(a)=b$

$A$ is the domain
$B$ is the codomain
The set of all $b$ is the range

2.2 Function Types

• Injective
  • One-to-one
• Surjective
  • Every value on RHS has at least one mapping
  • Not surjective
• Bijection
  • Injective and surjective
  • One-to-one correspondent
  • $|A|=|B|$, i.e. $A$ and $B$ has the same number of elements

2.3 Counting Functions

2.3.1 Generic Functions

For set $A$ and $B$ with size $m$ and $n$, there are $n^m$ functions $A\to B$

Because for every value in $A$, there are $n$ possible choices, i.e. $\underset{m\text{ times}}{\underbrace{n\times n\times \cdots \times n}}=n^m$

Applied in Ex 4

2.3.2 Injective Functions

For set $A$ and $B$ with size $m$ and $n$

If $m>n$, there is no injective function

If $m\le n$, there are $n(n-1)(n-2)\dots (n-m+1)$ functions