*The following assumes that you have defined the concept of the cardinality of a finite set. It's harder than it sounds. One also must have the idea of a set having infinite cardinality, even if one does not have an ordering on different kinds of infinity.*
**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_{1} in B with g(b_{1}) = a. Similarly if b_{1} is in f(A) then there exists a unique a_{1} in A with f(a_{1}) = b. This can be continued to produce a set S(a) = {b_{1}, a_{1}, b_{2}, a_{2}, . . . }. 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_{0} = {a in A: |S(a)| is even} and A_{1} = {a in A: |S(a)| is odd}. Similarly define B_{inf}, B_{0}, B_{1}.

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_{0} and B_{1}. By a parity argument, f maps A_{0} into B_{1} injectively. Also, as |S(b)| is odd, it must be at least 1, implying that any b in B_{1} has an inverse in A_{0}. Therefore f is a bijection from A_{0} to B_{1} and, by symmetry, g is a bijection from B_{0} to A_{1}. By combining the three bijections, we can then construct a bijection between A and B.