## Tuesday, August 13, 2013

### Notes on set cardinality

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.

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$.