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 $\phi :P(S)\to P(S)$by $\phi (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 $\phi$ 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 $\phi$ is a complete lattice and thus nonempty.

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

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

Hence ${g|}_{T\setminus f(C)}: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:S\to T$ by defining

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