# strictly increasing function from reals to reals which is never an algebraic number

Let $$f:\Bbb R\rightarrow\Bbb R$$ have the properties $$\forall x,y\in\Bbb R,\space x and $$\forall x\in\Bbb R,\space f(x)\notin\Bbb A$$ where $$\Bbb A$$ is the set of algebraic numbers; i.e. $$f$$ is strictly increasing, but nowhere is $$f(x)$$ algebraic.

Does such a function exist? And if so, can one be explicitly constructed?

My thoughts are that such a function should exist, since the algebraic numbers are "small" compared to the reals; we can show that a bijection (or more weakly an injection) must exist from $$\Bbb R$$ to $$\Bbb R\backslash\Bbb A$$ because they have the same cardinality, but I'm not entirely sure how to show rigorously that a strictly increasing function exists, even if in principle this is just a special type of injection.

Replacing $$\Bbb A$$ by a set such as $$\Bbb Z$$ in the definition makes the question trivial, and these sets have the same cardinality, so clearly the difficulty arises because $$\Bbb A$$ is dense in the reals - any hints or answers would be appreciated.

• @астонвіллаолофмэллбэрг Gelfond-Schneider only holds if $r$ and $f(x)$ are algebraic, in $r^{f(x)}$. But $f(x)$ cannot be algebraic for all $x$ as otherwise $f$ would be an injection from the reals to a set with smaller cardinality, which is not possible. – stanley dodds Nov 28 '18 at 17:49
• @stanleydodds I see. Thank you for the point out. – астон вілла олоф мэллбэрг Nov 28 '18 at 18:01
• Do you know the answer to the easier question of finding an increasing $f$ which is never rational? Also, something which might be relevant is the fact that an increasing function is continuous off of a countable set. – Jason DeVito Nov 28 '18 at 18:26
• No I do not know the answer to that simpler question - from all I've been able to do so far, exchanging $\Bbb A$ with any other set that is dense in the reals but countable (e.g. $\Bbb Q$) makes another tricky question. – stanley dodds Nov 28 '18 at 18:32

A possible (I will explain why later) example could be ...

Let's take an $$x \in \mathbb{R}$$ and have its binary (for simplicity) representation $$x=(x_nx_{n-1}...x_0\color{red}{,}x_{-1}x_{-2}...x_{-m}...)_2, x_k\in\{0,1\}, k\in\{-\infty,...,n\}$$ or $$x=\sum\limits_{k=0}^nx_k2^k + \sum\limits_{m=1}\frac{x_{-m}}{2^{m}}$$ and build the function $$f(x)=f\left(\sum\limits_{k=0}^nx_k2^k + \sum\limits_{m=1}\frac{x_{-m}}{2^{\color{red}{m}}}\right)= \sum\limits_{k=0}^nx_k2^k + \sum\limits_{m=1}\frac{x_{-m}}{2^{\color{red}{m!}}}$$ i.e. $$f(x)$$ becomes

• a Liouville number, if $$x$$ is irrational
• a Liouville number, if $$x$$ is rational with periodic (never ending) fractional part
• a rational, if $$x$$ is rational with finite fractional part
• $$f(x)=x$$, if $$x$$ is integer

All the Liouville numbers are transcendentals, so this function never returns an algebraic number.

It's not too difficult to show it's strictly increasing, if $$a < b$$ or $$(a_na_{n-1}...a_0\color{red}{,}a_{-1}a_{-2}...a_{-m}...)_2 < (b_nb_{n-1}...b_0\color{red}{,}b_{-1}b_{-2}...b_{-m}...)_2$$ ($$a_n,a_{n-1}, ...$$ can be $$0$$, just to have a common upper index $$n$$ for both $$a$$ and $$b$$) means that $$\exists k \in\{-\infty, ...,n\}$$ such that $$a_k while $$a_t=b_t, t\in\{k+1,...,n\}$$. With $$f(x)$$ we have $$(a_na_{n-1}...a_0\color{red}{,}a_{-1}a_{-2}\color{blue}{000}a_{-3}\color{blue}{00000000000000000}a_{-4}\color{blue}{00...}a_{-m}...)_2 < (b_nb_{n-1}...b_0\color{red}{,}b_{-1}b_{-2}\color{blue}{000}b_{-3}\color{blue}{00000000000000000}b_{-4}\color{blue}{00...}b_{-m}...)_2$$

Note 1: I restricted the function to $$\mathbb{R^+}\rightarrow \mathbb{R^+}$$, but it can be extended, taking into account the sign of $$x$$.

Note 2 As per the comments below, integers and rationals are algebraic numbers. To overcome this part, we can apply these tricks $$(x_nx_{n-1}...x_0)_2=((x_nx_{n-1}...x_0-1)\color{red}{,}11111...)_2$$ and $$(x_nx_{n-1}...x_0\color{red}{,}x_{-1}x_{-2}...x_{-m})_2=(x_nx_{n-1}...x_0\color{red}{,}x_{-1}x_{-2}...(x_{-m}-1)11111...)_2$$ leading to Liouville numbers in all the cases.

Now why possible, because not all reals are computable.

• This is a good answer, but I should mention that rationals and integers are also algebraic numbers, so for integer or rational with finite fractional part $x$ we still have an algebraic $f(x)$. This is not a problem though, since both of these $x$ can instead be written with infinite trailing 1's in base 2 form, and defining $f$ to use this form in these cases again gives a Liouville number. I'm not sure if you didn't notice, or if you knew this already. – stanley dodds Nov 28 '18 at 18:58
• @stanleydodds oh yes, you are right! I ignored (or forgot) that part :( – rtybase Nov 28 '18 at 19:14
• It's amusing that Liouville numbers come up here, because this solution versus mine seems somewhat like Liouville's proof of the existence of transcendental numbers versus Cantor's.... – David C. Ullrich Dec 6 '18 at 13:20

It's actually very simple; the same result holds with any countable set in place of the algebraic numbers. Since $$\Bbb R$$ is order-isomorphic to $$(0,\infty)$$ it's enough to prove this:

If $$C\subset(0,\infty)$$ is countable there exists a strictly increasing function $$f:(0,\infty)\to(0,\infty)\setminus C$$.

Since a countable set is contained in an open set of finite measure this follows from the stronger result (where $$m$$ is Lebesgue measure):

Suppose $$V\subset(0,\infty)$$ is open, let $$E=(0,\infty)\setminus V$$ and assume $$m(E)=\infty$$. There exists a strictly increasing function $$f:(0,\infty)\to E$$.

Proof: Define $$\phi:[0,\infty)\to[0,\infty)$$ by $$\phi(y)=m(E\cap[0,y)).$$Then $$\phi$$ is continuous, $$\phi(0)=0$$ and $$\phi(\infty)=\infty$$, so $$\phi((0,\infty))=(0,\infty).$$

Suppose $$y\in V$$. Say $$y\in(a,b)$$, where $$(a,b)$$ is a connected component of $$V$$. Then $$\phi(y)=\phi(b)$$ and $$b\in E$$. Hence $$\phi(E)=\phi((0,\infty))=(0,\infty).$$So for every $$t>0$$ there exists $$f(t)\in E$$ with $$\phi(f(t))=t.$$If $$0 it follows that $$f(t)-f(s)\ge m([f(s),f(t))\cap E)=\phi(f(t))-\phi(f(s))= t-s>0;$$hence $$f$$ is strictly increasing.