Countable

The secret in finding this pairing was to avoid a trap. Had the pairing been that which appears in Table 3, one would never reach the negative integers.

In working with infinite sets, one considers a pairing complete if there is a scheme that enables one to reach any number or element in the set after a finite number of steps. (Not everyone agrees that that is the same thing as reaching them all.) The former pairing does this.

Are the rational numbers countable? If one plots the rational numbers on a number line, they seem to fill it up. Intuitively one would guess that they form an uncountable set. But consider the pairing in Table 4, in which the rational numbers are represented in their ratio form.

The listing scheme is a two-step procedure. First, in each ratio, the denominator and numerator are added. All those ratios with the same total are put in a group, and these groups are listed in the order of increasing totals. Within each group, the ratios are listed in order of increasing size. Thus the ratio 9/2 will show up in the group whose denominators and numerators total 11, and within that group it will fall between 8/3 and 10/1. The

list will eventually include any positive rational number one can name.

Unfortunately, there are two flaws. The list leaves out the negative numbers and it pairs the same rational number with more than one natural number. Because 1/1, 2/2, and 3/3 have different numerators and denominators, they show up at different places in the list and are paired with different natural numbers. They are the same rational number, however. The first flaw can be corrected by interleaving the negative numbers with the positive numbers, as was done with the integers. The second flaw can be corrected by throwing out any ratio which is not in lowest terms since it will already have been listed.

Correcting the flaws greatly complicates any formula one might devise for pairing a particular ratio a/b with a particular natural number, but the pairing is nevertheless one-to-one. Each ratio a/b will be assigned to a group a + b, and once in the group will be assigned a specific place. It will be paired with exactly one natural number. The set of rational numbers is, again remarkably, countable.

Another countable set is the set of algebraic numbers. Algebraic numbers are numbers which satisfy polynomial equations with integral coefficients. For instance, √ 2 , I, and (-1 + √ 5 )/2 are algebraic, satisfying x² - 2 = 0, x² + 1 = 0, and x² + x - 1 = 0, respectively.