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.


Suppose f:ST and g:TS are injectivePlanetmathPlanetmath. Define a function φ:P(S)P(S) by φ(X)=Sg(Tf(X)).

If XYS, then Sg(Tf(X))Sg(Tf(Y)), and so φ is monotone. Since P(S) is a complete latticeMathworldPlanetmath, we may apply the Tarski-Knaster theorem to conclude that the set of fixed pointsPlanetmathPlanetmath of φ is a complete lattice and thus nonempty.

Let C be a fixed point of φ. We have


Hence g|Tf(C):Tf(C)SC and f|C:Cf(C) are bijections. We can therefore construct the desired bijection h:ST by defining

h(x)={f(x)if xC(g|Tf(C))-1(x)if xC.

The usual proof of Schroeder-Bernstein theorem explicitly constructs a fixed point of φ.


  • 1 Thomas Forster, Logic, inductionMathworldPlanetmath 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