Definition. Types over an Algebraic Theory

Fix a finitary algebraic theory 𝒯︀: sorts 𝑆, a signature 𝜎, equations, and a set 𝑉 of generators. Write 𝑴 for the free 𝒯︀-model on 𝑉 and |𝑴|𝑠 for its carrier at sort 𝑠.

A 𝒯︀-type of sort 𝑠 is a family 𝐴:|𝑴|𝑠→𝖳𝗒𝗉𝖾.

For 𝒯︀-types 𝐴 and 𝐡 of sort 𝑠 we have the additives, defined pointwise,

(𝐴&𝐡)(π‘š)=𝐴(π‘š)×𝐡(π‘š),(π΄βŠ•π΅)(π‘š)=𝐴(π‘š)+𝐡(π‘š),(𝐴⇒𝐡)(π‘š)=𝐴(π‘š)→𝐡(π‘š),

along with ⊀, βŠ₯, and their indexed versions.

Each operation π‘œ:𝑠0,…,π‘ π‘›βˆ’1→𝑠 of 𝒯︀ gives a multiplicative, defined by Day convolution,

βŠ—[π‘œ](𝐴0,…,π΄π‘›βˆ’1)(π‘š)=Ξ£π‘œ(π‘š0,…,π‘šπ‘›βˆ’1)=π‘šΓ—Ξ π‘–<𝑛𝐴𝑖(π‘šπ‘–).

Each lifted operation also has closed structure: a residual in each of its arguments. Day algebras [1] give a more general convolutional definition.

When 𝒯︀ is the theory of monoids and 𝑉 is an alphabet, 𝒯︀-types are formal grammars. Multiplication gives βŠ—, the unit gives πœ€, and we recover Lambek𝙳.

References

Day algebras β†—
theory-type definition entries/parsing/theory-type.hel