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
Note: This page is about categories (in the sense of category theory) built out of syntax, i.e. “term models”. The phrase “syntactic category” is also sometimes used to mean a grouping of syntactic objects, so that e.g. terms belong to one syntactic category and formulas to another. For this usage, see also categorial grammar.
As described at relation between type theory and category theory, for many kinds of logic and type theory there is an adjunction or equivalence
where on the left we have a category or 2-category of theories of some sort (i.e. in some doctrine), and on the right we have a category or 2-category of categories with some structure (e.g. finite limits, cartesian closure, etc.).
The syntactic category construction is the functor from theories to categories, denoted or . Given a theory, it generates the walking model of that theory, i.e. a structured category of the appropriate sort which is generated by a model of that theory. Since the objects of the syntactic category are frequently taken to be the contexts in the theory, the syntactic category is also called the category of contexts.
The functor in the other direction associates to any category its internal logic.
Given a type theory , its syntactic category or category of contexts is defined as follows.
Its morphisms between contexts are substitutions, or interpretations of variables.
A morphism from the context to the context consists of a way of fulfilling the assumptions required by by appropriately interpreting those provided by , generally by substituting terms available in for variables needed in and proving whatever is necessary from the assumptions at hand.
More precisely, let and be contexts of some type theory of the form
and
(Here we allow the possibility that each type in these contexts depends on the variables occurring earlier in the context, but for simplicity we can ignore that. )
Then a morphism in the category of contexts consists of a sequence of terms such as the following:
In other words, to give such a morphism we must give, for each type (or assumption) required by , a way to construct an element of that type (or a proof of that assumption) out of the data and assumptions contained in .
This might fit better after the motivating examples below; but maybe those examples don't make sense to a newcomer. This is incomplete, however, since it doesn't address contexts that include propositional hypotheses. —Toby
Depending on the type-forming operations available in , the category will have categorical structure. Roughly:
And so on. (If lacks eta-conversion, then this categorical structure may only be “weak”.) One thing worth noting is that
This is due to the objects of being contexts rather than types. A way to avoid this is to work instead with a syntactic cartesian multicategory.
In fact, is not just a structured category, it is a split model of type theory in any of the senses described there. In constructing formally an internal logic that involves dependent types, this is important to keep track of.
The syntactic category has the universal property that for any suitable category, functors
that preserve the relevant structure correspond to interpretations of in .
The construction
is the left adjoint in an adjunction that relates type theories and categories, whose right adjoint extracts the internal logic of a category.
Accordingly, the adjunction counit evaluated on any category
says that there a canonical interpretation of the internal logic of a category in itself, while the unit evaluated at a theory :
says that there is a canonical interpretation of in the internal logic of its syntactic category.
Given a context and a type , there is a new context .
Given a term there is a canonical morphism of contexts
which picks that term in . The base change functor along this morphism
is the operation of substitution of variables: it sends a dependent type to .
There is also the canonical morphism of contexts
which simply forgets the type . The base change along this morphism is the context extension functor
Its right adjoint is the dependent product functor giving the universal quantifier , and its left adjoint is the dependent sum functor giving the existential quantifier .
For example, consider these contexts in the theory of a group :
One interpretation of in (that is, a morphism from to ) is given by the substitution
The fact that in is ignored. In type-theoretic language, this would consist of the two terms
Note that in this way of presenting things, the names of the variables in do not appear; only the order in which the types appear in matters.
A less obvious interpretation of in is the substitution
There is no reason to keep variable names the same. (At this point, compare and ; when the definition is complete, it ought to follow that these are isomorphic.)
Another, perhaps even less obvious, morphism is
Not only does this ignore that ; it also ignores the very existence of in . (It also uses the existence of more than once. Ignoring and reusing information like this is not always allowed in substructural logics such as linear logic.)
We can interpret in without renaming variables because the theory of a group allows us to derive the judgment
That is, we get a morphism from to by performing the substitution
and then inserting a proof of the above judgment. As it happens, the argument in such a proof is reversible, so you should expect that and are also isomorphic.
Are there any morphisms from to ? The obvious substitution does not define a morphism, since the required fact cannot be proved. However, you get one using the substitution
and then inserting a proof that
All the same, we would not want to say that and are isomorphic contexts; although there are morphisms in each direction, composing them should never produce identity morphisms on both sides.
The category structure of can be seen explicitly as well. First, given a context , there is an obvious identity morphism where every variable is substituted for itself and every statement assumed is proved immediately from itself.
Given morphisms , form the composite as follows: First, for each variable required by , tells us how to substitute a term built out of the variables in , while tells us how to substitute a term from for each of these variables. So in the end, is expressed as a term involving variables available in . Also, by combining the proofs provided by and , we get the proofs required for their composite.
To really complete the definition of a category, I should also describe when two morphisms are equal. There are actually many options here; the most strict is to say that they are equal only if the substitutions and proofs used are syntactically identical, and the most weak is to say that any parallel morphisms are equal. Neither of these is very useful; for purposes of this example, let us require only that the expressions substituted for each variable in can be proved equal in the context .
Now you should be able to prove that composition satisfies the axioms of a category.
Notice that the exact definition of equality of morphisms can depend heavily on the theory in question and your own purposes. For example, this definition makes sense only because we have a notion of proving equality of elements of a group. Also, you can sometimes place interesting conditions on whether two proofs count as equivalent, rather than requiring either syntactic identity or (as we do here) accepting proof irrelevance.
Now that the category of contexts (in one sense) of the theory of a group has been completely defined, describe that category (up to equivalence) in terms familiar to an algebraist. In particular, compare it to the category of groups.
In rot13 (so that you have a chance to think about it yourself without accidentally seeing the answer): gur bccbfvgr bs gur pngrtbel bs svavgryl cerfragrq tebhcf.
The result of this exercise is true in more generality: it works for any finite-limit theory; see in particular Lawvere theory. Presumably there are also infinitary generalizations. There’s some general discussion in the Elephant.
Instead of a syntactic category, for a non-dependent type theory one can construct instead a syntactic cartesian multicategory (or, in the case of a linear type theory, a plain (symmetric) multicategory). This avoids the need to take the objects to be contexts rather than single types.
For some doctrines, the syntactic category of any theory is naturally equipped with the structure of a site. For instance, if is a regular, coherent, or geometric theory, then is a regular, coherent, or geometric category, which comes with a naturally defined topology. When equipped with this topology, the syntactic category is called the syntactic site.
In each of these cases, the category of sheaves on the syntactic site is the classifying topos of the theory. In other words, it has the universal property that for any Grothendieck topos , geometric morphisms are equivalent to models of the theory in .
More or less the same concept is that of term model.
Sections D4.1 and D4.4 of
A description of the construction of the category of contexts is in
Another description, via sketches, is in chapter VIII of
A review of this is around section 2.8 of
Last revised on August 19, 2015 at 17:02:41. See the history of this page for a list of all contributions to it.