Cantor-Schröder-Bernstein Theorem

The cardinality of a set is first defined by the equivalence class of which other sets it is equipollent to, that is where there exists a bijective function between the sets. The notion of cardinality at this stage is not further defined, but it is in some sense a measure of size.

A partial order is defined on cardinalities by saying that |A| <= |B| iff there is an injection from A into B. This is then equivalent to there being a bijection from A onto a subset of B.

The hard part is to show that if |A| <= |B| and |B| <= |A| then |A| = |B|. This is actually harder than I'm prepared to try to detail here, since I'd have to re-read my book a few more times to get it right. Informally, if A is the same size as part of B, and B is the same size as part of A, then A and B are the same size.

This only defines a partial order. There may be sets that are incommensurable with other sets in this order. The steps after this are to construct a hierarchy of ordinals, which are well-ordered sets, so we can take a least ordinal of any given cardinality, and call that ordinal a cardinal.

By the Well-Ordering Principle any set can be well-ordered, so every set has a cardinality of some cardinal. Unfortunately this principle is equivalent to the Axiom of Choice. There is no intuitive consensus on whether to accept it, though it does make things a sight easier if you do.

Theorem (Cantor-Schröder-Bernstein): If f: A -> B is an injection and g: B -> A is an injection, then there exists a bijection between A and B.

Proof: For any a in A, we construct the 'ancestors' of a as follows. If a is in g(B), then there exists a unique b₁ in B with g(b₁) = a. Similarly if b₁ is in f(A) then there exists a unique a₁ in A with f(a₁) = b. This can be continued to produce a set S(a) = {b₁, a₁, b₂, a₂, . . . }. We can produce a similar set S(b) for any b in B.

Now we partition A and B based on the cardinalities of S(a) and S(b). Let A_inf = {a in A: |S(a)| is infinite}. Let A₀ = {a in A: |S(a)| is even} and A₁ = {a in A: |S(a)| is odd}. Similarly define B_inf, B₀, B₁.

Consider the sets A_inf and B_inf. Every b in B_inf obviously has an inverse under f in A_inf. Therefore f is a bijection from A_inf to B_inf. Now consider A₀ and B₁. By a parity argument, f maps A₀ into B₁ injectively. Also, as |S(b)| is odd, it must be at least 1, implying that any b in B₁ has an inverse in A₀. Therefore f is a bijection from A₀ to B₁ and, by symmetry, g is a bijection from B₀ to A₁. By combining the three bijections, we can then construct a bijection between A and B.

Here's another proof, that's different enough (at least on the surface) from The Numbered One's above to seem worth noding. Hence showing the splendiferous multifacetedness of mathematics, or something similar.

We have f:A->B, g:B->A, both injective (aka 1-1). Let C₀ := A \ ran(g), this being the bit of A which g doesn't map onto - the bit which stops g being the desired bijection. The idea is to reflect C₀ between A and B via f and g. So define by recursion

C_n+1 := g[f[C_n]]

Now we define our bijection, h, by

h(x) := f(x) if x \in C_n for some n,
h(x) := g^-1(x) else

(g is injective, so g^-1 is defined on ran(g) - i.e. on all but C₀ which is excluded by the first line)

We need to show h is bijective. First, we show it's injective. So suppose x, x' are distinct elements of A. If h is defined in the same way for both, either by f or by g^-1, then we have no problem since these functions are injective. The remaining case is when one has h defined by f, the other by g^-1. WLOG, suppose x \in C_m, and x' is not in UC_n. Then

h(x) = h(x')=> f(x) = g^-1(x') => g(f(x)) = g(g^-1(x') = x' => x' \in g[f[C_m]] = C_m+1,

contradicting our choice of x'.

So h is injective.

It remains to show that h is surjective (onto). So let b \in B.
First supppose g(b) is not in any of the C_n's. Then h(g(b)) = g^-1(g(b)) = b, so b \in ran(h).
Else, say g(b) \in C_m. m can't be 0, since C₀ = A \ ran(g). So m-1 >= 0. So g(b) \in C_m = g[f[C_m-1]], so, since g is injective, we have b \in f[C_m] = h[C_m]. So again, b \in ran(h).

So h is surjective, so h is bijective, so A is equinumerous to B.

QED.

Source: Elements of Set Theory - Enderton