Simulation between many-sorted structures #
One structure simulates another over the same domains when each function of the second is the value of a term of the first over the argument places, a term operation. Then every term of the second has a term of the first with its value: the clone of term operations of the second is included in that of the first.
Main definitions #
ManySorted.Language.Structure.Simulates: every function of one structure is a term operation of another.
structure
ManySorted.Language.Structure.Simulates
{S : Type u}
{L L' : Language S}
{D : S → Type x}
(M' : L'.Structure D)
(M : L.Structure D)
:
M' simulates M when every function of M is the value in M' of a term over its
argument places.
- funMap {σ : Signature S} {t : S} (f : L.Functions σ t) : ∃ (u : L'.Term σ.Place (Signature.of t)), ∀ (args : Signature.Interpret D σ), Term.realize M' (fun {s : S} (p : σ.Place s) => p.val args) u = Structure.funMap f args
Each function is a term operation.
Instances For
theorem
ManySorted.Language.Structure.Simulates.exists_term
{S : Type u}
{L L' : Language S}
{α : S → Type w}
{D : S → Type x}
{M : L.Structure D}
{M' : L'.Structure D}
(h : M'.Simulates M)
{σ : Signature S}
(t : L.Term α σ)
:
∃ (t' : L'.Term α σ), ∀ (ρ : {s : S} → α s → D s), Term.realize M' (fun {s : S} => ρ) t' = Term.realize M (fun {s : S} => ρ) t
Whatever term the simulated language has, the simulating one has a term with its value, whatever the values of the variables.