Cardinality, Countable and Uncountable Sets

Countable and Uncountable Sets

A set is countable if it is finite, or it can be placed in 1-1 correspondence with the positive integers. A set is countably infinite if it is countable and infinite, just like the positive integers.

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.

Diagonalization

all the finite sets of integers are countable, but not so for the infinite subsets. Here is a simple diagonalization argument. If the infinite sets are countable then the correspondence builds a list of all possible subsets. Build a new subset S as follows. Let n be in S iff n is not in the nth subset on the list. Therefore S cannot appear anywhere on the list. If S is in position n, then S contains n iff it doesn't. Every possible correspondence fails, because it misses some set S. A generalization of this important theorem will be given later on.

The Reals are Uncountable

Consider the reals between 0 and 1, represented as decimal numbers. Suppose they can be arranged in a list. Build a new decimal as follows. Make the nth digit anything other than the nth digit of the nth number on the list. Also avoid the digits 0 and 9. The constructed real number cannot appear on the list. Since we're avoiding 0 and 9, an equivalent form of the same number cannot appear on the list either, e.g. 0.720000… = 0.719999…

Combinations that are not Sets

A counting argument shows there are collections of integers that are not guaranteed to be sets. If a set is implied by the ZFC axioms, a finite chaine of inference forces that set to exist. Such a chain can be encoded as a finite sequence of numbers, and there are countably many such sequences. Therefore the number of sets implied by our axioms is countable. However, there are uncountably many collections of integers. Most of these are never described mathematically, i.e. never gathered together into sets. Some of them may become sets, if you bring in more axioms, but they are not sets by ZFC construction.

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.