Documentation

CombinatorialGames.SignExpansion.Basic

Sign expansions #

In this repository we define the type of Surreal numbers following Conway's theory of games. A popular alternative is to instead define the surreals as potentially infinite "expansions of signs", setting for instance + = 1, - = -1, +- = ½, etc.

This file defines the type SignExpansion and constructs its basic instances. We do not yet link it to the development of surreal numbers.

For Mathlib #

theorem Set.preimage_neg {α : Type u_1} {ι : Type u_2} [InvolutiveNeg α] (f : ι → α) {s : Set α} :
f ⁻¹' (-s) = (-f) ⁻¹' s
@[simp]
theorem Pi.Lex.neg_apply {α : Type u_1} {β : Type u_2} [Neg β] (x : Lex (α → β)) (i : α) :
(-x) i = -x i
theorem SignType.neg_lt {x y : SignType} :
-x < y ↔ -y < x
theorem SignType.lt_neg {x y : SignType} :
x < -y ↔ y < -x
theorem Pi.Lex.neg_lt_neg {α : Type u_1} [LinearOrder α] {x y : Lex (α → SignType)} (h : x < y) :
-y < -x
@[simp]
theorem Pi.Lex.neg_lt_neg_iff {α : Type u_1} [LinearOrder α] {x y : Lex (α → SignType)} :
-x < -y ↔ y < x
@[simp]
theorem Pi.Lex.neg_le_neg_iff {α : Type u_1} [LinearOrder α] [WellFoundedLT α] {x y : Lex (α → SignType)} :
-x ≤ -y ↔ y ≤ x
theorem Pi.Lex.neg_lt_iff {α : Type u_1} [LinearOrder α] {x y : Lex (α → SignType)} :
-x < y ↔ -y < x
theorem Pi.Lex.lt_neg_iff {α : Type u_1} [LinearOrder α] {x y : Lex (α → SignType)} :
x < -y ↔ y < -x
theorem Pi.Lex.neg_le_iff {α : Type u_1} [LinearOrder α] [WellFoundedLT α] {x y : Lex (α → SignType)} :
-x ≤ y ↔ -y ≤ x
theorem Pi.Lex.le_neg_iff {α : Type u_1} [LinearOrder α] [WellFoundedLT α] {x y : Lex (α → SignType)} :
x ≤ -y ↔ y ≤ -x

Sign expansions #

structure SignExpansion :
Type (u + 1)

A sign expansion is a an ordinal indexed sequence of 1s and -1s, followed by 0s.

Instances For

    Every sign after the first 0 is also 0.

    def SignExpansion.copy (x : SignExpansion) (sign : NatOrdinal → SignType) (h : sign = ⇑x) :

    Adjust definitional equalities of a sign expansion.

    Equations
    • x.copy sign h = { sign := sign, isUpperSet_preimage_singleton_zero' := ⋯ }
    Instances For
      @[simp]
      theorem SignExpansion.copy_eq (x : SignExpansion) (sign : NatOrdinal → SignType) (h : sign = ⇑x) :
      x.copy sign h = x
      @[simp]
      theorem SignExpansion.coe_mk (f : NatOrdinal → SignType) (h : IsUpperSet (f ⁻¹' {0})) :
      ⇑{ sign := f, isUpperSet_preimage_singleton_zero' := h } = f
      theorem SignExpansion.ext {x y : SignExpansion} (hxy : ∀ (o : NatOrdinal), x o = y o) :
      x = y
      theorem SignExpansion.ext_iff {x y : SignExpansion} :
      x = y ↔ ∀ (o : NatOrdinal), x o = y o
      theorem SignExpansion.mk_eq_mk {f g : NatOrdinal → SignType} {h₁ : IsUpperSet (f ⁻¹' {0})} {h₂ : IsUpperSet (g ⁻¹' {0})} :
      { sign := f, isUpperSet_preimage_singleton_zero' := h₁ } = { sign := g, isUpperSet_preimage_singleton_zero' := h₂ } ↔ f = g
      theorem SignExpansion.apply_eq_zero_of_le {x : SignExpansion} {o o' : NatOrdinal} (hoo' : o ≤ o') (ho : x o = 0) :
      x o' = 0

      The length of a sign expansion is the smallest ordinal at which it equals zero, or ⊤ is no such ordinal exists.

      Equations
      Instances For

        Basic sign expansions #

        The constant sign expansion sss...

        Equations
        Instances For
          @[instance_reducible]
          Equations
          @[simp]
          theorem SignExpansion.coe_zero :
          ⇑0 = 0
          @[instance_reducible]
          Equations
          @[simp]
          theorem SignExpansion.coe_bot :
          ⇑⊥ = -1
          @[simp]

          We say a sign expansion is "small" when it has length < ⊤. Equivalently, it contains at least one (and thus infinitely many) zeros.

          Instances
            @[reducible, inline]

            The length of a small sign expansion, as a NatOrdinal.

            Equations
            Instances For
              @[instance_reducible]
              Equations
              @[simp]
              theorem SignExpansion.coe_neg (x : SignExpansion) :
              ⇑(-x) = -⇑x
              @[simp]
              theorem SignExpansion.neg_mk (f : NatOrdinal → SignType) (h : IsUpperSet (f ⁻¹' {0})) :
              -{ sign := f, isUpperSet_preimage_singleton_zero' := h } = { sign := -f, isUpperSet_preimage_singleton_zero' := ⋯ }
              @[simp]

              Cut off the part of a sign expansion after an ordinal o, by filling it in with zeros.

              Equations
              Instances For

                Cut off the part of a sign expansion after an ordinal o, by filling it in with zeros.

                Conventions for notations in identifiers:

                • The recommended spelling of ↾ in identifiers is trunc.
                Equations
                Instances For
                  theorem SignExpansion.coe_trunc (x : SignExpansion) (o : WithTop NatOrdinal) :
                  ⇑(x.trunc o) = fun (i : NatOrdinal) => if ↑i < o then x i else 0
                  theorem SignExpansion.trunc_apply_of_coe_lt {x : SignExpansion} {o₁ : WithTop NatOrdinal} {o₂ : NatOrdinal} (h : ↑o₂ < o₁) :
                  (x.trunc o₁) o₂ = x o₂
                  theorem SignExpansion.trunc_apply_of_le_coe {x : SignExpansion} {o₁ : WithTop NatOrdinal} {o₂ : NatOrdinal} (h : o₁ ≤ ↑o₂) :
                  (x.trunc o₁) o₂ = 0
                  @[simp]

                  Alias of the reverse direction of SignExpansion.trunc_eq_self.

                  @[simp]
                  theorem SignExpansion.trunc_trunc_eq {x : SignExpansion} {o₁ o₂ : WithTop NatOrdinal} :
                  (x.trunc o₁).trunc o₂ = x.trunc (min o₁ o₂)

                  Order structure #

                  @[instance_reducible]
                  Equations
                  • One or more equations did not get rendered due to their size.
                  theorem SignExpansion.neg_lt_neg {x y : SignExpansion} (h : x < y) :
                  -y < -x
                  @[simp]
                  @[simp]
                  theorem SignExpansion.lt_trunc_iff {x : SignExpansion} {o : NatOrdinal} :
                  x < x.trunc ↑o ↔ x o = -1
                  @[simp]
                  theorem SignExpansion.trunc_lt_iff {x : SignExpansion} {o : NatOrdinal} :
                  x.trunc ↑o < x ↔ x o = 1

                  Floor function #

                  The floor function on a function NatOrdinal → SignType "rounds" it downwards to the nearest valid SignExpansion.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    theorem SignExpansion.floor_of_isUpperSet {f : NatOrdinal → SignType} (hf : IsUpperSet (f ⁻¹' {0})) :
                    floor f = { sign := f, isUpperSet_preimage_singleton_zero' := hf }
                    @[simp]
                    noncomputable def SignExpansion.gciFloor :
                    GaloisCoinsertion (⇑toLex ∘ fun (x : SignExpansion) => ⇑x) (floor ∘ ⇑ofLex)

                    floor as a Galois coinsertion.

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

                      Ceiling function #

                      The ceiling function on a function NatOrdinal → SignType "rounds" it upwards to the nearest valid SignExpansion.

                      Equations
                      Instances For
                        theorem SignExpansion.ceil_of_isUpperSet {f : NatOrdinal → SignType} (hf : IsUpperSet (f ⁻¹' {0})) :
                        ceil f = { sign := f, isUpperSet_preimage_singleton_zero' := hf }
                        @[simp]
                        theorem SignExpansion.ceil_apply_of_lt_sInf {f : NatOrdinal → SignType} {a : NatOrdinal} (hf : a < sInf (f ⁻¹' {0})) :
                        (ceil f) a = f a
                        noncomputable def SignExpansion.giCeil :
                        GaloisInsertion (ceil ∘ ⇑ofLex) (⇑toLex ∘ fun (x : SignExpansion) => ⇑x)

                        ceil as a Galois insertion.

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

                          Complete linear order instance #

                          @[instance_reducible]
                          Equations
                          • One or more equations did not get rendered due to their size.
                          @[instance_reducible]
                          Equations
                          • One or more equations did not get rendered due to their size.
                          theorem SignExpansion.coe_sInf (s : Set SignExpansion) :
                          ⇑(sInf s) = ofLex (sInf ((fun (x : SignExpansion) => toLex ⇑x) '' s))
                          theorem SignExpansion.coe_iInf {ι : Sort u_1} (f : ι → SignExpansion) :
                          ⇑(⨅ (i : ι), f i) = ofLex (⨅ (i : ι), toLex ⇑(f i))
                          theorem SignExpansion.sInf_apply (s : Set SignExpansion) (i : NatOrdinal) :
                          (sInf s) i = ⨅ (x : { x : SignExpansion // x ∈ s ∧ ∀ j < i, x j = (sInf s) j }), ↑x i
                          theorem SignExpansion.coe_sSup (s : Set SignExpansion) :
                          ⇑(sSup s) = ofLex (sSup ((fun (x : SignExpansion) => toLex ⇑x) '' s))
                          theorem SignExpansion.coe_iSup {ι : Sort u_1} (f : ι → SignExpansion) :
                          ⇑(⨆ (i : ι), f i) = ofLex (⨆ (i : ι), toLex ⇑(f i))
                          theorem SignExpansion.sSup_apply (s : Set SignExpansion) (i : NatOrdinal) :
                          (sSup s) i = ⨆ (x : { x : SignExpansion // x ∈ s ∧ ∀ j < i, x j = (sSup s) j }), ↑x i

                          Successor function #

                          The successor of a small sign expansion is the unique sign expansion which covers it.

                          Equations
                          Instances For
                            theorem SignExpansion.succ_apply_of_lt {x : SignExpansion} [x.Small] {o : NatOrdinal} (ho : ↑o < x.length) :
                            x.succ o = x o
                            theorem SignExpansion.succ_apply_of_eq {x : SignExpansion} [x.Small] {o : NatOrdinal} (ho : x.length = ↑o) :
                            x.succ o = 1
                            theorem SignExpansion.succ_apply_of_gt {x : SignExpansion} [x.Small] {o : NatOrdinal} (ho : x.length < ↑o) :
                            x.succ o = -1

                            Predecessor function #

                            The predecessor of a small sign expansion is the unique sign expansion which is covered by it.

                            Equations
                            Instances For
                              theorem SignExpansion.pred_apply_of_lt {x : SignExpansion} [x.Small] {o : NatOrdinal} (ho : ↑o < x.length) :
                              x.pred o = x o
                              theorem SignExpansion.pred_apply_of_eq {x : SignExpansion} [x.Small] {o : NatOrdinal} (ho : x.length = ↑o) :
                              x.pred o = -1
                              theorem SignExpansion.pred_apply_of_gt {x : SignExpansion} [x.Small] {o : NatOrdinal} (ho : x.length < ↑o) :
                              x.succ o = -1

                              Cast from ordinals #

                              Returns the sign expansion with the corresponding number of 1s.

                              Equations
                              Instances For
                                theorem NatOrdinal.toSignExpansion_apply_of_lt {o₁ o₂ : NatOrdinal} (h : o₂ < o₁) :
                                (toSignExpansion o₁) o₂ = 1
                                theorem NatOrdinal.toSignExpansion_apply_of_le {o₁ o₂ : NatOrdinal} (h : o₁ ≤ o₂) :
                                (toSignExpansion o₁) o₂ = 0