Proof:Cantor-Schroeder-Bernstein theorem

From CS2800 wiki
If [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math] and [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A5}{≥} |B| [/math] then [math]|A| \href{/cs2800/wiki/index.php?title=Equal_(cardinality)&action=edit&redlink=1}{=} |B| [/math].
Proof:
This proof is adapted from a proof given on Wikipedia.


We will do a direct proof. Assume that [math]|A|\href{/cs2800/wiki/index.php/%E2%89%A4}{≤}|B| [/math] and [math]|B|\href{/cs2800/wiki/index.php/%E2%89%A4}{≤}|A| [/math]. By definition, this means that there exists functions [math]f:A\href{/cs2800/wiki/index.php/%E2%86%92}{→}B [/math] and [math]g:B\href{/cs2800/wiki/index.php/%E2%86%92}{→}A [/math] that are both injective.


Our goal is to piece these together to form a single function [math]h:A\href{/cs2800/wiki/index.php/%E2%86%92}{→}B [/math] which is both injective and surjective.

Chains

To build the function [math]h [/math], 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 [math]f [/math] and [math]g [/math].

We start by defining the chain of an element: the chain of an element [math]x\href{/cs2800/wiki/index.php/%E2%88%88}{∈}A [/math] contains [math]x, f(x), g(f(x)), f(g(f(x))), g(f(g(f(x)))) [/math] 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 [math]y [/math] such that [math]g(y)=x [/math], then [math]y [/math] is in the chain.


There need not be such a [math]y [/math] because [math]g [/math] is not necessarily surjective. However, if there is a [math]y [/math], it must be unique, because g is injective. If such a y exists, we will call it [math]g^{-1}(y) [/math]. This discussion shows that [math]g^{-1} [/math] is a partial function.


Rephrasing the description above, the chain of [math]x [/math] will also include [math]f^{-1}(g^{-1}(x)), g^{-1}(f^{-1}(g^{-1}(x))) [/math] 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 [math]x , g^{-1}(x), f^{-1}(g^{-1}(x), \dots [/math] 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 [math]x [/math] with [math]g^{-1}(x) [/math] 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 [math]h [/math] as follows. If [math]x [/math] is in a chain of type 1, 2, or 3, then we define [math]h(x)\href{/cs2800/wiki/index.php/Definition}{:=} f(x) [/math]. If [math]x [/math] is in a chain of type 4, then we define [math]h(x):=g^{-1}(x) [/math]. [math]g^{-1}(x) [/math] is defined, because if it wasn't, then [math]x [/math] would be in a chain of type 3.

What's left is to show that [math]h [/math] is a bijection.

Proof that h is injective

We must show that whenever [math]h(x_1)=h(x_2) [/math], that [math]x_1=x_2 [/math]. We will prove this directly: assume that [math]h(x_1)=h(x_2) [/math]. Notice that [math]h(x) [/math] is always part of the same chain as [math]x [/math]. Therefore, [math]x_1 [/math] and [math]x_2 [/math] must be in the same chain.

Let's consider the possible types of chains:

  • If the chain of [math]x_1 [/math] and [math]x_2 [/math] is of type 1, 2, or 3, then [math]h(x_1)=f(x_1) [/math] and [math]h(x_2)=f(x_2) [/math]. Therefore, [math]f(x_1)=h(x_1)=h(x_2)=f(x_2) [/math]. Since [math]f [/math] is injective, this implies that [math]x_1=x_2 [/math] as required.
  • If the chain is of type 4, then we have that [math]h(x_1)=y_1 [/math] with [math]g(y_1)=x_1 [/math], and [math]h(x_2)=y_2 [/math] with [math]g(y_2)=x_2 [/math]. Since [math]h(x_1)=h(x_2) [/math], we have [math]y_1=y_2 [/math], so [math]x_1=g(y_1)=g(y_2)=x_2 [/math] as required.

In any case, we have shown that [math]x_1=x_2 [/math], so we conclude that [math]h [/math] is injective.

Proof that h is surjective

Given an arbitrary [math]y\href{/cs2800/wiki/index.php/%E2%88%88}{∈}B [/math], we must find some [math]x\href{/cs2800/wiki/index.php/%E2%88%88}{∈}A [/math] with [math]h(x)=y [/math]. We consider the chain containing [math]y [/math].

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

In either case, we have found an element that maps to [math]y [/math], so [math]h [/math] is surjective.

Conclusion

We have defined a function [math]h:A\href{/cs2800/wiki/index.php/%E2%86%92}{→}B [/math] and shown that it is both injective and surjective (and therefore a bijection). Therefore (by definition) [math]|A|\href{/cs2800/wiki/index.php/Equality_(cardinality)}{=}|B| [/math].