KindiakMath

Counting the Fractions

In this post, we will prove that \mathbb Q is countable. But let’s revisit some previous results in a different perspective.

Definition 1. Let A and B be sets. We denote C := A \sqcup B if C = A \cup B and A \cap B = \emptyset.

Lemma 1. Let A and B be countable. Then A \sqcup B is countable.

Proof. Let f_A : A \to \{1\} \times \mathbb N and f_B : B \to \{2\} \times \mathbb N be injections, where \{k\} \times \mathbb N is clearly countable by the injection n \mapsto (k, n). Then the map f : A \sqcup B \to \mathbb N \times \mathbb N defined by

\displaystyle f(x) = \begin{cases} f_A(x),\quad \text{if}\, x \in A,\\f_B(x),\quad \text{if}\, x \in B, \end{cases}

is an injection.

Corollary 1. Let A_1,\dots,A_n be countable. Then

\displaystyle \bigsqcup_{k=1}^n A_k := A_1 \sqcup A_2 \sqcup \cdots \sqcup A_n,

where the right-hand side can be defined inductively, is countable.

Proof. Apply Lemma 1 inductively.

Corollary 2. \mathbb Z is countably infinite.

Proof. Define \mathbb N^- := \{-n : n \in \mathbb N\}, which is countable by the bijection x \mapsto -x. Then

\mathbb Z = \mathbb N^- \sqcup \{0\} \sqcup \mathbb N^+ \supseteq \{0\} \cup \mathbb N^+ = \mathbb N

is countably infinite.

In like fashion, if we can prove that \mathbb Q^+ := \{r \in \mathbb Q : r > 0\} is countable, the countability of \mathbb Q is obvious.

Theorem 1. If \mathbb Q^+ is countably infinite, then so is \mathbb Q = \mathbb Q^- \sqcup \{0\} \sqcup \mathbb Q^+.

We shall now answer the golden question: is \mathbb Q^+ countably infinite? Yes!

Theorem 2. \mathbb Q^+ countably infinite.

Proof. For any r \in \mathbb Q^+, find unique positive integers p,q with no common factors such that r = p/q. Define the required injection f : \mathbb Q^+ \to \mathbb N \times \mathbb N by f(r) = (p, q).

What about \mathbb R? Remarkably, Georg Cantor used a diagonal argument to prove that this is false. Before that, let’s prove a slightly easier result, which will “transfer” over to \mathbb R.

Theorem 3. Let \mathcal P(\mathbb N) := \{K : K \subseteq \mathbb N\} denote the collection of subsets of \mathbb N. Then there is no bijection f : \mathbb N \to \mathcal P(\mathbb N).

Proof. An obvious injection \mathbb N \to \mathcal P(\mathbb N) is given by n \mapsto \{n\}. Suppose, for contradiction, that there exists a bijection f : \mathbb N \to \mathcal P(\mathbb N). Define the set

K := \{x \in \mathbb N : x \notin f(x)\} \in \mathcal P(\mathbb N).

Since f is bijective, there exists n \in \mathbb N such that f(n) = K. Then

\quad n \in f(n) \quad \iff \quad n \in K \quad \iff \quad n \notin f(n),

a contradiction.

Corollary 4. \mathcal P(\mathbb N) is not countable.

Definition 2. A set K that is not countable is uncountable.

Corollary 3. \mathbb R is uncountable.

Proof. To show that \mathbb R is infinite follows from \mathbb Q \subseteq \mathbb R. We now aim to show that \mathbb R is not countable.

To that end, define the injection f : \mathcal P(\mathbb N) \to \mathbb R by

\displaystyle f(K) = \sum_{k \in K} \frac{1}{{10}^k}.

Thus, if \mathbb R is countable, then \mathcal P(\mathbb N) is countable, a contradiction.

Finally, since \mathbb R \subseteq \mathbb C := \{a + bi : a, b \in \mathbb R\}, we know that \mathbb C is uncountable. In fact, it is not hard to show that \mathbb C \sim \mathbb R \times \mathbb R as sets.

However, a curious question emerges. We have seen that \mathbb N \sim \mathbb N \times \mathbb N—is is true that \mathbb R \sim \mathbb R \times \mathbb R? This question is left as an exercise—please let me know in the comments section below.

—Joel Kindiak, 6 Nov 24, 1459H

,

Published by

joelkindiak

Response

  1. Analysing Baby Infinity – KindiakMath

    […] the next post, we will revisit the cardinality of through a different perspective, and use that to establish the […]

    Like

    Reply

Leave a comment