Htykuut

Let $f:Bbb RrightarrowBbb R$ have the properties $forall x,yinBbb R,space x<yimplies f(x)<f(y)$ and $forall xinBbb R,space f(x)notinBbb 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 RbackslashBbb 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.

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_0color{red}{,}x_{-1}x_{-2}...x_{-m}...)_2, x_kin{0,1}, kin{-infty,...,n}$ or
$$x=sumlimits_{k=0}^nx_k2^k + sumlimits_{m=1}frac{x_{-m}}{2^{m}}$$
and build the function
$$f(x)=fleft(sumlimits_{k=0}^nx_k2^k + sumlimits_{m=1}frac{x_{-m}}{2^{color{red}{m}}}right)=
sumlimits_{k=0}^nx_k2^k + sumlimits_{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_0color{red}{,}a_{-1}a_{-2}...a_{-m}...)_2 < (b_nb_{n-1}...b_0color{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<b_k$ while $a_t=b_t, tin{k+1,...,n}$. With $f(x)$ we have
$$(a_na_{n-1}...a_0color{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_0color{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_0color{red}{,}x_{-1}x_{-2}...x_{-m})_2=(x_nx_{n-1}...x_0color{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.

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 $Csubset(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 $Vsubset(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(Ecap[0,y)).$$Then $phi$ is continuous, $phi(0)=0$ and $phi(infty)=infty$, so $$phi((0,infty))=(0,infty).$$

Suppose $yin V$. Say $yin(a,b)$, where $(a,b)$ is a connected component of $V$. Then $phi(y)=phi(b)$ and $bin 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<s<t$ 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.