# proof of Schroeder-Bernstein theorem using Tarski-Knaster theorem

The Tarski-Knaster theorem can be used to give a short, elegant proof of the Schroeder-Bernstein theorem.

###### Proof.

Suppose $f:S\to T$ and $g:T\to S$ are injective. Define a function $\varphi\colon P(S)\to P(S)$ by $\varphi(X)=S\setminus g(T\setminus f(X))$.

If $X\subseteq Y\subseteq S$, then $S\setminus g(T\setminus f(X))\subseteq S\setminus g(T\setminus f(Y))$, and so $\varphi$ is monotone. Since $P(S)$ is a complete lattice, we may apply the Tarski-Knaster theorem to conclude that the set of fixed points of $\varphi$ is a complete lattice and thus nonempty.

Let $C$ be a fixed point of $\varphi$. We have

 $S\setminus C=g(T\setminus f(C)).$

Hence $g|_{T\setminus f(C)}\colon T\setminus f(C)\to S\setminus C$ and $f|_{C}:C\to f(C)$ are bijections. We can therefore construct the desired bijection $h\colon S\to T$ by defining

 $h(x)=\begin{cases}f(x)&\text{if\ }x\in C\\ (g|_{T\setminus f(C)})^{-1}(x)&\text{if\ }x\notin C.\qed\end{cases}$

The usual proof of Schroeder-Bernstein theorem explicitly constructs a fixed point of $\varphi$.

## References

• 1 Thomas Forster, Logic, induction and sets, Cambridge University Press, Cambridge, 2003.
• 2 M. Kolibiar, A. Legéň, T. Šalát, and Š. Znám, Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992 (Slovak).
Title proof of Schroeder-Bernstein theorem using Tarski-Knaster theorem ProofOfSchroederBernsteinTheoremUsingTarskiKnasterTheorem 2013-03-22 15:30:24 2013-03-22 15:30:24 kompik (10588) kompik (10588) 7 kompik (10588) Proof msc 06B99 SchroederBernsteintheorem TarskiKnastertheorem TarskiKnasterTheorem SchroederBernsteinTheorem