Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Donation Acolyte
    Now With Added BA
    20 Nov '02 19:55
    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.
  2. Donation bbarr
    Chief Justice
    21 Nov '02 03:27
    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 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.
  3. 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

    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)

    The Squirrel Lover
  4. Donation bbarr
    Chief Justice
    21 Nov '02 04:04
    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

  5. Donation Acolyte
    Now With Added BA
    21 Nov '02 09:40
    I found a bijection by thinking about rationals as p/q. I'll have to think about the repeating
    decimal interpretation.
  6. Donation Acolyte
    Now With Added BA
    21 Nov '02 09:32
    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.
  7. Donation Acolyte
    Now With Added BA
    30 Nov '02 13:19
    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:


    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.
  8. Standard member royalchicken
    05 Dec '02 20:12
    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
  9. Standard member royalchicken
    05 Dec '02 21:27 / 1 edit
    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).
  10. Standard member royalchicken
    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:

    / 2^y(j)

    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
  11. 05 Dec '02 21:40
    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

  12. Standard member royalchicken
    05 Dec '02 23:50
    i'd be interested to see what Acolyte thinks about that
  13. Donation Acolyte
    Now With Added BA
    07 Dec '02 09:43
    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.
  14. Standard member royalchicken
    07 Dec '02 21:58
    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.
  15. Donation Acolyte
    Now With Added BA
    08 Dec '02 21:05
    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.