The Preconditions of Infinity

A common topic being discussed on YouTube is how some infinities are bigger than others. We formulate that precisely using cardinality. We first make some preliminary notations.

Definition 1. Let $K_1, K_2$ be sets. Write $K_1 \sim K_2$ whenever there exists a bijection $f : K_1 \to K_2$ .

Lemma 1. The relation $\sim$ satisfy the following properties:

For any set $K$ , $K \sim K$ .
For sets $K_1, K_2$ , $K_1 \sim K_2$ implies $K_2 \sim K_2$ .
For sets $K_1,K_2,K_3$ , $K_1 \sim K_2$ and $K_2 \sim K_3$ together imply that $K_1 \sim K_3$ .

By Russell’s paradox, we cannot call $\sim$ an equivalence relation on the set of sets.

Denote $[0]:= \{\} \equiv \emptyset$ and $[n]:= \{1,\dots,n\}$ for $n \in \mathbb N^+$ . For the rest of this writeup, we will adopt the convention $\mathbb N = \mathbb{N}_0$ .

Theorem 1. Let $K \subseteq \mathbb N$ . Exactly one of the following is true:

$K \sim [n]$ for some $n \in \mathbb N$ .
$K \sim \mathbb N$ .

In the first case, we say that $K$ is finite. In the second case, we say that $K$ is infinite.

Proof. Firstly, if $K = \emptyset$ , then $K = \emptyset \sim \emptyset = [0]$ . Next, suppose $K \neq \emptyset$ . Define $K_0 := K$ . By the well-ordering principle, for each $i \in \mathbb N$ , whenever $K_i \neq \emptyset$ , iteratively define

$y_i := \min K_i,\quad K_{i+1} := K_i \backslash \{y_i\}.$

Define $L := \{y_i : i \in \mathbb N\} \subseteq K$ .

If the process ends, then there exists $n \in \mathbb N$ such that $K_{n+1} = \emptyset$ . In this case, $L = \{y_1,\dots,y_n\}$ and $L \sim [n]$ via the bijection $k \mapsto y_k$ .

If the process never ends, then $L \sim \mathbb N$ via the bijection $k \mapsto y_k$ . We need to prove that $K = L$ . It suffices to show that $K \subseteq L$ .

Fix $x \in K$ . Define $M := \{y_i \in L : y_0 \leq y_i < x\}$ . We claim that $M$ is finite. Suppose otherwise. Then for any $n \in \mathbb{N}^+$ ,

$y_n \geq y_{n-1} + 1 \geq \cdots \geq \underbrace{ 1 + \cdots + 1 }_n = n.$

We can make this calculation airtight using a quick exercise in mathematical induction. In particular, $y_{x+1} \geq x$ .

On the other hand, $y_{n+1} \in M$ , so that $y_{x+1} < x \leq y_{x+1}$ , a contradiction. Thus, $M$ is finite and we can write $M = \{y_0,y_1,\dots,y_{n-1}\}$ for simplicity, so that $y_n \geq x$ .

Clearly, $x \in K \backslash M$ . On the other hand, by construction,

$y_n = \min (K \backslash M) \leq x.$

Therefore, $x = y_n \in L$ , as required.

Corollary 1. A set $K$ is countable precisely when $K \sim L$ for some $L \subseteq \mathbb N$ . For any countable set $K$ , exactly one of the following is true:

$K \sim [n]$ for some $n \in \mathbb N$ .
$K \sim \mathbb N$ .

In the first case, we say that $K$ is finite. In the second case, we say that $K$ is infinite.

Proof. The result follows by the transitivity of $\sim$ .

Now, we have almost the necessary groundwork to discuss cardinality. We need to ensure that the notion of size as “number of items” is a consistent (i.e. well-defined) notion, at least for finite sets.

—Joel Kindiak, 4 Nov 24, 0951H

KindiakMath

The Preconditions of Infinity

Response

Leave a comment Cancel reply

The Preconditions of Infinity

Share this:

Response

Leave a comment Cancel reply