Natural operations on ordinals

The goal of this file is to define natural addition and multiplication on ordinals, also known as the Hessenberg sum and product, and provide a basic API. The natural addition of two ordinals a ♯ b is recursively defined as the least ordinal greater than a' ♯ b and a ♯ b' for a' < a and b' < b. The natural multiplication a ⨳ b is likewise recursively defined as the least ordinal such that a ⨳ b ♯ a' ⨳ b' is greater than a' ⨳ b ♯ a ⨳ b' for any a' < a and b' < b.

These operations form a rich algebraic structure: they're commutative, associative, preserve order, have the usual 0 and 1 from ordinals, and distribute over one another.

Moreover, these operations are the addition and multiplication of ordinals when viewed as combinatorial Games. This makes them particularly useful for game theory.

Finally, both operations admit simple, intuitive descriptions in terms of the Cantor normal form. The natural addition of two ordinals corresponds to adding their Cantor normal forms as if they were polynomials in ω. Likewise, their natural multiplication corresponds to multiplying the Cantor normal forms as polynomials.

Implementation notes

Given the rich algebraic structure of these two operations, we choose to create a type synonym NatOrdinal, where we provide the appropriate instances. However, to avoid casting back and forth between both types, we attempt to prove and state most results on Ordinal.

Todo

• Prove the characterizations of natural addition and multiplication in terms of the Cantor normal form.

Basic casts between Ordinal and NatOrdinal

def NatOrdinal : Type (u_1 + 1)

A type synonym for ordinals with natural addition and multiplication.

Equations

• NatOrdinal = Ordinal.{u_1}

instance NatOrdinal.linearOrder : LinearOrder NatOrdinal

Equations

• NatOrdinal.linearOrder = let src := Ordinal.linearOrder; LinearOrder.mk (_ : ∀ (a b : Ordinal.{u_1}), a ≤ b ∨ b ≤ a) LinearOrder.decidableLE LinearOrder.decidableEq LinearOrder.decidableLT

instance NatOrdinal.succOrder : SuccOrder NatOrdinal

Equations

• One or more equations did not get rendered due to their size.

@[match_pattern]

def Ordinal.toNatOrdinal : Ordinal.{u_1} ≃o NatOrdinal

The identity function between Ordinal and NatOrdinal.

Equations

• Ordinal.toNatOrdinal = OrderIso.refl Ordinal.{u_1}

@[match_pattern]

def NatOrdinal.toOrdinal : NatOrdinal ≃o Ordinal.{u_1}

The identity function between NatOrdinal and Ordinal.

Equations

• NatOrdinal.toOrdinal = OrderIso.refl NatOrdinal

@[simp]

theorem NatOrdinal.toOrdinal_symm_eq : OrderIso.symm NatOrdinal.toOrdinal = Ordinal.toNatOrdinal

@[simp]

theorem NatOrdinal.toOrdinal_toNatOrdinal (a : NatOrdinal) : Ordinal.toNatOrdinal (NatOrdinal.toOrdinal a) = a

theorem NatOrdinal.lt_wf : WellFounded fun (x x_1 : NatOrdinal) => x < x_1

instance NatOrdinal.instWellFoundedLTNatOrdinalToLTToPreorderToPartialOrderToSemilatticeInfToLatticeInstDistribLatticeLinearOrder : WellFoundedLT NatOrdinal

Equations

• NatOrdinal.instWellFoundedLTNatOrdinalToLTToPreorderToPartialOrderToSemilatticeInfToLatticeInstDistribLatticeLinearOrder = Ordinal.wellFoundedLT

instance NatOrdinal.instIsWellOrderNatOrdinalLtToLTToPreorderToPartialOrderToSemilatticeInfToLatticeInstDistribLatticeLinearOrder : IsWellOrder NatOrdinal fun (x x_1 : NatOrdinal) => x < x_1

Equations

• NatOrdinal.instIsWellOrderNatOrdinalLtToLTToPreorderToPartialOrderToSemilatticeInfToLatticeInstDistribLatticeLinearOrder = Ordinal.isWellOrder

@[simp]

theorem NatOrdinal.toOrdinal_zero : NatOrdinal.toOrdinal 0 = 0

@[simp]

theorem NatOrdinal.toOrdinal_one : NatOrdinal.toOrdinal 1 = 1

@[simp]

theorem NatOrdinal.toOrdinal_eq_zero (a : NatOrdinal) : NatOrdinal.toOrdinal a = 0 ↔ a = 0

@[simp]

theorem NatOrdinal.toOrdinal_eq_one (a : NatOrdinal) : NatOrdinal.toOrdinal a = 1 ↔ a = 1

@[simp]

theorem NatOrdinal.toOrdinal_max {a : NatOrdinal} {b : NatOrdinal} : NatOrdinal.toOrdinal (max a b) = max (NatOrdinal.toOrdinal a) (NatOrdinal.toOrdinal b)

@[simp]

theorem NatOrdinal.toOrdinal_min {a : NatOrdinal} {b : NatOrdinal} : NatOrdinal.toOrdinal (min a b) = min (NatOrdinal.toOrdinal a) (NatOrdinal.toOrdinal b)

theorem NatOrdinal.succ_def (a : NatOrdinal) : Order.succ a = Ordinal.toNatOrdinal (NatOrdinal.toOrdinal a + 1)

def NatOrdinal.rec {β : NatOrdinal → Sort u_1} (h : (a : Ordinal.{u_2}) → β (Ordinal.toNatOrdinal a)) (a : NatOrdinal) : β a

A recursor for NatOrdinal. Use as induction x using NatOrdinal.rec.

Equations

• NatOrdinal.rec h a = h (NatOrdinal.toOrdinal a)

theorem NatOrdinal.induction {p : NatOrdinal → Prop} (i : NatOrdinal) : (∀ (j : NatOrdinal), (∀ k < j, p k) → p j) → p i

Ordinal.induction but for NatOrdinal.

@[simp]

theorem Ordinal.toNatOrdinal_symm_eq : OrderIso.symm Ordinal.toNatOrdinal = NatOrdinal.toOrdinal

@[simp]

theorem Ordinal.toNatOrdinal_toOrdinal (a : Ordinal.{u_1}) : NatOrdinal.toOrdinal (Ordinal.toNatOrdinal a) = a

@[simp]

theorem Ordinal.toNatOrdinal_zero : Ordinal.toNatOrdinal 0 = 0

@[simp]

theorem Ordinal.toNatOrdinal_one : Ordinal.toNatOrdinal 1 = 1

@[simp]

theorem Ordinal.toNatOrdinal_eq_zero (a : Ordinal.{u_1}) : Ordinal.toNatOrdinal a = 0 ↔ a = 0

@[simp]

theorem Ordinal.toNatOrdinal_eq_one (a : Ordinal.{u_1}) : Ordinal.toNatOrdinal a = 1 ↔ a = 1

@[simp]

theorem Ordinal.toNatOrdinal_max (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.toNatOrdinal (max a b) = max (Ordinal.toNatOrdinal a) (Ordinal.toNatOrdinal b)

@[simp]

theorem Ordinal.toNatOrdinal_min (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.toNatOrdinal (min a b) = min (Ordinal.toNatOrdinal a) (Ordinal.toNatOrdinal b)

We place the definitions of nadd and nmul before actually developing their API, as this guarantees we only need to open the NaturalOps locale once.

noncomputable def Ordinal.nadd : Ordinal.{u} → Ordinal.{u} → Ordinal.{u}

Natural addition on ordinals a ♯ b, also known as the Hessenberg sum, is recursively defined as the least ordinal greater than a' ♯ b and a ♯ b' for all a' < a and b' < b. In contrast to normal ordinal addition, it is commutative.

Natural addition can equivalently be characterized as the ordinal resulting from adding up corresponding coefficients in the Cantor normal forms of a and b.

Equations

• One or more equations did not get rendered due to their size.

def NaturalOps.«term_♯_» : Lean.TrailingParserDescr

Natural addition on ordinals a ♯ b, also known as the Hessenberg sum, is recursively defined as the least ordinal greater than a' ♯ b and a ♯ b' for all a' < a and b' < b. In contrast to normal ordinal addition, it is commutative.

Natural addition can equivalently be characterized as the ordinal resulting from adding up corresponding coefficients in the Cantor normal forms of a and b.

Equations

• NaturalOps.«term_♯_» = Lean.ParserDescr.trailingNode `NaturalOps.term_♯_ 65 65 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ♯ ") (Lean.ParserDescr.cat `term 66))

noncomputable def Ordinal.nmul : Ordinal.{u} → Ordinal.{u} → Ordinal.{u}

Natural multiplication on ordinals a ⨳ b, also known as the Hessenberg product, is recursively defined as the least ordinal such that a ⨳ b + a' ⨳ b' is greater than a' ⨳ b + a ⨳ b' for all a' < a and b < b'. In contrast to normal ordinal multiplication, it is commutative and distributive (over natural addition).

Natural multiplication can equivalently be characterized as the ordinal resulting from multiplying the Cantor normal forms of a and b as if they were polynomials in ω. Addition of exponents is done via natural addition.

Equations

• Ordinal.nmul x✝ x = sInf {c : Ordinal.{?u.266} | ∀ a' < x✝, ∀ b' < x, Ordinal.nadd (Ordinal.nmul a' x) (Ordinal.nmul x✝ b') < Ordinal.nadd c (Ordinal.nmul a' b')}

def NaturalOps.«term_⨳_» : Lean.TrailingParserDescr

Natural multiplication on ordinals a ⨳ b, also known as the Hessenberg product, is recursively defined as the least ordinal such that a ⨳ b + a' ⨳ b' is greater than a' ⨳ b + a ⨳ b' for all a' < a and b < b'. In contrast to normal ordinal multiplication, it is commutative and distributive (over natural addition).

Natural multiplication can equivalently be characterized as the ordinal resulting from multiplying the Cantor normal forms of a and b as if they were polynomials in ω. Addition of exponents is done via natural addition.

Equations

• NaturalOps.«term_⨳_» = Lean.ParserDescr.trailingNode `NaturalOps.term_⨳_ 70 70 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ⨳ ") (Lean.ParserDescr.cat `term 71))

Natural addition

theorem Ordinal.nadd_def (a : Ordinal.{u}) (b : Ordinal.{u}) : Ordinal.nadd a b = max (Ordinal.blsub a fun (a' : Ordinal.{u}) (x : a' < a) => Ordinal.nadd a' b) (Ordinal.blsub b fun (b' : Ordinal.{u}) (x : b' < b) => Ordinal.nadd a b')

theorem Ordinal.lt_nadd_iff {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} : a < Ordinal.nadd b c ↔ (∃ b' < b, a ≤ Ordinal.nadd b' c) ∨ ∃ c' < c, a ≤ Ordinal.nadd b c'

theorem Ordinal.nadd_le_iff {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} : Ordinal.nadd b c ≤ a ↔ (∀ b' < b, Ordinal.nadd b' c < a) ∧ ∀ c' < c, Ordinal.nadd b c' < a

theorem Ordinal.nadd_lt_nadd_left {b : Ordinal.{u}} {c : Ordinal.{u}} (h : b < c) (a : Ordinal.{u}) : Ordinal.nadd a b < Ordinal.nadd a c

theorem Ordinal.nadd_lt_nadd_right {b : Ordinal.{u}} {c : Ordinal.{u}} (h : b < c) (a : Ordinal.{u}) : Ordinal.nadd b a < Ordinal.nadd c a

theorem Ordinal.nadd_le_nadd_left {b : Ordinal.{u}} {c : Ordinal.{u}} (h : b ≤ c) (a : Ordinal.{u}) : Ordinal.nadd a b ≤ Ordinal.nadd a c

theorem Ordinal.nadd_le_nadd_right {b : Ordinal.{u}} {c : Ordinal.{u}} (h : b ≤ c) (a : Ordinal.{u}) : Ordinal.nadd b a ≤ Ordinal.nadd c a

theorem Ordinal.nadd_comm (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nadd a b = Ordinal.nadd b a

theorem Ordinal.blsub_nadd_of_mono (a : Ordinal.{u}) (b : Ordinal.{u}) {f : (c : Ordinal.{u}) → c < Ordinal.nadd a b → Ordinal.{max u v} } (hf : ∀ {i j : Ordinal.{u}} (hi : i < Ordinal.nadd a b) (hj : j < Ordinal.nadd a b), i ≤ j → f i hi ≤ f j hj) : Ordinal.blsub (Ordinal.nadd a b) f = max (Ordinal.blsub a fun (a' : Ordinal.{u}) (ha' : a' < a) => f (Ordinal.nadd a' b) (_ : Ordinal.nadd a' b < Ordinal.nadd a b)) (Ordinal.blsub b fun (b' : Ordinal.{u}) (hb' : b' < b) => f (Ordinal.nadd a b') (_ : Ordinal.nadd a b' < Ordinal.nadd a b))

theorem Ordinal.nadd_assoc (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) (c : Ordinal.{u_1}) : Ordinal.nadd (Ordinal.nadd a b) c = Ordinal.nadd a (Ordinal.nadd b c)

@[simp]

theorem Ordinal.nadd_zero (a : Ordinal.{u}) : Ordinal.nadd a 0 = a

@[simp]

theorem Ordinal.zero_nadd (a : Ordinal.{u}) : Ordinal.nadd 0 a = a

@[simp]

theorem Ordinal.nadd_one (a : Ordinal.{u}) : Ordinal.nadd a 1 = Order.succ a

@[simp]

theorem Ordinal.one_nadd (a : Ordinal.{u}) : Ordinal.nadd 1 a = Order.succ a

theorem Ordinal.nadd_succ (a : Ordinal.{u}) (b : Ordinal.{u}) : Ordinal.nadd a (Order.succ b) = Order.succ (Ordinal.nadd a b)

theorem Ordinal.succ_nadd (a : Ordinal.{u}) (b : Ordinal.{u}) : Ordinal.nadd (Order.succ a) b = Order.succ (Ordinal.nadd a b)

@[simp]

theorem Ordinal.nadd_nat (a : Ordinal.{u}) (n : ℕ) : Ordinal.nadd a ↑n = a + ↑n

@[simp]

theorem Ordinal.nat_nadd (a : Ordinal.{u}) (n : ℕ) : Ordinal.nadd (↑n) a = a + ↑n

theorem Ordinal.add_le_nadd (a : Ordinal.{u}) (b : Ordinal.{u}) : a + b ≤ Ordinal.nadd a b

instance NatOrdinal.instAddNatOrdinal : Add NatOrdinal

Equations

• NatOrdinal.instAddNatOrdinal = { add := Ordinal.nadd }

instance NatOrdinal.add_covariantClass_lt : CovariantClass NatOrdinal NatOrdinal (fun (x x_1 : NatOrdinal) => x + x_1) fun (x x_1 : NatOrdinal) => x < x_1

Equations

• NatOrdinal.add_covariantClass_lt = (_ : CovariantClass NatOrdinal NatOrdinal (fun (x x_1 : NatOrdinal) => x + x_1) fun (x x_1 : NatOrdinal) => x < x_1)

instance NatOrdinal.add_covariantClass_le : CovariantClass NatOrdinal NatOrdinal (fun (x x_1 : NatOrdinal) => x + x_1) fun (x x_1 : NatOrdinal) => x ≤ x_1

Equations

• NatOrdinal.add_covariantClass_le = (_ : CovariantClass NatOrdinal NatOrdinal (fun (x x_1 : NatOrdinal) => x + x_1) fun (x x_1 : NatOrdinal) => x ≤ x_1)

instance NatOrdinal.add_contravariantClass_le : ContravariantClass NatOrdinal NatOrdinal (fun (x x_1 : NatOrdinal) => x + x_1) fun (x x_1 : NatOrdinal) => x ≤ x_1

Equations

• NatOrdinal.add_contravariantClass_le = (_ : ContravariantClass NatOrdinal NatOrdinal (fun (x x_1 : NatOrdinal) => x + x_1) fun (x x_1 : NatOrdinal) => x ≤ x_1)

instance NatOrdinal.orderedCancelAddCommMonoid : OrderedCancelAddCommMonoid NatOrdinal

Equations

• NatOrdinal.orderedCancelAddCommMonoid = let src := NatOrdinal.linearOrder; OrderedCancelAddCommMonoid.mk NatOrdinal.orderedCancelAddCommMonoid.proof_4

instance NatOrdinal.addMonoidWithOne : AddMonoidWithOne NatOrdinal

Equations

• NatOrdinal.addMonoidWithOne = AddMonoidWithOne.unary

@[simp]

theorem NatOrdinal.add_one_eq_succ (a : NatOrdinal) : a + 1 = Order.succ a

@[simp]

theorem NatOrdinal.toOrdinal_cast_nat (n : ℕ) : NatOrdinal.toOrdinal ↑n = ↑n

theorem Ordinal.nadd_eq_add (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nadd a b = NatOrdinal.toOrdinal (Ordinal.toNatOrdinal a + Ordinal.toNatOrdinal b)

@[simp]

theorem Ordinal.toNatOrdinal_cast_nat (n : ℕ) : Ordinal.toNatOrdinal ↑n = ↑n

theorem Ordinal.lt_of_nadd_lt_nadd_left {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd a b < Ordinal.nadd a c → b < c

theorem Ordinal.lt_of_nadd_lt_nadd_right {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd b a < Ordinal.nadd c a → b < c

theorem Ordinal.le_of_nadd_le_nadd_left {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd a b ≤ Ordinal.nadd a c → b ≤ c

theorem Ordinal.le_of_nadd_le_nadd_right {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd b a ≤ Ordinal.nadd c a → b ≤ c

theorem Ordinal.nadd_lt_nadd_iff_left (a : Ordinal.{u_1}) {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd a b < Ordinal.nadd a c ↔ b < c

theorem Ordinal.nadd_lt_nadd_iff_right (a : Ordinal.{u_1}) {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd b a < Ordinal.nadd c a ↔ b < c

theorem Ordinal.nadd_le_nadd_iff_left (a : Ordinal.{u_1}) {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd a b ≤ Ordinal.nadd a c ↔ b ≤ c

theorem Ordinal.nadd_le_nadd_iff_right (a : Ordinal.{u_1}) {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd b a ≤ Ordinal.nadd c a ↔ b ≤ c

theorem Ordinal.nadd_le_nadd {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} {d : Ordinal.{u_1}} : a ≤ b → c ≤ d → Ordinal.nadd a c ≤ Ordinal.nadd b d

theorem Ordinal.nadd_lt_nadd {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} {d : Ordinal.{u_1}} : a < b → c < d → Ordinal.nadd a c < Ordinal.nadd b d

theorem Ordinal.nadd_lt_nadd_of_lt_of_le {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} {d : Ordinal.{u_1}} : a < b → c ≤ d → Ordinal.nadd a c < Ordinal.nadd b d

theorem Ordinal.nadd_lt_nadd_of_le_of_lt {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} {d : Ordinal.{u_1}} : a ≤ b → c < d → Ordinal.nadd a c < Ordinal.nadd b d

theorem Ordinal.nadd_left_cancel {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd a b = Ordinal.nadd a c → b = c

theorem Ordinal.nadd_right_cancel {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd a b = Ordinal.nadd c b → a = c

theorem Ordinal.nadd_left_cancel_iff {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd a b = Ordinal.nadd a c ↔ b = c

theorem Ordinal.nadd_right_cancel_iff {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} : Ordinal.nadd b a = Ordinal.nadd c a ↔ b = c

theorem Ordinal.le_nadd_self {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} : a ≤ Ordinal.nadd b a

theorem Ordinal.le_nadd_left {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} (h : a ≤ c) : a ≤ Ordinal.nadd b c

theorem Ordinal.le_self_nadd {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} : a ≤ Ordinal.nadd a b

theorem Ordinal.le_nadd_right {a : Ordinal.{u_1}} {b : Ordinal.{u_1}} {c : Ordinal.{u_1}} (h : a ≤ b) : a ≤ Ordinal.nadd b c

theorem Ordinal.nadd_left_comm (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) (c : Ordinal.{u_1}) : Ordinal.nadd a (Ordinal.nadd b c) = Ordinal.nadd b (Ordinal.nadd a c)

theorem Ordinal.nadd_right_comm (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) (c : Ordinal.{u_1}) : Ordinal.nadd (Ordinal.nadd a b) c = Ordinal.nadd (Ordinal.nadd a c) b

Natural multiplication

theorem Ordinal.nmul_def (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul a b = sInf {c : Ordinal.{u_1} | ∀ a' < a, ∀ b' < b, Ordinal.nadd (Ordinal.nmul a' b) (Ordinal.nmul a b') < Ordinal.nadd c (Ordinal.nmul a' b')}

theorem Ordinal.nmul_nonempty (a : Ordinal.{u}) (b : Ordinal.{u}) : Set.Nonempty {c : Ordinal.{u} | ∀ a' < a, ∀ b' < b, Ordinal.nadd (Ordinal.nmul a' b) (Ordinal.nmul a b') < Ordinal.nadd c (Ordinal.nmul a' b')}

The set in the definition of nmul is nonempty.

theorem Ordinal.nmul_nadd_lt {a : Ordinal.{u}} {b : Ordinal.{u}} {a' : Ordinal.{u}} {b' : Ordinal.{u}} (ha : a' < a) (hb : b' < b) : Ordinal.nadd (Ordinal.nmul a' b) (Ordinal.nmul a b') < Ordinal.nadd (Ordinal.nmul a b) (Ordinal.nmul a' b')

theorem Ordinal.nmul_nadd_le {a : Ordinal.{u}} {b : Ordinal.{u}} {a' : Ordinal.{u}} {b' : Ordinal.{u}} (ha : a' ≤ a) (hb : b' ≤ b) : Ordinal.nadd (Ordinal.nmul a' b) (Ordinal.nmul a b') ≤ Ordinal.nadd (Ordinal.nmul a b) (Ordinal.nmul a' b')

theorem Ordinal.lt_nmul_iff {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} : c < Ordinal.nmul a b ↔ ∃ a' < a, ∃ b' < b, Ordinal.nadd c (Ordinal.nmul a' b') ≤ Ordinal.nadd (Ordinal.nmul a' b) (Ordinal.nmul a b')

theorem Ordinal.nmul_le_iff {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} : Ordinal.nmul a b ≤ c ↔ ∀ a' < a, ∀ b' < b, Ordinal.nadd (Ordinal.nmul a' b) (Ordinal.nmul a b') < Ordinal.nadd c (Ordinal.nmul a' b')

theorem Ordinal.nmul_comm (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul a b = Ordinal.nmul b a

@[simp]

theorem Ordinal.nmul_zero (a : Ordinal.{u_1}) : Ordinal.nmul a 0 = 0

@[simp]

theorem Ordinal.zero_nmul (a : Ordinal.{u_1}) : Ordinal.nmul 0 a = 0

@[simp]

theorem Ordinal.nmul_one (a : Ordinal.{u_1}) : Ordinal.nmul a 1 = a

@[simp]

theorem Ordinal.one_nmul (a : Ordinal.{u_1}) : Ordinal.nmul 1 a = a

theorem Ordinal.nmul_lt_nmul_of_pos_left {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} (h₁ : a < b) (h₂ : 0 < c) : Ordinal.nmul c a < Ordinal.nmul c b

theorem Ordinal.nmul_lt_nmul_of_pos_right {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} (h₁ : a < b) (h₂ : 0 < c) : Ordinal.nmul a c < Ordinal.nmul b c

theorem Ordinal.nmul_le_nmul_of_nonneg_left {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} (h₁ : a ≤ b) (h₂ : 0 ≤ c) : Ordinal.nmul c a ≤ Ordinal.nmul c b

theorem Ordinal.nmul_le_nmul_of_nonneg_right {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} (h₁ : a ≤ b) (h₂ : 0 ≤ c) : Ordinal.nmul a c ≤ Ordinal.nmul b c

theorem Ordinal.nmul_nadd (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) (c : Ordinal.{u_1}) : Ordinal.nmul a (Ordinal.nadd b c) = Ordinal.nadd (Ordinal.nmul a b) (Ordinal.nmul a c)

theorem Ordinal.nadd_nmul (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) (c : Ordinal.{u_1}) : Ordinal.nmul (Ordinal.nadd a b) c = Ordinal.nadd (Ordinal.nmul a c) (Ordinal.nmul b c)

theorem Ordinal.nmul_nadd_lt₃ {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} {a' : Ordinal.{u}} {b' : Ordinal.{u}} {c' : Ordinal.{u}} (ha : a' < a) (hb : b' < b) (hc : c' < c) : Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul (Ordinal.nmul a' b) c) (Ordinal.nmul (Ordinal.nmul a b') c)) (Ordinal.nmul (Ordinal.nmul a b) c')) (Ordinal.nmul (Ordinal.nmul a' b') c') < Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul (Ordinal.nmul a b) c) (Ordinal.nmul (Ordinal.nmul a' b') c)) (Ordinal.nmul (Ordinal.nmul a' b) c')) (Ordinal.nmul (Ordinal.nmul a b') c')

theorem Ordinal.nmul_nadd_le₃ {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} {a' : Ordinal.{u}} {b' : Ordinal.{u}} {c' : Ordinal.{u}} (ha : a' ≤ a) (hb : b' ≤ b) (hc : c' ≤ c) : Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul (Ordinal.nmul a' b) c) (Ordinal.nmul (Ordinal.nmul a b') c)) (Ordinal.nmul (Ordinal.nmul a b) c')) (Ordinal.nmul (Ordinal.nmul a' b') c') ≤ Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul (Ordinal.nmul a b) c) (Ordinal.nmul (Ordinal.nmul a' b') c)) (Ordinal.nmul (Ordinal.nmul a' b) c')) (Ordinal.nmul (Ordinal.nmul a b') c')

theorem Ordinal.nmul_nadd_lt₃' {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} {a' : Ordinal.{u}} {b' : Ordinal.{u}} {c' : Ordinal.{u}} (ha : a' < a) (hb : b' < b) (hc : c' < c) : Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul a' (Ordinal.nmul b c)) (Ordinal.nmul a (Ordinal.nmul b' c))) (Ordinal.nmul a (Ordinal.nmul b c'))) (Ordinal.nmul a' (Ordinal.nmul b' c')) < Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul a (Ordinal.nmul b c)) (Ordinal.nmul a' (Ordinal.nmul b' c))) (Ordinal.nmul a' (Ordinal.nmul b c'))) (Ordinal.nmul a (Ordinal.nmul b' c'))

theorem Ordinal.nmul_nadd_le₃' {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} {a' : Ordinal.{u}} {b' : Ordinal.{u}} {c' : Ordinal.{u}} (ha : a' ≤ a) (hb : b' ≤ b) (hc : c' ≤ c) : Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul a' (Ordinal.nmul b c)) (Ordinal.nmul a (Ordinal.nmul b' c))) (Ordinal.nmul a (Ordinal.nmul b c'))) (Ordinal.nmul a' (Ordinal.nmul b' c')) ≤ Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul a (Ordinal.nmul b c)) (Ordinal.nmul a' (Ordinal.nmul b' c))) (Ordinal.nmul a' (Ordinal.nmul b c'))) (Ordinal.nmul a (Ordinal.nmul b' c'))

theorem Ordinal.lt_nmul_iff₃ {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} {d : Ordinal.{u}} : d < Ordinal.nmul (Ordinal.nmul a b) c ↔ ∃ a' < a, ∃ b' < b, ∃ c' < c, Ordinal.nadd (Ordinal.nadd (Ordinal.nadd d (Ordinal.nmul (Ordinal.nmul a' b') c)) (Ordinal.nmul (Ordinal.nmul a' b) c')) (Ordinal.nmul (Ordinal.nmul a b') c') ≤ Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul (Ordinal.nmul a' b) c) (Ordinal.nmul (Ordinal.nmul a b') c)) (Ordinal.nmul (Ordinal.nmul a b) c')) (Ordinal.nmul (Ordinal.nmul a' b') c')

theorem Ordinal.nmul_le_iff₃ {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} {d : Ordinal.{u}} : Ordinal.nmul (Ordinal.nmul a b) c ≤ d ↔ ∀ a' < a, ∀ b' < b, ∀ c' < c, Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul (Ordinal.nmul a' b) c) (Ordinal.nmul (Ordinal.nmul a b') c)) (Ordinal.nmul (Ordinal.nmul a b) c')) (Ordinal.nmul (Ordinal.nmul a' b') c') < Ordinal.nadd (Ordinal.nadd (Ordinal.nadd d (Ordinal.nmul (Ordinal.nmul a' b') c)) (Ordinal.nmul (Ordinal.nmul a' b) c')) (Ordinal.nmul (Ordinal.nmul a b') c')

theorem Ordinal.lt_nmul_iff₃' {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} {d : Ordinal.{u}} : d < Ordinal.nmul a (Ordinal.nmul b c) ↔ ∃ a' < a, ∃ b' < b, ∃ c' < c, Ordinal.nadd (Ordinal.nadd (Ordinal.nadd d (Ordinal.nmul a' (Ordinal.nmul b' c))) (Ordinal.nmul a' (Ordinal.nmul b c'))) (Ordinal.nmul a (Ordinal.nmul b' c')) ≤ Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul a' (Ordinal.nmul b c)) (Ordinal.nmul a (Ordinal.nmul b' c))) (Ordinal.nmul a (Ordinal.nmul b c'))) (Ordinal.nmul a' (Ordinal.nmul b' c'))

theorem Ordinal.nmul_le_iff₃' {a : Ordinal.{u}} {b : Ordinal.{u}} {c : Ordinal.{u}} {d : Ordinal.{u}} : Ordinal.nmul a (Ordinal.nmul b c) ≤ d ↔ ∀ a' < a, ∀ b' < b, ∀ c' < c, Ordinal.nadd (Ordinal.nadd (Ordinal.nadd (Ordinal.nmul a' (Ordinal.nmul b c)) (Ordinal.nmul a (Ordinal.nmul b' c))) (Ordinal.nmul a (Ordinal.nmul b c'))) (Ordinal.nmul a' (Ordinal.nmul b' c')) < Ordinal.nadd (Ordinal.nadd (Ordinal.nadd d (Ordinal.nmul a' (Ordinal.nmul b' c))) (Ordinal.nmul a' (Ordinal.nmul b c'))) (Ordinal.nmul a (Ordinal.nmul b' c'))

theorem Ordinal.nmul_assoc (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) (c : Ordinal.{u_1}) : Ordinal.nmul (Ordinal.nmul a b) c = Ordinal.nmul a (Ordinal.nmul b c)

instance instMulNatOrdinal : Mul NatOrdinal

Equations

• instMulNatOrdinal = { mul := Ordinal.nmul }

instance instOrderedCommSemiringNatOrdinal : OrderedCommSemiring NatOrdinal

Equations

• instOrderedCommSemiringNatOrdinal = let src := NatOrdinal.orderedCancelAddCommMonoid; let src_1 := NatOrdinal.linearOrder; OrderedCommSemiring.mk Ordinal.nmul_comm

theorem Ordinal.nmul_eq_mul (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul a b = NatOrdinal.toOrdinal (Ordinal.toNatOrdinal a * Ordinal.toNatOrdinal b)

theorem Ordinal.nmul_nadd_one (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul a (Ordinal.nadd b 1) = Ordinal.nadd (Ordinal.nmul a b) a

theorem Ordinal.nadd_one_nmul (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul (Ordinal.nadd a 1) b = Ordinal.nadd (Ordinal.nmul a b) b

theorem Ordinal.nmul_succ (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul a (Order.succ b) = Ordinal.nadd (Ordinal.nmul a b) a

theorem Ordinal.succ_nmul (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul (Order.succ a) b = Ordinal.nadd (Ordinal.nmul a b) b

theorem Ordinal.nmul_add_one (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul a (b + 1) = Ordinal.nadd (Ordinal.nmul a b) a

theorem Ordinal.add_one_nmul (a : Ordinal.{u_1}) (b : Ordinal.{u_1}) : Ordinal.nmul (a + 1) b = Ordinal.nadd (Ordinal.nmul a b) b

theorem NatOrdinal.mul_le_nmul (a : Ordinal.{u}) (b : Ordinal.{u}) : a * b ≤ Ordinal.nmul a b