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 b1 in B with g(b1) = a. Similarly if b1 is in f(A) then there exists a unique a1 in A with f(a1) = b. This can be continued to produce a set S(a) = {b1, a1, b2, a2, . . . }. 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 Ainf = {a in A: |S(a)| is infinite}. Let A0 = {a in A: |S(a)| is even} and A1 = {a in A: |S(a)| is odd}. Similarly define Binf, B0, B1.

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