The Schröder–Bernstein theorem is a fundamental result in set theory: if there is an injective function from a set into a set , and another injective function from into , then there is a bijection between and . In other words, if each set can be embedded into the other without identifying distinct elements, the two sets have the same cardinality. The theorem applies to finite and infinite sets alike and can be proved without the axiom of choice.
Statement and meaning
Let and be sets. Suppose there are injections
Then there exists a bijection
An injection assigns different outputs to different inputs but need not reach every element of its codomain. A bijection is both injective and surjective: every element of the target set is reached exactly once.
Cardinal comparison is defined through these kinds of functions:
while
The theorem therefore establishes
This is the antisymmetry property underlying the partial ordering of cardinalities. The result does not say that either of the original injections must itself be a bijection. Rather, their existence guarantees that a suitable bijection can be constructed.
Proof by separating the sets into parts
A standard proof builds the bijection by using on one part of and reversing on the rest.
For a function and a subset of its domain, write
for the image of .
Define
and recursively set
Thus, consists of the elements of that are not reached by ; each successive set is obtained by applying and then .
Let
Define
Here means the inverse function from to . It exists because is injective. The second branch is well-defined: since , every element outside belongs to .
Injectivity
On , the function is injective because it agrees with . On , it is injective because it agrees with .
The two branches cannot produce the same output. If , , and
then
But , by the definition of the sets . This would imply , a contradiction. Thus is injective on all of .
Surjectivity
Take any .
If , then for some .
If , consider . This element cannot lie in , since it lies in . It also cannot lie in any : otherwise,
and injectivity of would imply .
Consequently, , so the second branch gives
Every element of is therefore reached, completing the proof.
Interpretation through chains
The construction also has a graph-theoretic interpretation. Regard and as disjoint copies, even if the original sets overlap. Draw an arrow from each to , and from each to .
Every vertex has one outgoing arrow and at most one incoming arrow. The resulting components are alternating cycles, chains infinite in both directions, or one-sided infinite chains.
The elements of begin precisely those one-sided chains whose initial vertex lies in . The set contains all -vertices on those chains. On such chains, pairing along matches every vertex correctly. On all remaining components, pairing by reversing does the same.
This explains why simply using everywhere may leave elements of unmatched, while using everywhere may fail to assign values to some elements of . The proof identifies exactly where to switch between the two rules.
Applications
Proving equal cardinality indirectly
The principal use of the theorem is to replace the search for one bijection with the search for two injections. An injection often arises naturally from an inclusion, an encoding, or a simple formula, whereas a direct bijection may be cumbersome.
For example, let
The inclusion is injective. In the other direction,
injects into . The theorem therefore gives
Adding the two endpoints does not change the cardinality of the interval.
Cardinal sandwich arguments
Suppose
and . Inclusion gives an injection , while inclusion into , followed by a bijection , gives an injection . Hence
This is often called a cardinal sandwich argument. It allows the size of an intermediate set to be determined without explicitly matching its elements to those of either outer set.
Countably infinite products
Let . There is an injection
Conversely,
injects the Cartesian product into : each positive integer has a unique decomposition as a power of two times an odd number.
The theorem shows that is a countably infinite set. The two encodings establish this without requiring a separate explicit bijection.
Foundations and limitations
No choice principle is required
The theorem is provable in Zermelo–Fraenkel set theory without the axiom of choice. In the proof above, every value is uniquely determined; there is no need to make arbitrary selections from families of sets.
This should be distinguished from the assertion that any two sets have comparable cardinalities:
Over Zermelo–Fraenkel set theory, this general comparability assertion is equivalent to the axiom of choice. Schröder–Bernstein establishes equality when injections in both directions are already available; it does not guarantee that either direction exists for arbitrary sets.
Classical existence need not give an effective algorithm
Although the proof specifies a bijection by a formula, deciding whether a given element belongs to
may not be computationally feasible or even decidable for a particular representation of the sets and functions. A set-theoretic construction is therefore not automatically an algorithm for computing the resulting bijection.
The logical setting also matters. The unrestricted theorem is not generally available in intuitionistic logic without additional principles; in particular, the classical division into and its complement need not provide a decidable case distinction.
Additional structure need not be preserved
The theorem concerns sets and functions, not arbitrary forms of mathematical structure. Mutual embeddings of structured objects need not imply an isomorphism preserving that structure.
For example, there are continuous injections in both directions between the real line and . Inclusion provides one direction, and
provides the other. Nevertheless, they are not homeomorphic: is a compact space, whereas is not. The theorem guarantees a bijection of their underlying sets, not a homeomorphism.
Historical development
The theorem emerged from Georg Cantor’s work on comparing infinite sets. Richard Dedekind found a proof in 1887 that remained unpublished at the time. Felix Bernstein independently proved the theorem in 1897. Ernst Schröder also worked on the result, although his proposed proof contained an error.
The names Schröder–Bernstein, Cantor–Bernstein, and Cantor–Schröder–Bernstein reflect these overlapping contributions. Its lasting significance is foundational: injections in both directions suffice to establish equality of size, even for infinite sets and without assuming the axiom of choice.