Documentation

Linglib.Core.ModelTheory.ManySorted.Basic

Many-sorted algebraic languages and structures #

A many-sorted language has function symbols typed by the sorts of their arguments and the sort of their result, where a first-order language of mathlib has symbols of each arity. The arguments of a symbol have a shape, a Signature: none, one of a sort, or a pair of shapes, and a structure gives each symbol a function from the product of domains that its shape describes.

Main definitions #

Implementation notes #

The definitions follow the many-sorted generalization of FirstOrder.Language being developed outside mathlib, in which a shape is a binary tree of sorts read as a nested product, so that a binary symbol takes a pair. Only function symbols are defined: a language here is what that development calls algebraic. The domains are a parameter of a structure.

inductive ManySorted.Signature (S : Type u) :

The shape of a symbol's arguments over sorts S: none, one of a sort, or a pair of shapes.

Instances For
    @[reducible, inline]
    abbrev ManySorted.Signature.Interpret {S : Type u} (X : S → Type w) :
    Signature S → Type w

    The arguments of a shape over the domains X: a nested product.

    Equations
    Instances For
      structure ManySorted.Language (S : Type u) :
      Type (max u (v + 1))

      A many-sorted algebraic language over sorts S: the function symbols with arguments of a given shape and a result of a given sort.

      • Functions : Signature S → S → Type v

        The function symbols with arguments of shape σ and result of sort t.

      Instances For
        class ManySorted.Language.Structure {S : Type u} (L : Language S) (D : S → Type w) :
        Type (max (max u v) w)

        A structure for a language over the domains D: a function for each symbol.

        Instances
          @[reducible, inline]
          abbrev ManySorted.Language.Unary {S : Type u} (L : Language S) (a b : S) :

          The symbols of a language with one argument.

          Equations
          Instances For
            @[reducible, inline]
            abbrev ManySorted.Language.Binary {S : Type u} (L : Language S) (a b c : S) :

            The symbols of a language with two arguments.

            Equations
            Instances For

              Languages of unary and binary symbols #

              @[reducible]
              def ManySorted.Language.mk₂ {S : Type u} (U : S → S → Type v) (B : S → S → S → Type v) :

              The language whose symbols are those of two families, of one argument and of two.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                @[instance_reducible]
                def ManySorted.Language.Structure.mk₂ {S : Type u} {D : S → Type w} {U : S → S → Type v} {B : S → S → S → Type v} (unary : {a b : S} → U a b → D a → D b) (binary : {a b c : S} → B a b c → D a → D b → D c) :

                A structure for a language of unary and binary symbols, from a function for each.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  @[simp]
                  theorem ManySorted.Language.Structure.funMap_mk₂_unary {S : Type u} {D : S → Type w} {U : S → S → Type v} {B : S → S → S → Type v} (unary : {a b : S} → U a b → D a → D b) (binary : {a b c : S} → B a b c → D a → D b → D c) {a b : S} (f : U a b) (x : D a) :
                  funMap f x = unary f x
                  @[simp]
                  theorem ManySorted.Language.Structure.funMap_mk₂_binary {S : Type u} {D : S → Type w} {U : S → S → Type v} {B : S → S → S → Type v} (unary : {a b : S} → U a b → D a → D b) (binary : {a b c : S} → B a b c → D a → D b → D c) {a b c : S} (f : B a b c) (p : D a × D b) :
                  funMap f p = binary f p.fst p.snd

                  The sum of two languages #

                  inductive ManySorted.Language.Sum {S : Type u} (L L' : Language S) (σ : Signature S) (t : S) :

                  A symbol of one of two languages. It is indexed by the languages, where _root_.Sum would be indexed by their types of symbols, so that a statement about the symbols of any two languages applies to two given ones whatever their types of symbols unfold to.

                  Instances For
                    @[reducible]
                    def ManySorted.Language.sum {S : Type u} (L L' : Language S) :

                    The sum of two languages, with the symbols of both.

                    Equations
                    Instances For
                      @[instance_reducible]
                      def ManySorted.Language.Structure.sum {S : Type u} {L L' : Language S} {D : S → Type w} (M : L.Structure D) (M' : L'.Structure D) :
                      (L.sum L').Structure D

                      A structure for the sum of two languages, from a structure for each.

                      Equations
                      • One or more equations did not get rendered due to their size.
                      Instances For
                        @[instance_reducible]
                        instance ManySorted.Language.instStructureSum {S : Type u} {L L' : Language S} {D : S → Type w} [M : L.Structure D] [M' : L'.Structure D] :
                        (L.sum L').Structure D
                        Equations
                        @[simp]
                        theorem ManySorted.Language.Structure.funMap_sum_inl {S : Type u} {L L' : Language S} {D : S → Type w} (M : L.Structure D) (M' : L'.Structure D) {σ : Signature S} {t : S} (f : L.Functions σ t) (x : Signature.Interpret D σ) :
                        funMap (Sum.inl f) x = funMap f x
                        @[simp]
                        theorem ManySorted.Language.Structure.funMap_sum_inr {S : Type u} {L L' : Language S} {D : S → Type w} (M : L.Structure D) (M' : L'.Structure D) {σ : Signature S} {t : S} (f : L'.Functions σ t) (x : Signature.Interpret D σ) :
                        funMap (Sum.inr f) x = funMap f x

                        Structures over a parameter #

                        def ManySorted.Signature.Interpret.app {S : Type u} {D : S → Type w} {A : Type x} {σ : Signature S} :
                        Interpret (fun (s : S) => A → D s) σ → A → Interpret D σ

                        The arguments of a shape at one value of a parameter.

                        Equations
                        Instances For
                          @[simp]
                          theorem ManySorted.Signature.Interpret.app_of {S : Type u} {D : S → Type w} {A : Type x} {s : S} (f : A → D s) (g : A) :
                          app f g = f g
                          @[simp]
                          theorem ManySorted.Signature.Interpret.app_prod {S : Type u} {D : S → Type w} {A : Type x} {σ τ : Signature S} (p : Interpret (fun (s : S) => A → D s) (σ.prod τ)) (g : A) :
                          p.app g = (p.fst.app g, p.snd.app g)
                          @[instance_reducible]
                          def ManySorted.Language.Structure.pi {S : Type u} {L : Language S} {D : S → Type w} (A : Type x) (M : L.Structure D) :
                          L.Structure fun (s : S) => A → D s

                          The structure on values that depend on a parameter: each symbol applies at one value of the parameter.

                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            theorem ManySorted.Language.Structure.funMap_pi {S : Type u} {L : Language S} {D : S → Type w} {A : Type x} (M : L.Structure D) {σ : Signature S} {t : S} (f : L.Functions σ t) (p : Signature.Interpret (fun (s : S) => A → D s) σ) :
                            funMap f p = fun (g : A) => funMap f (p.app g)
                            @[simp]
                            theorem ManySorted.Language.Structure.funMap_pi_unary {S : Type u} {L : Language S} {D : S → Type w} {A : Type x} (M : L.Structure D) {a b : S} (f : L.Unary a b) (x : A → D a) :
                            funMap f x = fun (g : A) => funMap f (x g)
                            @[simp]
                            theorem ManySorted.Language.Structure.funMap_pi_binary {S : Type u} {L : Language S} {D : S → Type w} {A : Type x} (M : L.Structure D) {a b c : S} (f : L.Binary a b c) (p : (A → D a) × (A → D b)) :
                            funMap f p = fun (g : A) => funMap f (p.fst g, p.snd g)

                            Listing the symbols that apply #

                            class ManySorted.Language.LocallyFinite {S : Type u} (L : Language S) :
                            Type (max u v)

                            A language is locally finite when the symbols that take arguments of a given shape can be listed.

                            • symbols (σ : Signature S) : List ((t : S) × L.Functions σ t)

                              The symbols that take arguments of shape σ.

                            • mem_symbols {σ : Signature S} {t : S} (f : L.Functions σ t) : ⟨t, f⟩ ∈ symbols σ

                              Every symbol is listed.

                            Instances
                              @[instance_reducible]
                              def ManySorted.Language.LocallyFinite.mk₂ {S : Type u} {U : S → S → Type v} {B : S → S → S → Type v} (us : (a : S) → List ((b : S) × U a b)) (bs : (a b : S) → List ((c : S) × B a b c)) (hu : ∀ {a b : S} (f : U a b), ⟨b, f⟩ ∈ us a) (hb : ∀ {a b c : S} (f : B a b c), ⟨c, f⟩ ∈ bs a b) :

                              A language of unary and binary symbols is locally finite when the symbols of each family that apply can be listed.

                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For
                                @[instance_reducible]
                                Equations
                                • One or more equations did not get rendered due to their size.
                                @[simp]
                                theorem ManySorted.Language.LocallyFinite.symbols_sum {S : Type u} {L L' : Language S} [L.LocallyFinite] [L'.LocallyFinite] (σ : Signature S) :
                                symbols σ = List.map (fun (x : (t : S) × L.Functions σ t) => match x with | ⟨t, f⟩ => ⟨t, Sum.inl f⟩) (symbols σ) ++ List.map (fun (x : (t : S) × L'.Functions σ t) => match x with | ⟨t, f⟩ => ⟨t, Sum.inr f⟩) (symbols σ)