The nonnegative integers are countable, as shown by the bijection f(n) = n+1. Some people prefer this definition. It is sometimes more natural to begin counting at 0, rather than 1. I guess it depends on whether you program in C or fortran.

The even numbers are countable; map n to n/2. Thus an infinite set can be just as large as a proper subset of itself.

The integers are countable. Map n to 2n for n ≥ 0, and map n to 1-2n for n < 0.

Any set that can be listed in order, or enumerated, is countable. For instance, any subset of the positive integers is countable. Take the smallest number in the set and place it first on the list. Take the next smallest and place it second on the list. Continue this process until the entire set has been "counted", i.e. mapped onto the positive integers. Thus the prime numbers are countable, and so on.

Ordered pairs of positive integers are countable. List them this way:

1/1 2/1 1/2 3/1 2/2 1/3 4/1 3/2 2/3 1/4 5/1 4/2 3/3 2/4 1/5 …

Since fractions are ordered pairs of integers, the rational numbers are countable. This is counterintuitive, since they are densely packed in the number line. There are infinitely many rationals packed into the tiniest of intervals, yet there are just as many rationals as integers.

We showed that the cross product (i.e. ordered pairs) of countable sets is countable. Use this fact again and again to show that the n-tuples of integers are countable. The integer points, or even the rational points in n space are countable.

In fact all finite ordered tuples of the integers, or any other countable set for that matter, are countable. Here is a recipe for listing all possible tuples in order. We know that the tuples of size n can be listed in order; this was described above. So start with the first tuple of size 1, then the first tuple of size 2 followed by the second tuple of size 1, then the first tuple of size 3 and the second tuple of size 2 and the third tuple of size 1, then the first tuple of size 4 and the second tuple of size 3 and the third tuple of size 2 and the fourth tuple of size 1, and so on.

As a corollary, the finite sets of integers are countable, as these are all represented, perhaps many times, by various ordered tuples. The set (1,2,3) appears six times when order is significant. Since the ordered tuples over count the unordered subsets, and the tuples are countable, the finite subsets are also countable.

Note that the integer polynomials are precisely the finite ordered tuples of integers. Wel almost; the tuples that have leading zeros can be thrown away. Anyways, since the tuples are countable, the polynomials are countable. Of course the coefficients can be drawn from any countable set, so the polynomials over the rationals are countable.

The polynomials over x and y are the polynomials in y, whose coefficients are polynomials in x. We just showed the polynomials in x are countable, and since these act as coefficients, the polynomials in x and y are countable. This extends to polynomials in x y z, and so on.

Yes I know, all ordinals are sets, and there are uncountably many ordinals. This is a contradiction that I don't understand. If you can explain it to me, please drop me a line.