Cantor's Bijection Theorem

Cantor's Bijection Theorem is as follows:

• Let $\mathbb{A}$ and $\mathbb{B}$ be non-empty sets.
  Let $\alpha: \mathbb{A} \rightarrow \mathbb{B}$ and $\beta: \mathbb{B}\rightarrow \mathbb{A}$ be injections.
  Then there is a bijection $\gamma: \mathbb{A} \rightarrow \mathbb{B}$.

Proof:
We begin by remarking that, without loss of generality, we may assume that $\mathbb{A}$ and $\mathbb{B}$ are disjoint sets, since, otherwise, we may replace $\mathbb{A}$ and $\mathbb{B}$ by the sets $\mathbb{A}' = \mathbb{A}\times \{1\}$ and $\mathbb{B}' = \mathbb{B}\times \{2\}$, respectively and then $\mathbb{A}'\cap\mathbb{B}' = \phi$ and there are bijections between $\mathbb{A}$ and $\mathbb{A}'$ and between $\mathbb{B}$ and $\mathbb{B}'$.

• Given $a \in \mathbb{A}$, an immediate ancestor for $a$ is an element $b$ of $\mathbb{B}$ such that $\beta(b) = a$. Then $b$ is unique if it exists since $\beta$ is injective.
• Similarly given $p \in \mathbb{B}$, an immediate ancestor for $p$ is an element $q$ of $\mathbb{A}$ such that $\alpha(q) = p$. Then $q$ is unique if it exists since $\alpha$ is injective.

So given any $x_0 \in \mathbb{A}$ we may form its chain of ancestors, $x_0, x_{-1}, x_{-2} , x_{-3}, \dots$ with $x_{-1}, x_{-3}, \dots$ in $\mathbb{B}$ and $x_0, x_{-2}, x_{-4}, \dots$ in $\mathbb{A}$, so that $\beta(x_{-(2k + 1)}) = x_{-2k}$ and $\alpha(x_{-2k}) = -x_{1 - 2k}$, in each case going on for as long as possible. Then we may augment the chain with the recursion: $x_{j+ 1} = \alpha(x_j)$ for $j$ even and $j \ge 0$, $x_{k +1} = \beta(x_k)$, for $k$ odd and $k \ge 1$.

Similarly, given any $y_0 \in \mathbb{B}$ we may form its chain of ancestors, $y_0, y_{-1}, y_{-2} , y_{-3}, \dots$ with $y_{-1}, y_{-3}, \dots$ in $\mathbb{A}$ and $y_0, y_{-2}, y_{-4}, \dots$ in $\mathbb{B}$, so that $\alpha(y_{-(2k + 1)}) = y_{-2k}$ and $\beta(y_{-2k}) = - y_{1 - 2k}$. Then we may augment the chain with the recursion: $y_{j+ 1} = \beta(y_j)$ for $j$ even and $j \ge 0$, $y_{k +1} = \alpha(y_k)$, for $k$ odd and $k \ge 1$.
In this way every element of $\mathbb{A}$ belongs to a unique chain, as does every element of $\mathbb{B}$.
Note that in such a chain, if we have a repetition, say $x_p = x_{p + q}$, for some positive integer $q\ge 2$, where $q$ is as small as possible for the given chain (using POW), then $q$ is even and the chain is just a finite cycle consisting of the elements $x_p, x_{p +1}, x_{p +2}, \dots x_{p + q - 1}$.
In this case every element of the chain has an immediate ancestor (necessarily unique, as usual).
In particular the immediate ancestor of $x_p$ is $x_{p + q - 1}$ and the immediate ancestor of $x_j$ is $x_{j - 1}$, for $p+1 \le j \le p + q - 1$. There are then four mutually exclusive possibilities for the chain that an element of $\mathbb{A}\cup \mathbb{B}$ may belong to.

• The chain may be a finite cycle, so possibly after relabeling takes the form $\{x_k; k \in \mathbb{N}_{2m}\}$, where $m \ge 1$ and such that $\alpha(x_k) = x_{k + 1}$, for $1 \le k< 2m$ odd and $\beta(x_k) = x_{k + 1}$ for $1 < k< 2m$ even and $\beta(x_{2m}) = x_1$. Here $x_{k}$ belongs to $\mathbb{A}$ for $k$ odd and $x_k$ belongs to $\mathbb{B}$ for $k$ even.
• The chain may go on forever, without repetitions, so (possibly after a relabeling), gives a doubly infinite sequence $\{x_{k}: k \in \mathbb{Z}\}$ such that $x_k \in \mathbb{A}$ for $k$ even and $x_{k}\in \mathbb{B}$ for $k$ odd, such that $\alpha(x_k) = x_{k + 1}$, for $k$ even and $\beta(x_k) = x_{k + 1}$ for $k$ odd and all the elements of the chain are distinct.
• The chain may stop at an element $a = x_{-2k}$ or $a = y_{-2k - 1}$ of $\mathbb{A}$, for some integer $k \ge 0$.
  This occurs when $a$ has no immediate ancestor.
  Then after relabeling the sequence, we have an infinite (automatically non-repetitive) sequence $x_k: k \in \mathbb{N}$, with $x_1 \in \mathbb{A}$, such that $x_1 = a$ has no immediate ancestor and such that $\alpha(x_k) = x_{k + 1}$, for $k$ odd and $\beta(x_k) = x_{k + 1}$ for $k$ even.
  In this case we say the chain is rooted in $\mathbb{A}$.
• The chain may stop at an element $b = x_{-2k-1}$ or $b = y_{-2k}$ of $\mathbb{B}$, for some integer $k \ge 0$.
  This occurs when $b$ has no immediate ancestor.
  Then after relabeling the sequence, we have an infinite (automatically non-repetitive) sequence $x_k: k \in \mathbb{N}$, with $x_1 \in \mathbb{B}$, such that $x_1 = b$ has no immediate ancestor and such that $\alpha(x_k) = x_{k + 1}$, for $k$ even and $\beta(x_k) = x_{k + 1}$ for $k$ odd.
  In this case we say the chain is rooted in $\mathbb{B}$.

Then each element $x$ of $\mathbb{A}\cup \mathbb{B}$ belongs to exactly one of these chains, called the chain of $x$. We are now in a position to define the map $\gamma: \mathbb{A} \rightarrow \mathbb{B}$, which we want to be a bijection.
We choose $\gamma$ to map each chain to itself.
So to check that $\gamma$ is a bijection, we just need to construct an inverse for $\gamma$ within each chain.
We will call the inverse map $\delta: \mathbb{B}\rightarrow \mathbb{A}$.

• If $x \in \mathbb{A}$ belongs to a chain which is a finite cycle $\{x_k: k \in \mathbb{N}_{2m}\}$, then $x = x_{2j-1}$ for some (unique) integer $j$, with $1 \le j \le m$ and we define $\gamma(x) = x_{2j} \in \mathbb{B}$.
  Then the inverse for $\gamma$ for this chain maps any element $y = x_{2p}$ of this chain to $\delta(y) = x_{2p-1} \in \mathbb{A}$ for $1\le p \le m$.
  Clearly $\gamma$ and $\delta$ are well-defined and $\delta$ is the inverse of $\gamma$ in this chain.
• If $x \in \mathbb{A}$ belongs to a doubly infinite chain $\{x_k: k \in \mathbb{Z}\}$, and $x = x_{2j}$, for some (unique) integer $j$, we define $\gamma(x) = x_{2j+1}\in \mathbb{B}$.
  The inverse $\delta$ then maps $y = x_{2p + 1}$ in this chain to $\delta(y) = x_{2p}$.
  Clearly $\gamma$ and $\delta$ are well-defined and $\delta$ is the inverse of $\gamma$ in this chain.
• If $x \in \mathbb{A}$ belongs to a chain rooted in $\mathbb{A}$, $\{x_k: k \in \mathbb{N}\}$, then $x = x_{2j-1}$ for some (unique) positive integer $j$ and we define $\gamma(x) = x_{2j} \in \mathbb{B}$.
  The inverse $\delta$ maps $y = x_{2p}$ for some positive integer $p$, to $\delta(y) = x_{2p-1} \in \mathbb{A}$.
  Clearly $\gamma$ and $\delta$ are well-defined and $\delta$ is the inverse of $\gamma$ in this chain.
• If $x \in \mathbb{A}$ belongs to a chain rooted in $\mathbb{B}$, $\{x_k: k \in \mathbb{N}\}$, then $x = x_{2j}$ for some (unique) positive integer $j$ and we define $\gamma(x) = x_{2j-1} \in \mathbb{B}$.
  The inverse $\delta$ maps $y = x_{2p-1}$ for some positive integer $p$, to $\delta(y) = x_{2p}\in \mathbb{A}$.
  Clearly $\gamma$ and $\delta$ are well-defined and $\delta$ is the inverse of $\gamma$ in this chain.

Putting the maps $\gamma$ and $\delta$ together for all the chains, we obtain the desired bijections: $\gamma: \mathbb{A} \rightarrow \mathbb{B}$ and $\delta: \mathbb{B}\rightarrow \mathbb{A}$, with $\delta$ the inverse of $\gamma$ and Cantor's Bijection Theorem is proved. Given sets $\mathbb{A}$ and $\mathbb{B}$ we say that $\vert\mathbb{A}\vert\le \vert\mathbb{B}\vert$ if and only if there is an injection $\alpha: \mathbb{A} \rightarrow \mathbb{B}$.
We say that $\vert\mathbb{A}\vert = \vert\mathbb{B}\vert$ if and only if there is a bijection $\gamma: \mathbb{A} \rightarrow \mathbb{B}$.
Then Cantor's Bijection Theorem may be rephrased as:

• If $\vert\mathbb{A}\vert\le \vert\mathbb{B}\vert$ and $\vert\mathbb{B}\vert\le \vert\mathbb{A}\vert$, then we have $\vert\mathbb{A}\vert = \vert\mathbb{B}\vert$.

Also we have the relations, valid for any sets $\mathbb{A}$, $\mathbb{B}$, $\mathbb{C}$ and $\mathbb{D}$:

• If $\vert\mathbb{A}\vert\le \vert\mathbb{B}\vert$ and $\vert\mathbb{B}\vert\le \vert\mathbb{C}\vert$, then $\vert\mathbb{A}\vert\le \vert\mathbb{C}\vert$.
• If $\vert\mathbb{A}\vert = \vert\mathbb{B}\vert$ and $\vert\mathbb{B}\vert = \vert\mathbb{C}\vert$, then $\vert\mathbb{A}\vert = \vert\mathbb{C}\vert$.
• If $\vert\mathbb{A}\vert\le \vert\mathbb{B}\vert$ and $\vert\mathbb{A}\vert = \vert\mathbb{C}\vert$ and $\vert\mathbb{B}\vert = \vert\mathbb{D}\vert$, then $\vert\mathbb{C}\vert\le \vert\mathbb{D}\vert$

Finally we say that $\vert\mathbb{A}\vert < \vert\mathbb{B}\vert$ if $\vert\mathbb{A}\vert\le \vert\mathbb{B}\vert$ but $\vert\mathbb{A}\vert = \vert\mathbb{B}\vert$ is false.
Then we have the properties, valid for any sets $\mathbb{A}$, $\mathbb{B}$, $\mathbb{C}$ and $\mathbb{D}$:

• If $\vert\mathbb{A}\vert < \vert\mathbb{B}\vert$ then $\vert\mathbb{B}\vert < \vert\mathbb{A}\vert$ is false.
• If $\vert\mathbb{A}\vert < \vert\mathbb{B}\vert$ and $\vert\mathbb{B}\vert< \vert\mathbb{C}\vert$, then $\vert\mathbb{A}\vert < \vert\mathbb{C}\vert$.
• If $\vert\mathbb{A}\vert < \vert\mathbb{B}\vert$ and $\vert\mathbb{B}\vert\le \vert\mathbb{C}\vert$, then $\vert\mathbb{A}\vert < \vert\mathbb{C}\vert$.
• If $\vert\mathbb{A}\vert\le \vert\mathbb{B}\vert$ and $\vert\mathbb{B}\vert< \vert\mathbb{C}\vert$, then $\vert\mathbb{A}\vert < \vert\mathbb{C}\vert$.
• If $\vert\mathbb{A}\vert < \vert\mathbb{B}\vert$ and $\vert\mathbb{A}\vert = \vert\mathbb{C}\vert$ and $\vert\mathbb{B}\vert = \vert\mathbb{D}\vert$, then $\vert\mathbb{C}\vert< \vert\mathbb{D}\vert$