(

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 **C**_{0} := **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_{0} 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**_{0} 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**_{0} = **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