◀ ▲ ▶Branches / Set-theory / Proof

Proof

(related to Theorem: Schröder-Bernstein Theorem)

The following proof is a special case of a more general fixpoint theorem formulated by Alfred Tarski for lattices, which we will be studying later in more detail.

• Let $A$ and $B$ be sets with the cardinalities $|A|$ and $|B|$.
• By hypothesis, $|A|\le |B|$ and $|B|\le |A|.$
• By the definition of comparing cardinal numbers this means that there are injective functions $f:A\to B$ and $g:B\to A.$
• On the power sets $\mathcal P(A)$ and $\mathcal P(B),$ we define a function $\Phi:\mathcal P(A)\to \mathcal P(B)$ such that for every subset $X\subseteq A$ $$\Phi(X):=A\setminus g[B\setminus f[X]],$$ here we use the set differences "$\setminus$" and denote by $f[X]$ and $g[B\setminus f[X]]$ the respective ranges of the functions $f$ and $g.$
• $f$ is injective by hypothesis, therefore $$(\forall X,Y\in A):X\subseteq Y\Rightarrow f(X)\subseteq f(Y).$$
• By analogy, since $g$ is injective by hypothesis, $$(\forall X,Y\in B):X\subseteq Y\Rightarrow g(X)\subseteq g(Y).$$
• Because the composition of two injective functions is again injective, by analogy: $$(\forall X,Y\in \mathcal P(A)):X\subseteq Y\Rightarrow \Phi(X)\subseteq \Phi(Y).\quad\quad( * )$$
• We will now show that $\Phi$ has a fixed point, i.e. that there exists a subset $U\in \mathcal P(A)$ with $\Phi(U)=U.$
  • We set $U:=\bigcap_{Z\in \mathcal U}$, where the set $\mathcal U$ is defined by $$\mathcal U:=\{Z\in\mathcal P(A)\mid \Phi(Z)\subseteq Z\}.$$
  • By definition of the set intersection, for every $Z\in\mathcal U$ we have $U\subseteq Z$, which leads to $\Phi(U)\subseteq\Phi(Z)\subseteq Z,$ by $( * )$ and the definition of $\mathcal U.$
  • By the behaviour of functions with set intersection we also have $\Phi(U)\subseteq \bigcap_{Z\in \mathcal U}=U.$
  • Therefore, $U$ is a fixed point of $\Phi.$
• Now, we are able to study what happens if we build the value $\Phi(U).$ By definition, $U=\Phi(U)=A\setminus g[B\setminus f[U]],$ or in other words $g[B\setminus f[U]]=A\setminus U$ and we have the situation illustrated in the below Venn-diagram:

• The diagram shows that all elements of the fixed point $U$ are mapped by the composition $g\circ f$ of the injective functions $f$ and $g$ exactly to the elements of the set complement $A\setminus U.$ By symmetry, the same can be said of mapping all elements of $f[U]$ by the composition $f\circ g$ to the set complement $B\setminus f[U].$
• Now we define a new function $h:A\to B$ as follows: $$h(a):\begin{cases} f(a)&\text{ for }a\in U\\ g^{-1}(a)&\text{ for }a\in A\setminus U \end{cases}$$
• Obviously, the function $h:A\to B$ is bijective.
• Therefore, $|A|=|B|.$
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github: