Countable Sets

# Countable Sets

Often times we may be interested is knowing just how many elements a set has. We will now formally define the size of a set.

 Definition: A set $S$ is said to have $n$-many elements if there exists a bijection $f : \mathbb{N}_n \to S$ where $\mathbb{N}_n := \{ 1, 2, ..., n \}$. A set containing $n$-many elements is said to be a finite set. If $S$ is not a finite set then it is said to be an infinite set.

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 another important definition for the number of elements in a set.

 Definition: A set $S$ is said to be denumerable or countably infinite if there exists a bijection $f: \mathbb{N} \to S$. $S$ is said to be countable if it is either a finite set or denumerable. $S$ is said to be uncountable otherwise.

Let's first look at an example of a denumerable set. Consider the set of even natural numbers $\mathbb{N}_{\mathrm{even}} := \{ 2n : n \in \mathbb{N} \} = \{ 2, 4, 6, ... \}$ We can find a bijection $f : \mathbb{N} \to S$ with the formula $f(n) = 2n$, so we can say that $S_{\mathrm{even}}$ is denumerable and thus also countable. Similarly, the set of odd natural numbers is also denumerable

Another example of a denumerable set is the set of integers $\mathbb{Z}$. To show that this is true, we need to show that there exists a bijection $f: \mathbb{N} \to \mathbb{Z}$. Consider the following bijection:

(1)
\begin{align} f(n) = \left\{\begin{matrix} \frac{n}{2} & \mathrm{if \: n \:is \:even}\\ -\frac{n-1}{2} & \mathrm{if \: n \: is \: odd } \end{matrix}\right. \end{align}

For example, $f(1) = 0$, $f(2) = 1$, $f(3) = -1$, $f(4) = 2$, $f(5) = -2$, … So such a bijection exists and so $\mathbb{Z}$ is denumerable.

Of course, there are sets that are not countable, for example, the set of real numbers $\mathbb{R}$, that is, there does not exist a bijection that maps $\mathbb{N}$ onto $\mathbb{R}$.

We will now look at some theorems regarding finite and infinite 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:
(2)
\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$