5

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

Alex Reinking
  • 573

4 Answers4

7

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.

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

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

bof
  • 78,265
  • 1
    +1. Quite nice, although invoking Lebesgue measure to show that $\mathbb{R}\setminus Z$ has an uncountable closed subset is overkill. – Noah Schweber Sep 10 '18 at 23:45
2

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

Yanko
  • 13,758
  • That's clever: squeezing the whole real line in between two integers. I wonder how one would construct $f$ for a dense $Z$? – Alex Reinking Sep 10 '18 at 22:45
  • @AlexReinking Looks like Noah is up to something – Yanko Sep 10 '18 at 22:46
  • How does this relate to the question? – Michael Sep 10 '18 at 22:50
  • @Michael $f$ is a function from $\mathbb{R}$ to $(0,1)$ and $(0,1)\subseteq \mathbb{R}\backslash \mathbb{Z}$. – Yanko Sep 10 '18 at 22:51
  • @Michael It handles a specific case - $Z=\mathbb{Z}$. – Noah Schweber Sep 10 '18 at 22:51
  • My understanding is that we need $f(\mathbb{R}) = \mathbb{R} \setminus \mathbb{Z}$, which is not the case here because nothing maps to $1.5$. – Michael Sep 10 '18 at 22:52
  • 3
    @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). – Noah Schweber Sep 10 '18 at 22:53
  • I interpret "codomain" as the set $f(\mathbb{R})$. I do not know what a "surjection" would mean in this case (a surjection from what to what?), and so the emphasis does me no good. – Michael Sep 10 '18 at 22:55
  • 3
    @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. – Noah Schweber Sep 10 '18 at 22:58
  • @NoahSchweber : Oh. I generally use "image" and "range" and I assumed codomain meant "image" (I never use that word). – Michael Sep 10 '18 at 23:01
  • @Michael Yeah, it can be annoying - especially since if we identify functions with their graphs (that is, $h$ "is" the set ${(x,y): x\in dom(h), h(x)=y}$) there isn't really any notion of "codomain" apart from image. Basically, there are two main ways of thinking about functions: as a set of ordered pairs, or as a triple $(A,B, R)$ where $A$ is a set (the domain), $B$ is a set (the codomain), and $R\subseteq A\times B$ is a set of ordered pairs such that for each $a\in A$ there is a unique $b\in B$ with $(a,b)\in R$ (cont'd) – Noah Schweber Sep 10 '18 at 23:03
  • (this $R$ being the graph of the function). In the former case, "codomain" isn't really a thing apart from image; in the latter case, the codomain data is built "directly into the function." Personally I've always found the "functions-as-graphs" idea more intuitive, but the latter approach actually has a lot of practical advantages. – Noah Schweber Sep 10 '18 at 23:04
  • @NoahSchweber : Thanks. The term "co-domain" sounds like it should have a more intimate relationship with the domain, such as "those points of the target set that get touched." Your link above suggests that we can have a domain/co-domain relationship without any physical touching. That is likely safer, but not as much fun! – Michael Sep 10 '18 at 23:41
1

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

Eric Wofsey
  • 330,363