Return to Answer

Sign sequences. I'll show that the computable surreal numbers are precisely the ones with hyperarithmetic sign sequences. Going from computable surreal notation to hyperarithmetic sign sequence is again an effective transfinite recursion on the rank of the notation.

For the other direction, fix a computable ordinal $\delta$ and some $\emptyset^{(\alpha)}$. I claim that there is a uniform process that takes a $\beta < \delta$ and a partial $\emptyset^{(\alpha)}$-computable function $f: \beta \to \{+, -\}$ and produces a computable surreal notation $s_f$, such that if $f$ is total then $s_f$ corresponds to the surreal number represented by $f$. Again this is effective transfinite recursion on $\beta$, but I'll present it as induction.

First, consider the constant $+$ sequence of length $\delta$, and the constant $-$ sequence of length $\delta$. These serve as bounds for all the sequences we will be considering. It is straightforward to create computable surreal notations for them, so we can obtain a notation for their difference. Call it $d$. Now to the induction.

For $\beta = 0$, this is immediate.

For $\beta > 0$, fix some partial $\emptyset^{(\alpha)}$-computable function $f: \beta \to \{+,-\}$. We can list all pairs $(\gamma, g)$, where $\gamma < \beta$ and $g$ is a partial $\emptyset^{(\alpha)}$-computable function from $\gamma$ to $\{+,-\}$. The statement that $f$ and $g$ are both total, that $g$ is an initial segment of $f$, and that $f(\gamma) = +$ is $\Pi^0_2(\emptyset^{(\alpha)})$, so it is $\Sigma^c_{\alpha+3}$. So using the method described previously, we can make a $b_g$ which is 1 if this is true and 0 if it's false. Similarly, we make $c_g$ which is for the same statement, except $f(\gamma) = -$.

Now $s_f = \{ s_g - d + b_g\cdot d : (\gamma, g) \ | \ s_g + d - c_g\cdot d : (\gamma, g)\}$.

Note that if $f$ is partial, the left set of $s_f$ consists entirely of negative numbers and its right set entirely of positive numbers, so $s_f$ is a notation for 0.

These are precisely the hyperarithmetical reals, as you conjectured. I'll be making use of your argument that the field operations are effective.

In the one direction, every computable surreal notation has a rank $\alpha$, which is a computable ordinal. By induction (actually effective transfinite recursion), the corresponding real is computable from something like $0^{(2\alpha+1)}$.

In the other direction, I first claim that for any computable ordinal $\alpha$, from a $\Sigma^c_\alpha$ sentence we can uniformly obtain a notation which corresponds to $0$ if the sentence is false and $1$ if the sentence is true. Again this is effective transfinite recursion masquerading as induction. You already did the base case in your example of $\alpha_h$.

For the inductive step, if $\phi$ is $\Sigma^c_\alpha$, then $\phi = \bigvee_n \theta_n$, where the $\theta_n$ are all $\Pi^c_{<\alpha}$. Let $b_n$ be from the inductive hypothesis applied to $\neg \theta_n$. Then $\{ 0-b_n : n \in \omega \ | \ 2 \}$ is as desired for $\phi$.

Now let $x$ be some hyperarithmetical real. WLOG, $0 < x < 1$. We wish to give a notation. If $x$ is a dyadic rational, the result is immediate. Otherwise, there is some computable $\alpha$ such that for $q$ a dyadic rational and $n \in \omega$, "$x \in (q, q+2^{-n})$" is $\Sigma^c_\alpha$. For each dyadic rational $q \in (0, 1)$ and $n \in \omega$, let $b_{q, n}$ be as from the previous claim for this sentence. Then $x = \{ q +b_{q,n} - 1 : q, n \ | \ q + 2^{-n} + 1 - b_{q,n} : q, n\}$.

Edit: Thinking further, I don't need to handle the case that $x$ is dyadic separately. Everything I wrote after that is still true in that case.

The reals which are computable surreals are precisely the hyperarithmetical reals, as you conjectured. I'll be making use of your argument that the field operations are effective (really just addition and subtraction, and the fact that we know how to create notations for $2^{-n}$).

In the one direction, every computable surreal notation has a rank $\alpha$, which is a computable ordinal. By induction (actually effective transfinite recursion), the corresponding real is computable from something like $0^{(2\alpha+1)}$.

In the other direction, I first claim that for any computable ordinal $\alpha$, from a $\Sigma^c_\alpha$ sentence we can uniformly obtain a notation which corresponds to $0$ if the sentence is false and $1$ if the sentence is true. Again this is effective transfinite recursion masquerading as induction. You already did the base case in your example of $\alpha_h$.

For the inductive step, if $\phi$ is $\Sigma^c_\alpha$, then $\phi = \bigvee_n \theta_n$, where the $\theta_n$ are all $\Pi^c_{<\alpha}$. Let $b_n$ be from the inductive hypothesis applied to $\neg \theta_n$. Then $\{ 0-b_n : n \in \omega \ | \ 2 \}$ is as desired for $\phi$.

Now let $x$ be some hyperarithmetical real. WLOG, $0 < x < 1$. We wish to give a notation. If $x$ is a dyadic rational, the result is immediate. Otherwise, there is some computable $\alpha$ such that for $q$ a dyadic rational and $n \in \omega$, "$x \in (q, q+2^{-n})$" is $\Sigma^c_\alpha$. For each dyadic rational $q \in (0, 1)$ and $n \in \omega$, let $b_{q, n}$ be as from the previous claim for this sentence. Then $x = \{ q +b_{q,n} - 1 : q, n \ | \ q + 2^{-n} + 1 - b_{q,n} : q, n\}$.

Edit: Thinking further, I don't need to handle the case that $x$ is dyadic separately. Everything I wrote after that is still true in that case.

Reciprocals. Note that if $y \neq 0$ is hyperarithmetic, then so is $1/y$. From this, it follows that if $y \neq 0$ is real and a computable surreal, then $1/y$ is also a computable surreal.

The process is mostly uniform: going from a hyperarithmetic real to a computable surreal real required a prior bounds (0 and 1 in my above writeup, but any computable bounds would have sufficed). So it will be uniformly computable if also given a rational bound away from 0: a rational $q$ with $|y| > q > 0$. Then we can use $-1/q < 1/y < 1/q$ as our bounds.

This is an example of a phenomenon known as level computability. The domain is an increasing union of sets, $\bigcup_n U_n$, where $U_n = (-\infty, -2^{-n}) \cup (2^{-n}, \infty)$. The function (reciprocal) is uniformly computable if in addition to being given a $y$ from the domain, it is also given an $n$ with $y \in U_n$.

These are precisely the hyperarithmetical reals, as you conjectured. I'll be making use of your argument that the field operations are effective.

In the one direction, every computable surreal notation has a rank $\alpha$, which is a computable ordinal. By induction (actually effective transfinite recursion), the corresponding real is computable from something like $0^{(2\alpha+1)}$.

In the other direction, I first claim that for any computable ordinal $\alpha$, from a $\Sigma^c_\alpha$ sentence we can uniformly obtain a notation which corresponds to $0$ if the sentence is false and $1$ if the sentence is true. Again this is effective transfinite recursion masquerading as induction. You already did the base case in your example of $\alpha_h$.

For the inductive step, if $\phi$ is $\Sigma^c_\alpha$, then $\phi = \bigvee_n \theta_n$, where the $\theta_n$ are all $\Pi^c_{<\alpha}$. Let $b_n$ be from the inductive hypothesis applied to $\neg \theta_n$. Then $\{ 0-b_n : n \in \omega \ | \ 2 : n \in \omega\}$ is as desired for $\phi$.

Now let $x$ be some hyperarithmetical real. WLOG, $0 < x < 1$. We wish to give a notation. If $x$ is a dyadic rational, the result is immediate. Otherwise, there is some computable $\alpha$ such that for $q$ a dyadic rational and $n \in \omega$, "$x \in (q, q+2^{-n})$" is $\Sigma^c_\alpha$. For each dyadic rational $q \in (0, 1)$ and $n \in \omega$, let $b_{q, n}$ be as from the previous claim for this sentence. Then $x = \{ q +b_{q,n} - 1 : q, n \ | \ q + 2^{-n} + 1 - b_{q,n} : q, n\}$.

Edit: Thinking further, I don't need to handle the case that $x$ is dyadic separately. Everything I wrote after that is still true in that case.

These are precisely the hyperarithmetical reals, as you conjectured. I'll be making use of your argument that the field operations are effective.

In the one direction, every computable surreal notation has a rank $\alpha$, which is a computable ordinal. By induction (actually effective transfinite recursion), the corresponding real is computable from something like $0^{(2\alpha+1)}$.

In the other direction, I first claim that for any computable ordinal $\alpha$, from a $\Sigma^c_\alpha$ sentence we can uniformly obtain a notation which corresponds to $0$ if the sentence is false and $1$ if the sentence is true. Again this is effective transfinite recursion masquerading as induction. You already did the base case in your example of $\alpha_h$.

For the inductive step, if $\phi$ is $\Sigma^c_\alpha$, then $\phi = \bigvee_n \theta_n$, where the $\theta_n$ are all $\Pi^c_{<\alpha}$. Let $b_n$ be from the inductive hypothesis applied to $\neg \theta_n$. Then $\{ 0-b_n : n \in \omega \ | \ 2 \}$ is as desired for $\phi$.

Now let $x$ be some hyperarithmetical real. WLOG, $0 < x < 1$. We wish to give a notation. If $x$ is a dyadic rational, the result is immediate. Otherwise, there is some computable $\alpha$ such that for $q$ a dyadic rational and $n \in \omega$, "$x \in (q, q+2^{-n})$" is $\Sigma^c_\alpha$. For each dyadic rational $q \in (0, 1)$ and $n \in \omega$, let $b_{q, n}$ be as from the previous claim for this sentence. Then $x = \{ q +b_{q,n} - 1 : q, n \ | \ q + 2^{-n} + 1 - b_{q,n} : q, n\}$.

Edit: Thinking further, I don't need to handle the case that $x$ is dyadic separately. Everything I wrote after that is still true in that case.