Difference between revisions of "SchröderBernstein theorem/Citable Version"
m (Protected "SchröderBernstein theorem": Approved version [edit=sysop:move=sysop]) 
m (moved SchröderBernstein theorem to SchröderBernstein theorem/Citable Version: citable version policy) 
(No difference)

Latest revision as of 20:34, 23 September 2013
The SchröderBernstein theorem (sometimes CantorSchröderBernstein theorem) is a fundamental theorem of set theory. Essentially, it states that if two sets are such that each one has at least as many elements as the other then the two sets have equally many elements. Though this assertion may seem obvious it needs a proof, and it is crucial for the definition of cardinality to make sense.
Remark: In analogy to this theorem the term SchröderBernstein property is used in other contexts to describe similar properties.
The SchröderBernstein theorem
Theorem. If for two sets A and B there are an injective function from A into B and an injective function from B into A then there is a bijective function from A onto B.
In terms of cardinal numbers this is equivalent to:
Corollary. If A ≤ B and B ≤ A then A = B.
Here A and B denote the cardinal numbers corresponding to the sets A and B.
The corollary shows that ≤ is a partial order for cardinal numbers.
(The order is indeed a linear order, but this aspect is not touched by the theorem
since the existence of injective functions between the two sets is assumed in its statement.)
Remark. It is of theoretical interest that the proof of the theorem does not depend on the Axiom of Choice.
History
As it is often the case in mathematics, the name of this theorem does not truly reflect its history. The traditional name "SchröderBernstein" is based on two proofs published independently in 1898. Cantor is often added because he first stated the theorem in 1895, while Schröder's name is often omitted because his proof turned out to be flawed while the name of the mathematician who first proved it is not connected with the theorem.
In reality, the history was more complicated:
 1887 Richard Dedekind proves the theorem but does not publish it.
 1895 Georg Cantor states the theorem in his first paper on set theory and transfinite numbers (as an easy consequence of the linear order of cardinal numbers which he was going to prove later).
 1896 Ernst Schröder announces a proof (as a corollary of a more general statement).
 1897 Felix Bernstein, a young student in Cantor's Seminar, presents his proof.
 1897 After a visit by Bernstein, Dedekind independently proves it a second time.
 1898 Bernstein's proof is published by Émile Borel in his book on functions. (Communicated by Cantor at the 1897 congress in Zürich.)
Both proofs of Dedekind are based on his famous 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:
Cantor observed this property as early as 1882/83 during his studies in set theory and transfinite numbers and therefore (implicitly) relying on the Axiom of Choice.
Proof
The bijective function between the two sets can be explicitly constructed from the two injective functions given. Therefore the Axiom of Choice is not needed in the proof. (There are many versions of the proof.)
Outline
We denote by f the injective function from A to B, and by g the injective function from B to A.
The proof is based on a simple observation:
If A is the disjoint union of two sets, A_{1} and A_{2}, and B the disjoint union of two sets, B_{1} and B_{2},
such that B_{1} is the image of A_{1} under f and A_{2} is the image of B_{2} under g
then a bijection from A onto B is obtained by taking f on A_{1} and g^{−1} on A_{2}.
Such a dissection is characterized by the property that the following process, if performed on A_{1}, gives A_{1} as a result. (Thus A_{1} is a fixed point.)
 Take a subset of A, find its image under f in B, take the complement, find its image under g in A, and, finally, take the complement.
This defines a mapping of subsets of A to subsets of A that is increasing, and such a mapping always has a fixed point.
Proof
By assumption, there are injective functions
They induce two (injective) image mappings between the power sets
The mapping
on the power set of A is monotone increasing
and
is a fixed point of σ
Thus the function h defined as
is a bijective function between A and B.
Details
(1) Recalling the definition of the image of a set under a function, the induced image mappings are
(2) σ is a monotone increasing function on the power set of A:
(3) Any monotone increasing function on a power set has a fixed point A_{1}:
(4) h is welldefined and injective because f and g are injective and g^{−1} is defined on the complement of A_{1}:

 Moreover, this also shows that h is bijective because it follows that the image of A under h is
 In other words, A_{1} induces a decomposition of A and B as described in the outline of the proof:
 that has the desired properties.