representation, ∞-representation?
symmetric monoidal (∞,1)-category of spectra
natural deduction metalanguage, practical foundations
type theory (dependent, intensional, observational type theory, homotopy type theory)
computational trinitarianism = propositions as types +programs as proofs +relation type theory/category theory
logic | category theory | type theory |
---|---|---|
true | terminal object/(-2)-truncated object | h-level 0-type/unit type |
proposition(-1)-truncated objecth-proposition, mere proposition
proofgeneralized elementprogram
cut rulecomposition of classifying morphisms / pullback of display mapssubstitution
cut elimination for implicationcounit for hom-tensor adjunctionbeta reduction
introduction rule for implicationunit for hom-tensor adjunctioneta conversion
logical conjunctionproductproduct type
disjunctioncoproduct ((-1)-truncation of)sum type (bracket type of)
implicationinternal homfunction type
negationinternal hom into initial objectfunction type into empty type
universal quantificationdependent productdependent product type
existential quantificationdependent sum ((-1)-truncation of)dependent sum type (bracket type of)
equivalencepath space objectidentity type
equivalence classquotientquotient type
inductioncolimitinductive type, W-type, M-type
higher inductionhigher colimithigher inductive type
completely presented setdiscrete object/0-truncated objecth-level 2-type/preset/h-set
setinternal 0-groupoidBishop set/setoid
universeobject classifiertype of types
modalityclosure operator, (idemponent) monadmodal type theory, monad (in computer science)
linear logic(symmetric, closed) monoidal categorylinear type theory/quantum computation
proof netstring diagramquantum circuit
(absence of) contraction rule(absence of) diagonalno-cloning theorem
synthetic mathematicsdomain specific embedded programming language
</table>
A mathematical structure is essentially algebraic if its definition involves partially defined operations satisfying equational laws, where the domain of any given operation is a subset where various other operations happen to be equal. An actual algebraic theory is one where all operations are total functions.
The most familiar example may be the (strict) notion of category: a small category consists of a set $C_0$ of objects, a set $C_1$ of morphisms, source and target maps $s,t : C_1 \to C_0$ and so on, but composition is only defined for pairs of morphisms where the source of one happens to equal the target of the other.
Essentially algebraic theories can be understood through category theory at least when they are finitary, so that all operations have only finitely many arguments. This gives a generalisation of Lawvere theories, which describe finitary algebraic theories.
As the domains of the operations are given by the solutions to equations, they may be understood using the notion of equalizer. So, just as a Lawvere theory is defined using a category with finite products, a finitary essentially algebraic theory is defined using a category with finite limits — or in other words, finite products and also equalizers (from which all other finite limits, including pullbacks, may be derived).
As alluded to above, the most concise and elegant definition is through category theory. The traditional definition is this:
An essentially algebraic theory or finite limits theory is a category that is finitely complete, i.e., has all finite limits. A model of an essentially algebraic theory $T$ is a functor
that is left exact, i.e., preserves all finite limits. A homomorphism of models is a natural transformation
between left exact functors $F, F' : T \to Set$. Models of an essentially algebraic theory $T$ and the homomorphisms between them form a category $Mod(T) = Lex(T, Set)$.
More generally, for any category with finite limits $X$, we can define the category of models of $T$ in $X$, $Lex(T, X)$, which has left exact functors $F: T \to X$ as objects and natural transformations between these as morphisms.
However, the finiteness restriction on the limits above is not part of the core concept of an ‘essentially algebraic’ structure, so one may prefer to call a category with finite limits a finitary essentially algebraic theory. We do this in what follows.
A more traditional syntactic definition (following Adámek–Rosicky; see the references below) is as follows:
An essentially algebraic theory is a quadruple
where $\Sigma$ is a many-sorted signature consisting only of operation symbols, $E$ is a set of $\Sigma$-equations, $\Sigma_t \subseteq \Sigma$ is a set of operation symbols called “total”, and $Def$ is a function which assigns, to each operation $\sigma \in \Sigma - \Sigma_t$ of type $\prod_{i \in I} s_i \to s$, a set $Def(\sigma)$ of $\Sigma_t$-equations involving only variables $x_i \in Var(s_i)$.
A (set-theoretic) model $M$ of a theory $\Gamma$ assigns to each sort $s$ a set $M(s)$, to each operation symbol $\sigma: \prod_{i \in I} s_i \to s$ of $\Sigma$ a partial function
such that
For each $\sigma \in \Sigma_t$ the function $M(\sigma)$ is a total function;
For each $\sigma \in \Sigma - \Sigma_t$ of type $\prod_{i \in I} s_i \to s$, and each $I$-tuple
$M(\sigma)(a)$ is defined if and only if all the equations in $Def(\sigma)$ are satisfied at the argument $a$.
All the equations of $E$ are satisfied (i.e., are interpreted as equations between partial functions).
Homomorphisms of models $\theta: M \to M'$ are defined in the standard way: a collection of functions $\theta(s): M(s) \to M'(s)$ for each sort of the signature $\Sigma$ which are compatible with the $M(\sigma), M'(\sigma)$ in the evident way.
The point is that (in the finitary case) either notion of theory may be used to specify the same category of models, and that
Categories of models of finitary essentially algebraic theories are precisely equivalent to locally finitely presentable categories. These are equivalent to categories of models of finite limit sketches.
A (multisorted) Lawvere theory $T$ is the same thing (has the same models) as a finitary essentially algebraic theory in which all operations are total. If $C_T$ is the opposite of the category of finitely presented $T$-algebras, then the category of models is equivalent to $Lex(C_T, Set)$.
As mentioned above, categories are models of a finitary essentially algebraic theory.
An equational Horn theory is essentially algebraic, but not all essentially algebraic theories are equational Horn theories. Perhaps surprisingly, $Cat$ is not the category of models of any equational Horn theory, nor is even the category $Pos$ of posets. See this paper by Barr for a proof.
algebraic theory / Lawvere theory / essentially algebraic theory
Freyd first introduced essentially algebraic theories here:
Peter Freyd, Aspects of Topoi, Bull. Austr. Math. Soc. 7, pp. 1–76, 467–80. 1972 (pdf)
Ji?í Adámek?, M. Hébert, Ji?í Rosický?, On essentially algebraic theories and their generalizations, Algebra Universalis, August 1999, Volume 41, Issue 3, pp 213-227
Ji?í Adámek?, Ji?í Rosický?, section 3.D of Locally presentable and accessible categories, Cambridge University Press, (1994)
A nice equivalent formulation can be found in
Last revised on June 11, 2018 at 08:08:51. See the history of this page for a list of all contributions to it.