0.4 Cardinality of Sets, Schröder-Bernstein's Theorem

Now we move on to cardinality of sets.

If $X$ and $Y$ are nonempty sets, we define the expressions

1. $\left| X \right| \leq \left| Y \right|$ if there exist injection from $X$ to $Y$.
2. $\left| X \right| = \left| Y \right|$ if there exist bijection from $X$ to $Y$.
3. $\left| X \right| \geq \left| Y \right|$ if there exist surjection from $X$ to $Y$.

Note that cardinality is defined in relative sense.

Let $X$ and $Y$ be sets.

1. $\left| X \right| \leq \left| Y \right| \iff \left| Y \right| \geq \left| X \right|$
2. Either $\left| X \right| \leq \left| Y \right|$ or $\left| Y \right| \leq \left| X \right|$.

1. Suppose $|X| \leq |Y|$. Then there exist an injection $f: X \rightarrow Y$. Pick any $x_{0} \in X$. Define $g: Y \rightarrow X$ as follows. $$ g(y) = \begin{cases} f^{-1}(y) & (\text{if } y \in f(X)) \\ x_{0} & (\text{otherwise}) \end{cases} $$ $g$ is well defined for $y \in f(X)$ since $f$ is injective. It is evident that $g$ is surjective. So $|Y| \geq |X|$.
   Conversely, suppose $|Y| \geq |X|$. Then there exist a surjection $g: Y \rightarrow X$. For any $x \in X$, $g^{-1}(x)$ is nonempty subset of $X$. So using axiom of choice, $$ \prod_{x \in X} g^{-1}(x) $$ is nonempty. Any function $f: X \rightarrow Y$ in $\prod_{x \in X} g^{-1}(x)$ would be injection. This gives $|X| \leq |Y|$.
2. Let $\mathcal{J}$ be a collection of injections from subsets of $X$ to $Y$. Memebers of $\mathcal{J}$ can be considered as subsets of $X \times Y$, so $\mathcal{J}$ is partially ordered by set inclusion $\subset$. Let $S$ be a linearly ordered subset of $\mathcal{J}$. Then consider $$ f^{\ast} = \bigcup_{f \in S} f $$ By linear ordering of $S$, if a function $f \in S$ has element $(x, y) \in f$, then so does any function in $S$ which has $x$ in its domain. So $f^{\ast}$ is well defined function. Also for if $f^{\ast}(s) = f^{\ast}(t)$, then $f^{\ast}(s) = f_{1}(s)$ for some $f_{1} \in S$ such that $s \in dom(f_{1})$, $f^{\ast}(t) = f_{2}(t)$ for some $f_{2} \in S$ such that $t \in dom(f_{2})$. Either $f_{1} \subset f_{2}$ or $f_{2} \subset f_{1}$, it is clear that $s = t$; $f^{\ast}$ is indeed injection.
   
   It is clear that $f^{\ast}$ is an upper bound of $S$. By Zorn's Lemma, there exist a maximal element of $\mathcal{J}$; namely $\bar{f}$ with domain $A$ and range $B$. If $x_{0} \in X \setminus A$ and $y_{0} \in Y \setminus B$, we can extend $\bar{f}$ by setting $\bar{f}(x_{0}) = y_{0}$, contradicting maximality. Hence either $A = X$, in which case $|X| \leq |Y|$, or $B = Y$, in which case $|Y| \leq |X|$.

Now comes the most important theorem.

(Schröder-Bernstein's Theorem). If $|X| \leq |Y|$ and $|Y| \leq |X|$, then $|X| = |Y|$.

Let $f: X \rightarrow Y$ and $g:Y \rightarrow X$ be injections. Given $x \in X$, we construct a sequence $$ x \rightarrow g^{-1}(x) \rightarrow (f^{-1} \circ g^{-1})(x) \rightarrow (g^{-1} \circ f^{-1} \circ g^{-1})(x) \rightarrow ... $$ until each terms exist. Then we can distinguish such $x$, by four types.

1. The sequence repeats (or has a loop).
2. The sequence goes indefinitely without repeating.
3. The sequence stops in finite number of steps, in set $X$.
4. The sequence stops in finite number of steps, in set $Y$.

We define a new function $h: X \rightarrow Y$ as follows. $$ h(x) = \begin{cases} f(x) & (\text{if }x\text{ is type 1, 2, and 3}) \\ g^{-1}(x) & (\text{if }x\text{ is type 4}) \end{cases}$$ For all $x \in X$, $x$ and $h(x)$ are always in same sequence regardless of the type of $x$. For if $h(a) = h(b)$ and $a$ is in type 1, 2, or 3, then $h(a) = f(a) = h(b) = f(b)$, so that $a = b$ because $f$ is injection. For if $h(a) = h(b)$ and $a$ is in type 4, then $h(a) = g^{-1}(a) = h(b) = g^{-1}(b)$, which implies $a = b$. So $h$ is injective.

Now pick $y \in Y$. Every $y$ is in some sequence of $x$, because there should exist $x \in X$ such that $g(y) = x$. If $y$ is in type 1, 2, or 3, then there exist some $x \in X$ such that $h(x) = f(x) = y$. If $y$ is in type 4, there exist $x \in X$ such that $x = g(y)$. Now $x$ and $y$ are in same sequence, so $h(x) = g^{-1}(x) = y$. This means $h$ is surjective. Combining the facts, $h$ is bijection; $|X| = |Y|$.

Together with Proposition 1, Schröder-Bernsten's Theorem makes $\leq$ on cardinality of sets to behave like a linear ordering. (Transitivity is almost trivial, since composition of two injections are still injection)

Lastly we introduce famous theorem, which states that every set has strictly smaller cardinality than its power set. This arise concept of countability (which we will discuss next).

For any set $X$, $|X| < |\mathcal{P}(X)|$.

It is clear that $|X| \leq |\mathcal{P}(X)|$, since $x \longmapsto \left\{ x \right\}$ is injection. Define $$ A = \left\{ x \in X: x \not\in g(x) \right\}$$ If $g: X \rightarrow \mathcal{P}(X)$ is surjection, then there exist $x_{0} \in X$ such that $g(x_{0}) = A$. But \begin{align} x_{0} \in A &\iff x_{0} \not\in g(x_{0}) \\ &\iff x_{0} \not\in A \end{align} which is contradiction. So there is no surjection from a set to its power set. This gives $|X| < |\mathcal{P}(X)|$.