1) You need to prove it for and the rest will follow by induction. To do this note that is an injection, and since there is a natural injection the rest follows from the Schroeder-Bernstein theorem. Use this then to show that implies by creating mappings of the form .