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).
cantor's method of counting only establishes that the set of rational nos. is countable. it does not give a one to one mapping(bijection).
Royalchic, you are yet to prove that ur method of counting is one-to one mapping.....
Originally posted by Acolyte 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.
Have 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....
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).
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 denominator. The same discrepancy mars the representation using product as the binary operator over the numerator and denominator.
Originally posted by sarathian 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.
Erm, no, 2/4 is Sir-not-appearing-in-this-sequence.
Originally posted by royalchicken Erm, no, 2/4 is Sir-not-appearing-in-this-sequence.
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.
Originally posted by observantU 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.
Hmm, 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.
Originally posted by royalchicken Erm, no, 2/4 is Sir-not-appearing-in-this-sequence.
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 tabulating all the rationals up to that ? It still will require proof of this being bijection. Tabulation or even computer-search is no "proof'.
.
Originally posted by Acolyte 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.
Originally posted by sarathian 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'.
.
Perhaps you mean "rational" where you have used the word "prime" in second part of your post.
Originally posted by royalchicken I gave the germ of a proof in my response to observantU.
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 countability was never the issue of this puzzle.
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 ?
Originally posted by observantU 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 ?
That's true and I have not done this.
It's not too hard to do a keep-dividing-by-two-and-looking-at-the-remainder thing.
10 Jul '04 14:39
Counting problem
Back to Top