We say that two sets A and B have the same cardinality if there is a bijection of A with B...

We say that two sets A and B have the same cardinality if there is a bijection of A with B.

(a) Show that if B ⊂ A and if there is an injection

then A and B have the same cardinality. [Hint: Define A1 = A, B1 = B. and for n > 1, An = f(An−1) and Bn = f(Bn−1). (Recursive definition again!) Note that A1 ⊃ B1 ⊃ A2 ⊃ B2 ⊃ A3 ⊃ …. Define a bijection  by the rule

(b) Theorem (Schroeder-Bernstein theorem). If there are injections  and , then A and C have the same cardinality.