Interleaving Ad Infinitum

A given set S with linear ordering O is said to be dense if between every two distinct members of S there is another member (where the notion of "between" is based on the ordering O). For example, the rational numbers ordered by magnitude are dense, whereas the integers ordered by magnitude are not. However, we can place the naturals in one-to-one correspondence with the rationals (as in Cantor's diagonal argument), and with this ordering the natural numbers are dense. This illustrates that the quality of "denseness" is not a property of a set by itself, but only of a set with a particular ordering.

If a set S with linear ordering O can be partitioned into two subsets A and B such that between every two distinct elements of A is an element of B, and vice versa, then the sets A and B are said to be "mutually dense". (Notice that A and B need not be individually dense in order to be mutually dense, if they are finite sets.) The most familiar example of this is the set of real numbers ordered by magnitude, which can be partitioned into the rational numbers and the non-rational numbers. It's easy to see that between any two distinct rational numbers is a non-rational number, and by the Archimedean property there also exists a rational number between any two non-rational numbers.

Can we infer anything about the cardinality of the sets A and B if we know they are mutually dense? Notice that in the case of finite sets it is possible that A and B have the same (finite) cardinalities based on an arrangement like {ABAB}, and it is also possible for their cardinalities to differ by 1 based on an arrangement like {ABABA}. Of course, their cardinalities cannot differ by more than 1.

We might be tempted to conclude that mutually dense infinite sets must have the same cardinality, based on the idea that mutual denseness implies an alternating interleaving pattern as it does in the case of finite sets, and that this pattern could be used to establish a one-to-one correspondence between the elements of the two sets. However, the rationals are countable whereas the non-rationals are not, i.e., the cardinalities of these two mutually dense sets are א₀ and C (the continuum) respectively.

Of course, we could simply define a new kind of cardinality based on the interleaving property, i.e., we could say that two sets have the same "I-cardinality" if and only if they can be ordered in such a way that they are mutually dense. The shortcoming of this definition is that, as noted above, the I-cardinality of two sets (such as the naturals and the rationals) can be the same even when their cardinality is different. In other words, the traditional concept of cardinality evidently captures a distinction between infinite sets that is lost in the definition of "I-cardinality".

This implies that the ability to place the elements of two sets in one-to-one correspondence is a stronger condition than the ability to interleave the elements of two sets. To clarify why this is so, it's worthwhile to make the constructions explicit. First, let's make a "listing" of all the natural numbers 1, 2, 3, ..., and then assign to each of these naturals a rational number in the usual way to demonstrate the countability of the rationals. The ordering of the rationals on this list is obviously not unique, but one approach is to consider each positive integer N in sequence, and form all the ratios a/b such that a + b = N. We include a ratio on the list if a,b have no common factors (to eliminate redundant appearances such as 3/2 and 6/4).

As soon as we've listed our first two irrational numbers, p and q, with p less than q, we can specify an irrational number lying strictly between them as p + (q − p)/√2. Thereafter, each time we add a new rational number Q to the list, it becomes part of a pair of rationals with no irrational between them, and it is the only such pair. Letting P,Q denote these rationals we can add a new irrational to the list to "plug the hole". The start of our list of naturals and rationals is shown below.

Placing these rational in order of magnitude gives the sequence

The rational pairs to be interpolated at each stage

The choices on the 7th and 8th steps depend on where the earlier interpolated values have fallen in their respective intervals. Using our "1/√2" interpolation rule, we find that "2 7" and "1 8" are the consecutive rationals at these stages. We are assured of never producing the same irrational twice, because if there were two pairs of rationals (p,q) and (P,Q) giving the same interpolated value, we would have

Solving for √2 gives

which is impossible because √2 is irrational.

It might seem that we're approaching a paradox here, because we know the list of naturals and rationals can be "continued to infinity", and this completed infinite list will include all the rationals. Also, it seems that we can continue to interpolate one new irrational at each step in such a way that the rationals and irrationals of the combined lists alternate by magnitude. The apparent paradox is that Cantor's diagonal argument shows that from the "completed" infinite list of irrationals we can form another, distinct, irrational number. Placing this number on the list must (it may seem) result in two "consecutive" irrational numbers, whereas we know there is a rational between every two distinct irrationals. Unfortunately we cannot just insert another rational number here, because our list has already exhausted the rationals. In other words, it seems as if Cantor's diagonal argument, combined with the mutual denseness of the rationals and irrationals, forces us to add a new rational number for each new irrational number, and this seems to imply that these two sets of numbers have the same cardinality – which, if true, would contradict the fact that they have different cardinalities.

The fallacy in this paradox is in the construction of the auxiliary list of irrational numbers. Notice that to construct each of these numbers it is necessary to explicitly arrange the rationals that have appeared so far by magnitude. In principle we can do this for any finite number of rationals, but the completed list of rationals is infinite, and it is not well-ordered by magnitude. In particular, given any rational number, there is no such thing as "the next larger" rational number. Consequently we can't rightly conceive of the completion of this infinite list of irrationals.

Likewise, any other method we choose to partition the reals into finite segments bounded by distinct irrational numbers can result in only a countably infinite number of segments, i.e., א₀ segments, each of which contains א₀ rationals and א₁ irrationals (taking the continuum C equal to א₁). But since (א₀)(א₀) = א₀ and (א₀)(א₁) = א₁, this doesn't alter our evaluation of the cardinalities.

All of this just emphasizes that the continuum is fundamentally distinct from countable infinity. The property of denseness doesn't capture the full measure of the continuum. The property that fully characterizes the continuum is "completeness", which means that the limit of every sequence of numbers is also in the set. This clearly distinguishes the irrationals from the rationals. For example, all the continued fraction convergents to √2 are rational, but the limit of this sequence is not. Hence, even though the rationals are dense, they are not complete, whereas the reals are complete. In fact, this can be taken as the definition of the reals.

It's interesting to compare this with the situation in algebra where the complex numbers are the completion of the reals, in the sense that not every root of a polynomial with real coefficients is real, whereas every root of a polynomial with complex coefficients is complex.

In transfinite set theory this raises some deep questions, such as whether the reals are the minimal completion of the rationals, or whether there might be intermediate cardinals between א₀ and C. Cantor guessed that the answer is no, but he couldn't prove it. In 1938 Goedel proved that the continuum hypothesis can't be disproved within Zermelo-Fraenkel, and in 1963 Cohen proved that it's negation also cannot be disproved. Hence it is (within ZF) an independent assumption, somewhat like Euclid's parallel postulate.

Return to MathPages Main Menu