Prove that the set n mod 3 = 1 is countably infinite if n belongs to all non-negative integers I understand for the set to be countably infinite that it has to have the same cardinality as the set of positive integers. I am mostly confused on how to prove this. I understand surjective and injective but I am not understanding this step.
 A: You can proceed by showing that the function $f(n) = \frac{n-1}{3}$ is a bijection (both injection and surjection) between the given set and the set of all non-negative integers.  Basically this means showing that it is well-defined on the domain and has an inverse which is well-defined on the range.
A: Here's one way you could go about it: First show that the set is at most countably infinite, meaning that the largest it could possibly be is countably infinite. To do this, note that the set you described above is a subset of the positive integers. This allows us to conclude that the set cannot be larger than the positive integers, so we can say that it is at most countable. To see that it is actually infinite, note that it contains the sequence $1,4,7,...,1+3n,...$ is contained in it. (Actually a direct way to show that it is countably infinite is to show that the above sequence is the entire set itself. Since we have ''listed'' out the elements of the set, the set must be countably infinite.)
