In: Advanced Math
Let f be a one-to-one function from A into b with B countable. Prove that A is countable.
Section on Cardinality
Since is countable, we can enumerate its elements as . We now enumerate as follows. Let be the smallest integer such that . Then for a unique (because is one-to-one). We define .
Suppose that , and that we have defined in . Let be the smallest integer such that . Then for a unique (because is one-to-one). We define .
By induction, we have defined for all integer .
We claim that unless . Proof: Let . Then we may assume that . Then where is the smallest integer such that . Since , we know that . Thus, .
Finally, we claim that . Proof: If not, say and . Then . But this is impossible because by construction of , every element corresponds to a unique . Hence, .
This shows that is countable.