18
$\begingroup$

Let $f:\Bbb R\rightarrow\Bbb R$ have the properties $\forall x,y\in\Bbb R,\space x<y\implies f(x)<f(y)$ 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.

$\endgroup$
  • $\begingroup$ @астонвіллаолофмэллбэрг 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. $\endgroup$ – stanley dodds Nov 28 '18 at 17:49
  • $\begingroup$ @stanleydodds I see. Thank you for the point out. $\endgroup$ – астон вілла олоф мэллбэрг Nov 28 '18 at 18:01
  • $\begingroup$ 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. $\endgroup$ – Jason DeVito Nov 28 '18 at 18:26
  • $\begingroup$ 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. $\endgroup$ – stanley dodds Nov 28 '18 at 18:32
6
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – stanley dodds Nov 28 '18 at 18:58
  • $\begingroup$ @stanleydodds oh yes, you are right! I ignored (or forgot) that part :( $\endgroup$ – rtybase Nov 28 '18 at 19:14
  • $\begingroup$ 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.... $\endgroup$ – David C. Ullrich Dec 6 '18 at 13:20
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.