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
Canonical name	ProofOfSchroederBernsteinTheoremUsingTarskiKnasterTheorem
Date of creation	2013-03-22 15:30:24
Last modified on	2013-03-22 15:30:24
Owner	kompik (10588)
Last modified by	kompik (10588)
Numerical id	7
Author	kompik (10588)
Entry type	Proof
Classification	msc 06B99
Related topic	SchroederBernsteintheorem
Related topic	TarskiKnastertheorem
Related topic	TarskiKnasterTheorem
Related topic	SchroederBernsteinTheorem