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)
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=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)$.
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)
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]
(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.
