Set of all rational numbers less than given computable real number is decidable

Question

Prove that set of rational numbers less than given computable real number is decidable

This problem was in my exam yesterday, but I was not able to solve it. However I still want to give it another try.

Same problem can be stated in this way:
Construct an algorithm, which answers the question: Is our given rational number less or greater than their(fixed) computable number?

Here's my poor try so far.

Since it's analysis related problem, I used the $\epsilon - \delta$ definition of computable number, which is:

$\exists f$ computable function, such that $\forall \epsilon > 0, \epsilon \in \mathbb{Q}, f$ gives us $\delta > 0, \delta \in \mathbb{Q}$ such that$|a - \delta| \leq \epsilon$ holds for given computable number $a$

Let $p \in \mathbb{Q}$ be our input, and let $f$ compute for us 2 rationals $q_1$ and $q_2$. It is well known that $|q_1 - q_2| < 2\epsilon$

Now let's choose $\epsilon = \frac{1}{2^{i}}, i = 0,1,2,...$
For each $i$-th step I compute $f$ twice and get $q_{i_{1}},q_{i_{2}}$. I think that our given rational $p$ should hold some condition with both $q_{i_1},q_{i_2}$ which will help me to finish the algorithm, but I couldn't figure this out. I believe there are finitely many checks for each step which will let me know that for example $p < a$ just like in picture below.

What do you think about this problem? Maybe there's more straightforward way to prove this. Thank you.

Answer 1

I would approach this problem as follows. Let $a$ be the computable real, and $A = \{x\in\mathbb{Q}\ |\ x<a\}$.

If $a \in \mathbb{Q}$, then $A$ is decidable since $x<a$ is a comparison between rationals, which is decidable.

Otherwise, we can assume $a$ is irrational. Our algorithm performs the following. First, we take the candidate $x\in\mathbb{Q}$ as input. We then query $f$ (the function which approximates $a$ as requested) repeatedly with $q=2^{-n}$ for every $n>0$. Eventually, for some $n$ we will obtain one of

$$ f(2^{-n}) + 2^{-n} < x \qquad \lor\qquad x < f(2^{-n}) - 2^{-n} $$ Indeed, this will happen as soon as $2^{-n} < |x-a| / 2$, which is a possibility because we know $x \neq a$.

In the first case, we return $x > a$ ($x \notin A$), in the second we return $x<a$ ($x \in A$).

The correctness comes from $$ a \leq f(2^{-n}) + 2^{-n} \qquad \land\qquad f(2^{-n}) - 2^{-n} \leq a $$ being true for all $n$.

---

Note that this solution is not uniform in $a$. That is, we only prove that there is an algorithm for any computable $a$, taking a candidate rational $x$ as input. We do not show that there is a single algorithm that, given both $a$ and $x$ as input is able to decide $<$ (indeed, that would be undecidable).