Here are several interesting results from computable analysis:

Theorem 1. If $f$ is a computable function from $\mathbb{R}$ to $\mathbb{R}$ and $\alpha$ is an isolated root of $f$, then $\alpha$ is computable.

Corollary 2. If $p(x)$ is a polynomial over $\mathbb{R}$ with computable coefficients, then every root of $p(x)$ is computable.

Theorem 3. There is a effective closed subset of $\mathbb{R}$ which is nonempty (in fact, uncountable) but which has no computable point.

Theorem 4. There is a computable function from $\mathbb{R}$ to $\mathbb{R}$ which has uncountably many roots but no computable roots.

These are all well known to computable analysts and I take no credit for any ideas in this post. I happened to think about these theorems based on a question at math.stackexchange.com, and I realized the literature I usually look at doesn’t have proofs of them, so I am going to prove them here. The proofs are interesting because they will use a correspondence between root sets of continuous functions on $[0,1]$ and $\Pi^0_1$ classes in $2^{\omega}$. The latter are a standard tool in computability theory, and the correspondence reduces the above results to standard exercises from a computability course.

One interesting aspect is that these results have no direct formalization in Reverse Mathematics. When we formalize things in that setting, the adjective “computable” disappears, and so the first two results simply say that every root is a number. The third result becomes contradictory, claiming there is a nonempty set that has no points, and the fourth has the same issue. Of course we could try to directly formalize “is computable” using Kleene’s $T$ predicate, but that would be a sort of meta-formalization rather than a direct formalization of the results. This is why results like these can’t be directly found in Simpson (1999).

I want to sketch a proof of the four results using the following two theorems, which follow immediately from results in section II.7 of Simpson (1999). I have seen these cited to Nerode and Huang (1985); see the “history” section below.

Theorem 5. If $f$ is a computable function from $\mathbb{R}$ to $\mathbb{R}$ then there is an effective open set $U$ such that for all $x$, $x \in U$ if and only if $f(x) \not = 0$.

Theorem 6. If $U$ is an effective open subset of $\mathbb{R}$ then there is a continuous computable function $f \colon \mathbb{R} \to \mathbb{R}$ such that $U = \{ x : f(x) \not = 0\}$.

These two results, together with some understanding of effective open and closed sets, will be enough. First, here are the definitions:

Definition 7. A quickly converging Cauchy sequence in $\mathbb{R}$ is a sequence $(a_n)$ such that for all $n$ and $m > n$, $d(a_n, a_m) < 2^{-n}$.

Definition 8. A function $f\colon \mathbb{R} \to \mathbb{R}$ is computable if there is a Turing functional which, given any quickly converging Cauchy sequence $(a_n)$ of rationals, produces as output a quickly converging Cauchy sequence $(b_n)$ of rationals such that $f(\lim a_n) = \lim b_n$.

Definition 9. A set $U \subseteq \mathbb{R}$ is an effective open set if it is empty or is the union of an r.e. sequence of open rational intervals, and is an effective closed set if its complement is an effective open set.

Definition 10. A subset $U \subseteq 2^{\omega}$ is $\Sigma^0_1$ if it is empty or is the union of an r.e. sequence of cylinder sets, that is, sets of the form $N_\sigma = \{ g \in 2^{\omega} : \sigma \sqsubseteq g\}$. A subset $C \subseteq 2^{\omega}$ is $\Pi^0_1$ if its complement is $\Sigma^0_1$.

The $\Sigma^0_1$ and $\Pi^0_1$ subsets of $2^{\omega}$ play the same role as the effective open and effective closed subsets of $\mathbb{R}$, respectively. We first note that the functional $I$ from $2^{\omega}$ to $[0,1]$ such that
$$
I(g) = \sum_{i \in \omega} g(i) 2^{-(i+1)}.
$$
is surjective and computable in the sense that from any $g \in 2^{\omega}$ we can uniformly compute a quickly converging Cauchy sequence for $I(g)$. Moreover, $I$ is continuous in a nice way:

Theorem 11.

• If $U$ is an effective open subset of $[0,1]$ then $I^{-1}(U)$ is a $\Sigma^0_1$ subset of $2^{\omega}$.
• If $C$ is an effective closed subset of $[0,1]$ then $I^{-1}(C)$ is a $\Pi^0_1$ subset of $2^{\omega}$. Moreover, if $\alpha$ is an isolated point in $C$ and is not a dyadic rational then
  $I^{-1}(\alpha)$ is an isolated point in $I^{-1}(C)$.

This result gives Theorem 1 with little additional work.

Proof of Theorem 1. As a special case, given a computable function $f \colon [0,1] \to \mathbb{R}$, we first form the effective closed set $C$ of roots of $f$. We can assume $f$ has no dyadic rational roots because these are all computable. Now if $\alpha \in (0,1)$ is an isolated root of $f$ then $I^{-1}(\alpha)$ is isolated in $I^{-1}(C)$. But an isolated point in a $\Pi^0_1$ subclass of $2^{\omega}$ is computable, so $I^{-1}(\alpha)$ is computable, hence $\alpha$ is computable.

For the general case where $f\colon \mathbb{R} \to \mathbb{R}$, every isolated root $\alpha$ of $f$ is isolated in some rational interval $(q, 1+q)$; by translating $q$ units left and applying the special case, we see that $\alpha – q$ is computable, so $\alpha$ is computable as well. ∎

Corollary 2 follows immediately from Theorem 1 because every polynomial with computable coefficients gives a computable function, and every root of a polynomial is isolated.

Proof of Theorem 3. We ignore $I$ and use a more direct technique. The middle-thirds Cantor set $M \subseteq [0,1]$ is an effectively closed subset of $[0,1]$ which is computably homeomorphic to $2^{\omega}$. It is well known that there is a nonempty $\Pi^0_1$ class $P$ which has no computable points; this in turn gives an effective closed subset of $M$ under the homeomorphism. This subset of $M$ is nonempty because $P$ is, and has no computable points because each point in $M$ computes the corresponding point in $P$. The uncountability of the set follows from the Cantor-Bendixson analysis: if $P$ was countable it would have an isolated (and thus computable) point. ∎

Theorem 4 follows directly from Theorem 3 and Theorem 6.

History

I believe Corollary 2 and Theorem 4 are due to Specker, and Theorems 1 and 3 are due to Nerode and Huang (1985), although I am going by secondary sources to make these claims. The MathSciNet review of Specker (1959) claims Specker also used the existence of a nonempty $\Pi^0_1$ set with no computable points to prove Theorem 4. I cannot read the language that either of these papers was written in.

The correspondence between effective open (closed) subsets of $[0,1]$ and $\Sigma^0_1$ ($\Pi^0_1$) classes in $2^{\omega}$ was also apparently noticed by Nerode and Huang, although I have no idea whether their proof is similar to mine. It seems like this correspondence could have been known much earlier.

References

• Nerode, Anil; Huang, Wen Qi. An application of pure recursion theory to recursive analysis. (Chinese) Acta Math. Sinica 28 (1985), no. 5, 625–636.
• Simpson, Stephen. Subsystems of second-order arithmetic. Springer, 1999.
• Specker, Ernst. Der Satz vom Maximum in der rekursiven Analysis. (German) In A. Heyting, editor, Constructivity in Mathematics, 254–265. North-Holland, 1959.