KindiakMath

Analysing Baby Infinity

A fuller discussion on infinity can be contemplated in set theory. Here, we’ll discuss the zeroth-order infinity: the cardinal number \aleph_0, which we defined to be |\mathbb N|. In fact, we will gradually analyse the cardinality of the famous sets \mathbb Z, \mathbb Q, \mathbb R, \mathbb C.

Definition 1. Let K be a set. Write |K| = \aleph_0 = |\mathbb N| if K \sim \mathbb N (in these posts, the notation K \sim L refers to the existence of a bijection f : K \to L). In words, we say that K is countably infinite.

Example 1. The set 2\mathbb N := \{2n : n \in \mathbb N\} is countably infinite.

Proof. Define the bijection f : \mathbb N \to 2\mathbb N by f(k) = 2k.

In fact, more is true.

Theorem 1. Let K be any set, and f : \mathbb N \to K be injective. Then f(\mathbb N) is countably infinite.

Proof. Define the bijection \tilde f : \mathbb N \to f(\mathbb N) by \tilde f(k) = f(k).

We have seen previously that any countable set K, if not finite, must satisfy K \sim \mathbb N. Sometimes, it is easier to use several intermediate results to establish countability. To take full advantage of these results, we need some auxiliary tools.

Lemma 1. Fix finite sets K,L \subseteq \mathbb N. Suppose there exists an injection f : K \to L. Then |K| \leq |L|.

Proof. Writing K \sim [m] and L \sim [n], it suffices to prove the case K = [m] and L = [n]. Similar to before, we will prove this result by induction on n.

Base case: Suppose n = 0. Then [m] \sim \emptyset. Let f : [m] \to \emptyset denote an injection, which must be the empty function f : \emptyset \to \emptyset, f = \emptyset. In particular, [m] = \emptyset, and following previous arguments, m = 0 \leq n, as required.

Induction step: Fix n \in \mathbb N. Suppose f : [m] \to [n+1] is injective. We need to show that m \leq n + 1. If [m] = \emptyset then we are done. Assume instead that m \geq 1.

Define the sets M^- := [m-1] and N := [n+1] \backslash \{g(m)\}. Then N \sim [n] via the bijection h : N \to [n] defined by

\displaystyle h(i) := \begin{cases} i & \text{if}\quad 1 \leq i < g(m), \\ i-1 & \text{if}\quad g(j) < i \leq m. \end{cases}

Furthermore, the map \phi : [m-1] \to [n] defined by

\phi(x) = (h \circ f)(x)

is injective. By the induction hypothesis, we have m-1 \leq n, which simplifies to m \leq n+1, as required.

Next, we will establish two preservation results.

Lemma 2. Let K, L be sets and f : K \to L be an injection.

  • If L is finite, so is K.
  • If L is countable, so is K.

Proof. Since K \sim f(K) \subseteq L, we will assume K \subseteq L without loss of generality via the injective inclusion map \iota : K \to L defined by \iota(k) = k. The second claim is immediate from established definitions. For the first claim, L \sim [n] for some n \in \mathbb N.

Suppose for a contradiction that K is not finite. Then K \sim \mathbb N. Let g : \mathbb N \to K denote a possible bijection. This means that the composite map \iota \circ g : \mathbb N \to [n] is injective. In particular, the restriction (\iota \circ g) |_{[n+1]} : [n+1] \to [n] is injective. This implies n +1 \leq n, a blatant contradiction.

This characterisation of countability in terms of injections is an incredibly useful abbreviation whenever we need to evaluate a set’s cardinality.

Lemma 3. Let K be any set. Then K is countable (resp. finite) if and only if there exists a countable set L (resp. finite) and an injection f : K \to L.

Proof. The proof of (\Leftarrow) is the content of Lemma 2. For (\Rightarrow), let’s first suppose K is countable. Then there exists a (countable) set L \subseteq \mathbb N such that K \sim L. Let g : K \to L denote the bijection. Then f : K \to \mathbb N defined by f(x) = g(x) is injective, as required. If K is finite, replace \mathbb N with [n] for sufficiently large n.

Lemma 4. \mathbb N \times \mathbb N is countably infinite.

Proof. Define the injective map f : \mathbb N \times \mathbb N \to \mathbb N by f(i,j) = 2^i \times 3^j. Since \mathbb N \times \mathbb N \sim f(\mathbb N \times \mathbb N) \subseteq \mathbb N, we can conclude \mathbb N \times \mathbb N is countable. Since \mathbb N \times \mathbb N contains \mathbb N \times \{0\} \sim \mathbb N, it is not finite. Thus, \mathbb N \times \mathbb N \sim \mathbb N, which implies |\mathbb N \times \mathbb N| = \aleph_0.

In fact, more is true.

Theorem 2. Let K, L be countable. Then K \times L is countable.

Proof. By the proof of Lemma 3, find injections f : K \to \mathbb N and g : L \to \mathbb N. Then the map h : K \times L \to \mathbb N \times \mathbb N defined by h(x,y) = (f(x),g(y)) is injective. By Lemma 3 again, K \times L is countable.

Finally, we can evaluate the cardinality of \mathbb Z.

Theorem 3. \mathbb Z is countably infinite.

Proof. Define the injection f : \mathbb Z \to \mathbb N \times \mathbb N by

\displaystyle f(x) = \begin{cases} (x,0), & \text{if}\, x \geq 0, \\ (0,x), & \text{if}\, x \leq 0. \end{cases}

In the next post, we will revisit the cardinality of \mathbb Z through a different perspective, and use that to establish the cardinality of \mathbb Q.

—Joel Kindiak, 6 Nov 24, 1232H

,

Published by

joelkindiak

Responses

  1. The Peculiar Dimensions of Polynomial Space – KindiakMath

    […] it true that ? No! Consider the case . It turns out there isn’t even a bijection, since is a countably infinite set and is uncountably […]

    Like

    Reply
  2. The Size of Finity – KindiakMath

    […] this shows us is that finite cardinality makes sense. What about infinite cardinality? This is where the fun […]

    Like

    Reply

Leave a comment