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 
Archimedian 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 aleph0 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)/sqrt(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.

      1    2    3    4    5    6    7    8    9    10   11
     1/1  1/2  2/1  1/3  3/1  1/4  2/3  3/2  4/1  1/5  5/1

Placing these rational in order of magnitude gives the sequence

   10    6     4     2     7     1     8     3     5     9    11
  1/5  1/4   1/3   1/2   2/3   1/1   3/2   2/1   3/1   4/1   5/1

The rational pairs to be interpolated at each stage

                  2  1             0.853553391...
               1  3                1.707106781...
                  4  2             0.451184464...
               3  5                2.707106769...
                  6  4             0.308925571...
               2  7                0.617851142...
               1  8                1.353553384...
               5  9                3.707106769...
                 10  6             0.235355339...
               9 11                4.707106769...

The choices on the 7th and 8th steps depend on where the earlier
interpolated values have fallen in their respective intervals.  Using
our "1/sqrt(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

         p + (q-p)/sqrt(2)  =  P + (Q-P)/sqrt(2)

Solving for sqrt(2) gives

               sqrt(2) = (Q-P-q+p)/(p-P)

which is impossible.

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.  So what gives?!

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., aleph0 segments,
each of which contains aleph0 rationals and aleph1 irrationals (taking
the continuum C equal to aleph1).  But since

  aleph0*aleph0 = aleph0            aleph0*aleph1 = aleph1

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 sqrt(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 aleph0 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.