(Cantor-Schroeder-Bernstein Theorem)

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 C0 := 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 C0 between A and B via f and g. So define by recursion

:= g[f[Cn]]

Now we define our bijection, h, by

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

(g is injective, so g-1 is defined on ran(g) - i.e. on all but C0 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 Cm, and x' is not in UCn. Then

h(x) = h(x')=> f(x) = g-1(x') => g(f(x)) = g(g-1(x') = x' => x' \in g[f[Cm]] = Cm+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 Cn's. Then h(g(b)) = g-1(g(b)) = b, so b \in ran(h).
Else, say g(b) \in Cm. m can't be 0, since C0 = A \ ran(g). So m-1 >= 0. So g(b) \in Cm = g[f[Cm-1]], so, since g is injective, we have b \in f[Cm] = h[Cm]. So again, b \in ran(h).

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


Source: Elements of Set Theory - Enderton