In my class, we have this definition of countable: The statement that the set A is countable means that A is finite or else there is a one-to-one correspondence between C and A.

Using this definition, prove that every subset of C is countable.

To start, I've taken C to be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,...} and a subset, S, of C to be {2, 3, 5, 7, 9, 10,...} and I'm trying to show S is countable by making a one-to-one correspondence (map 1 to 2, 2 to 3, 3 to 5, 4 to 7, 5 to 9, 6 to 10, etc...). How do I show that this correspondence continues? I was thinking by induction, starting by letting x(sub 1) be the element of S that no other element of S precedes.

Any more help proving this by induction, or any other method, would be helpful. Thanks.