Re: Two results of set geometry

David R Tribble wrote:
Tony Orlow wrote:
Any rational fraction you express in binary will become an infinitely
repeating finite string of digits, in this case 0.10..., and can be
associated with that finite string. In fact, is there not a 1-1
correspondence between such repeating fractions and the finite naturals,
each being a finite string?

William Hughes wrote:
You have just shown that the rationals are countable.
Don't stop the presses.

Tony Orlow wrote:
I was answering ***'s challenge to assign a node to the path
0.101010..., which I did, if you noticed. Besides, it's a rather nice
proof that the rationals are countable, wouldn't you say?

Just to be pedantic, it only proves that a subset of the
rationals is countable, specifically, all the rationals in [0,1]
with denominators that are relatively prime to 2. All other
rationals have finite-length binary fractions. E.g., 3/7 is an
infinite-length binary fraction, while 3/8 is not.

But William's point is well taken.


I'm not ashamed.

Well, I'm big enough to admit that Tony has, for once, produced
something somewhat clever. Yes, we can take every natural k and
make a repeating binary fraction out of it (e.g., k=14 gives
.1110 1110 1110...), thus yielding a bijection between N and all
the repeating binary fractions, which are (as I stated above)
all the rationals in [0,1] with denominators relatively prime to 2.

But wait, this mapping is not a bijection at all. Consider
k=10, which corresponds to .1010 1010 1010.... Notice that this
is identical to .10 10 10..., which is the binary fraction for
k=2. So there are a lot of duplicates in this mapping, and
there is not a 1-1 mapping between the naturals and the fractions.

Oh well, it at least proves that those binary fractions are
countable.


Right. It's not a complete answer to the ultimate question there. Your terminating fractions are already included, being associated with their last 1 bit. All the 0 bits are then left unused. Those that repeat a string from the beginning are then included by associating them with the first 0 node after their repeated substring. Indeed, as you point out, more than one such 0 bit can produce the same infinite string, like 100 and 10100 both producing 0.10101010..., but all this means is that there are still many of the 0 nodes left to assign to infinite strings. The rational strings this approach still leaves out are those with an initial segment before the repeating pattern, such as 0.1110011001100.... So, it still doesn't map all the rationals to the nodes, but there are still nodes unmapped and available. It's probably not important, but just a little exercise.

Peace,

Tony
.

Quantcast