Schroeder-Bernstein theorem

From Knowino
Jump to: navigation, search


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 Schroeder-Bernstein property is used in other contexts to describe similar properties.

[edit] 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.

[edit] 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:

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.

[edit] 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.)

[edit] 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.

[edit] 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)


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

is a fixed point of σ

σ(A1) = A1

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.

[edit] 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 )
         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) )

   \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.
Information.svg Some content on this page may previously have appeared on Citizendium.
Personal tools