# Proof:Cantor-Schroeder-Bernstein theorem

If and then .
Proof:
This proof is adapted from a proof given on Wikipedia.

We will do a direct proof. Assume that and . By definition, this means that there exists functions and that are both injective.

Our goal is to piece these together to form a single function which is both injective and surjective.

## Contents

### Chains

To build the function , we need to give its output on every input. To define it, we need to consider chains of elements that are formed by repeatedly applying and .

We start by defining the chain of an element: the chain of an element contains and so on. It also contains any elements that can be reached by going backwards along the chain. That is, if there happens to be some such that , then is in the chain.

There need not be such a because is not necessarily surjective. However, if there is a , it must be unique, because g is injective. If such a y exists, we will call it . This discussion shows that is a partial function.

Rephrasing the description above, the chain of will also include and so on.

We want to distinguish between various types of chains, based on what happens as you walk backwards along them (that is, if we consider as defined above). There are 4 types:

1. The chain forms a loop
2. Chains that go "backwards" forever without repeating.
3. Chains that stop in A (that is, they end on some with undefined.
4. Chains that stop in B

Note that every element of both A and B is part of exactly one chain.

### Constructing h

We define as follows. If is in a chain of type 1, 2, or 3, then we define . If is in a chain of type 4, then we define . is defined, because if it wasn't, then would be in a chain of type 3.

What's left is to show that is a bijection.

### Proof that h is injective

We must show that whenever , that . We will prove this directly: assume that . Notice that is always part of the same chain as . Therefore, and must be in the same chain.

Let's consider the possible types of chains:

• If the chain of and is of type 1, 2, or 3, then and . Therefore, . Since is injective, this implies that as required.
• If the chain is of type 4, then we have that with , and with . Since , we have , so as required.

In any case, we have shown that , so we conclude that is injective.

### Proof that h is surjective

Given an arbitrary , we must find some with . We consider the chain containing .

• If that chain is of type 1, 2, or 3, then we know there is some such that . Since and are in the same chain, we have that 's chain is of type 1, 2 or 3, so .
• If the chain is of type 4, then we know that is also in a chain of type 4. That means that . Therefore there is some (namely ) that maps to

In either case, we have found an element that maps to , so is surjective.

### Conclusion

We have defined a function and shown that it is both injective and surjective (and therefore a bijection). Therefore (by definition) .