CantorBernstein

Cantor–Bernstein theorem, also known as the Cantor–Bernstein–Schröder theorem, is a fundamental result in set theory concerning cardinalities. It states that if there exist injective functions f: A → B and g: B → A between sets A and B, then there is a bijection h: A → B, and hence |A| = |B|. Consequently, the two sets have the same cardinality. The theorem does not require the axiom of choice; it is provable in ZF alone.

For example, the natural numbers N and the Cartesian product N × N are equinumerous, as are any two countably infinite sets. The theorem also implies that any two infinite sets that can be injected into each other are equinumerous, which underpins many cardinal arithmetic results.

History: Georg Cantor announced the result in the 1870s; it was also proven independently by Heinrich Bernstein and by Ernst Schröder in separate works in the 1890s; the combined attribution is Cantor–Bernstein–Schröder.

Proof sketch: A standard constructive proof builds a partition of A into chains of alternating applications of f and g. On elements belonging to chains that start in A and eventually land in B, h is defined via f; on other chains, h is defined via the inverse of g. This yields a bijection A → B.