Counting problem

Following on from the discussion about Cantor a few days ago, I have a challenge: to count
the rational numbers (both positive and negative!) Obviously you can't count all the rationals
explicitly, so I want you to generate a list of rationals so that you can give me a rule for
finding the nth number on the list, and also one for finding any particular rational. Note: 2/3,
4/6, 6/9 etc are the same number, to give an example, so take care that you haven't counted
numbers twice.

Believe it or not, this shows that there are exactly as many rational numbers as natural
numbers (though there are easier ways of showing this.)

Hint: Writing your list as 1,2,3,4,.... is probably not a good start. You might find it easier to
make a list of all integers, and go from there onto the rationals.

The rational numbers are finite strings of digits following a decimal
point. .5, for instance, is rational and can be represented by the
fraction 1/2. If you think of each rational number as being
represented by some fraction(s), then how would you show that the
rational numbers are enumerable? Note: Acolyte's original warning is
still in effect...you need to provide a procedure that allows us to (1)
determine, in principle, the ordinal position of any rational number on
your list, while (2) ensuring that every rational appears somewhere or
other on the list and (3) that each rational appears only once on the
list. If you can do this, you will have replicated the feat of Georg
Cantor, a true bad-ass.

"The rational numbers are finite strings of digits following a decimal
point. .5"

Not true. It is possible for a rational number to have an *infinite*
string of digits following a decimal point (I think you probably know
this, you just made a forgetful error/thinking about more complex
things).

The rational number 1/3 has an infinite string of digits following a
decimal point for instance.

The definition for a rational number is, to my understanding of it, any
number that can be represented as a fraction with integer numerator
and integer denominator.

I do agree that Cantor kicked some serious ass though :o)

Mark
The Squirrel Lover

You're right, of course. My example .5 should be written as
either .500...... or .4999........ In fact, any infinite string of digits that
betrays some repeating pattern will be representable as a fraction. As
far as the hint goes, it is this representability that is the key.

Thanks for keeping my honest, and for your charitable interpretation
of my mistake 😉

Bennett

I found a bijection by thinking about rationals as p/q. I'll have to think about the repeating
decimal interpretation.

I don't know if Cantor found a bijection (one-one correspondence) directly. It's easier to
show that N and Q are the same size by finding an injection (a map where there's no
'overlap'😉 from N to Q (trivial) and another from Q to N (not too hard either, drawing a
zigzag or spiral shape on a graph is usually used to illustrate this.) What got me started
looking for a bijection was seeing a poster which had double arrows connecting the first few
naturals with some rationals. I couldn't spot the pattern from the poster (perhaps there
wasn't one) but I thought that bijections must exist if the sets are the same size, so I tried to
find one.

Ok, I'll give an example as to what I mean if anyone's interested. Suppose I wanted to count
the integers (whole numbers); I could write something like this:

0,1,-1,2,-2,3,-3,.....

where the 1st number is 0
the (2n)th number is -n
and the (2n-1)th number is +n.

It's clear that if I kept going, I would list all the integers exactly once each. The challenge is
to do something similar for the rational numbers, ie numbers you can write as a fraction.

one way to look at this would be to think of the rationals (as you said) as
fractions p/q (p & q are positive integers for the moment) and then group then
together according to how their numerator and denominator associate by some
binary operation. further, ignore those not in lowest terms. so say our
operation is addition. then we find all positive rationals whose numerator and
denominator sum to one, namely 0/1. so we associate this with 1. then take all
of those (in lowest terms) that give two-1/1 (we already have 0/2). associate
this with 2. then for 3-> 1/2, 2/1. make these 3 and 4. this gives:

0/1 -> 1
1/1 -> 2
1/2 -> 3
2/1 -> 4
1/3 -> 5
3/1 -> 6
1/4 -> 7
2/3 -> 8
3/2 -> 9
4/1 -> 10
1/5 -> 11
5/1 -> 12
2/5 -> 13

...

happily i won't repeat this litany for any other operation i can think of. this
shows that there is some 1-1 correspondence between natural numbers and positive
rational numbers. if we now put the additive inverse of each of these in
correspondence with the negative integers (e.g. -2/5 -> -13), then we have a 1-1
correspondence between integers and all rationals. now if we put 0 -> 0, 1 ->
1, 2 -> -1, ..., then we find that we have a 1-1 correspondence between integers
and natural numbers (this can be proved more rigourously) and this finally
implies that a 1-1 correspondence exists between all rationals and all natural
nnumbers.

this is actually quite an interesting problem from the number-theory
perspective. if one counts the rationals (just positive for now) except using
multiplication rather than addition for an associating operation, in the exact
same manner as above, then the following circumstances arise. say m is a
natural number that will be the product of the numerator and denominator of each
rational number. by the fundamental theorem of arithmetic, there exist primes
p(1)-p(y) such that:

p(1)^c(1) p(2)^c(2)...p(y)^c(y) = m

now the rational numbers q/r associated with m are those such that qr = m.
furthermore, q/r must be in lowest terms. therefore, q/r may be equal to the
quotient of any combinations of the p(i)^c(i).

(cont'd). simple calculation shows that there are 2^y such quotients associated
with each m. by the original scheme, m will associate itself with 2^y
consecutive integers n so that the first integer associated with m is:

m-1
-----
\
/ 2^y(j)
-----
j=1

from here, it is possible to delineate the association between n and q/r.
however, the more interesting question is "how big is y(m), the number of
distinct prime factors of m?" i managed to prove that y(m) is gets infinitely
close to log(log m) (base e...). if anyone wishes to have a go, post your proof...

i am sincerely sorry for the length and lack of clarity

Originally posted by royalchicken
i am sincerely sorry for the length and lack of clarity

Noooo, apologise not. I confess to struggling (more than a little) to
keep up but any post where care and thought has gone into it is very
welcome in my opinion. Thank you 🙂

Mark

i'd be interested to see what Acolyte thinks about that

Originally posted by royalchicken
this gives:

0/1 -> 1
1/1 -> 2
1/2 -> 3
2/1 -> 4
1/3 -> 5
3/1 -> 6
1/4 -> 7
2/3 -> 8
3/2 -> 9
4/1 -> 10
1/5 -> 11
5/1 -> 12
2/5 -> 13

Fair enough, but what is the 1000th number on your list? I managed to come up with a
bijection where most of the work in finding the nth number is factorising ~n/2 (when n is
large.) Proving a bijection exists is the same as proving Q is countable; actually finding such
a bijection with 'nice' properties can be harder.

look at the next part, see what you can do. it doesn't immediately give an
explicit bijection, but it does provide somewhere to start.

OK, I must have worded the question badly. If I had said 'prove that a bijection exists
between N and Q', the mathematically preferred answer would be to show that Q is a
countable (/finite) union of countable (/finite) sets, and that Q is not finite.

So I was looking for something more explicit: basically I wanted you to give me an
algorithm, with a natural input and a rational output, that was uniquely reversible (so it
corresponds to a bijection), and sufficiently 'natural' that it could be defined directly rather
than inductively. I realise that this is completely unnecessary to show that Q is countable
(though it is sufficient!), but some people might have found it an interesting exercise.