Skip to main content
4 of 4
Removed wrong argument about x<y
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

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.

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 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:

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$

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