Article Index

Schröder Bernstein Theorem

Published on

Statement

If there exists an injective function $f: \mathcal S \to \mathcal T$ and an injective function $g: \mathcal T \to \mathcal S$, then there exists a bijective function $h: \mathcal S \to \mathcal T$. In other words, $\mathcal S$ and $\mathcal T$ have the same cardinality.

Gyula Kőnig's Proof

We may assume without loss of generality that $\mathcal S \cap \mathcal T = \varnothing$.

We represent the mappings as a bipartite graph as follows:

Elements of $\mathcal S$ are taken as left vertices, and elements of $\mathcal T$ are taken as right vertices. Hence, each left vertex $x$ has an outgoing edge $x \to f\left(x\right)$. Similarly, each right vertex $y$ has an outgoing edge $y \to g\left(y\right)$.

A chain containing a left vertex $x$ is defined as follows:

  • Let $a_0 = x$;
  • if $a_i$ is defined, then $b_i = f\left(a_i\right)$;
  • if $b_i$ is defined, then $a_{i + 1} = g\left(b_i\right)$;
  • if $a_i$ is defined and $g^{-1}\left(a_i\right)$ is defined (note that $g$ is injective, so $a_i$ might not be in the image of $g$), then $b_{i - 1} = g^{-1}\left(a_i\right)$; otherwise, $b_{i - 1}$ is undefined;
  • if $b_i$ is defined and $f^{-1}\left(b_i\right)$ is defined, then $a_i = f^{-1}\left(b_i\right)$; otherwise, $a_i$ is undefined.

Explicitly, the chain looks like

$$\cdots \to a_i \to b_i \to a_{i + 1} \to \cdots.$$

In other words,

$$\cdots \to f^{-1}\left(g^{-1}\left(x\right)\right) \to g^{-1}\left(x\right) \to x \to f\left(x\right) \to g\left(f\left(x\right)\right) \to \cdots$$

Recall that our goal is to construct a bijective function $h : \mathcal S \to \mathcal T$. We will discuss three scenarios.

  • The chain is an A-stopper.
    This means there exists an $a_i$, such that $b_{i - 1}$ is undefined.
    In this case, the function $f$ is a bijection between the corresponding elements of $\mathcal S$ and $\mathcal T$.
  • The chain is a B-stopper.
    This means there exists a $b_i$, such that $a_i$ is undefined.
    In this case, the function $g$ is a bijection between the corresponding elements of $\mathcal S$ and $\mathcal T$.
  • The chain is double-infinite.
    This means there does not exist a $a_i$ such that $b_{i - 1}$ is undefined and there does not exist a $b_i$ such that $a_i$ is undefined.
    In this case, $f$ and $g$ are both satisfied.

Corollary

Given surjective functions $f: \mathcal S \to \mathcal T$ and $g: \mathcal T \to \mathcal S$, we can define injective functions $f' : \mathcal T \to \mathcal S$ and $g' : \mathcal S \to \mathcal T$ by choosing suitable preimages, and then apply the previous proof to obtain a bijection. Note that suitable choices of preimages make $f^{-1}$ and $g^{-1}$ well-defined as injective functions, since $f$ and $g$ are surjective.

Examples

$\left[0, 1\right]$ and $\left[0, 1\right)$ have the same cardinality

Let $f: \left[0, 1\right] \to \left[0, 1\right)$ with $f\left(x\right) = x / 2$; and $g: \left[0, 1\right) \to \left[0, 1\right]$ with $g\left(x\right) = x$.

Applying Gyula Kőnig's proof, we will directly get a bijective function $h$ as follows:

Let $C_n = 2^{-n}$, and $C = \displaystyle\bigcup\limits_{n = 0}^{\infty}C_n$ denotes all the elements need to be moved.

$$ h\left(x\right) = \begin{cases} \frac x2 &\text{if } x \in C \\ x &\text{if }x \in \left[0, 1\right] \setminus C \end{cases} $$

$\mathbb Q$ and $\mathbb N$ have the same cardinality

It is sufficient to find an injective function $f: \mathbb Q \to \mathbb N$, since we already have an injective function $g: \mathbb N \to \mathbb Q$ defined by $g\left(x\right) = x$.

Recall that each element in $\mathbb Q$ can be represented by the form $a / b$, where $a \in \mathbb Z$, $b \in \mathbb N$, and $\gcd\left(a, b\right) = 1$.

Let us first construct an injective function $h: \mathbb Z \to \mathbb N$:

$$ h\left(x\right) = \begin{cases} 2x &\text{if } x \geq 0 \\ -2x - 1 &\text{if } x < 0 \end{cases} $$

For $q = a / b$ with $\gcd\left(a, b\right) = 1$, define

$$f\left(q\right) = \frac{\left(h\left(a\right) + b - 1\right)\left(h\left(a\right) + b\right)}2 + b$$

this is the Cantor pairing function.

No comments

Post a comment