Notes on set cardinality

Credit: deviantART / Sc0t0ma

I'm working through LMU's Introduction to Mathematical Philosophy on Coursera at the moment. I stumbled across something that confused me (specifically, the claim that has fewer elements than defines a total order), so I'm using this blog post as a medium in which to work through it methodically enough to explain it to someone else.

(Warning: maths below the fold.)

Some boring technical definitions of function properties:

Definition (injectivity): we say \(f \in (X \rightarrow Y)\) is injective iff no two elements map to the same result, i.e. \(\forall x_0, x_1 \in X: f(x_0) = f(x_1) \Leftrightarrow x_0 = x_1\).
Definition (surjectivity): we say \(f \in (X \rightarrow Y)\) is surjective iff the preimage of \(Y\) in \(f\) is \(X\), i.e. \(\forall y \in Y: \exists x \in X: f(x)=y\).
Definition (bijectivity): we say \(f \in (X \rightarrow Y)\) is bijective (or one-to-one) iff it is injective and surjective.

Some boring technical definitions of relations on sets:

Definition: the sets \(X\) and \(Y\) have equal size (\(X =_\Sigma Y\)) iff there exists a bijection (one-to-one function) between them.

Example: \(\{0,1,2,3,\cdots\} =_\Sigma \{0,2,4,6,\cdots\}\), with one possible bijection being \(\lambda x \cdot 2x\).

Example: \(\mathbb{N} \neq_\Sigma \mathbb{R}\), due to Cantor's classic proof.

Definition: \(X\) is no larger than \(Y\) (\(X \leq_\Sigma Y\)) iff \(X =_\Sigma Y' \subset Y\).

Definition: \(X\) is smaller than \(Y\) (\(X <_\Sigma Y\)) iff \(X \leq_\Sigma Y \land X \neq_\Sigma Y\).

Example: \(\mathbb{N} <_\Sigma \mathbb{R}\). We already have non-equality; we also have \(\mathbb{N} \leq_\Sigma \mathbb{R}\) due to \(\mathbb{N} =_\Sigma \mathbb{N} \subset \mathbb{R}\).

At this point, the lecturer continued with, And so this is a total order!. My immediate reaction to this was Okay!, followed half a minute later by Wait... we're talking about an ordering which implies some very non-intuitive things I don't really understand, like all the transfinite ordinals. Maybe I should double check this makes sense.

Transitivity and reflexivity of \(\leq_\Sigma\) are obvious. It seems that we can break down the hard part of the proof that \(\leq_\Sigma\) is a total order into two parts:

Conjecture 1 (totality): for all sets \(X\) and \(Y\), at least one of \(X \leq_\Sigma Y\) or \(Y \leq_\Sigma X\).

Conjecture 2 (antisymmetry): for all sets \(X\) and \(Y\), if \(X \leq_\Sigma Y\) and \(Y \leq_\Sigma X\), then \(X =_\Sigma Y\).

Let's plow right in:

Proof of Conjecture 1: Assume \(\lnot(Y \leq_\Sigma X)\). It suffices to show that there exists some injective function from \(X\) to \(Y\).

By our initial assumption, there are no injective functions from \(Y\) to \(X\). Thus we can invoke Zorn's lemma (over the set of \(X \rightarrow Y\) functions, and the repeated operation of find some \(f(x_0) = f(x_1)\), and redefine \(f(x_0)\) to some value not in the image of \(f\)). The resulting function can't be surjective (otherwise its inverses would be injective functions from \(Y\) to \(X\), a contradiction); hence it must be injective.

The second half took me far longer than it should have (the better part of a day):

Proof of Conjecture 2: Assume \(X \leq_\Sigma Y\) and \(Y \leq_\Sigma X\). It follows that there exist functions \(u, v \in (X \rightarrow Y)\), such that \(u\) is injective and \(v\) is surjective. (The latter results by inverting some injective function going in the opposite direction.)

Then, we invoke Zorn's lemma (over the set of surjective \(X \rightarrow Y\) functions, and the repeated operation of find some \(f(x_0) = f(x_1) \neq u(x_1)\) and redefine \(f(x_1)\) as \(u(x_1)\).) The resulting function must be a bijection, as desired.

Thus, set cardinalities are a total order. It's not clear to me whether the Axiom of Choice was necessary to prove this, though.

...well, fuck.
Credit: Abstruse Goose

From here, the lecture notes went on to provide a definition of infinity attributed to Dedekind:

Definition (infinitude): \(X\) is infinite iff \(X =_\Sigma X'\) for some \(X' \subset X\). (That is, it is equal-sized to a strict subset of itself.)

Just for kicks (and going completely off-track from the lecture) let's prove that \(\mathbb{N}\) is the (well, a) smallest infinite set.

Lemma: \(X\) is infinite if and only if \(\mathbb{N} \leq_\Sigma X\).

Proof (\(\Rightarrow\)): We prove the contrapositive. Assume \(X <_\Sigma \mathbb{N}\). Then we can show that \(X =_\Sigma \{0, 1, \cdots, n-1\}\) for some \(n \in \mathbb{N}\) (\(|X| = n\)). By induction, we can show that any set of size \(n \in \mathbb{N}\) is not infinite.

Proof (\(\Leftarrow\)): Let \(f\) be an injective function from \(\mathbb{N} \rightarrow X\). Let \(X' = X \setminus \{f(0)\}\). It remains to provide a bijection \(g \in (X \rightarrow X')\): \[ g(x) = \left\{ \begin{array}{ll} f(f^{-1}(x) + 1), & x \in f(\mathbb{N}) \\ x, & \textrm{otherwise} \end{array} \right. \]

Finally, let's prove a couple of simple properties about Hilbert's hotel:

Lemma (infinity plus infinity): If \(X\) is infinite, then \(X =_\Sigma \mathbb{Z}_2 \times X\).

Proof (sketch): By infinitude, we can take an element out of \(X\) without decreasing its size. Combined with Zorn's lemma, this gives a simple construction.

Lemma (infinity times infinity): If \(X\) is infinite, then \(X =_\Sigma X^2\).

Example: \(\mathbb{N} =_\Sigma \mathbb{N^2}\). One bijection is: \[f(x_0,x_1) = x_0 + \dfrac{(x_0 + x_1)(x_0 + x_1 + 1)}{2}\]

Example: \(\mathbb{R} =_\Sigma \mathbb{R^2}\). We could construct a bijection by taking two real numbers and interlacing their digits (with suitable fudging to remove [countably many] duplicates).

Proof: Let \(X\) be given. To show that \(X^2 \leq_\Sigma X\), we want to find a partition function \(f \in (X \rightarrow \mathcal{P}X)\) such that all \(f(x)\) are disjoint and all \(f(x) =_\Sigma X\). (The construction follows fairly easily from that.)

Zorn's lemma again. This time, the set under consideration is the set of partition functions in \(X \rightarrow \mathcal{P}X\) such that all \(f(x)\) satisfy \(f(x) =_\Sigma X \lor f(x) = \emptyset\). The repeated operation is taking some \(f(x_0) = X', f(x_1) = \emptyset\), picking a bijection \(g \in (\mathbb{Z}_2 \times X' \leftrightarrow X')\), and redefining \(f(x_i) = g(i,X')\).

The resulting function is a partition with all \(f(x) =_\Sigma X\) as desired.

Corollary: If \(X \leq_\Sigma Y\) and \(Y\) is infinite, then \(X \times Y =_\Sigma Y\).

Proof: \(Y \leq_\Sigma X \times Y \leq_\Sigma Y \times Y \leq_\Sigma Y\).