Documentation

Linglib.Core.ModelTheory.ManySorted.Semantics

Realization of many-sorted terms #

A term has a value in a structure, given the values of its variables, and the value of a substituted term is the value of the term at the values of what was substituted. A relation between the domains of two structures that every function respects holds between the two values of every term.

Main definitions #

def ManySorted.Signature.Place.val {S : Type u} {D : S → Type x} {σ : Signature S} {s : S} :
σ.Place s → Interpret D σ → D s

The argument at a place, among the arguments of a shape.

Equations
Instances For
    def ManySorted.Signature.LiftRel {S : Type u} {D : S → Type x} {D' : S → Type x'} (R : (s : S) → D s → D' s → Prop) (σ : Signature S) :
    Interpret D σ → Interpret D' σ → Prop

    A relation between two families of domains holds between the arguments of a shape when it holds between them place by place.

    Equations
    Instances For
      def ManySorted.Language.Term.realize {S : Type u} {L : Language S} {α : S → Type w} {D : S → Type x} (M : L.Structure D) (ρ : {s : S} → α s → D s) {σ : Signature S} :
      L.Term α σ → Signature.Interpret D σ

      The value of a term in a structure, given the values of its variables.

      Equations
      Instances For
        theorem ManySorted.Language.Term.realize_bind {S : Type u} {L : Language S} {α : S → Type w} {β : S → Type w'} {D : S → Type x} (M : L.Structure D) (ρ : {s : S} → β s → D s) {σ : Signature S} (t : L.Term α σ) (θ : {s : S} → α s → L.Term β (Signature.of s)) :
        realize M (fun {s : S} => ρ) (t.bind fun {s : S} => θ) = realize M (fun {s : S} (x : α s) => realize M (fun {s : S} => ρ) (θ x)) t
        theorem ManySorted.Language.Term.realize_proj {S : Type u} {L : Language S} {α : S → Type w} {D : S → Type x} (M : L.Structure D) (ρ : {s : S} → α s → D s) {σ : Signature S} {s : S} (t : L.Term α σ) (p : σ.Place s) :
        realize M (fun {s : S} => ρ) (proj p t) = p.val (realize M (fun {s : S} => ρ) t)
        theorem ManySorted.Language.Term.realize_places {S : Type u} {L : Language S} {D : S → Type x} (M : L.Structure D) (σ : Signature S) (args : Signature.Interpret D σ) :
        realize M (fun {s : S} (p : σ.Place s) => p.val args) (places σ) = args

        The term of argument places takes the arguments as its value.

        structure ManySorted.Language.Structure.IsLogicalRel {S : Type u} {L : Language S} {D : S → Type x} {D' : S → Type x'} (M : L.Structure D) (M' : L.Structure D') (R : (s : S) → D s → D' s → Prop) :

        A logical relation between two structures for one language: a relation between their domains that every function respects, taking related arguments to related values.

        Instances For
          theorem ManySorted.Language.Structure.IsLogicalRel.realize {S : Type u} {L : Language S} {α : S → Type w} {D : S → Type x} {D' : S → Type x'} {M : L.Structure D} {M' : L.Structure D'} {R : (s : S) → D s → D' s → Prop} (h : M.IsLogicalRel M' R) {ρ : {s : S} → α s → D s} {ρ' : {s : S} → α s → D' s} (hρ : ∀ {s : S} (a : α s), R s (ρ a) (ρ' a)) {σ : Signature S} (t : L.Term α σ) :
          Signature.LiftRel R σ (Term.realize M (fun {s : S} => ρ) t) (Term.realize M' (fun {s : S} => ρ') t)

          The basic lemma of logical relations: a logical relation holds between the two values of a term whose variables have related values.

          theorem ManySorted.Language.Structure.IsLogicalRel.sum {S : Type u} {L : Language S} {D : S → Type x} {D' : S → Type x'} {M : L.Structure D} {M' : L.Structure D'} {R : (s : S) → D s → D' s → Prop} {L' : Language S} {N : L'.Structure D} {N' : L'.Structure D'} (h : M.IsLogicalRel M' R) (h' : N.IsLogicalRel N' R) :
          (M.sum N).IsLogicalRel (M'.sum N') R

          Logical relations for two languages make one for their sum.

          theorem ManySorted.Language.Structure.IsLogicalRel.mk₂ {S : Type u} {D : S → Type x} {D' : S → Type x'} {R : (s : S) → D s → D' s → Prop} {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} {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} (hu : ∀ {a b : S} (f : U a b) (x : D a) (x' : D' a), R a x x' → R b (unary f x) (unary' f x')) (hb : ∀ {a b c : S} (f : B a b c) (x : D a) (x' : D' a) (y : D b) (y' : D' b), R a x x' → R b y y' → R c (binary f x y) (binary' f x' y')) :
          (Structure.mk₂ (fun {a b : S} => unary) fun {a b c : S} => binary).IsLogicalRel (Structure.mk₂ (fun {a b : S} => unary') fun {a b c : S} => binary') R

          A relation that the unary and the binary functions respect is a logical relation between two structures for a language of unary and binary symbols.

          theorem ManySorted.Language.Structure.IsLogicalRel.pi {S : Type u} {L : Language S} {D : S → Type x} {D' : S → Type x'} {M : L.Structure D} {M' : L.Structure D'} {R : (s : S) → D s → D' s → Prop} {A : Type w} {A' : Type w'} (h : M.IsLogicalRel M' R) (Q : A → A' → Prop) :
          (Structure.pi A M).IsLogicalRel (Structure.pi A' M') fun (s : S) (v : A → D s) (v' : A' → D' s) => ∀ (g : A) (g' : A'), Q g g' → R s (v g) (v' g')

          A logical relation between two structures is one between the structures on values that depend on a parameter, at related values of the parameters.