# Not All Infinities Are Born Equal

The reader is probably familiar with the notion of countable and uncountable sets. Though, most students are only familiar with the use of cantor’s diagonalization argument to prove countability of things like $\mathbb{Q}$. As is the spirit of this blog, I’d like to talk about proving these sorts of things with an alternate argument.

We begin with a notion of the cardinality of sets, and use this to define a countable set. The goal here is to show that, for an infinite set, injectivity into $\mathbb{N}$ is enough to prove countability. We proceed to prove that finite cartesian products of countable sets are countable, as well as countable unions of countable sets, using this lemma.

Formally,
Let $A$ and $B$ be sets. We say that $A$ and $B$ have the same cardinality if there is a bijective mappings $f: A \to B$.

We definite countability as follows:

Definition 1:
A set $A$ is finite if it has the same cardinality to a finite subset $\{1,\ldots,n\} \subset \mathbb{N}$. A set $A$ is countable if there is a bijective mapping $f: A \to \mathbb{N}$.

If $A$ is finite or countable, we say $A$ is at most countable.

Often, one may see $\aleph_0$ used to represent a countable cardinality, and $\aleph_1$ used to represent the cardinality of $\mathbb{R}$.

In the definition, we may relax the requirement that $f$ be bijective through the following lemma:

Lemma 1:
If $A$ is infinite, and $f: A \to \mathbb{N}$ is injective, then $A$ is countable.

Proof:

Let $\eta_1 = \min \limits_{x \in A} \{f(x)\}$

$\eta_2 = \min \limits_{x \in A} \{f(x) \setminus \{\eta_1\}\}$

$\vdots$

$\eta_k = \min \limits_{x \in A} \{f(x) \setminus \{\eta_1,\eta_2, \ldots, \eta_k\}\}$

Since $f$ is injective, for each $a_i \in A$, there is a unique $\eta_i \in \mathbb{N}$ with $f(a_i) = \eta_i$.

Define $g(a_i) = i$. Clearly $g$ is bijective. Thus, given an injective $f$, the map $g \circ f: A \to \mathbb{N} \to \mathbb{N}$ is bijective. Thus, $A$ is countable.

With this lemma, we may prove that $\mathbb{Q}$ is countable. This is of vital importance in the study of analysis, as this gives $\mathbb{R}$ a countable dense subset (making it  a separable space).

Theorem 1: $\mathbb{Q}$ is countable.

Proof:

Recall $\mathbb{Q} := \{\frac{s}{r} \, ; \, s \in \mathbb{N}, r \in \mathbb{N}\}$. By the lemma, we need define an injective $f: \mathbb{Q} \to \mathbb{N}$. We may use a trick involving primes. Let $p_1,p_2$ be prime numbers greater than $1$. Define $f(\frac{s}{r}) = p_1^sp_2^r$. WE see that $f$ is injective (check this), so we may order the co-domain of $f$ and construct a mapping $g$ as in the lemma.

Using the same trick with primes, we may prove a finite cartesian product of countable sets is countable. Therefore, say, $\mathbb{Q}^n$ or $\mathbb{Q} \times \mathbb{N}$ are countable.

Theorem 2:
If $\{A_i\}_{i \in I_n}$ is a finite set of countable sets, $A = \prod \limits_{i \in I_n} A_i$ is countable.

Proof:

Let $p_1,\ldots,p_n$ be prime numbers greater than $1$. Since each $A_i$ is countable, there are injective mappings $f_i: A_i \to \mathbb{N}$. For an $a \in A$, define $f(a) = p_1^{f(a_1)}p_2^{f(a_2)} \cdots p_k^{f(a_k)}$

If $a \neq b$, $f(a) \neq f(b)$ since this will only happen if $f(a_i) = f(b_i)$. Thus, $A$ is countable.

Moreover, given a countable union of countable sets, said union is countable. This will be useful for proving various properties about infinite subsets of $latex\mathbb{R}&s=1$.

Let $I$ be countable, and $\{A_i\}_{i \in I}$ be a set of countable sets. Then, $A = \bigcup \limits_{i \in I} A_i$ is countable.

Proof:

Since $I$ is countable, there is a mapping $g: I \to \mathbb{N}$. Since each $A_i$ is countable, there are mappings $f_i: A_i \to \mathbb{N}$. We need find a mapping $h: \bigcup \limits_{i \in I} A_i \to \mathbb{N}$ that is injective.

Define for each $x \in A$, an indice $\alpha(x) = \min \limits_{i \in I} \{g(i) : x \in A_i \}$. Let $p_1,p_2$ be primes greater than $1$. Then the mapping $h(x) = p_1^{f_{\alpha(x)}(x)}p_2^{\alpha(x)}$ is injective.To see $h$ is injective, consider $x \neq y$. Then, either $\alpha_1 = \alpha_2$ or $\alpha_1 \neq \alpha_2$. In either case, we use the injectivity of $f$ and $g$ to see that $h$ is injective at $x$. Thus, $A$ is countable.

An interesting lemma involving all binary strings is given as well. That is, the set of binary strings is uncountable.

Lemma 2:
The set $A:= \{(a_0,a_1 \ldots) \, ; \, a_i \in \{0,1\}\}$ is uncountable.

Suppose $A$ is countable. Then we may split $A$ into countably many members, so that we can define

$X_1 = (a_1^1,a_2^2, \ldots)$

$\vdots$

$X_k = (a_0^k, a_1^k, \ldots )$

Now we may if we find an element not in the collection $\{X_j\}_{j \in \mathbb{N}}$, then $A$ is not countable. Consider $b = (b_0, b_1, \ldots)$ where

$b_j=\left\{ \begin{array}{lr} 0 & : a_j =1 \\ 0 & : a_j =0 \end{array} \right.$

Clearly $b \in A$, but $b \neq X_k$ for any $k \in \mathbb{N}$. Thus, we have a contradiction.

As a corollary to this lemma, we have the nice fact:
$\mathbb{R}$ is not countable. To prove this just note that $A \subset \mathbb{R}^+ \subset \mathbb{R}$, so that $\mathbb{R}$ cannot be countable.

I think I’ll stop here, as that’s about all I really need to say about countability basics. I’d recommend seeing how these arguments can be used to prove different facts about countable sets. For example, use the lemma above to prove $(a,b)$ is uncountable. As usual, any inquiries can be sent to erdosninth@gmail.com.

Cheers,

J.T.