Documentation

Linglib.Core.Order.GornAddress

Gorn addresses #

A GornAddress is a position in a tree, written as in [Gor67]: the list of daughter indices on the way down from the root. Addresses chain, with the root address as identity, so they form the free monoid on ℕ, and his partial ordering of addresses puts an address below those it is a head of: p ≤ q exactly when q = p * r for some r, which is divisibility. Under it the addresses form the rooted tree in which every node has a daughter for each natural number, with the order structure of Mathlib/Order/SuccPred/Tree.lean: the root 1 is least, Order.pred drops the last index, p ⊓ q is the longest common head, and strict dominance is well founded. An address is covered exactly by its immediate successors p * of i, and lies below at most one of them. Chaining on the left is an order embedding and the depth of an address is additive. The addresses of a concrete tree form a set closed under predecessors (RoseTree.validPaths); [Gor67] calls a finite such set, closed also under earlier sisters, a tree domain.

p precedes q when the two part at some address with p taking the earlier daughter. Precedence is lexicographic order between addresses neither of which dominates the other. It is a decidable strict order, it passes to dominated addresses, and any two addresses are related by dominance or by precedence.

Two addresses are left-aligned when they differ only in trailing first-daughter steps, so that the subtrees at them begin with the same leaf, which is to say that descending through first daughters from each reaches a common address. Left-alignment is a decidable equivalence relation, and left-aligned addresses lie on one branch.

Implementation notes #

The type is a structure over List ℕ, not a synonym of FreeMonoid ℕ, because lists carry the lexicographic order that precedence compares against dominance; GornAddress.toFreeMonoid is the isomorphism. Dominance unfolds to the prefix relation on the lists, and is divisibility by GornAddress.le_iff_dvd. The order is one-sided: chaining on the left is monotone, chaining on the right is not, so the addresses are not a canonically ordered monoid.

References #

structure GornAddress :

A Gorn address: the daughter indices on the way down from the root of a tree.

  • toList : List ℕ

    The daughter indices, from the root down.

Instances For
    theorem GornAddress.ext {x y : GornAddress} (toList : ↑x = ↑y) :
    x = y
    theorem GornAddress.ext_iff {x y : GornAddress} :
    x = y ↔ ↑x = ↑y
    def instDecidableEqGornAddress.decEq (x✝ x✝¹ : GornAddress) :
    Decidable (x✝ = x✝¹)
    Equations
    Instances For
      def instReprGornAddress.repr :
      GornAddress → ℕ → Std.Format
      Equations
      • instReprGornAddress.repr x✝ prec✝ = Std.Format.bracket "{ " (Std.Format.nil ++ Std.Format.text "toList" ++ Std.Format.text " := " ++ (Std.Format.nest 10 (repr ↑x✝)).group) " }"
      Instances For
        @[instance_reducible]
        Equations
        @[instance_reducible]
        instance instCoeOutGornAddressListNat :
        CoeOut GornAddress (List ℕ)

        An address is read as its list of indices wherever a list is expected.

        Equations

        Chaining #

        @[instance_reducible]

        The root address.

        Equations
        @[instance_reducible]

        Chaining: the address reached by following q from p.

        Equations
        @[simp]
        theorem GornAddress.toList_one :
        ↑1 = []
        @[simp]
        theorem GornAddress.toList_mul (p q : GornAddress) :
        ↑(p * q) = ↑p ++ ↑q
        theorem GornAddress.toList_injective :
        Function.Injective toList
        @[instance_reducible]
        Equations
        • One or more equations did not get rendered due to their size.

        The address of the ith daughter of the root.

        Equations
        Instances For
          @[simp]
          theorem GornAddress.toList_of (i : ℕ) :
          ↑(of i) = [i]
          theorem GornAddress.of_injective :
          Function.Injective of
          def GornAddress.toFreeMonoid :
          GornAddress ≃* FreeMonoid ℕ

          Addresses are the free monoid on the daughter indices.

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

            The partial ordering of addresses #

            @[instance_reducible]

            An address dominates the addresses it is a head of.

            Equations
            theorem GornAddress.le_def {p q : GornAddress} :
            p ≤ q ↔ ↑p <+: ↑q
            theorem GornAddress.le_iff_exists_mul {p q : GornAddress} :
            p ≤ q ↔ ∃ (r : GornAddress), q = p * r

            An address dominates another exactly when the other is obtained from it by chaining.

            theorem GornAddress.le_iff_dvd {p q : GornAddress} :
            p ≤ q ↔ p ∣ q

            Dominance is divisibility in the monoid of addresses.

            @[simp]
            theorem GornAddress.mk_le_mk {l m : List ℕ} :
            { toList := l } ≤ { toList := m } ↔ l <+: m
            @[instance_reducible]
            Equations
            @[instance_reducible]
            Equations
            • One or more equations did not get rendered due to their size.
            @[instance_reducible]
            Equations
            • x✝¹.instDecidableLT x✝ = decidable_of_iff (x✝¹ ≤ x✝ ∧ ¬x✝ ≤ x✝¹) ⋯
            @[instance_reducible]

            The root address is the least address.

            Equations
            @[simp]
            theorem GornAddress.bot_toList :
            ↑⊥ = []
            theorem GornAddress.le_mul_right (p q : GornAddress) :
            p ≤ p * q

            Chaining an address on the left is an order embedding of addresses.

            Equations
            Instances For
              @[simp]
              theorem GornAddress.mulLeft_apply (r p : GornAddress) :
              r.mulLeft p = r * p
              theorem GornAddress.le_mul_iff {p r s : GornAddress} :
              r ≤ s * p ↔ r ≤ s ∨ ∃ q ≤ p, s * q = r

              An address above a chained one is above the first part or is itself chained from it.

              Depth #

              The depth of an address: the number of steps from the root.

              Equations
              Instances For
                @[simp]
                @[simp]
                theorem GornAddress.depth_of (i : ℕ) :
                (of i).depth = 1
                @[simp]
                theorem GornAddress.depth_mul (p q : GornAddress) :
                (p * q).depth = p.depth + q.depth
                theorem GornAddress.depth_eq_zero {p : GornAddress} :
                p.depth = 0 ↔ p = 1

                Heads #

                The addresses dominating an address, from the root down to the address itself.

                Equations
                Instances For
                  @[simp]
                  theorem GornAddress.mem_inits {p q : GornAddress} :
                  q ∈ p.inits ↔ q ≤ p
                  @[instance_reducible]
                  instance GornAddress.instLocallyFiniteOrderBot :
                  LocallyFiniteOrderBot GornAddress

                  The addresses at or above an address are its heads, finitely many.

                  Equations

                  The head of an address of depth n, or the address itself if it is shallower.

                  Equations
                  Instances For
                    @[simp]
                    theorem GornAddress.take_toList (n : ℕ) (p : GornAddress) :
                    ↑(take n p) = List.take n ↑p
                    theorem GornAddress.take_le (n : ℕ) (p : GornAddress) :
                    take n p ≤ p
                    @[simp]
                    theorem GornAddress.depth_take (n : ℕ) (p : GornAddress) :
                    (take n p).depth = min n p.depth
                    theorem GornAddress.take_depth_of_le {p q : GornAddress} (h : q ≤ p) :
                    take q.depth p = q

                    The relative address of q with respect to p: what remains of q below p.

                    Equations
                    Instances For
                      @[simp]
                      theorem GornAddress.mul_relativeTo (p r : GornAddress) :
                      (p * r).relativeTo p = r
                      theorem GornAddress.mul_relativeTo_of_le {p q : GornAddress} (h : p ≤ q) :
                      p * q.relativeTo p = q

                      Parents #

                      The parent of an address drops its last index. The root is its own parent.

                      Equations
                      • p.parent = { toList := (↑p).dropLast }
                      Instances For
                        @[simp]
                        theorem GornAddress.parent_toList (p : GornAddress) :
                        ↑p.parent = (↑p).dropLast
                        @[simp]
                        @[simp]
                        theorem GornAddress.parent_mul_of (p : GornAddress) (i : ℕ) :
                        (p * of i).parent = p
                        theorem GornAddress.parent_mul {p : GornAddress} (s : GornAddress) (hp : p ≠ 1) :
                        (s * p).parent = s * p.parent
                        def GornAddress.last? (p : GornAddress) :
                        Option ℕ

                        The last index of an address: which daughter of its parent it is. The root has none.

                        Equations
                        • p.last? = (↑p).getLast?
                        Instances For
                          @[simp]
                          theorem GornAddress.last?_one :
                          last? 1 = none
                          @[simp]
                          theorem GornAddress.last?_mul_of (p : GornAddress) (i : ℕ) :
                          (p * of i).last? = some i
                          theorem GornAddress.exists_eq_parent_mul_of {p : GornAddress} (hp : p ≠ 1) :
                          ∃ (i : ℕ), p = p.parent * of i

                          An address other than the root is a daughter of its parent.

                          theorem GornAddress.le_parent_of_lt {p q : GornAddress} (h : p < q) :
                          p ≤ q.parent
                          @[instance_reducible]
                          Equations
                          @[simp]
                          theorem GornAddress.pred_eq_parent (p : GornAddress) :
                          Order.pred p = p.parent

                          Immediate successors #

                          theorem GornAddress.lt_mul_of (p : GornAddress) (i : ℕ) :
                          p < p * of i
                          theorem GornAddress.covBy_mul_of (p : GornAddress) (i : ℕ) :
                          p ⋖ p * of i
                          theorem GornAddress.covBy_iff {p q : GornAddress} :
                          p ⋖ q ↔ ∃ (i : ℕ), q = p * of i

                          An address is covered exactly by its immediate successors.

                          theorem GornAddress.of_inj_of_mul_of_le {p q : GornAddress} {i j : ℕ} (hi : p * of i ≤ q) (hj : p * of j ≤ q) :
                          i = j

                          An address lies below at most one immediate successor of an address.

                          theorem GornAddress.disjoint_Ici_mul_of (p : GornAddress) {i j : ℕ} (h : i ≠ j) :
                          Disjoint (Set.Ici (p * of i)) (Set.Ici (p * of j))

                          The addresses below distinct immediate successors are disjoint.

                          Least common ancestors #

                          @[instance_reducible]

                          The meet of two addresses is their longest common head, the deepest address dominating both.

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

                          Linear precedence #

                          p precedes q when, at some common address, p continues into an earlier daughter than q.

                          Equations
                          Instances For
                            theorem GornAddress.Precedes.lt {p q : GornAddress} (h : p.Precedes q) :
                            ↑p < ↑q

                            An address comes lexicographically before every address it precedes.

                            theorem GornAddress.Precedes.not_le {p q : GornAddress} (h : p.Precedes q) :
                            ¬p ≤ q
                            theorem GornAddress.Precedes.not_ge {p q : GornAddress} (h : p.Precedes q) :
                            ¬q ≤ p
                            theorem GornAddress.Precedes.mono {p q p' q' : GornAddress} (h : p.Precedes q) (hp : p ≤ p') (hq : q ≤ q') :
                            p'.Precedes q'
                            theorem GornAddress.Precedes.mul_left {p q : GornAddress} (s : GornAddress) (h : p.Precedes q) :
                            (s * p).Precedes (s * q)

                            Precedence is preserved by chaining on the left.

                            theorem GornAddress.Precedes.cons {p q : GornAddress} (i : ℕ) (h : p.Precedes q) :
                            { toList := i :: ↑p }.Precedes { toList := i :: ↑q }
                            theorem GornAddress.precedes_cons_of_lt {i j : ℕ} (hij : i < j) (p q : GornAddress) :
                            { toList := i :: ↑p }.Precedes { toList := j :: ↑q }
                            theorem GornAddress.precedes_iff_lt_and_not_le {p q : GornAddress} :
                            p.Precedes q ↔ ↑p < ↑q ∧ ¬p ≤ q

                            p precedes q exactly when p comes lexicographically before q without dominating it.

                            @[instance_reducible]
                            instance GornAddress.instDecidablePrecedes (p q : GornAddress) :
                            Decidable (p.Precedes q)
                            Equations
                            theorem GornAddress.Precedes.trans {p q r : GornAddress} (h₁ : p.Precedes q) (h₂ : q.Precedes r) :
                            theorem GornAddress.Precedes.trichotomy (p q : GornAddress) :
                            p ≤ q ∨ q ≤ p ∨ p.Precedes q ∨ q.Precedes p

                            Any two addresses are related by dominance or by precedence.

                            theorem GornAddress.precedes_mul_of_iff {p : GornAddress} {i j : ℕ} :
                            (p * of i).Precedes (p * of j) ↔ i < j

                            Two daughters of an address stand in precedence exactly as their indices are ordered.

                            Left edges #

                            Two positions are left-aligned when their addresses agree once trailing first-daughter steps are dropped, so that the subtrees at them begin with the same leaf.

                            Equations
                            • p.LeftAligned q = (List.dropWhile (fun (x : ℕ) => x == 0) (↑p).reverse = List.dropWhile (fun (x : ℕ) => x == 0) (↑q).reverse)
                            Instances For
                              theorem GornAddress.LeftAligned.trans {p q r : GornAddress} (h₁ : p.LeftAligned q) (h₂ : q.LeftAligned r) :
                              theorem GornAddress.leftAligned_iff_exists {p q : GornAddress} :
                              p.LeftAligned q ↔ ∃ (j : ℕ) (k : ℕ), ↑p ++ List.replicate j 0 = ↑q ++ List.replicate k 0

                              Positions are left-aligned exactly when descending through first daughters from each reaches a common position.

                              theorem GornAddress.LeftAligned.le_or_ge {p q : GornAddress} (h : p.LeftAligned q) :
                              p ≤ q ∨ q ≤ p