In set theory, the SchröderâBernstein theorem states that, if there exist injective functions f : A â B and g : B â A between the sets A and B, then there exists a bijective function h : A â B.
In terms of the cardinality of the two sets, this classically implies that if |A| †|B| and |B| †|A|, then |A| = |B|; that is, A and B are equipotent. This is a useful feature in the ordering of cardinal numbers.
The theorem is named after Felix Bernstein and Ernst Schröder. It is also known as the CantorâBernstein theorem or CantorâSchröderâBernstein theorem, after Georg Cantor, who first published it (albeit without proof).
The following proof is attributed to Julius König. [1]
Assume without loss of generality that A and B are disjoint. For any a in A or b in B we can form a unique two-sided sequence of elements that are alternately in A and B, by repeatedly applying and to go from A to B and and to go from B to A (where defined; the inverses and are understood as partial functions.)
For any particular a, this sequence may terminate to the left or not, at a point where or is not defined.
By the fact that and are injective functions, each a in A and b in B is in exactly one such sequence to within identity: if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by the definition of the sequences. Therefore, the sequences form a partition of the (disjoint) union of A and B. Hence it suffices to produce a bijection between the elements of A and B in each of the sequences separately, as follows:
Call a sequence an A-stopper if it stops at an element of A, or a B-stopper if it stops at an element of B. Otherwise, call it doubly infinite if all the elements are distinct or cyclic if it repeats. See the picture for examples.
The traditional name "SchröderâBernstein" is based on two proofs published independently in 1898. Cantor is often added because he first stated the theorem in 1887, while Schröder's name is often omitted because his proof turned out to be flawed while the name of Richard Dedekind, who first proved it, is not connected with the theorem. According to Bernstein, Cantor had suggested the name equivalence theorem (Ăquivalenzsatz). [2]
Both proofs of Dedekind are based on his famous 1888 memoir Was sind und was sollen die Zahlen? and derive it as a corollary of a proposition equivalent to statement C in Cantor's paper, [7] which reads A â B â C and |A| = |C| implies |A| = |B| = |C|. Cantor observed this property as early as 1882/83 during his studies in set theory and transfinite numbers and was therefore (implicitly) relying on the Axiom of Choice.
The 1895 proof by Cantor relied, in effect, on the axiom of choice by inferring the result as a corollary of the well-ordering theorem. [8] [9] However, König's proof given above shows that the result can also be proved without using the axiom of choice.
On the other hand, König's proof uses the principle of excluded middle to draw a conclusion through case analysis. As such, the above proof is not a constructive one. In fact, in a constructive set theory such as intuitionistic set theory , which adopts the full axiom of separation but dispenses with the principle of excluded middle, assuming the SchröderâBernstein theorem implies the latter. [19] In turn, there is no proof of König's conclusion in this or weaker constructive theories. Therefore, intuitionists do not accept the statement of the SchröderâBernstein theorem. [20]
There is also a proof which uses Tarski's fixed point theorem. [21]
In set theory, the SchröderâBernstein theorem states that, if there exist injective functions f : A â B and g : B â A between the sets A and B, then there exists a bijective function h : A â B.
In terms of the cardinality of the two sets, this classically implies that if |A| †|B| and |B| †|A|, then |A| = |B|; that is, A and B are equipotent. This is a useful feature in the ordering of cardinal numbers.
The theorem is named after Felix Bernstein and Ernst Schröder. It is also known as the CantorâBernstein theorem or CantorâSchröderâBernstein theorem, after Georg Cantor, who first published it (albeit without proof).
The following proof is attributed to Julius König. [1]
Assume without loss of generality that A and B are disjoint. For any a in A or b in B we can form a unique two-sided sequence of elements that are alternately in A and B, by repeatedly applying and to go from A to B and and to go from B to A (where defined; the inverses and are understood as partial functions.)
For any particular a, this sequence may terminate to the left or not, at a point where or is not defined.
By the fact that and are injective functions, each a in A and b in B is in exactly one such sequence to within identity: if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by the definition of the sequences. Therefore, the sequences form a partition of the (disjoint) union of A and B. Hence it suffices to produce a bijection between the elements of A and B in each of the sequences separately, as follows:
Call a sequence an A-stopper if it stops at an element of A, or a B-stopper if it stops at an element of B. Otherwise, call it doubly infinite if all the elements are distinct or cyclic if it repeats. See the picture for examples.
The traditional name "SchröderâBernstein" is based on two proofs published independently in 1898. Cantor is often added because he first stated the theorem in 1887, while Schröder's name is often omitted because his proof turned out to be flawed while the name of Richard Dedekind, who first proved it, is not connected with the theorem. According to Bernstein, Cantor had suggested the name equivalence theorem (Ăquivalenzsatz). [2]
Both proofs of Dedekind are based on his famous 1888 memoir Was sind und was sollen die Zahlen? and derive it as a corollary of a proposition equivalent to statement C in Cantor's paper, [7] which reads A â B â C and |A| = |C| implies |A| = |B| = |C|. Cantor observed this property as early as 1882/83 during his studies in set theory and transfinite numbers and was therefore (implicitly) relying on the Axiom of Choice.
The 1895 proof by Cantor relied, in effect, on the axiom of choice by inferring the result as a corollary of the well-ordering theorem. [8] [9] However, König's proof given above shows that the result can also be proved without using the axiom of choice.
On the other hand, König's proof uses the principle of excluded middle to draw a conclusion through case analysis. As such, the above proof is not a constructive one. In fact, in a constructive set theory such as intuitionistic set theory , which adopts the full axiom of separation but dispenses with the principle of excluded middle, assuming the SchröderâBernstein theorem implies the latter. [19] In turn, there is no proof of König's conclusion in this or weaker constructive theories. Therefore, intuitionists do not accept the statement of the SchröderâBernstein theorem. [20]
There is also a proof which uses Tarski's fixed point theorem. [21]