A Blueprint for Short Surreal Numbers in Lean

4.2 A simultaneous well-founded proof

Definition 4.5 Dershowitz–Manna goal order
✓
#

Three kinds of induction goal are used:

\[ A(x,y),\qquad B(x_1,x_2,y),\qquad C(x_1,x_2,y). \]

Their measures are the multisets

\[ \mu _A(x,y)=\{ \operatorname {bd}(x),\operatorname {bd}(y)\} ,\qquad \mu _B(x_1,x_2,y)=\mu _C(x_1,x_2,y) =\{ \operatorname {bd}(x_1),\operatorname {bd}(x_2),\operatorname {bd}(y)\} . \]

The goal order is the pullback of the Dershowitz–Manna multiset extension \({\lt}_{\rm DM}\) of \({\lt}\) on \(\mathbb N\) along these measures. For example, if \(a'{\lt}a\) and \(a_1,a_2{\lt}a\), then

\[ \{ a',b\} {\lt}_{\rm DM}\{ a,b\} ,\qquad \{ a',b,c\} {\lt}_{\rm DM}\{ a,b,c\} , \]
\[ \{ a_1,a_2,b\} {\lt}_{\rm DM}\{ a,b\} ,\qquad \{ a,b\} {\lt}_{\rm DM}\{ a,b,c\} . \]

The first two comparisons replace one birthday by a smaller birthday, the third replaces one birthday by two smaller birthdays, and the fourth deletes one birthday. Lemma 2.3, transitivity, and permutation invariance of multisets reduce the recursive dependencies in the \(A\)-, \(B\)-, and \(C\)-cases to these examples. Since \({\lt}\) on \(\mathbb N\) is well founded, so is the resulting goal order.

Definition 4.6 Cross inequalities
✓

For \(x_1\prec x_2\), the two forms needed to compare product options are

\[ \begin{aligned} C_L(x_1,x_2;y,y^L)& :\quad x_1y+x_2y^L\prec x_1y^L+x_2y,\\ C_R(x_1,x_2;y,y^R)& :\quad x_1y^R+x_2y\prec x_1y+x_2y^R. \end{aligned} \]

For arbitrary games \(x_1,x_2,y_1,y_2\), define the weak and strict four-product relations by

\[ \begin{aligned} \operatorname {Cross}_{\preceq }(x_1,x_2;y_1,y_2)& :\quad x_1y_2+x_2y_1\preceq x_1y_1+x_2y_2,\\ \operatorname {Cross}_{\prec }(x_1,x_2;y_1,y_2)& :\quad x_1y_2+x_2y_1\prec x_1y_1+x_2y_2. \end{aligned} \]

Thus \(C_L(x_1,x_2;y,y^L)\) is \(\operatorname {Cross}_{\prec }(x_1,x_2;y^L,y)\), while \(C_R(x_1,x_2;y,y^R)\) is \(\operatorname {Cross}_{\prec }(x_1,x_2;y,y^R)\).

Let \(\mathrel {\bowtie }\) denote either \(\preceq \) or \(\prec \). If \(\operatorname {Cross}_{\bowtie }(a,c;d,e)\) holds, then

\[ \begin{array}{ll} \text{(a)}& \operatorname {M}(a,e;b,d)\mathrel {\bowtie }\operatorname {M}(c,e;b,d),\\ \text{(b)}& \operatorname {M}(c,d;b,e)\mathrel {\bowtie }\operatorname {M}(a,d;b,e),\\ \text{(c)}& \operatorname {M}(a,b;c,d)\mathrel {\bowtie }\operatorname {M}(a,b;c,e),\\ \text{(d)}& \operatorname {M}(c,b;a,e)\mathrel {\bowtie }\operatorname {M}(c,b;a,d). \end{array} \]

For the strict relation, the transpose, composition, and two endpoint-replacement rules are

\[ \begin{aligned} \text{(e)}\quad & \operatorname {Cross}_{\prec }(a,c;d,e) \Longrightarrow \operatorname {Cross}_{\prec }(d,e;a,c),\\ \text{(f)}\quad & \operatorname {Cross}_{\prec }(a,b;d,e)\ \wedge \operatorname {Cross}_{\prec }(b,c;d,e) \Longrightarrow \operatorname {Cross}_{\prec }(a,c;d,e),\\ \text{(g)}\quad & \operatorname {Cross}_{\prec }(a,b;d,e)\ \wedge bd\sim cd\ \wedge \ be\sim ce \Longrightarrow \operatorname {Cross}_{\prec }(a,c;d,e),\\ \text{(h)}\quad & ad\sim bd\ \wedge \ ae\sim be\ \wedge \operatorname {Cross}_{\prec }(b,c;d,e) \Longrightarrow \operatorname {Cross}_{\prec }(a,c;d,e). \end{aligned} \]
Proof ▶

Work in the quotient \(\mathcal G/{\sim }\) of Definition 3.8, equipped with the ordered additive group structure of Theorem 3.9. The hypothesis is

\[ [ae]+[cd]\mathrel {\bowtie }[ad]+[ce]. \]

Adding the same class to both sides and rearranging the additive group gives, respectively,

\[ \begin{aligned} {}[ae]+[bd]-[ad]& \mathrel {\bowtie }[ce]+[bd]-[cd],\\ {}[cd]+[be]-[ce]& \mathrel {\bowtie }[ad]+[be]-[ae],\\ {}[ab]+[cd]-[ad]& \mathrel {\bowtie }[ab]+[ce]-[ae],\\ {}[cb]+[ae]-[ce]& \mathrel {\bowtie }[cb]+[ad]-[cd]. \end{aligned} \]

For example, Definition 4.1 gives

\[ \operatorname {M}(a,e;b,d)=ae+bd-ad, \qquad \operatorname {M}(c,e;b,d)=ce+bd-cd. \]

Hence the first rearranged inequality is exactly

\[ [\operatorname {M}(a,e;b,d)]\mathrel {\bowtie }[\operatorname {M}(c,e;b,d)], \]

which is the class-level form of rule (a). The other three lines give rules (b)–(d) in the same way. The argument works for both weak and strict order because translation preserves both in the ordered additive group.

We prove rule (g),

\[ \operatorname {Cross}_{\prec }(a,b;d,e) \ \wedge \ bd\sim cd \ \wedge \ be\sim ce \quad \Longrightarrow \quad \operatorname {Cross}_{\prec }(a,c;d,e); \]

the other strict rules (e), (f), and (h) are analogous. The first hypothesis means

\[ ae+bd\prec ad+be. \]

By Theorem 3.9, this is the strict quotient inequality

\[ [ae]+[bd]{\lt}[ad]+[be]. \]

The two equivalence hypotheses give the class equalities

\[ [bd]=[cd], \qquad [be]=[ce]. \]

Substituting them into the strict inequality gives

\[ [ae]+[cd]{\lt}[ad]+[ce]. \]

Reflecting strict order from the quotient yields

\[ ae+cd\prec ad+ce, \]

which is exactly \(\operatorname {Cross}_{\prec }(a,c;d,e)\).

Lemma 4.8 Terminal product-option bounds
✓

The following statements hold:

\[ \begin{array}{ll} (LL)& ay^L\sim by^L,\ C_L(a^L,b;y,y^L) \Longrightarrow \operatorname {M}(a^L,y;a,y^L)\prec by,\\[1mm] (RR)& ay^R\sim by^R,\ C_R(b,a^R;y,y^R) \Longrightarrow \operatorname {M}(a^R,y;a,y^R)\prec by,\\[1mm] (LR)& by^R\sim ay^R,\ C_R(b^L,a;y,y^R) \Longrightarrow ay\prec \operatorname {M}(b^L,y;b,y^R),\\[1mm] (RL)& by^L\sim ay^L,\ C_L(a,b^R;y,y^L) \Longrightarrow ay\prec \operatorname {M}(b^R,y;b,y^L). \end{array} \]
Proof ▶

We prove only the \(LL\) statement. Its hypotheses are

\[ ay^L\sim by^L \quad \text{and}\quad C_L(a^L,b;y,y^L): a^Ly+by^L\prec a^Ly^L+by. \]

In the quotient \(\mathcal G/{\sim }\), add \(-[a^Ly^L]\) to both sides and use \([by^L]=[ay^L]\). This gives

\[ [a^Ly]+[ay^L]-[a^Ly^L]{\lt}[by], \]

whose left side is \([\operatorname {M}(a^L,y;a,y^L)]\) by Definition 4.1. The quotient order in Theorem 3.9 therefore gives

\[ \operatorname {M}(a^L,y;a,y^L)\prec by. \]

The \(RR\), \(LR\), and \(RL\) statements follow from the same quotient rearrangement with their displayed equivalence and cross-inequality hypotheses.

Theorem 4.9 Simultaneous Conway theorem
✓
#

The following assertions hold simultaneously for all games satisfying the displayed hypotheses:

  1. \(A(x,y)\): if \(x,y\) are surreal, then \(xy\) is surreal;

  2. \(B(x_1,x_2,y)\): if \(x_1\sim x_2\) and all three games are surreal, then \(x_1y\sim x_2y\);

  3. \(C(x_1,x_2,y)\): if \(x_1\prec x_2\) and all three games are surreal, then \(C_L(x_1,x_2;y,y^L)\) holds for every \(y^L\), and \(C_R(x_1,x_2;y,y^R)\) holds for every \(y^R\).

Proof ▶

Apply well-founded induction with the goal order of Definition 4.5. The induction hypothesis is available for every \(A\)-, \(B\)-, or \(C\)-assertion whose multiset measure is smaller. The comparisons in that definition justify replacing a coordinate by an option, replacing one birthday by two smaller birthdays, and deleting an unused coordinate.

Consider \(A(x,y)\). By Definition 2.9, it is enough to prove that every option of \(xy\) is surreal and that every left option is strictly below every right option. Definition 4.1 gives the four option families. If \(x'\) and \(y'\) are options of \(x\) and \(y\), respectively, the corresponding option has the form

\[ \operatorname {M}(x',y;x,y')=x'y+xy'-x'y'. \]

The smaller assertions \(A(x',y)\), \(A(x,y')\), and \(A(x',y')\) prove that its three product terms are surreal. Closure under addition and negation, Theorem 3.7, then proves the whole expression surreal.

For separation put \(P(u,v)=\operatorname {M}(u,y;x,v)\). By Definition 4.1, a left option of \(xy\) is

\[ P(x^L,y^L)\quad (LL),\qquad P(x^R,y^R)\quad (RR), \]

and a right option is

\[ P(x^L,y^R)\quad (LR),\qquad P(x^R,y^L)\quad (RL). \]

Consider first \(P(x^L_1,y^L)\) and \(P(x^L_2,y^R)\). Since the first is a left option and the second is a right option, we need to prove

\[ P(x^L_1,y^L)\prec P(x^L_2,y^R). \]

Theorem 2.11 compares \(x^L_1\) and \(x^L_2\). Also, Theorem 2.10 and strict transitivity from Theorem 2.7 give \(y^L\prec y\prec y^R\), hence \(y^L\prec y^R\). The three possible comparisons of the two left options give

\[ \begin{array}{ll} x^L_1\prec x^L_2: & P(x^L_1,y^L)\prec P(x^L_2,y^L) \prec P(x^L_2,y^R),\\[1mm] x^L_1\sim x^L_2: & P(x^L_1,y^L)\prec P(x^L_1,y^R) \preceq P(x^L_2,y^R),\\[1mm] x^L_2\prec x^L_1: & P(x^L_1,y^L)\prec P(x^L_1,y^R) \prec P(x^L_2,y^R). \end{array} \]

Here is the first branch in detail. Assume \(x^L_1\prec x^L_2\). The smaller assertion \(C(x^L_1,x^L_2,y)\) gives

\[ C_L(x^L_1,x^L_2;y,y^L) =\operatorname {Cross}_{\prec }(x^L_1,x^L_2;y^L,y). \]

Substitute \((a,c;d,e;b)=(x^L_1,x^L_2;y^L,y;x)\) in rule (a) of Theorem 4.7. It becomes

\[ \operatorname {M}(x^L_1,y;x,y^L)\prec \operatorname {M}(x^L_2,y;x,y^L), \qquad \text{that is,}\qquad P(x^L_1,y^L)\prec P(x^L_2,y^L). \]

For the second step, the smaller assertion \(C(y^L,y^R,x)\), evaluated at the left option \(x^L_2\) of \(x\), gives

\[ \operatorname {Cross}_{\prec }(y^L,y^R;x^L_2,x). \]

Applying rule (e) of Theorem 4.7 gives \(\operatorname {Cross}_{\prec }(x^L_2,x;y^L,y^R)\). Rule (c), now with \((a,c;d,e;b)=(x^L_2,x;y^L,y^R;y)\), gives

\[ P(x^L_2,y^L)\prec P(x^L_2,y^R). \]

Strict transitivity therefore proves the first chain in the display.

If \(x^L_1\sim x^L_2\), the same \(y\)-slot argument first gives \(P(x^L_1,y^L)\prec P(x^L_1,y^R)\). The two smaller assertions \(B(x^L_1,x^L_2,y)\) and \(B(x^L_1,x^L_2,y^R)\) give

\[ x^L_1y\sim x^L_2y, \qquad x^L_1y^R\sim x^L_2y^R. \]

Hence, in \(\mathcal{G}/{\sim }\),

\[ [P(x^L_1,y^R)] =[x^L_1y+xy^R-x^L_1y^R] =[x^L_2y+xy^R-x^L_2y^R] =[P(x^L_2,y^R)]. \]

Thus \(P(x^L_1,y^R)\sim P(x^L_2,y^R)\), and the strict–weak composition law proves the middle chain.

Finally, assume \(x^L_2\prec x^L_1\). After the same strict \(y\)-slot movement at \(x^L_1\), the smaller assertion \(C(x^L_2,x^L_1,y)\) gives

\[ C_R(x^L_2,x^L_1;y,y^R) =\operatorname {Cross}_{\prec }(x^L_2,x^L_1;y,y^R). \]

Rule (b) of Theorem 4.7, with \((a,c;d,e;b)=(x^L_2,x^L_1;y,y^R;x)\), reverses the \(x\)-slot direction and gives

\[ P(x^L_1,y^R)\prec P(x^L_2,y^R). \]

Strict transitivity proves the last chain. All the \(B\)- and \(C\)-assertions just invoked are smaller by the one-to-two birthday replacement in Definition 4.5.

The \(LL\)-versus-\(RL\), \(RR\)-versus-\(LR\), and \(RR\)-versus-\(RL\) comparisons are proved analogously. This proves \(A(x,y)\).

Now consider \(B(a,b,y)\). Assume \(a\sim b\). By Definition 2.4, to prove \(ay\preceq by\) one must rule out \(by\preceq \lambda \) for every left option \(\lambda \) of \(ay\), and rule out \(\rho \preceq ay\) for every right option \(\rho \) of \(by\).

Definition 4.1 gives two kinds of left option of \(ay\):

\[ \begin{aligned} \lambda _{LL}& =\operatorname {M}(a^L,y;a,y^L) =a^Ly+ay^L-a^Ly^L,\\ \lambda _{RR}& =\operatorname {M}(a^R,y;a,y^R) =a^Ry+ay^R-a^Ry^R. \end{aligned} \]

We must prove \(\lambda _{LL}\prec by\) and \(\lambda _{RR}\prec by\); either strict inequality contains the corresponding conclusion \(\neg (by\preceq \lambda )\).

For \(\lambda _{LL}\), the smaller assertion \(B(a,b,y^L)\) gives

\[ ay^L\sim by^L. \]

The comparison \(a^L\prec a\), together with \(a\preceq b\) from \(a\sim b\), gives \(a^L\prec b\). Hence the smaller assertion \(C(a^L,b,y)\) gives the explicit cross inequality

\[ C_L(a^L,b;y,y^L):\qquad a^Ly+by^L\prec a^Ly^L+by. \]

These are exactly the two hypotheses of the \(LL\) implication in Lemma 4.8, so

\[ \lambda _{LL}=a^Ly+ay^L-a^Ly^L\prec by. \]

For \(\lambda _{RR}\), the smaller assertion \(B(a,b,y^R)\) gives

\[ ay^R\sim by^R. \]

Now \(b\preceq a\) follows from \(a\sim b\), while \(a\prec a^R\); hence \(b\prec a^R\). The smaller assertion \(C(b,a^R,y)\) therefore gives

\[ C_R(b,a^R;y,y^R):\qquad by^R+a^Ry\prec by+a^Ry^R. \]

The \(RR\) implication in Lemma 4.8 now yields

\[ \lambda _{RR}=a^Ry+ay^R-a^Ry^R\prec by. \]

Every assertion used here is smaller by Definition 4.5 and Lemma 2.3.

The two right-option cases are analogous. Explicitly, for the two right options of \(by\), one must prove

\[ \begin{aligned} ay& \prec \rho _{LR} =\operatorname {M}(b^L,y;b,y^R)=b^Ly+by^R-b^Ly^R,\\ ay& \prec \rho _{RL} =\operatorname {M}(b^R,y;b,y^L)=b^Ry+by^L-b^Ry^L. \end{aligned} \]

These follow analogously from the \(LR\) and \(RL\) implications of Lemma 4.8. The four exclusions prove \(ay\preceq by\).

Interchanging \(a\) and \(b\) gives \(by\preceq ay\). This does not invoke the induction hypothesis at the unchanged measure: the equality

\[ \mu _B(a,b,y)=\mu _B(b,a,y) \]

from Definition 4.5 identifies the two collections of strictly smaller assertions, and symmetry of \(a\sim b\) permits the same one-sided proof to be reused. The two weak inequalities are exactly \(ay\sim by\) by Definition 2.5.

Finally consider \(C(x_1,x_2,y)\), with \(x_1\prec x_2\). The assertion to be proved is that, for every left option \(y^L\) and right option \(y^R\) of \(y\),

\[ \begin{aligned} C_L(x_1,x_2;y,y^L):\quad & x_1y+x_2y^L\prec x_1y^L+x_2y,\\ C_R(x_1,x_2;y,y^R):\quad & x_1y^R+x_2y\prec x_1y+x_2y^R. \end{aligned} \]

Unfolding Definition 2.4 gives the following bridge alternative: either a right option \(x_1^R\) satisfies \(x_1^R\preceq x_2\), or a left option \(x_2^L\) satisfies \(x_1\preceq x_2^L\). Indeed, if neither existed, the two universal clauses in that definition would give \(x_2\preceq x_1\), contradicting \(x_1\prec x_2\).

Suppose first that \(x_1^R\preceq x_2\). The smaller assertion \(A(x_1,y)\) makes \(x_1y\) surreal. Its product options are those of Definition 4.1. For each left option \(y^L\) of \(y\), the \(RL\) product option lies above \(x_1y\), so

\[ x_1y\prec x_1^Ry+x_1y^L-x_1^Ry^L. \]

Work in the quotient of Definition 3.8, whose ordered additive group structure is given by Theorem 3.9. Adding \([x_1^Ry^L]\) gives

\[ [x_1y]+[x_1^Ry^L]{\lt}[x_1^Ry]+[x_1y^L]. \]

Reflection of strict order from the quotient gives

\[ \begin{aligned} C_L(x_1,x_1^R;y,y^L) & =\operatorname {Cross}_{\prec }(x_1,x_1^R;y^L,y),\\ & \text{i.e.}\quad x_1y+x_1^Ry^L\prec x_1y^L+x_1^Ry. \end{aligned} \]

Similarly, for a right option \(y^R\), the \(RR\) product option lies below \(x_1y\):

\[ x_1^Ry+x_1y^R-x_1^Ry^R\prec x_1y. \]

Adding \([x_1^Ry^R]\) and reflecting strict order gives

\[ \begin{aligned} C_R(x_1,x_1^R;y,y^R) & =\operatorname {Cross}_{\prec }(x_1,x_1^R;y,y^R),\\ & \text{i.e.}\quad x_1y^R+x_1^Ry\prec x_1y+x_1^Ry^R. \end{aligned} \]

These are called the adjacent conditions because their two endpoints are \(x_1\) and its option \(x_1^R\). The required conditions displayed above have endpoints \(x_1,x_2\), so it remains to move the second endpoint from \(x_1^R\) to \(x_2\).

By Theorem 2.11, either \(x_1^R\prec x_2\), \(x_1^R\sim x_2\), or \(x_2\prec x_1^R\). If \(x_1^R\prec x_2\), the smaller assertion \(C(x_1^R,x_2,y)\) supplies

\[ \begin{aligned} C_L(x_1^R,x_2;y,y^L) & =\operatorname {Cross}_{\prec }(x_1^R,x_2;y^L,y),\\ & \text{i.e.}\quad x_1^Ry+x_2y^L\prec x_1^Ry^L+x_2y,\\[1mm] C_R(x_1^R,x_2;y,y^R) & =\operatorname {Cross}_{\prec }(x_1^R,x_2;y,y^R),\\ & \text{i.e.}\quad x_1^Ry^R+x_2y\prec x_1^Ry+x_2y^R. \end{aligned} \]

Rule (f) of Theorem 4.7 now composes

\[ \begin{gathered} \operatorname {Cross}_{\prec }(x_1,x_1^R;y^L,y) \quad \text{and}\quad \operatorname {Cross}_{\prec }(x_1^R,x_2;y^L,y),\\ \operatorname {Cross}_{\prec }(x_1,x_1^R;y,y^R) \quad \text{and}\quad \operatorname {Cross}_{\prec }(x_1^R,x_2;y,y^R). \end{gathered} \]

The results are precisely \(C_L(x_1,x_2;y,y^L)\) and \(C_R(x_1,x_2;y,y^R)\).

If \(x_1^R\sim x_2\), the smaller \(B\)-assertions give

\[ x_1^Ry\sim x_2y,\qquad x_1^Ry^L\sim x_2y^L,\qquad x_1^Ry^R\sim x_2y^R. \]

Replacing these three products in the two adjacent inequalities gives, respectively,

\[ x_1y+x_2y^L\prec x_1y^L+x_2y, \qquad x_1y^R+x_2y\prec x_1y+x_2y^R, \]

which are again the two required conditions. The remaining alternative \(x_2\prec x_1^R\) contradicts \(x_1^R\preceq x_2\).

The alternative \(x_1\preceq x_2^L\) is analogous, using the adjacent conditions for \(x_2^L,x_2\) and then moving the first endpoint from \(x_2^L\) to \(x_1\).

Theorem 4.10 Conway A: closure of the product
✓
#

If \(x\) and \(y\) are surreal games, then \(xy\) is surreal.

Proof ▶

Apply the \(A(x,y)\) clause of Theorem 4.9 to the two surrealness hypotheses. Its conclusion is precisely that \(xy\) is surreal.

Theorem 4.11 Conway B: product respects equivalence
✓
#

If \(x_1,x_2,y\) are surreal and \(x_1\sim x_2\), then \(x_1y\sim x_2y\).

Proof ▶

Apply the \(B(x_1,x_2,y)\) clause of Theorem 4.9, with the three surrealness hypotheses and \(x_1\sim x_2\). The conclusion is \(x_1y\sim x_2y\).

Theorem 4.12 Conway C: strict cross inequalities
✓
#

If \(x_1,x_2,y\) are surreal and \(x_1\prec x_2\), then all the conditions \(C_L(x_1,x_2;y,y^L)\) and \(C_R(x_1,x_2;y,y^R)\) hold.

Proof ▶

Apply the \(C(x_1,x_2,y)\) clause of Theorem 4.9, with the three surrealness hypotheses and \(x_1\prec x_2\). Its two conclusions are precisely the required left and right cross inequalities.