The Syntactic Category and Categorical Semantics
/ 17 min read
0. The First-Order Signature
In the framework of topos-theoretic semantics, the signature is the purely syntactic bedrock upon which all logical constructions are erected. It specifies the non-logical vocabulary without imposing any axioms.
0.1. Definition
A first-order signature consists of the following data:
- Sorts (-Sort): A set of sorts (or types), denoted by .
- Function Symbols (-Fun): A set of function symbols, each equipped with a type consisting of a finite non-empty list of sorts. We write: to indicate that has type . If , is called a constant of sort .
- Relation Symbols (-Rel): A set of relation symbols, each equipped with a type consisting of a finite list of sorts. We write: to indicate that has type .
0.2. Diagram of a Signature
The following diagram visualizes as a labelled directed hypergraph, where sorts are nodes, functions are arrows, and relations are subobject markers.
1. Language
Following the conventions of Theories, Sites, Toposes, once a signature is fixed, we generate its language recursively. This language is stratified into three distinct levels: terms (which denote elements), formulas (which denote propositions), and sequents (which express entailment).
1.1. Terms
Given a signature , the terms of sort over are defined by the following inductive rules:
- Every variable is a term of sort .
- If is a constant symbol of , then is a term of sort .
- If are terms and is a function symbol of , then is a term of sort .
A term is closed if it has no free variables.
A term is therefore an expression built from variables, constants, and function symbols. Its purpose is to denote an element of a sort — it represents an object of a given type within the language.
A context is a finite list of variable declarations . A term of sort in context , written , is a term whose free variables are among those declared in .
1.2. Formulas
Definition. The formulas over a signature are built from atomic formulas using the logical connectives and quantifiers. An atomic formula is either:
- An expression , where is a relation symbol of and each is a term of sort .
- An equality , where and are terms of the same sort (if equality is present in the logic).
The set of formulas is the smallest collection containing all atomic formulas and closed under:
A formula with free variables contained in a context is denoted by .
1.3. Geometric Formulas
The geometric formulas — which are central to the topos-theoretic bridge — are those built from atomic formulas using only:
- Finite conjunctions ()
- Finite disjunctions ()
- Existential quantification ()
They do not contain implication (), negation (), or universal quantification () at the top level.
1.4. Context
Definition. A context over a signature is a finite list of variable declarations of the form:
where each is a variable and each is a sort (type) in . Notation. A context is typically denoted by or . When we write , we indicate that the formula has all its free variables declared in the context . Similarly, indicates that the term is of sort and has its free variables in .
1.5. Sequents
Definition. A sequent over a signature is an expression of the form:
where is a finite context, and and are formulas whose free variables are contained in .
The intended meaning is that follows from under the assumptions on the variables declared in .
A geometric sequent is a sequent where both and are geometric formulas.
1.6. Geometric Theories
Definition. A geometric theory over a signature is a set of geometric sequents over , closed under the rules of intuitionistic first-order logic (or, more specifically, the geometric sequent calculus).
2. Group Theory
Group theory is one of the most fundamental structures in modern mathematics. The theory of groups can be presented as a geometric theory over a suitable first-order signature.
2.1. Signature of Groups
Following the definitions of geometric logic, we define the signature for the theory of groups as follows:
Sorts:
- A single sort: (the sort of group elements).
Function Symbols:
- A constant symbol: (the identity element).
- A binary function symbol: (the group multiplication).
- A unary function symbol: (the inverse operation).
Relation Symbols:
- The equality relation is assumed to be present in the logic.
There are no additional relation symbols in the signature.
2.2. The Geometric Axioms
The theory of groups is axiomatized by the following geometric sequents (all in the empty context, as these are universal statements):
1. Associativity:
2. Identity element:
3. Inverse element:
Each of these sequents is of the form where and is an atomic equality formula. The context contains the variables as needed.
Note: These axioms are geometric because they are built from atomic formulas (equalities) using only conjunction (implicit in the context) and universal quantification at the meta-level. The absence of implication (), negation (), and disjunction () at the object level ensures that the theory is geometric.
3. Syntactic Category
3.1. Objects
The objects are the renaming-equivalence classes of geometric formulae-in-context over .
That is, two formulae-in-context and represent the same object if they are related by renaming (alpha-equivalence). This means that is a bijective renaming of the variables , and is obtained from by replacing each variable with the corresponding , following the standard capture-avoiding substitution rules for bound variables.
The notation emphasizes that the object is the equivalence class, not a particular syntactic presentation of the formula.
3.2. Morphisms
An arrow
(where the contexts and are assumed to be disjoint without loss of generality) is a -provable-equivalence class of a geometric formula which is -provably functional.
The equivalence class identifies two such formulas if they are provably equivalent in in the combined context ; that is, and are provable in .
is -provably functional if it satisfies the following three sequents in :
- Totality: For every satisfying , there exists some such that holds.
- Well-definedness: Whenever holds, holds for and holds for .
- Single-valuedness: If holds for and also for (with the same ), then and must be equal.
3.3. Composition
The composite of two arrows
is defined as the -provable-equivalence class of the formula.
This formula expresses the relation obtained by “composing” and : it holds for and exactly when there exists some such that both and hold.
3.4. Identity
The identity arrow on an object is given by:
Intuitively, the identity relation on holds exactly when the new variables are a renaming of and holds for both.
You should be sure that identity and composition are effectively -provably functionals.
Before continuing, there is a question that we should answer: why, at a morphism, the contexts of domain and codomain are assumed to be disjoint? And why does this not cause any problem?
A reason for assuming that these contexts are disjoint is that in the single-valuedness sequent, the sequent works with substitution: is , but with the free variables substituted by the variables . As we specified in the definition of the renaming (alpha-equivalence) of objects, the sequent aims to say that for the same inputs , gives the same “output”; but if and have a variable in common, this variable will be changed by the substitution , and this degrades the meaning of the sequent .
This supposition is not a problem because an object is an equivalence class, and if the representative of the class has variables in common with the other object of the arrow, we only need to change the representative for one that is disjoint.
3.5. Isomorphisms
An isomorphism in a category is a morphism such that there exists a morphism such that and . In the syntactic category, reflecting the above totality and well-definedness sequents, a morphism can be interpreted as a proof that implies ; so an isomorphism is a proof of the equivalence between two formulas. In fact, two objects of the syntactic category are isomorphic if and only if they are equivalent formulas with contexts of the same type and length.
4. Products
4.1. Definition of Product
A product in a category in category theory is a limit of a very special functor; this definition is analogous to an equalizer but with a functor indexed by:
The functor will be:
The diagram that represents a product is simply:
A cone with nadir will be:
And the universal cone with nadir :
This is basically the product.
4.2. Cartesian Categories
A category is cartesian if and only if it has finite products; that is, the empty product (terminal object) and products for pairs of objects.
4.3. Syntactic Category is Cartesian
As we said, we only need to see that the syntactic category has a terminal object and products for pairs of objects.
4.3.1. Terminal Object
The terminal object in is:
the formula-in-context with empty context and formula .
For any object , there is a unique morphism:
given by the equivalence class of the formula:
which is trivially provably functional.
4.3.2. Binary Product
For any two objects:
where and are disjoint contexts (we can always rename variables to ensure this); their product in is:
4.3.2.1. Projection Morphisms
The first projection is:
given by:
The second projection is:
given by:
4.3.2.2. Universal Property
For any object equipped with morphisms:
and
there exists a unique morphism:
given by:
This morphism is the unique one satisfying:
and
4.3.3. Product Diagram
For objects and , the product diagram is:
and commutativity is the universal property.
This shows that the syntactic category is a cartesian category, so it is a candidate for being used in a -structure.
5. Σ-Structures
Let be a first-order signature. A structure over in a cartesian category is specified by the following data:
- Sorts: For any sort of , an object
- Function Symbols: For any function symbol of , an arrow in .
- Relation Symbols: For any relation symbol of , a subobject in .
Now let’s see an example of a concrete syntactic category.
6. Group Syntactic Category
Now that we know the signature and sequents of group theory, we know what the objects and morphisms of the syntactic category of group theory are, but there are some special morphisms and one special object that we shall see.
6.1. Operations as Morphisms
6.1.1. The Identity (Unit)
The identity element is a morphism from the terminal object to the carrier object:
It is given by the equivalence class of the formula:
6.1.2. The Multiplication (Product)
The multiplication operation is a morphism from the product of the carrier with itself to the carrier:
It is given by the equivalence class of the formula:
6.1.3. The Inverse
The inverse operation is a morphism from the carrier to itself:
It is given by the equivalence class of the formula:
Note that all these morphisms act on one special object .
6.2. The Group Object
The abstract group object in is the object . This object, equipped with , and , has the structure of a group; let’s see why.
In , consider this diagram:
Commutativity means: ; let’s break down these morphisms.
Top morphism:
Right morphism:
Composition :
This formula is -provably equivalent to:
Analogously, the second composition is:
Then, by the associativity axiom , we have: .
Note that this result comes directly from the associativity axiom; analogously, the diagram of invertibility commutes directly, following from the respective axioms:
Existence of the neutral element is guaranteed by:
And this proves all group axioms for with , and .
7. Canonical Σ-Structure
7.1. The Σ-Structure
We already know the group theory signature and that the syntactic category is cartesian, so let’s define a Σ-structure in the syntactic category by interpreting each component of the signature as follows:
7.2. Sorts
For the unique sort of , we assign an object:
This is the abstract group object, the carrier of the group in the syntactic category.
7.3. Function Symbols
7.3.1. The Identity Constant
The constant symbol is interpreted as a morphism from the terminal object:
given by the formula .
7.3.2. The Multiplication Operation
The binary function symbol is interpreted as a morphism from the product of the carrier with itself:
given by the formula .
7.3.3. The Inverse Operation
The unary function symbol is interpreted as a morphism from the carrier to itself:
given by the formula .
Now is a Σ-structure; as we have seen before, it also satisfies all axioms of , so is a model for .
8. Cartesian Functors
8.1. Definition
Let and be cartesian categories. A functor is called cartesian if it preserves finite products, i.e.
for all .
Informally, one often writes this as
8.2. Functors Define Groups
Now consider a functor ; this functor sends to a specific set , and , and to morphisms in . The incredible fact is that these morphisms in together with form a group, because every axiom of was codified in as a commutative diagram, and it is a basic result of category theory that every commutative diagram is indeed a commutative diagram in the image of a functor.
8.3. Example: the Group of Integers
Consider the functor
It is defined on the generic object by
and, since it is cartesian, it preserves finite products:
On the basic group operations it is defined by
As we have seen, this is a model for ; specifically, it is the group .
We have only talked about group theory because it is a very simple example, but this does not work only for this theory: the axioms of every geometric theory will be codified as commutative diagrams in the corresponding syntactic category, and every cartesian functor from this category to another will be a model for the theory.
9. References
- Emily Riehl. Category Theory in Context. Aurora: Dover Modern Math Originals. Mineola, NY: Dover Publications, 2016.
- Paolo Aluffi. Algebra: Chapter 0. Graduate Studies in Mathematics, vol. 104. Providence, RI: American Mathematical Society, 2009.
- Olivia Caramello. Theories, Sites, Toposes: Relating and studying mathematical theories through topos-theoretic ‘bridges’. Oxford: Oxford University Press, 2017.