MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Questions about ordering of reals and irrationals

Three problems from G.Rosenstein "Linear orderings" (from the end of Chapter 2 and beginning of Chapter 4):

1) Is there a nondecreasing function from irrationals onto reals?

2) Is there a nondecreasing function from reals onto irrationals?

3) Is there an increasing function from reals into irrationals? (In other words, are reals a subordering of irrationals?)

Any hints would be appreciated.

(Please tag the question set-theory order-theory)

-
And maybe there should be a rule that homework should be tagged as such? They have it on StackOverflow: meta.stackoverflow.com/questions/18242/… – Ilya Nikokoshev Oct 11 2009 at 14:32
Sorry, a better link is meta.stackoverflow.com/questions/10811/… – Ilya Nikokoshev Oct 11 2009 at 14:34
It's not homework; I'm reading that book recreationally and these are only problems in these chapters I'm stuck on. I can wait longer for an answer. Otherwise I agree that homework should be tagged. – sdcvvc Oct 11 2009 at 15:04
Sorry, I should have asked you directly if it's homework or not... – Ilya Nikokoshev Oct 11 2009 at 17:39
Perhaps we should have a tag instead for "exercise"s or "book-problem"s. – Scott Morrison Oct 11 2009 at 18:38
show 4 more comments

Here is a simple proof of (3), without continued fractions.

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

-

(3) This is only a minute variant on Ilya's answer, but I think it looks a bit more perspicuous in continued fractions.
In fact, there's a negative continued fraction 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 = a0 - 1/(a1 - 1/(a2 - 1/(...))) with all an in Z and an>=2 for i>=1. x is rational iff the all an are 2 from some point on. And the negative continued fractions have the lexicographic order: x>x' iff ai>a'i for the first i for which ai and a'i differ.

So just map x to (a0+1) - 1/( (a1+1) - 1/( (a2+1) - 1/(...))).

-
 This answer is awesome. – S. Carnahan♦ Oct 11 2009 at 18:55 Thanks for the citation! Fractions are certainly cool. – Ilya Nikokoshev Oct 11 2009 at 19:47

(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 binary and target numbers in base 4.

Consider first the number 1/2, in binary 0.1000... Let's map it to 0.1[0102010...] — 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.

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...

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...

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.

We're still increasing, yahoo!

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 — 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.

Since every two irrationals are separated by rational, this function is always increasing. Qued erat construirum.

-
 (Sorry for nitpicking on what is not maths, but the right Latin ending phrase would be "Quod erat construendum" :) ) – Qfwfq Nov 11 at 23:27

1) modify Cantor function 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.

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.

3) if such embedding existed, irrationals and reals would be \infty-equivalent (think infinitely long Ehrenfeucht–Fraïssé game). But they are not. I think. (well, it's been shown that such embedding is actually possible, so my assumption was incorrect)

-
 (3) Are you sure you're right? The map will be into, not onto. – Ilya Nikokoshev Oct 11 2009 at 18:17 Also, what's the problem with links? Is it because they need to be escaped like in tip 7 of mathoverflow.net/tips? – Ilya Nikokoshev Oct 11 2009 at 18:19 Two /infty-equivalent structures don't have to be isomorphic if their cardinality is uncountable. But no, I'm not sure if I'm right about this one. – Grue Oct 11 2009 at 18:27 And the problem with links is that I have 1 reputation so this site thinks I'm a spammer. Great way to attract new users. – Grue Oct 11 2009 at 18:28 I added your links. – Scott Morrison♦ Oct 11 2009 at 18:44
show 1 more comment

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).

3) [removed due to being a flawed argument - Scott]

-
 The finite interval assertion in the last sentence is clearly false, since you can take an infinite subsequence of rationals with nested neighborhoods. I don't see a way to rescue the argument (but it's more or less moot at this point). – S. Carnahan♦ Oct 11 2009 at 19:05 Indeed why not just edit it out? – Ilya Nikokoshev Oct 11 2009 at 23:11

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.

-
I'm talking about the order type: is the order type of reals embeddable in irrational numbers? Use the first formulation if unclear. – sdcvvc Oct 11 2009 at 16:31
Sorry for -1 but the question is well-defined as stated. – Ilya Nikokoshev Oct 11 2009 at 17:53