Skip to main content
2 of 4
added 1027 characters in body
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

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.

Proof. We have to show that the computable surreal numbers are closed under addition, subtraction, and multiplication.

Surreal addition $x+y$ is defined recursively as follows: $$x+y=\left\{\ x+y_L\quad x_L+y\bigm\vert x+y_R\quad x_R+y\ \right\}.$$ We are using here the usual convention that $x_L$ and $x_R$ range over the left and right sets of $x$, respectively, and similarly for $y$.

It might seem initially unsurmountable to make this computable, since in order to produce the program for $x+y$, we might think that we have to undertake a transfinite recursion in order first to compute $x+y_L$ and so forth.

Nevertheless, I claim that we don't need to mount that recursion. In fact, there is a computable procedure to produce a program realizing $x+y$ as a computable surreal number, given programs for $x$ and $y$. The reason is that by the Kleene recursion theorem, there is a program solving the recursion expressed by the definition of $x+y$. That is, there is a program that takes programs for $x$ and $y$, starts enumerating the left and right sets, and then applies that same addition program to compute the values $x+y_L$, $x_L+y$ and so forth, as the values of $x_L$, $y_L$, $x_R$, $y_R$ are enumerated by $x$ and $y$. So we can computably produce the programs that will exhibit $x+y$ as a computable surreal number.

The same idea works with negation and subtraction $$\newcommand\unaryminus{-}\unaryminus x=\{\ \unaryminus X_R\mid\unaryminus X_L\ \}.$$ By the notation $\unaryminus X_R$ here we mean the set of all $\unaryminus x_R$ for $x_R\in X_R$, and similarly with $\unaryminus X_L$. Using this, we define subtraction simply as adding the negation: $$y-x=y+(\unaryminus x).$$ By applying the Kleene recursion theorem, there is a uniform computable procedure to produce $-x$ and $x-y$ from programs for $x$ and $y$.

Similarly with multiplication, which is defined by $$x\cdot y =\{\ X_{L}\mid X_{R}\ \}\cdot \{\ Y_{L}\mid Y_{R}\ \}=$$ $$=\{\ x_Ly+xy_{L}-x_{L}y_{L}\quad x_{R}y+xy_{R}-x_{R}y_{R}\ \mid\ x_{L}y+xy_{R}-x_{L} y_{R}\quad xy_{L}+x_{R}y-x_{R}y_{L}\ \}$$ By the Kleene recursion theorem, there is a multiplication program that obeys this recursive definition. As numbers get enumerated into the left and right side of $x$ and $y$, we apply that program suitably so as to carry out this definition of $xy$. $\Box$

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.

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$

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:

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.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k