Cantor-Schröder-Bernstein Theorem (idea)

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