A Sequence for Counting the RationalsDavid R. Tribbledavid@tribble.com Revision 1.2, 2007-12-15 |
Cantor used a diagonal counting method for counting all of the fractions, as illustrated in the following diagram. His scheme was slighltly less than perfect, though, because while it does indeed denumerate every possible rational number, it counts many of them more than once. This does not affect his proof, of course, because it simply shows that there are more than enough counting numbers (natural numbers) to number the rationals. It would be useful to construct a counting function or sequence that counts all of the rationals exactly once.
... define the following sequence:
S(0) = 0
S(1) = 1
S(2n) = S(n) + 1 for all n > 0
S(2n+1) = 1/S(2n) for all n > 0
Function S maps all of the natural numbers to all of the positive rational numbers. So for every natural number (i.e., every counting number) n = 0, 1, 2, etc., S(n) produces a unique rational number p/q in reduced form. (Reduced form means that p and q are integers with no common divisors, such as 2/3 and 8/5, but not 4/6 or 24/15.)
The first few values of sequence S are:
| n | S(n) | Derivation |
|---|---|---|
| 0 | 0 | by the definition, S(20) |
| 1 | 1 | by the definition, S(21) |
| 2 | 2 | S(2•1) = S(1)+1, S(21) |
| 3 | 1/2 | S(2+1) = 1/S(2) |
| 4 | 3 | S(2•2) = S(2)+1, S(22) |
| 5 | 1/3 | S(4+1) = 1/S(4) |
| 6 | 3/2 | S(2•3) = S(3)+1 |
| 7 | 2/3 | S(6+1) = 1/S(6) |
| 8 | 4 | S(2•4) = S(4)+1, S(23) |
| 9 | 1/4 | S(8+1) = 1/S(8) |
| 10 | 4/3 | S(2•5) = S(5)+1 |
| 11 | 3/4 | S(10+1) = 1/S(10) |
| 12 | 5/2 | S(2•6) = S(6)+1 |
| 13 | 2/5 | S(12+1) = 1/S(12) |
| 14 | 5/3 | S(2•7) = S(7)+1 |
| 15 | 3/5 | S(14+1) = 1/S(14) |
| 16 | 5 | S(2•8) = S(8)+1, S(24) |
| etc. | ... | ... |
The first 150 values of sequence S:
Table 1 — First 150 values of S(n)
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
Deriving the rational number for large naturals can take several steps, since the sequence function is a recurrence relation:
S(1000)
= S(2•500) + 1
= (S(2•250) + 1) + 1
= ((S(2•125) + 1) + 1) + 1
= (((S(2•62+1) + 1) + 1) + 1)
+INCOMPLETE
Out next goal is to derive the inverse function of S. That is, we'd like to define inverse function S −1, so that for a given S(n) = p/q, we can plug in p/q to get the original argument, n = S −1(p/q).
We already know that S(0) = 0 andS(1) = 1, so the inverse mappings of these are simply S −1(0) = 0 and S −1(1) = 1.
Closer examination of the sequence (Table 1 above) reveals some observations about the values of the sequence and its arguments:
a. S(2k) = k + 1
b. For even n > 1, S(n) = S(n/2) + 1
c. For odd n > 1, S(n) = 1/S(n−1)
d. For all even n > 0, S(n) = p/q where p > q
e. For all odd n, S(n) = p/q where p < q
The observations shown above allow us to derive the inverse sequence S −1, i.e., the function for mapping a rational number p/q to its corresponding natural number n.
In particular, note that S(2k) = k+1, in other words, that every power of 2 maps to an integer. This makes sense, because the sequence essentially produces a branching binary tree as we proceed along increasing arguments. It maps a certain number of fractions between each pair of integers k and k+1, and then twice as many fractions between the next pair of integers k+1 and k+2. As Table 1 above shows, there are two numbers mapped between S(2) = 2 and S(4) = 3 (if we include the first integer S(2) = 2), there are four numbers mapped between S(4) = 3 and S(8) = 4, there are eight numbers mapped between S(8) = 4 and S(16) = 5, and so on, doubling the number of fractions between each successive pair of integers mapped.
Thus observation (a) provides the next step in deriving the inverse function. Since S(2k) = k+1, therefore S −1(p) = 2p−1 for all positive integers p.
INCOMPLETE
Next we note that observation (b) tells us that
the value of S(2n) where argument 2n is even
can be derived from the previous value of S(n),
effectively working our way backwards through the recurrence function.
In addition, observation (d) tells us that given an even argument 2n,
that S(2n) = p/q
with p >q.
So combining (b) and (d), we get that for fractions
p/q when p >q, that
S −1(p/q) = S(XXX)+1,
+REDO
Observation (d) tells us that S(n) where argument n
is even produces a fraction p/q
with p > q.
Putting all of this together, we get the following definition for the inverse mapping function:
S −1(0) = 0
S −1(1) = 1
S −1( p ) = 2p−1 for p > 0
S −1( p/q ) = 2 S −1( p/q − 1) for p > q
S −1( p/q ) = S −1( q/p ) + 1 for p < q
It is the fact that function S and its inverse S −1 map each natural n to exactly one rational p/q and vice versa that allows us to denumerate all of the rationals efficiently with no duplications or redundancies.
+INCOMPLETE
This document: http://david.tribble.com/text/sequence1.html.
Copyright ©2007 by David R. Tribble, all rights reserved.
Permission is granted to reference, quote, and link to this document provided
that appropriate credit is given to the orginal author.