Questions about ordering of reals and irrationals - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T17:06:00Z http://mathoverflow.net/feeds/question/279 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/279/questions-about-ordering-of-reals-and-irrationals Questions about ordering of reals and irrationals sdcvvc 2009-10-11T13:33:37Z 2009-12-01T16:56:26Z <p>Three problems from G.Rosenstein "Linear orderings" (from the end of Chapter 2 and beginning of Chapter 4):</p> <p>1) Is there a nondecreasing function from irrationals onto reals?</p> <p>2) Is there a nondecreasing function from reals onto irrationals?</p> <p>3) Is there an increasing function from reals into irrationals? (In other words, are reals a subordering of irrationals?)</p> <p>Any hints would be appreciated.</p> <p>(Please tag the question set-theory order-theory)</p> http://mathoverflow.net/questions/279/questions-about-ordering-of-reals-and-irrationals/289#289 Answer by MathNerd for Questions about ordering of reals and irrationals MathNerd 2009-10-11T16:14:03Z 2009-10-11T16:14:03Z <p>Not sure I get your #3 question . . . irrational numbers ARE real numbers. Real numbers are the big set (include everything but non-reals such as the square root of a negative number, i) and within real numbers are the two subsets of rational and irrational numbers. Irrationals are a subset of reals, not vice-versa.</p> http://mathoverflow.net/questions/279/questions-about-ordering-of-reals-and-irrationals/293#293 Answer by S. Carnahan for Questions about ordering of reals and irrationals S. Carnahan 2009-10-11T17:37:59Z 2009-10-11T23:38:12Z <p>1) Take any nondecreasing continuous function from the reals to the reals that is constant in neighborhoods of rationals, and restrict it to irrationals. This can be constructed as a uniform limit by starting with f(0)(x) = x, enumerating the rationals as r(i) and for each i, setting f(i+1)(x) to be a sum of f(i)(x) and some piecewise linear function supported in a neighborhood of radius 2^(-i) around r(i).</p> <p>3) [removed due to being a flawed argument - Scott]</p> http://mathoverflow.net/questions/279/questions-about-ordering-of-reals-and-irrationals/295#295 Answer by Grue for Questions about ordering of reals and irrationals Grue 2009-10-11T18:02:45Z 2009-10-12T06:25:48Z <p>1) modify <a href="http://en.wikipedia.org/wiki/Cantor%5Ffunction" rel="nofollow">Cantor function</a> so that all it's growth points are irrational. Then you have a mapping from an interval of irrational numbers to an interval of reals. Then extend to the whole range of numbers.</p> <p>2) consider a sequence i[n] of irrationals that converges to a rational number. Then if for each member you take the inf of reals that map into it, and consider the limit L of those (it's a bounded sequence so there's a limit), then f(L) is irrational and greater than f(i[n]) for all n. It cannot be rational, so there would be a gap, but since it's an onto mapping there can't be any gaps.</p> <p>3) if such embedding existed, irrationals and reals would be \infty-equivalent (think infinitely long <a href="http://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Fra%C3%AFss%C3%A9%5Fgame" rel="nofollow">Ehrenfeucht–Fraïssé game</a>). But they are not. I think. (well, it's been shown that such embedding is actually possible, so my assumption was incorrect)</p> http://mathoverflow.net/questions/279/questions-about-ordering-of-reals-and-irrationals/297#297 Answer by Ilya Nikokoshev for Questions about ordering of reals and irrationals Ilya Nikokoshev 2009-10-11T18:16:29Z 2009-10-11T18:16:29Z <p>(3) Here's how to construct an example. We can assume the segment in question was from 0 to 1 non-inclusively. Also, I will write source numbers in <em>binary</em> and target numbers in <em>base 4</em>.</p> <p>Consider first the number 1/2, in binary 0.1000... Let's map it to 0.1[0102010...] &mdash; it doesn't matter what's inside [...] as long as it's irrational. Now we decide to map all numbers of the form 0.0... to 0.0... and 0.1... to 0.2... . Clearly, so far we didn't break anything.</p> <p>Now, let's take a different rational number, e.g. 1/4 = 0.010... Similarly, we decide to map it to one of irrationals of the form 0.01[10011010...] and the segment [1/4, 1/2] is ready to go to 0.02...</p> <p>Select the next rational number, e.g. 1/3 = 0.0101(01). It's breaking in half the segment destined to go to 0.02... No problem, again we select some irrational 0.021[010012...] for 1/3 and move left and right subsegments to 0.020... and 0.022...</p> <p>Now, so far I was using xxx0, xxx1 and xxx2. But let's sometimes move segments to xxx1, xxx2 and xxx3. Let's do it whenever I'm on a level which is a square of natural number.</p> <p>We're still increasing, yahoo!</p> <p>Repeat this process for all rationals ordered by denominator. For any rational we have selected an irrational number by definition. For any irrational, it's the limit of segments broken down into parts. Each breakdown reveals exactly one digit of the result &mdash; so we reconstruct it digit-by-digit in ternary. It has infinite number of digits. Moreover, these digits never become periodical thanks to the fact that each $n^2$-digit was shifted by 1. So the result is irrational too.</p> <p>Since every two irrationals are separated by rational, this function is always increasing. Qued erat construirum.</p> http://mathoverflow.net/questions/279/questions-about-ordering-of-reals-and-irrationals/300#300 Answer by Alex Fink for Questions about ordering of reals and irrationals Alex Fink 2009-10-11T18:45:02Z 2009-10-11T18:45:02Z <p>(3) This is only a minute variant on Ilya's answer, but I think it looks a bit more perspicuous in continued fractions.<br /> In fact, there's a <i>negative continued fraction</i> expansion that Richard Guy told me about which have a nicer ordering than standard regular cfs. Every real is uniquely representable as an infinite continued fraction x = a<sub>0</sub> - 1/(a<sub>1</sub> - 1/(a<sub>2</sub> - 1/(...))) with all a<sub>n</sub> in <b>Z</b> and a<sub>n</sub>>=2 for i>=1. x is rational iff the all a<sub>n</sub> are 2 from some point on. And the negative continued fractions have the lexicographic order: x&gt;x' iff a<sub>i</sub>&gt;a'<sub>i</sub> for the first i for which a<sub>i</sub> and a'<sub>i</sub> differ. </p> <p>So just map x to (a<sub>0</sub>+1) - 1/( (a<sub>1</sub>+1) - 1/( (a<sub>2</sub>+1) - 1/(...))).</p> http://mathoverflow.net/questions/279/questions-about-ordering-of-reals-and-irrationals/7458#7458 Answer by Joel David Hamkins for Questions about ordering of reals and irrationals Joel David Hamkins 2009-12-01T16:56:26Z 2009-12-01T16:56:26Z <p>Here is a simple proof of (3), without continued fractions.</p> <p>For any real number x, let f(x) be the real obtained by interleaving the binary digits of x with the binary digits of pi, a fixed irrational number. This is clearly order-preserving, and f(x) is irrational since the digits will not repeat. QED</p>