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 #
ManySorted.Signature: the shape of a symbol's arguments.ManySorted.Signature.Interpret: the arguments of a shape, over a family of domains.ManySorted.Language: function symbols by argument shape and result sort.ManySorted.Language.Structure: a function for each symbol, over a family of domains.ManySorted.Language.mk₂: the language of a family of unary and a family of binary symbols.ManySorted.Language.sum: the sum of two languages, with the function a symbol of one denotes in it.ManySorted.Language.Structure.pi: the structure on values that depend on a parameter.ManySorted.Language.LocallyFinite: the symbols that take given arguments can be listed.
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.
The shape of a symbol's arguments over sorts S: none, one of a sort, or a pair of shapes.
- nil
{S : Type u}
: Signature S
No arguments.
- of
{S : Type u}
(s : S)
: Signature S
One argument of a sort.
- prod
{S : Type u}
(σ τ : Signature S)
: Signature S
The arguments of one shape paired with those of another.
Instances For
The arguments of a shape over the domains X: a nested product.
Equations
- ManySorted.Signature.Interpret X ManySorted.Signature.nil = PUnit.{?u.1 + 1}
- ManySorted.Signature.Interpret X (ManySorted.Signature.of s) = X s
- ManySorted.Signature.Interpret X (σ.prod τ) = (ManySorted.Signature.Interpret X σ × ManySorted.Signature.Interpret X τ)
Instances For
A many-sorted algebraic language over sorts S: the function symbols with arguments of a
given shape and a result of a given sort.
The function symbols with arguments of shape
σand result of sortt.
Instances For
A structure for a language over the domains D: a function for each symbol.
The function a symbol denotes.
Instances
The symbols of a language with one argument.
Equations
- L.Unary a b = L.Functions (ManySorted.Signature.of a) b
Instances For
The symbols of a language with two arguments.
Equations
- L.Binary a b c = L.Functions ((ManySorted.Signature.of a).prod (ManySorted.Signature.of b)) c
Instances For
Languages of unary and binary symbols #
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
The sum of two languages #
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.
- inl
{S : Type u}
{L L' : Language S}
{σ : Signature S}
{t : S}
(f : L.Functions σ t)
: L.Sum L' σ t
A symbol of the first language.
- inr
{S : Type u}
{L L' : Language S}
{σ : Signature S}
{t : S}
(f : L'.Functions σ t)
: L.Sum L' σ t
A symbol of the second language.
Instances For
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
Structures over a parameter #
The arguments of a shape at one value of a parameter.
Instances For
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
Listing the symbols that apply #
A language is locally finite when the symbols that take arguments of a given shape can be listed.
The symbols that take arguments of shape
σ.Every symbol is listed.
Instances
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
Equations
- One or more equations did not get rendered due to their size.