# Does there always exist a strictly increasing function from $\mathbb{R}$ to $\mathbb{R}$ less a countably infinite set?

Given some countably infinite set $Z$, can one always construct a strictly increasing function whose domain is all of $\mathbb{R}$, and whose codomain is $\mathbb{R} \setminus Z$? Specifically, I mean that $f(x) \in \mathbb{R}\setminus Z$, not that $f$ is a surjection. If not, are there examples that work in special cases, such as $Z=\mathbb{Z}$ or $Z=\mathbb{Q}$?

I already know that there is no surjection $f : \mathbb{R} \to \mathbb{R}\setminus\mathbb{Q}$.

• Quibble: there are lots of surjections from $\mathbb{R}$ to $\mathbb{R}\setminus \mathbb{Q}$, there's no order-preserving surjection. Sep 10, 2018 at 22:55
• @NoahSchweber - yes, I suppose I should have said "such surjection" Sep 10, 2018 at 23:38

Let me first give a strictly increasing map from $(0,1)$ to $(0,1)\setminus\mathbb{Q}$; I'll then argue why this shows that the answer to your question is yes in general.

Given $x\in(0,1)$, let $f(x)$ be the real gotten by interleaving the binary expansion of $x$ with the sequence $$\sigma=011000111100000111111...$$ (where if $x$ has two binary expansions, we pick the eventually-all-zeroes one). For example, if $x={1\over 3}=0.010101..._2$, then $f(x)=0.0\color{red}{0}1\color{red}{1}0\color{red}{1}1\color{red}{0}0\color{red}{0}1\color{red}{0}0\color{red}{1}1\color{red}{1}0\color{red}{1}1\color{red}{1}...$

It's easy to see that $f(x)$ is always irrational - basically, the sequence $\sigma$ kills any possibility of a repeating expansion - and is increasing on $(0,1)$.

Now first, note that $(0,1)$ is basically the same as $\mathbb{R}$ - there's an (well, many) order-preserving bijection between them. So what we've really done is handled $\mathbb{R}\rightarrow\mathbb{R}\setminus Z$ for a particular coundable dense $Z$.

Now the key point is that all countable dense $Z$ are equivalent; specifically, that there is an order-preserving bijection from $\mathbb{R}\setminus Z_0$ to $\mathbb{R}\setminus Z_1$ whenever $Z_0,Z_1$ are countable dense sets of reals. This is a bit tedious, so I won't include the details here, but it's a back-and-forth argument; we first take an order-preserving bijection $g_0$ between $Z_0$ and $Z_1$, and then show that this extends to an order-preserving bijection $g_1$ from $\mathbb{R}$ to $\mathbb{R}$ sending $Z_0$ to $Z_1$, and then the restriction $g_2$ of $g_1$ to $\mathbb{R}\setminus Z_0$ is an order-preserving bijection from $\mathbb{R}\setminus Z_0$ to $\mathbb{R}\setminus Z_1$.

So we've in fact handled the case when $Z$ is an arbitrary countable dense set of reals. But every countable set of reals is contained in a countable dense set of reals - just take the union with $\mathbb{Q}$ - so in fact we've given a complete positive answer to your question.

• Great answer (+1) you can compose this with my function to obtain a map from $\mathbb{R}\rightarrow (0,1)\backslash\mathbb{Q}$. Sep 10, 2018 at 22:50
• This is a great answer! How did you come up with the $\sigma$ construction? Have similar techniques been used elsewhere? Sep 11, 2018 at 20:05

Theorem. If $Z$ is countable, or more generally if $|Z|\lt|\mathbb R|,$ then $\mathbb R\setminus Z$ contains an uncountable closed set.

Proof. It will suffice to exhibit a family of continuum many disjoint uncountable closed subsets of $\mathbb R;$ the set $Z$ will not be able to meet all of them. To this end, let $t\mapsto(g(t),h(t))$ be a continuous surjection from $[0,1]$ to $[0,1]\times[0,1],$ and consider the sets $g^{-1}(x)$, $x\in[0,1].$ Alternatively, note that the Cantor set $C$ is homeomorphic to $C\times C$ and therefore contains continuum many disjoint Cantor sets.

Therefore it will suffice to prove the following:

Theorem. If $S$ is an uncountable closed subset of $\mathbb R,$ then there is a strictly increasing function $f:\mathbb R\to S.$

Proof. It will suffice to construct a strictly increasing function $\varphi:\mathbb Q\to S;$ then, since $S$ is closed, we can extend $\varphi$ to a strictly increasing function $f:\mathbb R\to S.$ by setting $f(x)=\sup\{\varphi(r):r\in\mathbb Q,\ r\lt x\}.$

To define a strictly increasing function $\varphi:\mathbb Q\to S,$ start by fixing an enumeration of the rationals as $\mathbb Q=\{r_1,r_2,r_3,\dots\}.$ Now define $\varphi(r_n)$ recursively, taking care that after each step the restriction of $\varphi$ to $\{r_1,r_2,\dots,r_n\}$ is strictly increasing and each of the $n+1$ intervals into which the $n$ points $f(r_1),f(r_2),\dots,f(r_n)$ divide the line contains uncountably many points
of $S.$

• +1. Quite nice, although invoking Lebesgue measure to show that $\mathbb{R}\setminus Z$ has an uncountable closed subset is overkill. Sep 10, 2018 at 23:45

The map $f(x)=\frac{e^x}{e^x+1}$ is a strictly monotone function from $\mathbb{R}$ to $(0,1)$.

It is strictly monotone because $e^x$ and $\frac{x}{x+1}$ are strictly monotone and a composition of strictly monotone functions is strictly monotone. So this is an example for the special case $Z=\mathbb{Z}$ but you can easily generalize this for $Z=r\mathbb{Z}$ for any real number $r$ by taking $f(\frac{x}{r})$.

• That's clever: squeezing the whole real line in between two integers. I wonder how one would construct $f$ for a dense $Z$? Sep 10, 2018 at 22:45
• @AlexReinking Looks like Noah is up to something Sep 10, 2018 at 22:46
• How does this relate to the question? Sep 10, 2018 at 22:50
• @Michael Your understanding appears to be incorrect. To quote from the question: "Specifically, I mean that $f(x) \in \mathbb{R}\setminus Z$, not that $f$ is a surjection" (emph. mine). Sep 10, 2018 at 22:53
• @Michael That's not what "codomain" means. The set $f(\mathbb{R})$ is the image of $f$ (or the range, but some texts use "range" to refer to the codomain instead, so "image" is clearer); in general the image is much smaller than the codomain. Regardless, the OP's statement "Specifically, I mean that $f(x)\in\mathbb{R}\setminus Z$" should clarify what they mean. Sep 10, 2018 at 22:58

Yes, this is possible. Let me take an approach that may seem a little backwards--I will start with a function $f$, and then construct a countably infinite set $Z$ for which $f$ works.

Specifically, let us take the function $f:\mathbb{R}\to\mathbb{R}$ which takes the base $2$ expansion of a number and considers it instead as a base $3$ expansion. (For dyadic rationals, which have two different base $2$ expansions, just pick one of them to define $f$.) It is clear that $f$ is strictly increasing. Moreover, the image of $f$ is contained in the set of real numbers with a base $3$ expansion consisting of entirely $0$s and $1$s. This set is has empty interior: every interval contains numbers whose unique base $3$ expansion has a $2$.

So, we can pick a countable dense subset $Z\subset\mathbb{R}$ which is disjoint from the image of $f$ (for each interval with rational endpoints, pick a point not in the image of $f$ and put it in $Z$). The function $f$ then solves the problem for this $Z$.

However, I claim this then solves the problem in general. Indeed, suppose $W\subset \mathbb{R}$ is a countable subset. Enlarging $W$, we may assume that $W$ is dense in $\mathbb{R}$. A standard back-and-forth argument now constructs an order-isomorphism $g:Z\to W$. This $g$ extends to an order-isomorphism $\bar{g}:\mathbb{R}\to\mathbb{R}$, since $\mathbb{R}$ is the Dedekind completion of both $Z$ and $W$. The composition $\bar{g}\circ f$ is the a strictly increasing function $\mathbb{R}\to\mathbb{R}\setminus W$.