MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
And maybe there should be a rule that homework should be tagged as such? They have it on StackOverflow:… – Ilya Nikokoshev Oct 11 '09 at 14:32
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 '09 at 15:04
Perhaps we should have a tag instead for "exercise"s or "book-problem"s. – Scott Morrison Oct 11 '09 at 18:38
@ilya: wouldn't a [homework] tag be even worse? Anyway, no 8th grade problems here please. – Anton Geraschenko Oct 12 '09 at 2:22
Yeah, but if a tag is too narrow it is useless. I think that "exercise in a graduate level text" is about the right level of specificity, and I am fine with calling it "exercise". – David Speyer Dec 1 '09 at 17:01

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

share|cite|improve this answer
Minor nit-pick: One has to choose a 2-adic expansion of every $x$ to do this, for example the (uniquely determined) one that has infinitely many ones. It matters because the digit sequences 100000... and 0111111... will be mapped to different irrationals even though they represent the same rational number. – Johannes Hahn Jan 25 '15 at 17:07
Yes; so just use your favorite representation (say, the one without tailing $1$s), and there is no problem. – Joel David Hamkins Jan 25 '15 at 17:24

(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=a_{0}-1/\left(a_{1}-1/\left(a_{2}-1/\left(\ldots\right)\right)\right)$ with all $a_{n}$ in $\mathbb {Z}$ and $a_{n}\ge 2$ for $i\ge 1$. $x$ is rational iff the all $a_{n}$ are $2$ from some point on. And the negative continued fractions have the lexicographic order: $x\gt x^{\prime}$ iff $a_{i}\gt a^{\prime}_{i}$ for the first $i$ for which $a_{i}$ and $a^{\prime}_{i}$ differ.

So just map $x$ to $\left(a_{0}+1\right)-1/\left(\left(a_{1}+1\right)-1/\left(\left(a_{2}+1\right)-1/\left(\ldots\right)\right)\right)$.

share|cite|improve this answer
This answer is awesome. – S. Carnahan Oct 11 '09 at 18:55
Thanks for the citation! Fractions are certainly cool. – Ilya Nikokoshev Oct 11 '09 at 19:47

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)

share|cite|improve this answer
(3) Are you sure you're right? The map will be into, not onto. – Ilya Nikokoshev Oct 11 '09 at 18:17
Also, what's the problem with links? Is it because they need to be escaped like in tip 7 of – Ilya Nikokoshev Oct 11 '09 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 '09 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 '09 at 18:28
I added your links. – Scott Morrison Oct 11 '09 at 18:44

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]

share|cite|improve this answer
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 '09 at 19:05
Indeed why not just edit it out? – Ilya Nikokoshev Oct 11 '09 at 23:11

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

share|cite|improve this answer
(Sorry for nitpicking on what is not maths, but the right Latin ending phrase would be "Quod erat construendum" :) ) – Qfwfq Nov 11 '12 at 23:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.