Schröder–Bernstein theorem

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.

The theorem is named after Felix Bernstein and Ernst Schröder.

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

Otherwise, call it doubly infinite if all the elements are distinct or cyclic if it repeats.

If we assume the axiom of choice, then a pair of surjective functions

by picking a single element from the inverse image of each point in

guarantees the existence of at least one element in each such inverse image.

The Schröder-Bernstein theorem then can be applied to the injections h and k. 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.

, 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.

König's definition of a bijection h : A → B from given example injections f : A → B and g : B → A . An element in A and B is denoted by a number and a letter, respectively. The sequence 3 → e → 6 → ... is an A -stopper, leading to the definitions h (3) = f (3) = e , h (6) = f (6), .... The sequence d → 5 → f → ... is a B -stopper, leading to h (5) = g −1 (5) = d , .... The sequence ... → a → 1 → c → 4 → ... is doubly infinite, leading to h (1) = g −1 (1) = a , h (4) = g −1 (4) = c , .... The sequence b → 2 → b is cyclic, leading to h (2) = g −1 (2) = b .
Cantor's first statement of the theorem (1887) [ 3 ]