|This article/section deals with mathematical concepts appropriate for a student in mid to late high school.|
Note: This article has wikilinks into my sandbox. These need to be changed if it is moved to the main article space.
A set X is countable if and only if there is a bijection or "one-to-one correspondence" from X to the natural numbers or a subset of the natural numbers. Countable sets include all finite sets, and many infinite ones, such as the integers and, surprisingly, the rational numbers, but not the real numbers.
The question of whether a set is countable relates to the more general topic of cardinality, which is the description of the "size" of a set. For finite sets, the cardinality is straightforward—the cardinality of the days of the week is 7. But for infinite sets there are some surprises:
- Sets that are "obviously bigger" than others may in fact have the same cardinality in the strict mathematical sense. The famous case of this is the one-to-one correspondence between the integers and the even integers, given by mapping every integer x to the even integer 2x. This is a one-to-one correspondence, so the two sets have the same cardinality, and are therefore the "same size".
- Sets that seem radically different can have the same cardinality. The famous case of this is the rational numbers. They are countable, that is, they have the same cardinality as the integers, even though the integers seem the be "sparse" and the rationals are "dense". (In fact, there is a strict mathematical definition of what it means to be "dense", and it means precisely this.) The one-to-one correspondence between the natural numbers and the rationals is a little hard to visualize, but many things in mathematics are that way. The correspondence will be given below.
- Sets that might seem to be the same size can have different cardinality. The famous case of this is the real numbers. It may seem counterintuitive that the reals are such an enormously bigger kind of infinity than the integers and the rationals, but it's true. The proof that the real numbers are not countable is the celebrated "Cantor diagonalization theorem".
Making a list
Countable sets are extremely important and "well behaved" in advanced mathematics, so that proving something is countable is a very useful thing. The usual way of doing this is to find a way to "enumerate" them. That is, show that the set has a "first" element according to some ordering, and then a "second" element, and so on. This is the way one shows, for example, that the set of rational numbers is countable.
- First, all the rational numbers (that is, fractions of integers) are reduced to lowest terms in the usual way, so that there are no common divisors in the numerator and denominator.
- Next, all fractions for which the sum of the numerator and denominator is 1 are listed. 0/1, that is, the rational number zero, is the only such number.
- Next, all fractions for which the sum of the numerator and denominator is 2 are listed. 1/1, that is, the rational number one, is the only such number.
- Continue in this way, with the fractions 1/2 and 2/1, then 1/3, and 3/1 (2/2 isn't reduced), then 1/4, 2/3, 3/2, and 4/1, and so on.
By doing this, one has created a one-to-one correspondence between the integers and the rationals, and has also created a "natural order" for the rationals. This ordering has nothing to do with the usual order—the one that tells us the 3.7 is less than 3.8.
When the elements of a countable set have been put into a list like this, the set is said to be "well-ordered". This means that any subset (even infinite subsets) has a first item in the ordering. The "well-order" on the rationals is completely counterintuitive—it has nothing to do with the usual ordering. There is no least element of the open interval (0, 1) in the usual sense, but there is in the well-order.
Sets that aren't countable
One might think that the construction given above could be applied, one way or another, to just about any set. But in fact the real numbers are uncountable. It is proved, in Cantor's diagonalization theorem, that no such countable list can be made. The proof works like this:
- Suppose that the real numbers between zero and one have been listed, with a first one, a second one, and so on. Write out the (infinite) decimal expansion of the numbers in the list.
- Now make a new number by giving a decimal expansion for it: Set its first digit to some digit other than the first digit of the first number on the list. Set its second digit to some digit other than the second digit of the second number on the list. Continue this way through the entire (countably infinite) list.
- The number so constructed can't be on the original list, because it differs from every number on the list. It differs from the 574th number in its 574th digit, for example.
- Therefore, there was a real number not in the original enumeration, so the original enumeration did not encompass all the real numbers.
This proof gets its name from the fact that the digits were concocted along the "diagonal" of the (infinitely long and infinitely wide) list.
The hierarchy of cardinalities
The diagonalization proof shows that some infinities are "bigger" than others. The cardinality of countable sets is the smallest infinite cardinality. The diagonalization proof can be used to show that, for any set of any cardinality, the set of all subsets of the given set has a higher cardinality.
These cardinalities are usually denoted by the Hebrew letter aleph, , with a subscript. The cardinality of countable sets is denoted , usually pronounced "aleph-naught" or "aleph-null". Each cardinality distinctly bigger than the preceding one (Cantor's proof shows that these always exist) is given the next higher number.
Is the cardinality of the real numbers the smallest cardinality strictly bigger than ? The "continuum hypothesis" asserts that this is so. The continuum hypothesis can't be proved or disproved by the simple axioms of set theory. Like the axiom of choice, the continuum hypothesis is on the frontiers of mathematical logic.
The axiom of choice is equivalent to the "well-ordering axiom", which asserts that any set has a well-order. This is an extremely advanced topic.