Posers and Puzzles
20 Nov 02
10 Jul 04
Originally posted by royalchickencantor's method of counting only establishes that the set of rational nos. is countable. it does not give a one to one mapping(bijection).
How about this:
Let x(0) = 1, and let x(2n+1) = x(n) and x(2n+2) = x(n) + x(n+1). Then the nth positive rational number is x(n-1)/x(n).
Royalchic, you are yet to prove that ur method of counting is one-to one mapping.....
10 Jul 04
Originally posted by AcolyteHave you urself found such a bijection urself? Dont reveal it right now but U can share if you have found one. That adds fun and challenge for all others....
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 ...[text shortened]... ut I thought that bijections must exist if the sets are the same size, so I tried to
find one.
18 Sep 04
2 edits
Originally posted by royalchickenThis is quite interesting. But clearly this scheme of yours is not bijection as 1/2 and 2/4 though both are the same rational number, will have different cardinality n in this representation.
How about this:
Let x(0) = 1, and let x(2n+1) = x(n) and x(2n+2) = x(n) + x(n+1). Then the nth positive rational number is x(n-1)/x(n).
The same is the case with your earlier propasal of taking the binary operation of addition and go counting over rationals with equal sum of numerator and denominator. The same discrepancy mars the representation using product as the binary operator over the numerator and denominator.
18 Sep 04
Originally posted by sarathianErm, no, 2/4 is Sir-not-appearing-in-this-sequence.
This is quite interesting. But clearly this scheme of yours is not bijection as 1/2 and 2/4 though both are the same rational number, will have different cardinality n in this representation.
The same is the case with your earlier propasal of taking the binary operation of addition and go counting over rationals with equal sum of numerator and ...[text shortened]... mars the representation using product as the binary operator over the numerator and denominator.
18 Sep 04
Originally posted by observantUHmm, if you're interested, use induction on m+n to prove that if m and n are relatively prime, then m and n are consecutive terms in the sequence of xs.
This puzzle has been listed as one of the selected unsolved puzzles in at least one website which I accidentally came across. I dont recall the exact address of the site.
19 Sep 04
Originally posted by royalchickenI concede and withdraw my remark. But how can you tell what is the
Erm, no, 2/4 is Sir-not-appearing-in-this-sequence.
1000 th or the 10000 th rational? And how do you tell the cardinality (i.e. the serial no.) ,of any given prime ,say 355/113 or say 371/1000, without tabulating all the rationals up to that ? It still will require proof of this being bijection. Tabulation or even computer-search is no "proof'.
.
19 Sep 04
Originally posted by Acolyte0 0
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 particul ...[text shortened]... You might find it easier to
make a list of all integers, and go from there onto the rationals.
1 1
2 -1
3 2
4 3/2
5 1/2
6 -1/2
7 -3/2
8 -2
9 3
10 8/3
11 7/3
12 5/3
13 4/3
and so on.
19 Sep 04
1 edit
Originally posted by sarathianPerhaps you mean "rational" where you have used the word "prime" in second part of your post.
I concede and withdraw my remark. But how can you tell what is the
1000 th or the 10000 th rational? And how do you tell the cardinality (i.e. the serial no.) ,of any given prime ,say 355/113 or say 371/1000, without tabula ...[text shortened]... ion. Tabulation or even computer-search is no "proof'.
.
20 Sep 04
1 edit
Originally posted by royalchickenOkay, if m & n are relatively prime , then m+n is also relatively prime to both m and n. Basically Royalchic uses this very property to generate his sequence of consecutive successive relative primes. So? Proof of countability was never the issue of this puzzle.
I gave the germ of a proof in my response to observantU.
The poser has therefore alternatively framed the puzzle, that is , how do you find the 1000 th(or say million th) rational & how do you tell the serial no. of any given rational without generating the whole sequence ?
20 Sep 04
3 edits
Originally posted by observantUThat's true and I have not done this.
Okay, if m & n are relatively prime , then m+n is also relatively prime to both m and n. Basically Royalchic uses this very property to generate his sequence of consecutive successive relative primes. So? Proof of countabili ...[text shortened]... of any given rational without generating the whole sequence ?
It's not too hard to do a keep-dividing-by-two-and-looking-at-the-remainder thing.
For example, x(66) = x(32) + x(33) = x(15) + 2x(16) = 3x(7) + 2x(8) = 5x(3) + 2x(4) = 5 + 2 + 2x(2) = 11.
x(65) = x(32) = x(15) + x(16) = 2x(7) + x(8) = 3x(3) + x(4) = 3 + 1 + x(2) = 6.
Thus the 66th rational number is 6/11, unless I made an error, which is quite likely.