Surreal multiplication #
In this file, we show that multiplication of surreal numbers is well-defined, and thus the surreal numbers form a linear ordered commutative ring. This is Theorem 8 in [Conway2001], or Theorem 3.8 in [SchleicherStoll].
An inductive argument proves the following three main theorems:
- P1: being numeric is closed under multiplication,
- P2: multiplying a numeric pregame by equivalent numeric pregames results in equivalent pregames,
- P3: the product of two positive numeric pregames is positive (
mul_pos).
P1 allows us to define multiplication as an operation on numeric pregames, P2 says that this is
well-defined as an operation on the quotient by IGame.Equiv, namely the surreal numbers, and P3 is
an axiom that needs to be satisfied for the surreals to be a OrderedRing.
We follow the proof in [SchleicherStoll], except that we use the well-foundedness of the hydra
relation CutExpand on Multiset IGame instead of the argument based on a depth function in the
paper. As in said argument, P3 is proven by proxy of an auxiliary P4, which states that for
x₁ < x₂ and y, then x₁ * y + x₂ * a < x₁ * a + x₂ * y when a ∈ yᴸ, and
x₁ * b + x₂ * y < x₁ * y + x₂ * b when b ∈ yᴿ.
Reducing casework #
This argument is very casework heavy in a way that's difficult to automate. For instance, in P1, we
have to prove four different inequalities of the form
a ∈ (x * y)ᴸ → b ∈ (x * y)ᴿ → a < b, and depending on what form the options of
x * y take, we have to apply different instantiations of the inductive hypothesis.
To greatly simplify things, we work uniquely in terms of left options, which we achieve by rewriting
a ∈ xᴿ as -a ∈ (-x)ᴸ. We then show that our distinct lemmas and inductive
hypotheses are invariant under the appropriate sign changes. In the P1 example, this makes it so
that one case (mulOption_lt_of_lt) is enough to conclude the others (mulOption_lt), and the same
goes for the other parts of the proof.
Note also that we express all inequalities in terms of Game instead of IGame; this allows us to
make use of abel and all of the theorems on OrderedAddCommGroup.
Predicates P1 – P4 #
P1 x y a b c d means that mulOption x y a b < mulOption x y c d. This is the general form
of the statements needed to prove that x * y is numeric.
Equations
- Surreal.Multiplication.P1 x y a b c d = (Game.mk (IGame.mulOption x y a b) < Game.mk (IGame.mulOption x y c d))
Instances For
P3 x₁ x₂ y₁ y₂ states that x₁ * y₂ + x₂ * y₁ < x₁ * y₁ + x₂ * y₂. Using distributivity, this
is equivalent to (x₁ - x₂) * (y₁ - y₂) > 0.
Equations
Instances For
P4 x₁ x₂ y states that if x₁ < x₂, then P3 x₁ x₂ a y when a ∈ yᴸ, and
P3 x₁ x₂ b y when b ∈ yᴿ.
Note that we instead write this second part as P3 x₁ x₂ b (-y) when b ∈ (-y)ᴸ. See the
module docstring for an explanation.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The conjunction of P2 and P4. Both statements have the same amount of arguments and satisfy
similar symmetry properties, so we can slightly simplify the argument by merging them.
Equations
- Surreal.Multiplication.P24 x₁ x₂ y = (Surreal.Multiplication.P2 x₁ x₂ y ∧ Surreal.Multiplication.P4 x₁ x₂ y)
Instances For
Symmetry properties of P1 – P4 #
Inductive setup #
The multiset associated to a list of arguments.
Equations
- (Surreal.Multiplication.Args.P1 x_1 y).toMultiset = {x_1, y}
- (Surreal.Multiplication.Args.P24 x₁ x₂ y).toMultiset = {x₁, x₂, y}
Instances For
A list of arguments is numeric if all the arguments are.
Equations
- a.Numeric = ∀ x ∈ a.toMultiset, x.Numeric
Instances For
The well-founded relation specifying when a list of game arguments is considered simpler than
another: ArgsRel a₁ a₂ is true if a₁, considered as a multiset, can be obtained from a₂ by
repeatedly removing a game from a₂ and adding back one or two options of the game.
See also WellFounded.CutExpand.
Equations
Instances For
The statement that we will show by induction for all Numeric args, using the well-founded
relation ArgsRel.
The inductive hypothesis in the proof will be ∀ a', ArgsRel a' a → P124 a.
Equations
- Surreal.Multiplication.P124 (Surreal.Multiplication.Args.P1 x_1 y) = (x_1 * y).Numeric
- Surreal.Multiplication.P124 (Surreal.Multiplication.Args.P24 x₁ x₂ y) = Surreal.Multiplication.P24 x₁ x₂ y
Instances For
P1 follows from the inductive hypothesis #
A specialization of the inductive hypothesis used to prove P1.
Equations
- Surreal.Multiplication.IH1 x y = ∀ ⦃x₁ x₂ y' : IGame⦄, x₁.IsOption x → x₂.IsOption x → y' = y ∨ y'.IsOption y → Surreal.Multiplication.P24 x₁ x₂ y'
Instances For
P2 follows from the inductive hypothesis #
A specialization of the induction hypothesis used to prove P4.
Equations
- Surreal.Multiplication.IH4 x₁ x₂ y = ∀ ⦃z w : IGame⦄, w.IsOption y → (z.IsOption x₁ → Surreal.Multiplication.P2 z x₂ w) ∧ (z.IsOption x₂ → Surreal.Multiplication.P2 x₁ z w)
Instances For
P4 follows from the inductive hypothesis #
A specialization of the induction hypothesis used to prove P3.
Equations
- One or more equations did not get rendered due to their size.
Instances For
P3 follows from IH3, so P4 (with y₁ a left option of y₂) follows from the induction
hypothesis.
We tie everything together to complete the induction.
Instances and corollaries #
Equations
- One or more equations did not get rendered due to their size.