nLab
theory

Idea

A theory is a collection of axioms in some logic.

Definition

There are several different viewpoint on theories:

• The

  syntactic view

  is that the theory itself consists of the set of formulas in the first order language $\mathrm{Lang}(\Sigma )$ of a signature $\Sigma$ together with the set of logical consequences (aka theorems) of the axioms in $A$, relative to (some specified) fragment of first-order logic.

• The

  semantic view

  is that the theory is given by the class of its models appropriate to that fragment of logic. Gödel’s completeness theorem is that a sentence in $𝒯$ is a theorem iff it is satisfied in every model.

• The

  categorical view

  is that the logical formalism of a theory $𝒯$ can frequently be embodied in a syntactic category of terms $C_{𝒯}$, so that models of a theory $𝒯$ are identified with functors

  $$C_{𝒯}\to \mathrm{Set}$$C_{\mathcal{T}} \to Set

  that preserve some (typically property-like) structures on $C_{𝒯}$, such as certain classes of colimits or of limits, pertinent to the fragment of logic at hand. Then a completeness theorem would be the statement that the canonical map

  $$C_{𝒯}\to \prod _{\mathrm{models}F\mathrm{in}\mathrm{Set}}\mathrm{Set}$$C_{\mathcal{T}} \to \prod_{models F in Set} Set

  is a full faithful embedding (one that preserves all relevant logical structure). For this reason, completeness theorems are also known as embedding theorems.

Hm, is that the way it should be said?

In fact, the notion of model can be generalized away from $\mathrm{Set}$ to more general categories, namely those that have enough structure to “internalize” the fragment of logic at hand. From this very general point of view on model, the syntactic category $C_{𝒯}$ is the generic or universal model for $𝒯$, and if we simply call $C_{𝒯}$ the theory, then models and theories are placed on the same footing.

In this article we mostly consider the categorical view on “theory”.

Syntactic view

Definition

In first-order logic, a theory $𝒯$ is presented by

1. a signature $\Sigma$, specifying the allowed types of variables and the functions and relations between these;

2. a set $A$ of sequents of formula?s in this signature, called the axioms of the theory: expressed in the first-order language $\mathrm{Lang}(\Sigma )$ with equality generated by $\Sigma$

For instance (Johnstone, def. D1.1.6).

Semantic view

(…)

Categorical view

(…)

• categorical semantics

(…)

Examples

Classes of theories

There are many different kinds of “theory” depending on the strength of the “logic”: a by-no-means complete list includes

• equational logic?,

• Horn logic?,

• essentially algebraic logic?,

• geometric logic,

• regular logic,

• exact logic?,

• extensive logic?,

• coherent logic,

• first-order logic (aka pretopos logic),

and corresponding theories for these logics.

• essentially algebraic theory

• generalized algebraic theory

• algebraic theory

  • commutative algebraic theory

  • finitary algebraic theory: Lawvere theory

    • Fermat theory

Hierarchy of theories: cartesian, regular, coherent, geometric

There is a hierarchy of theories that can be interpreted in the internal logic of a hierarchy of types of categories. Since predicates in the internal logic are represented by subobjects, in order to interpret any connective or quantifier in the internal logic, one needs a corresponding operation on subobjects to exist in the category in question, and be well-behaved. For instance:

• cartesian theories Since $\wedge$ and $\top$ are represented by intersections and identities (top elements), these can be interpreted in any lex category. Theories involving only these are cartesian theories.

• regular theories Since $\exists$ is represented by the image of a subobject, it can be interpreted in any regular category. Theories involving only $\wedge$, $\top$, and $\exists$ are regular theories.

• coherent theories Since $\vee$ and $\perp$ are represented by union and bottom elements, these can be interpreted in any coherent category. Theories which add these to regular logic are called coherent theories.

• geometric theories Finally, theories which also involve infinitary $\bigvee$, which is again represented by an infinitary union, can be interpreted in infinitary coherent categories, aka geometric categories. These are geometric theories.

Note that the axioms of one of these theories are actually of the form

$$\phi {⊢}_{\stackrel{\rightharpoonup }{x}}\psi$$\varphi \vdash_{\vec{x}} \psi

where $\phi$ and $\psi$ are formulas involving only the specified connectives and quantifiers, $⊢$ means entailment, and $\stackrel{\rightharpoonup }{x}$ is a context. Such an axiom can also be written as

$$\forall \stackrel{\rightharpoonup }{x}.(\phi \Rightarrow \psi )$$\forall \vec{x}. (\varphi \Rightarrow \psi)

so that although $\Rightarrow$ and $\forall$ are not strictly part of any of the above logics, they can be applied “once at top level.” In an axiom of this form for geometric logic, the formulas $\phi$ and $\psi$ which must be built out of $\top$, $\wedge$, $\perp$, $\bigvee$, and $\exists$ are sometimes called positive formulas.

Abelian theories

Interestingly, one form of logic which made an early appearance but is not ordinarily thought of as logic at all is the logic of abelian categories, which is characterized by certain exactness properties. Here a small abelian category $A$ can be thought of as a syntactic site for some “abelian theory”; models of the theory are exact additive functors with domain $A$. The classical models would in fact be exact additive functors $A\to \mathrm{Ab}$, or exact additive functors to a category of modules. A “Freyd-Heron-Lubkin-Mitchell” embedding theorem is then a completeness theorem with respect to the classical models, and assures us that a statement in the language of abelian category theory is provable if and only if it is true when interpreted in any module category.

Specific examples

The simplest nontrivial theory is the

• theory of objects

• the theories

  • $\mathrm{Th}(\mathrm{Cat})$ of categories

  • $\mathrm{Th}(\mathrm{Lex})$ of finitely complete categories

  • $\mathrm{Th}(\mathrm{Topos})$ of elementary toposes

  • $\mathrm{Th}(\mathrm{ETCS})$ of sets (ETCS)

  are discussed at fully formal ETCS.

Models for a theory

From the categorical point of view, for every theory $T$ there exists a category $C_T$ – the syntactic category $C_T$ – such that a model for $T$ is a functor $C_T\to 𝒯$ into some topos $T$, satisfying certain conditions.

For instance the syntactic categories of Lawvere theories are precisely those categories that have finite cartesian products and in which every object is isomorphic to a finite cartesian power $x^n$ of a distinguished object $x$. A model for a Lawvere theory is precisely a finite product preserving functor $C_T\to 𝒯$.

We say a functor ${𝒯}_1\to {𝒯}_2$ of toposes (for instance a logical morphism or a geometric morphism) preserves a theory $T$ if for every model $C_T\to {𝒯}_1$ of $T$ in ${𝒯}_1$, the composite $C_T\to {𝒯}_1\to {𝒯}_2$ is a model of $T$ in ${𝒯}_2$.

For instance, every geometric morphism preserves every Lawvere theory since, being a right adjoint, it preserves limits, hence finite products.

Links and literature

A standard textbook reference is section D of

• Peter Johnstone, Sketches of an Elephant

A discussion of the relation between theories and their syntactic categories is at

• n-category cafe 2010: what is a theory

Other references include

• Mamuka Jibladze, Teimuraz Pirashvili, Cohomology of algebraic theories, J. Algebra 137 (1991), no. 2, 253–296, doi

• wikipedia: list of first-order theories, Morley’s categoricity theorem, Decidability (logic), signature (logic)

In Coq theories are specified with the

• Gallina specification language