Finite Sets

# Finite Sets

Often times we may be interested is knowing just how many elements a set has. This notion is easy to consider when the number of elements in a set is finite.

Definition: A set $S$ is said to be a Finite Set of size $n$ if there exists a bijection $f : \{ 1, 2, ..., n \} \to S$. A set $S$ is said to be an Infinite Set if it is not a finite set. |

*The notation "$\mathbb{N}_n$" is often used to denote the set $\{ 1, 2, ..., n \}$.*

The idea behind the definition above is that a set $S$ is a finite set of size $n$ if we can assign to each natural number $1, 2, ..., n$ an element of $S$ and that every element of $S$ is given such a number.

For example, consider the set $S = \{ 3, 6, -1, 4, \pi \}$. This set contains precisely $5$-elements, so by the definition there should exist a bijection $f : \mathbb{N}_5 \to S$. One such bijection is described below:

$x \in \mathbb{N}_5$ | $f(x) \in S$ |
---|---|

$1$ | $f(1) = 3$ |

$2$ | $f(2) = 6$ |

$3$ | $f(3) = -1$ |

$4$ | $f(4) = 4$ |

$5$ | $f(5) = \pi$ |

We will now look at some theorems on finite sets.

Theorem 1 (Uniqueness of the Size of a Set): Let $S$ be a finite set with $n \in \mathbb{N}$ elements. The natural number $n$ is unique. |

**Proof:**Let $S$ be a finite set containing $m$ elements. Then there exists a bijection $f_1 : \mathbb{N}_m \to S$. Suppose that $S$ also has $n$ elements where $m \neq n$. Then there exists a bijection $f_2 : \mathbb{N}_n \to S$.

- Now recall that is a function $f$ is bijective then there exists an inverse function $f^{-1}$. So $f_2$ has an inverse function that is bijective, namely $f^{-1}_2 : S \to \mathbb{N}_n$. Now since $f_1 : \mathbb{N}_m \to S$ and $f^{-1}_2 : S \to \mathbb{N}_n$ are bijective then the composition $f^{-1}_2 \circ f_1 : \mathbb{N}_m \to \mathbb{N}_n$ is bijective.

- However such a function that maps $\mathbb{N}_m$ onto $\mathbb{N}_n$ where $m \neq n$ cannot be bijective.

- For example, let $f : \mathbb{N}_m \to \mathbb{N}_n$ and consider the case where $m > n$. Then let $f(1) =1$, $f(2) = 2$, …, $f(n) = n$. So all elements in the codomain have been "taken". So $f(n+1) = f(k)$ for some $k \in \mathbb{N}_m$. But $n + 1 \neq k$, so $f$ is not injective.

- Now consider the case where $m < n$. Once again let $f(1) = 1$, $f(2) = 2$, …, $f(m) = m$. So then $(m + 1) \in \mathbb{N}_n$ is not mapped to from $f$ so $f$ is not surjective and so $f$ is not bijective.

- We thus conclude that $m = n$ and so the number of elements in a set is unique. $\blacksquare$

Theorem 2: Let $A$ be a set that has $m$ elements and let $B$ bet a set that has $n$ elements. If $A \cap B = \emptyset$ then $A \cup B$ has $m + n$ elements. |

**Proof:**Since $A$ has $m$ elements there exists a bijection $f_1 : \mathbb{N}_m \to A$, and since $B$ has $n$ elements there exists a bijection $f_2 : \mathbb{N}_n \to B$. Now we will define a function $h : \mathbb{N}_{m+n} \to A \cup B$ such that:

\begin{align} h(x) = \left\{\begin{matrix} f(x) & \mathrm{if} \: 1 \leq i \leq m \\ g(x - m) & \mathrm{if} \: m+1 \leq x \leq m + n \end{matrix}\right. \end{align}

- So such a bijection $h$ exists, so $A \cup B$ has $m + n$ elements. $\blacksquare$

Theorem 3: If $A$ is a set that contains $m$ elements and $B \subseteq A$ is a set that contains $1$ element then $A \setminus B$ contains $m - 1$ elements. |

**Proof:**Let $A$ be a set containing $m$ elements. Then $A = \{ a_1, a_2, ..., a_m \}$. If $B \subseteq A$ is a set containing $1$ element, then $B = \{ a_j \}$ for some $j = 1, 2, ..., m$.

- Since $A$ contains $m$ elements there exists a bijection $f_1 : \mathbb{N}_m \to A$, define it by $f(1) = a_1$, $f(2) = a_2$, …, $f(m) = a_m$. Then for the set $A \setminus B = \{ a_1, a_2, ..., a_{j-1}, a_{j+1}, ..., a_m \}$, we can define a bijection $f_2 : \mathbb{N}_{m-1} \to A \setminus B$ by omitting $f(j) = a_j$.

- Therefore $A \setminus B$ contains $m - 1$ elements. $\blacksquare$

Theorem 4: Let $A$ and $B$ be sets such that $B \subseteq A$. If $A$ is a finite set then $B$ is also a finite set. If $B$ is an infinite set then $A$ is also an infinite set. |

**Proof:**Let $A$ and $B$ be sets such that $B \subseteq A$.

- For the first part of the proof, let $A$ be a finite set and suppose instead that $B$ is NOT a finite set. Then $B$ is an infinite set, but since $B \subseteq A$, then there is an infinite number of elements contained in $A$ as well. But this contradicts the fact that $A$ is a finite set. So our assumption that $B$ was not finite was false, hence, $B$ is finite.

- The second part of the proof is the contrapositive of the first, so if $B$ is an infinite set, then $A$ is also infinite. $\blacksquare$