Return to Answer

Let me explicate fuller details about why the computable surreal numbers form a field. Let's start by showing that they form a ring.

Lemma. The computable surreal numbers form a ring.

To get that the computable surreals are a field, we need division. For reciprocal and division, see the formula on the Wikipedia entry. Notice that for positive $y$ the formula is applied only with positive values of $y_L$, and so we need to be able to compute the order.

Theorem. The order relation $x<y$ on computable surreal numbers is computably enumerable, given that $x$ and $y$ are computable surreal numbers. That is, this is the restriction of a c.e. relation to the set of programs that represent computable surreal numbers.

Proof. The order relation $x<y$ holds if and only if $x<y_L$ for some $y_L$ in the left set of $y$ or $x_R<y$ for some $x_R$ in the right set of $x$. This might again look computably insurmountable, since one might expect to have to mount a transfinite recursive process to check this. Nevertheless, by the Kleene recursion theorem, there is a computable enumeration procedure that solves this recursion. Given $x$ and $y$, we simply start enumerating the left and right sets and then applying the very same c.e. process to look for instances of $x<y_L$ or $x_R<y$. So $x<y$ is a c.e. relation for computable surreals. $\Box$

Because the complexity of being a computable surreal number is complicated, $\Pi^1_1$-complete, we should not expect to be able to enumerate all the numbers less than a given computable surreal number $y$, even though the relation is c.e., but rather the situation is that if $x$ is a computable surreal number and $x<y$ then we will eventually know this computably.

Now, we can show that the computable surreals form a field.

Theorem. The computable surreals form a field.

Proof. The definition of $1/y$ and $x/y$ given on Wikipedia are of the same recursive sort as for addition and multiplication, except that one must branch depending on the sign of $y$ and $y_L$. But we can get that information since $0<y_L$ is a c.e. property. So there is a computable process solving the recursive definition of reciprocal and division, and so the resulting numbers are computable surreal numbers. $\Box$

Incidently, the observation that $x<y$ is c.e. refutes an initial expectation I had that this would have complexity $\Pi^1_1$.

Let me also prove the following:

Proof. This is obvious, since $x=\{\ X\mid Y\ \}$ will be a computable surreal number strictly between, if we have computable enumerations of $X$ and $Y$. $\Box$

What remains for the real-closed field in question 1 is to show that if $x$ is a positive computable surreal number, then so is $\sqrt{x}$, and furthermore, every odd degree polynomial with computable coefficients has a computable root. We would be able to prove this using Kleene's theorem, as for addition and multiplication above, if we had recursive formulas for roots. But I am less sure about this. See also this related unanswered question of Mike Shulman.

Let me explicate fuller details about the computable surreal number operations. Let's start by showing that they form a ring.

Theorem. The computable surreal numbers form a ring.

To get that the computable surreals are a field, we would need division. For reciprocal and division, see the formula on the Wikipedia entry. Notice that for positive $y$ the formula is applied only with positive values of $y_L$, and so we would seem to need to be able to compute the order.

I had posted initially that the order $x<y$ was a c.e. relation, and then argued as a consequence that this was enough to apply the Kleene recursion theorem method to show that division $x/y$ (by nonzero) was computable.

But the c.e. argument was not correct (pointed out by Dan Turetsky in the comments). And so we don't currently know that the computable surreals form a field, and perhaps the evidence is now against this. See also this related unanswered question of Mike Shulman.

Lastly, regarding saturation, let me prove the following:

Proof. This is obvious, since $x=\{\ X\mid Y\ \}$ will be a computable surreal number strictly between, if we have computable enumerations of $X$ and $Y$. $\Box$

Theorem. The order relation $x<y$ on computable surreal numbers is computably enumerable.

Proof. The order relation $x<y$ holds if and only if $x<y_L$ for some $y_L$ in the left set of $y$ or $x_R<y$ for some $x_R$ in the right set of $x$. This might again look computably insurmountable, since one might expect to have to mount a transfinite recursive process to check this. Nevertheless, by the Kleene recursion theorem, there is a computable enumeration procedure that solves this recursion. Given $x$ and $y$, we simply start enumerating the left and right sets and then applying the very same c.e. process to look for instances of $x<y_L$ or $x_R<y$. So $x<y$ is a c.e. relation for computable surreals. $\Box$

Theorem. The order relation $x<y$ on computable surreal numbers is computably enumerable, given that $x$ and $y$ are computable surreal numbers. That is, this is the restriction of a c.e. relation to the set of programs that represent computable surreal numbers.

Proof. The order relation $x<y$ holds if and only if $x<y_L$ for some $y_L$ in the left set of $y$ or $x_R<y$ for some $x_R$ in the right set of $x$. This might again look computably insurmountable, since one might expect to have to mount a transfinite recursive process to check this. Nevertheless, by the Kleene recursion theorem, there is a computable enumeration procedure that solves this recursion. Given $x$ and $y$, we simply start enumerating the left and right sets and then applying the very same c.e. process to look for instances of $x<y_L$ or $x_R<y$. So $x<y$ is a c.e. relation for computable surreals. $\Box$

Because the complexity of being a computable surreal number is complicated, $\Pi^1_1$-complete, we should not expect to be able to enumerate all the numbers less than a given computable surreal number $y$, even though the relation is c.e., but rather the situation is that if $x$ is a computable surreal number and $x<y$ then we will eventually know this computably.

Let me also prove the following:

Theorem. The order on the computable surreal numbers is computably saturated, in the sense that every c.e. cut is filled. That is,if $X$ and $Y$ are c.e. sets of computable surreal numbers, with every element of $X$ below every element of $Y$, then there is a computable surreal number strictly between.

Proof. This is obvious, since $x=\{\ X\mid Y\ \}$ will be a computable surreal number strictly between, if we have computable enumerations of $X$ and $Y$. $\Box$

What remains for the real-closed field in question 1 is to show that if $x$ is a positive computable surreal number, then so is $\sqrt{x}$, and furthermore, every odd degree polynomial with computable coefficients has a computable root. We would be able to prove this using Kleene's theorem, as for addition and multiplication above, if we had recursive formulas for roots. But I am less sure about this. See also this related unanswered question of Mike Shulman.