- 20 Nov '02 19:55Following 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. - 21 Nov '02 03:27The 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. - 21 Nov '02 03:38"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 - 21 Nov '02 04:04You'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 - 21 Nov '02 09:32I 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. - 30 Nov '02 13:19Ok, 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. - 05 Dec '02 20:12one 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. - 05 Dec '02 21:27 / 1 editthis 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). - 05 Dec '02 21:34 / 1 edit(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 - 07 Dec '02 09:43

Fair enough, but what is the 1000th number on your list? I managed to come up with a*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

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. - 08 Dec '02 21:05OK, 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.