The Schroeder-Bernstein Theorem

 The Schroeder-Bernstein Theorem is a fundamental result in set theory that states that if there exist injections (one-to-one functions) f: A -> B and g: B -> A between two sets A and B, then there exists a bijection (a one-to-one and onto function) h: A -> B between the two sets.

 The Schroeder-Bernstein Theorem 

To prove the Schroeder-Bernstein Theorem, we will use a technique called the diagonalization argument. Suppose we have injections f: A -> B and g: B -> A, where A and B are sets. Our goal is to construct a bijection h: A -> B.

First, we can define two sequences of sets as follows:

A_0 = A

B_0 = B

A_{n+1} = g(B_n)

B_{n+1} = f(A_n)

Note that by definition, each set A_{n+1} is the image of B_n under g, and each set B_{n+1} is the image of A_n under f. We can visualize this process using the following diagram:

           A_0             B_0

            ↓               ↓

           g|               |f

            ↓               ↓

           A_1             B_1

            ↓               ↓

           g|               |f

            ↓               ↓

           A_2             B_2

            ↓               ↓

          ...              ...

We claim that there exists a set C such that A_n and B_n are both subsets of C for all n. To see why, note that A_0 = A is a subset of B, so A_1 = g(B_0) is also a subset of B. Then, B_1 = f(A_1) is a subset of A. Continuing in this way, we can show that each set A_n is a subset of B_{n-1}, and each set B_n is a subset of A_{n-1}. Therefore, we have A_n ⊆ B_{n-1} and B_n ⊆ A_{n-1} for all n.

Using this observation, we can define the sets C_n = A_n ∪ B_n for all n. Note that each set C_n contains both A_n and B_n as subsets. We claim that there exists a bijection h: A -> B such that h(a) = f(a) for a ∈ C and h(b) = g(b) for b ∈ C^c, where C^c denotes the complement of C.

To prove this claim, we define the set D = {x ∈ A | f(x) ∉ B} ⊆ A. Intuitively, D consists of those elements of A that are not "matched up" with any elements in B under the injection f. Note that since f is one-to-one, D and f(D) are disjoint subsets of A and B, respectively. We can then define a function h: A -> B as follows:

h(x) = {

f(x) if x ∈ D

g^{-1}(x) if x ∉ D

}

To see why h is a bijection, we need to show that it is both one-to-one and onto. Suppose h(x) = h(y) for some x, y ∈ A. If both x and y are in D, then f(x) = h(x) = h(y) = f(y), which contradicts the fact that f is one-to-one.

To see why h is a bijection, we need to show that it is both one-to-one and onto. Suppose h(x) = h(y) for some x, y ∈ A. If both x and y are in D, then f(x) = h(x) = h(y) = f(y), which contradicts the fact that f is one-to-one. Similarly, if both x and y are not in D, then g^{-1}(x) = h(x) = h(y) = g^{-1}(y), which again contradicts the fact that g is one-to-one. Therefore, we must have x ∈ D and y ∉ D (or vice versa) without loss of generality. But then h(x) = f(x) and h(y) = g^{-1}(y), so f(x) = g^{-1}(y). Since f is one-to-one and g is onto, there exists a unique element b ∈ B such that f(x) = b and g(b) = y. Therefore, we have h(x) = b = h(y), so h is one-to-one.

To show that h is onto, let b ∈ B be arbitrary. If b ∈ f(D), then there exists a unique element x ∈ D such that f(x) = b. Since h(x) = f(x) = b, we have h(A) = f(D). If b ∉ f(D), then we have g(b) ∈ A. Since h(g(b)) = g^{-1}(b) = b, we have h(B \ f(D)) = B. Therefore, h is onto.

We have shown that h is both one-to-one and onto, so it is a bijection between A and B. Hence, the Schroeder-Bernstein Theorem holds.

This completes the proof of the Schroeder-Bernstein Theorem using the diagonalization argument.

Code:  HelloGoodMorning29