I'm reading through Donald E. Knuth's book, Surreal Numbers, and I've been struggling for days now with one little step in a single proof.
Specifically, I'm trying to work through the proof that every surreal number is bounded by the elements of its left and right sets.
That is, for a surreal number $x = \{ X_L \,|\, X_R \}$, prove that $x_L \le x$ and that $x \le x_R$ for all numbers $x_L \in X_L$ and $x_R \in X_R$.
The proof starts by way of contradiction, assuming that there exists some number $x_l \in X_L$ such that $x_L \not\le x$. From this statement, the second axiom of surreal numbers gives us two possible cases; either there exists a number $x_{LL} \in X_{LL}$ (where $X_{LL}$ is $x_L$'s left set), with $x_{LL} \ge x$, or else there exists a number $x_R \in X_R$ with $x_L \ge x_R$.
This second case is an obvious contradiction of the first axiom of surreal numbers, so we go on checking the sole remaining case with $x_{LL} \ge x$. The proof then seems to try to chain this relation and another together with the transitive rule, eventually producing a contradiction. The transitive rule has been proved prior to this point in the book for the $\ge$ relation, so we just need a second relation to use it. And this is where I hit my wall.
The proof goes on to say that $x_{LL} \le x_L$, and I cannot for the life of me figure out the justification. Here's the wording for that statement in the book (Just after Ch 5 begins):
B. (continuing from above proof) …But what can we do with $x_{LL}$? I don't like double subscripts.
A. Well, $x_{LL}$ is an element of the left set of $x_L$. Since $x_L$ was created earlier than $x$, we can at least assume that $x_{LL} \le x_L$, by induction.
B. Lead on.
That seems to be the only justification for the statement; from here, Alice and Bill continue on down their productive and insightful train of reasoning without me.
I know how induction works, but I have absolutely no idea where this induction comes from or what it's doing. It all reads like a wholly obvious fact that follows perfectly naturally from what I already know, but I'm stuck. I'm convinced I'm forgetting something or that I"m on the wrong track. Either way, I need it explained to me more fully and simply than this. Thanks.
Best Answer
The surreal numbers are defined recursively: a surreal number is a pair $\{X_L\mid X_R\}$ where $X_L$ and $X_R$ are sets of surreal numbers (or more precisely, a surreal number is an equivalence class of recursively constructed objects of this form). This allows you to do induction on surreal numbers: to prove a statement about all surreal numbers, it suffices to show that if the statement is true for all elements of $X_L$ and $X_R$, then it is also true for the surreal numbers $\{X_L\mid X_R\}$, since all surreal numbers are built by iterating this construction. So in this case, the statement that $x_L\leq x$ and $x\leq x_R$ for all $x_L\in X_L$ and $x_R\in X_R$ is being proved by induction in this way, so the induction hypothesis tells you the result is already known for all elements of $X_L$ and $X_R$. In particular, the result is already known for the element $x_L$, so $x_{LL}<x_L$.
(To make sense of this recursive definition of surreal numbers completely rigorously takes some work, and I don't know how exactly Knuth does it. One way to make it precise is to recursively define the set of surreal numbers of birthday $\alpha$ for each ordinal $\alpha$ to be the pairs $\{X_L\mid X_R\}$ where $X_L$ and $X_R$ are both sets of surreal numbers of birthday $<\alpha$. Then the proof above is by induction on the birthday of the surreal number $x$, so all elements of $X_L$ and $X_R$ have lesser birthday and so are covered by the induction hypothesis.)