Hi guys,
since nothing much has been happening here lately, here is a nice one
that crept up on me while I was talking to a collegue:
We know that the rational numbers are countable, ie. we can find a one-
to-one relation between the rational numbers and the positive
integers. So let {q_k}, k = 1,2,.... , be an enumeration of the
rational numbers. We surround each rational number with an interval
I_k of length 2^-k, ie.
I_k = [q_k - 2^{-k-1}, q_k + 2^{-k-1} ].
Question: are all the irrational numbers covered by the union of those
intervals? Think about how dense the rationals lie on the real line,
and how each one has a little interval around it ...
Regards,
Andor
Inconsequential math riddle
Started by ●September 22, 2007
Reply by ●September 23, 20072007-09-23
On Sat, 22 Sep 2007 13:46:33 -0700, Andor wrote:> Hi guys, > > since nothing much has been happening here lately, here is a nice one > that crept up on me while I was talking to a collegue: > > We know that the rational numbers are countable, ie. we can find a one- > to-one relation between the rational numbers and the positive > integers. So let {q_k}, k = 1,2,.... , be an enumeration of the > rational numbers. We surround each rational number with an interval > I_k of length 2^-k, ie. > > I_k = [q_k - 2^{-k-1}, q_k + 2^{-k-1} ]. > > Question: are all the irrational numbers covered by the union of those > intervals? Think about how dense the rationals lie on the real line, > and how each one has a little interval around it ... >Answer: You have not given enough information, because you have only specified an enumeration of the rational numbers, not an _ordered_ enumeration. The easiest ordering for the rational numbers that I can think of would oscillate between zero and approximately sqrt(k) for it's entire length, and whose slope as it approaches sqrt(k) would approximate 1 (I think) - it wouldn't take long before your interval wasn't big enough to span the distance between the numbers. You would have to find an ordering for the rational numbers that sorts them as well; that would be a challenge. I suspect that once you did you would find that the slope wouldn't be right for your interval to hold. -- Tim Wescott Control systems and communications consulting http://www.wescottdesign.com Need to learn how to apply control theory in your embedded system? "Applied Control Theory for Embedded Systems" by Tim Wescott Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html
Reply by ●September 23, 20072007-09-23
Tim Wescott wrote:> On Sat, 22 Sep 2007 13:46:33 -0700, Andor wrote: > > Hi guys, > > > since nothing much has been happening here lately, here is a nice one > > that crept up on me while I was talking to a collegue: > > > We know that the rational numbers are countable, ie. we can find a one- > > to-one relation between the rational numbers and the positive > > integers. So let {q_k}, k = 1,2,.... , be an enumeration of the > > rational numbers. We surround each rational number with an interval > > I_k of length 2^-k, ie. > > > I_k = [q_k - 2^{-k-1}, q_k + 2^{-k-1} ]. > > > Question: are all the irrational numbers covered by the union of those > > intervals? Think about how dense the rationals lie on the real line, > > and how each one has a little interval around it ... > > Answer: > > You have not given enough information, because you have only specified an > enumeration of the rational numbers, not an _ordered_ enumeration.The question can be answered independent of the ordering of the enumeration.> The > easiest ordering for the rational numbers that I can think of would > oscillate between zero and approximately sqrt(k) for it's entire length, > and whose slope as it approaches sqrt(k) would approximate 1 (I think) - it > wouldn't take long before your interval wasn't big enough to span the > distance between the numbers. > > You would have to find an ordering for the rational numbers that sorts > them as well; that would be a challenge.You can start to find such a sorting enumeration by specifying the smallest positive rational number.> I suspect that once you did you > would find that the slope wouldn't be right for your interval to hold.Slope?? Regards, Andor
Reply by ●September 23, 20072007-09-23
On Sun, 23 Sep 2007 04:40:09 -0700, Andor wrote:> Tim Wescott wrote: >> On Sat, 22 Sep 2007 13:46:33 -0700, Andor wrote: >> > Hi guys, >> >> > since nothing much has been happening here lately, here is a nice one >> > that crept up on me while I was talking to a collegue: >> >> > We know that the rational numbers are countable, ie. we can find a one- >> > to-one relation between the rational numbers and the positive >> > integers. So let {q_k}, k = 1,2,.... , be an enumeration of the >> > rational numbers. We surround each rational number with an interval >> > I_k of length 2^-k, ie. >> >> > I_k = [q_k - 2^{-k-1}, q_k + 2^{-k-1} ]. >> >> > Question: are all the irrational numbers covered by the union of those >> > intervals? Think about how dense the rationals lie on the real line, >> > and how each one has a little interval around it ... >> >> Answer: >> >> You have not given enough information, because you have only specified an >> enumeration of the rational numbers, not an _ordered_ enumeration. > > The question can be answered independent of the ordering of the > enumeration. >I'm not figuring it out, but then I don't think it _can_ be ordered in a sensible way.> >> The >> easiest ordering for the rational numbers that I can think of would >> oscillate between zero and approximately sqrt(k) for it's entire >> length, and whose slope as it approaches sqrt(k) would approximate 1 (I >> think) - it wouldn't take long before your interval wasn't big enough >> to span the distance between the numbers. >> >> You would have to find an ordering for the rational numbers that sorts >> them as well; that would be a challenge. > > You can start to find such a sorting enumeration by specifying the > smallest positive rational number. >No you can't. Think -- the smallest positive rational number is infinitesimally small, which means that whenever _you_ pick a concrete "smallest" to assign to k = 0 _I_ can find a smaller one. You could declare that you're only going to do the proof on the positive real number line, assign k = 0 for 1/1 with rational numbers smaller than 1 assigned to k < 0 and rational numbers larger than one for k > 0.>> I suspect that once you did you >> would find that the slope wouldn't be right for your interval to hold. > > Slope??Slope. Change in the value of the corresponding members of the sorted set of rational numbers with change in k. Once you consider slope, it becomes apparent that a sorted ordering isn't going to get you there. If you allow repetition, there are an infinite number of rational numbers that are equal to one. Even if you don't, there are an infinite number of rational numbers in any finite interval in the vicinity of one -- so my clever sorted set idea doesn't make sense, because it'll be 1, or essentially 1, as far as the eye can see. -- Tim Wescott Control systems and communications consulting http://www.wescottdesign.com Need to learn how to apply control theory in your embedded system? "Applied Control Theory for Embedded Systems" by Tim Wescott Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html
Reply by ●September 23, 20072007-09-23
Tim Wescott wrote:> On Sun, 23 Sep 2007 04:40:09 -0700, Andor wrote: > > Tim Wescott wrote: > >> On Sat, 22 Sep 2007 13:46:33 -0700, Andor wrote: > >> > Hi guys, > > >> > since nothing much has been happening here lately, here is a nice one > >> > that crept up on me while I was talking to a collegue: > > >> > We know that the rational numbers are countable, ie. we can find a one- > >> > to-one relation between the rational numbers and the positive > >> > integers. So let {q_k}, k = 1,2,.... , be an enumeration of the > >> > rational numbers. We surround each rational number with an interval > >> > I_k of length 2^-k, ie. > > >> > I_k = [q_k - 2^{-k-1}, q_k + 2^{-k-1} ]. > > >> > Question: are all the irrational numbers covered by the union of those > >> > intervals? Think about how dense the rationals lie on the real line, > >> > and how each one has a little interval around it ... > > >> Answer: > > >> You have not given enough information, because you have only specified an > >> enumeration of the rational numbers, not an _ordered_ enumeration. > > > The question can be answered independent of the ordering of the > > enumeration. > > I'm not figuring it out, but then I don't think it _can_ be ordered in a > sensible way.The ordering doesn't matter.> > >> The > >> easiest ordering for the rational numbers that I can think of would > >> oscillate between zero and approximately sqrt(k) for it's entire > >> length, and whose slope as it approaches sqrt(k) would approximate 1 (I > >> think) - it wouldn't take long before your interval wasn't big enough > >> to span the distance between the numbers. > > >> You would have to find an ordering for the rational numbers that sorts > >> them as well; that would be a challenge. > > > You can start to find such a sorting enumeration by specifying the > > smallest positive rational number. > > No you can't. Think -- the smallest positive rational number is > infinitesimally small, which means that whenever _you_ pick a concrete > "smallest" to assign to k = 0 _I_ can find a smaller one.aSo, you've just proved that there is not enumeration that sorts the rationals.> > You could declare that you're only going to do the proof on the positive > real number line, assign k = 0 for 1/1 with rational numbers smaller than > 1 assigned to k < 0 and rational numbers larger than one for k > 0. > > >> I suspect that once you did you > >> would find that the slope wouldn't be right for your interval to hold. > > > Slope?? > > Slope. Change in the value of the corresponding members of the sorted set > of rational numbers with change in k.I'm not sure where you come up with that sorted set business. I was talking about an enumeration of the rationals, and you have just above proved that there is no such thing as a sorting enumeration of the rationals.> > Once you consider slope, it becomes apparent that a sorted ordering isn't > going to get you there. If you allow repetition, there are an infinite > number of rational numbers that are equal to one.Well, the enumeration should be one-to-one, so repetition technically isn't allowed. However, this fact is also not important for answering my original question.> Even if you don't, > there are an infinite number of rational numbers in any finite interval in > the vicinity of one -- so my clever sorted set idea doesn't make sense, > because it'll be 1, or essentially 1, as far as the eye can see.Not quite sure what you mean. One of the nice facettes of this riddle is the fact that in any "vicinity" (neighbourhood) of any irrational number, there is a rational number. No matter how small a neighbourhood one considers around an irrational, there will always be a rational number in there. And that rational number q_k will have a little interval I_k around it. Does that mean that all irrational numbers are covered by at least one interval I_k? Regards, Andor
Reply by ●September 23, 20072007-09-23
On Sun, 23 Sep 2007 11:18:05 -0700, Andor wrote:> Tim Wescott wrote: >> On Sun, 23 Sep 2007 04:40:09 -0700, Andor wrote: >> > Tim Wescott wrote: >> >> On Sat, 22 Sep 2007 13:46:33 -0700, Andor wrote: >> >> > Hi guys, >> >> >> > since nothing much has been happening here lately, here is a nice one >> >> > that crept up on me while I was talking to a collegue: >> >> >> > We know that the rational numbers are countable, ie. we can find a one- >> >> > to-one relation between the rational numbers and the positive >> >> > integers. So let {q_k}, k = 1,2,.... , be an enumeration of the >> >> > rational numbers. We surround each rational number with an interval >> >> > I_k of length 2^-k, ie. >> >> >> > I_k = [q_k - 2^{-k-1}, q_k + 2^{-k-1} ]. >> >> >> > Question: are all the irrational numbers covered by the union of those >> >> > intervals? Think about how dense the rationals lie on the real line, >> >> > and how each one has a little interval around it ... >> >> >> Answer: >> >> >> You have not given enough information, because you have only specified an >> >> enumeration of the rational numbers, not an _ordered_ enumeration. >> >> > The question can be answered independent of the ordering of the >> > enumeration. >> >> I'm not figuring it out, but then I don't think it _can_ be ordered in a >> sensible way. > > The ordering doesn't matter. > >> >> >> The >> >> easiest ordering for the rational numbers that I can think of would >> >> oscillate between zero and approximately sqrt(k) for it's entire >> >> length, and whose slope as it approaches sqrt(k) would approximate 1 (I >> >> think) - it wouldn't take long before your interval wasn't big enough >> >> to span the distance between the numbers. >> >> >> You would have to find an ordering for the rational numbers that sorts >> >> them as well; that would be a challenge. >> >> > You can start to find such a sorting enumeration by specifying the >> > smallest positive rational number. >> >> No you can't. Think -- the smallest positive rational number is >> infinitesimally small, which means that whenever _you_ pick a concrete >> "smallest" to assign to k = 0 _I_ can find a smaller one.a > > So, you've just proved that there is not enumeration that sorts the > rationals. > >> >> You could declare that you're only going to do the proof on the positive >> real number line, assign k = 0 for 1/1 with rational numbers smaller than >> 1 assigned to k < 0 and rational numbers larger than one for k > 0. >> >> >> I suspect that once you did you >> >> would find that the slope wouldn't be right for your interval to hold. >> >> > Slope?? >> >> Slope. Change in the value of the corresponding members of the sorted set >> of rational numbers with change in k. > > I'm not sure where you come up with that sorted set business. I was > talking about an enumeration of the rationals, and you have just above > proved that there is no such thing as a sorting enumeration of the > rationals. > >> >> Once you consider slope, it becomes apparent that a sorted ordering isn't >> going to get you there. If you allow repetition, there are an infinite >> number of rational numbers that are equal to one. > > Well, the enumeration should be one-to-one, so repetition technically > isn't allowed. However, this fact is also not important for answering > my original question. > >> Even if you don't, >> there are an infinite number of rational numbers in any finite interval in >> the vicinity of one -- so my clever sorted set idea doesn't make sense, >> because it'll be 1, or essentially 1, as far as the eye can see. > > Not quite sure what you mean. One of the nice facettes of this riddle > is the fact that in any "vicinity" (neighbourhood) of any irrational > number, there is a rational number. No matter how small a > neighbourhood one considers around an irrational, there will always be > a rational number in there. And that rational number q_k will have a > little interval I_k around it. Does that mean that all irrational > numbers are covered by at least one interval I_k? >What you originally asked for: "are all the irrationals covered in the union of the intervals you specified" boils down to "does the union of intervals span the whole real number line". I doubt that it does, while at the same time being pretty sure that my current level of mathematical training doesn't allow me to prove this one way or another. -- Tim Wescott Control systems and communications consulting http://www.wescottdesign.com Need to learn how to apply control theory in your embedded system? "Applied Control Theory for Embedded Systems" by Tim Wescott Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html
Reply by ●September 23, 20072007-09-23
Andor <andor.bariska@gmail.com> writes:> ... > We know that the rational numbers are countable, ie. we can find a one- > to-one relation between the rational numbers and the positive > integers. So let {q_k}, k = 1,2,.... , be an enumeration of the > rational numbers. We surround each rational number with an interval > I_k of length 2^-k, ie. > > I_k = [q_k - 2^{-k-1}, q_k + 2^{-k-1} ]. > > Question: are all the irrational numbers covered by the union of those > intervals? Think about how dense the rationals lie on the real line, > and how each one has a little interval around it ...Where is the question? First a remark on the standard way to enumerate rationals, as this proofs their countabiliyt: Each rational number is a pair of integers (don't care that this rep is not unique.) Now imagine a matrix, infinite to the right and downwards. Associate the pair (i,j), where i and j are integrs, with the i-th row and j-th column. I.e. the matrix contains a rep of any rational. Now start at the upper left corner of the matrix ``running on lines of slope 1'' upwards and downwards. I.e. you visit the elements in the order (1,1) (1,2) (2,1) (3,1) (2,2) (1,3) (1,4) .... Given any rational, it is obviously conceptually trivial to calculate the index at which first time one of it's reps is reached. Second, above is suggested to surround the n-th rational by a ``ball'' of diameter 2^{-n} (not careing of an extra factor 1/2). So, by elementary theory of sets, each rational is contained in the union of all those balls. Third, this construction is a standard example in treatments of the theory of Lebesgue integration. We could as well have enclosed the n-th rational in a ball of diameter \epsilon 2^{-n} or \epsilon /n^2. As both series (1/2^n) and (1/n^2) converge, we have shown, that we can enclose all rationals within a set of intervalls, such that the summ of the diameters of all these intervalls is _arbitrary_ small!!! This argument is used in theory of integration to show that any countable set has measure zero. -- hw
Reply by ●September 23, 20072007-09-23
Andor wrote: ...> You can start to find such a sorting enumeration by specifying the > smallest positive rational number.Is the smallest possible rational number more easily pinned down that the largest possible rational number? It is certainly easier to name a bound! ... Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●September 23, 20072007-09-23
Andor wrote: ...> Well, the enumeration should be one-to-one, so repetition technically > isn't allowed. However, this fact is also not important for answering > my original question.Without some sort of sieve, how will 1/1, 2/2, 3/3, ... be seen as redundant? ... Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●September 24, 20072007-09-24
On 23 , 03:46, Andor <andor.bari...@gmail.com> wrote:> Hi guys, > > since nothing much has been happening here lately, here is a nice one > that crept up on me while I was talking to a collegue: > > We know that the rational numbers are countable, ie. we can find a one- > to-one relation between the rational numbers and the positive > integers. So let {q_k}, k = 1,2,.... , be an enumeration of the > rational numbers. We surround each rational number with an interval > I_k of length 2^-k, ie. > > I_k = [q_k - 2^{-k-1}, q_k + 2^{-k-1} ]. > > Question: are all the irrational numbers covered by the union of those > intervals? Think about how dense the rationals lie on the real line, > and how each one has a little interval around it ... > > Regards, > AndorAnswer: No. This will not cover all numbers. We need enumeration that: exists i : for any k abs(q_k-i)>2^-k to build this enumeration: 1. take any enumeration 2. fix irrational i 3. suppose that exists k: abs(i-q_k)<2^-k 3.1 there is k1: abs(i-q_k)>2^-k1 4. find k2>k1: abs(i=q_k2)>2^-k1 (trivial that it is exists) 5. exchange numbers for q_k & q_k2 in enumeration 6. repeat from step 3. So there is enumeration that did not cover at least one irrational. Regards, Evgeny Cheremushkin, www.nprog.ru
