Prove that a surreal number is born in a finite stage if and only if it is of the form $\frac m{2^n}$.

inductionsurreal-numbers

We define surreal numbers here. My attempt is to first prove this lemma:

Lemma 1. Suppose in the $n$th stage, we have already constructed 2 surreals $a<b$, with no other surreals constructed between them. Then $$2\cdot\{a|b\}=a+b.$$

From this I can quite easily deduce the desired result. So now the difficulty lies in proving the lemma.

I have tried to expand the multiplication, and using the definition that $x=y\Leftrightarrow x\le y$ and $x\ge y$. Doing this I get something that, apparently, needs to be further simplified. However, using the definitions of inequalities breaks it up into more and more pieces, and I don't see anywhere that I can use induction. Also, I can't utilize the condition that $a$ and $b$ are 'adjacent'.

Is there a way to prove this lemma? Or am I going in the wrong direction? Any help is appreciated!

Best Answer

$\newcommand{surr}[2]{\left\{ #1 \mathbin{\big\vert} #2 \right\}}$ Conway's proof of the question in your title in On Numbers and Games is by a different and rather cleverly indirect argument. First, he proves that the surreal numbers form an ordered field. He also proves that any number $\surr{a}{b}$ is equal to the simplest number which is greater than $a$ and less than $b$. (where "simplest" means "constructed in the earliest stage"). Then, he proves the following lemma.

Lemma (Theorem 12 of ONAG): Suppose $x=\frac{\ell}{2^m}$ for some integer $\ell$. Then $x=\surr{x-\frac{1}{2^m}}{x+\frac{1}{2^m}}$.

Proof: We use induction on $m$. For $m=0$ this is easy, since $x$ is an integer and so if $x\geq 0$ then $x$ is the simplest number greater than $x-1$ and if $x<0$ then $x$ is the simplest number less than $x+1$.

Now suppose $m>0$ and we already know the result for $m-1$. Let $z=\surr{x-\frac{1}{2^m}}{x+\frac{1}{2^m}}$. Using the definition of addition, we find $$2z=z+z=\surr{z+x-\frac{1}{2^m}}{z+x+\frac{1}{2^m}}.$$ By the induction hypothesis, we know that $2x=\surr{2x-\frac{1}{2^{m-1}}}{2x+\frac{1}{2^{m-1}}}$, since $2x=\frac{2\ell}{2^{m-1}}$. Thus $2x$ is the simplest number between $2x-\frac{1}{2^{m-1}}$ and $2x+\frac{1}{2^{m-1}}$, and so it is also the simplest number between $z+x-\frac{1}{2^m}$ and $z+x+\frac{1}{2^m}$ since $$2x-\frac{1}{2^{m-1}}< z+x-\frac{1}{2^m} < 2x < z+x+\frac{1}{2^m}<2x+\frac{1}{2^{m-1}}$$ (these inequalities follow from $x-\frac{1}{2^m}<z<x+\frac{1}{2^m}$). Looking back at our expression for $2z$ above, this shows that $2x=2z$, and hence $x=z$ as desired.

Given this lemma, it is then straightforward to completely describe what the $n$th stage of the surreal numbers looks like by induction on $n$. Specifically, if $n>0$ then after the $n$th stage the surreal numbers constructed so far are exactly those of the form $\pm\left(i+\frac{j}{2^k}\right)$ for $i,j,k\in\mathbb{N}$ such that $j\leq 2^k$ and $i+k<n$. For the induction step, then, the $(n+1)$st stage will have the same form because every pair of consecutive numbers $a<b$ constructed after the $n$th stage can be written in the form $a=x-\frac{1}{2^m}$ and $b=x+\frac{1}{2^m}$ for some dyadic rational $x$ with denominator $2^m$, and so the new number $\surr{a}{b}$ will be $x=\frac{a+b}{2}$ by the lemma.

Let me finish with some observations on your proposed proof strategy in comparison with Conway's. As far as I know, there isn't any nice way to prove your lemma in isolation. The problem is that the assumption that there are no numbers between $a$ and $b$ constructed so far is not easy to use. You can only really make good use of it if you already know exactly what all the surreal numbers constructed up to the $n$th stage look like. So, your lemma needs to not be a separate lemma proved first, but instead embedded in an inductive proof of a description of the $n$th stage so that you can use the induction hypothesis to get a handle on what $a$ and $b$ can be. That's exactly what the argument above does, to reduce your lemma to Conway's lemma.

Related Question