Citizendium - a community developing a quality comprehensive compendium of knowledge, online and free. Click here to join and contribute—free
CZ thanks SEPTEMBER 2014 donors; special to Darren Duncan. OCTOBER 2014 donations open; need minimum total $100. Let's exceed that. Donate here. Treasurer's Financial Report -- Thanks to September content contributors. --




Schröder-Bernstein theorem/Citable Version

From Citizendium, the Citizens' Compendium

Jump to: navigation, search
This article has a Citable Version.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This version approved by an editor from the listed workgroup. The Mathematics Workgroup is responsible for this citable version. While we have done conscientious work, we cannot guarantee that this version is wholly free of mistakes. See here (not History) for authorship.
Help improve this work further on the editable Main Article!

Contents

The Schröder-Bernstein theorem (sometimes Cantor-Schröder-Bernstein 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öder-Bernstein property is used in other contexts to describe similar properties.

The Schröder-Bernstein 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öder-Bernstein" 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.

Georg Cantor (1895) states the theorem (B.)

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:


        A \subset B \subset C \quad\textrm{and}\quad |A|=|C| \qquad\Rightarrow\qquad |A|=|B|=|C|

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, A1 and A2, and B the disjoint union of two sets, B1 and B2, such that B1 is the image of A1 under f and A2 is the image of B2 under g then a bijection from A onto B is obtained by taking f on A1 and g−1 on A2.

Such a dissection is characterized by the property that the following process, if performed on A1, gives A1 as a result. (Thus A1 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

 f : A \to B \quad\text{and}\quad g : B \to A

They induce two (injective) image mappings between the power sets

 f_\ast : \mathcal P(A) \to \mathcal P(B) \quad\text{and}\quad
         g_\ast : \mathcal P(B) \to \mathcal P(A)

The mapping


  \sigma (S) := A \setminus g_\ast ( B \setminus f_\ast (S) ) \quad ( S \subset A )

on the power set of A is monotone increasing

  S_1 \subset S \subset A
          \Rightarrow \sigma (S_1) \subset \sigma (S)

and

  A_1 := \bigcap \{ \sigma(S) \mid \sigma(S) \subset S \subset A \}

is a fixed point of σ

  \sigma (A_1) = A_1

Thus the function h defined as

  h (a) := \begin{cases}      f(a)  &   a \in A_1              \\
                                 g^{-1}(a)  &   a \in A \setminus A_1  \\ \end{cases}

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

 f_\ast (S) := \{ f(s) | s \in S \} \quad ( S \subset A )
         \quad\text{and}\quad
         g_\ast (T) := \{ g(t) | t \in T \} \quad ( T \subset B )

(2) σ is a monotone increasing function on the power set of A:


  S_1 \subset S
  \Rightarrow f_\ast (S_1) \subset f_\ast (S)
  \Rightarrow B \setminus f_\ast (S_1) \supset B \setminus f_\ast (S)

  \Rightarrow g_\ast ( B \setminus f_\ast (S_1) ) \supset g_\ast ( B \setminus f_\ast (S) )

 \Rightarrow
   \sigma (S_1) := A \setminus ( g_\ast ( B \setminus f_\ast (S_1) ) )
   \subset  A \setminus ( g_\ast ( B \setminus f_\ast (S) ) ) =: \sigma (S)

(3) Any monotone increasing function on a power set has a fixed point A1:

  \sigma(A) \in \mathcal A := \{ \sigma(S) \mid \sigma(S) \subset S \subset A \}
          \Rightarrow \mathcal A \not= \emptyset
  (\forall \sigma(S) \in \mathcal A ) A_1 \subset \sigma(S) \subset S
          \Rightarrow  \sigma (A_1) \subset \sigma^2 (S) \subset \sigma(S) \in \mathcal A

          \Rightarrow  \sigma (A_1) \subset \bigcap \mathcal A = A_1
          \Rightarrow  \sigma(A_1) \in \mathcal A
          \Rightarrow  \sigma (A_1) \supset \bigcap \mathcal A = A_1

          \Rightarrow  \sigma (A_1) = A_1

(4) h is well-defined and injective because f and g are injective and g−1 is defined on the complement of A1:


  A \setminus ( g_\ast ( B \setminus f_\ast (A_1) ) ) = \sigma (A_1) = A_1 = A \setminus ( A \setminus A_1 )
   
   \Rightarrow  g_\ast ( B \setminus f_\ast (A_1) ) =  A \setminus A_1
Moreover, this also shows that h is bijective because it follows that the image of A under h is
   
    f_\ast (A_1) \cup g^{-1} ( A \setminus A_1 ) = f_\ast (A_1) \cup ( B \setminus f_\ast (A_1) ) = B
In other words, A1 induces a decomposition of A and B as described in the outline of the proof:

          A_1                    , \qquad
          A_2 := A \setminus A_1 , \qquad
          B_1 := f_\ast (A_1)    , \qquad
          B_2 := B \setminus B_1
that has the desired properties.
Views
Personal tools