Categorical Logic

Categorical logic is the branch of mathematics that studies logic and logical theories through the lens of category theory.

6 frameworks, from 1963 to today · Category Theory · Mathematics

still a working view ended · each leads to its entry below

Overview

Categorical logic is the branch of mathematics that studies logic and logical theories through the lens of category theory1. Where a traditional logician asks what a theory proves, a categorical logician asks what structure a theory is: a theory becomes a category, its formulas become objects, and its proofs become arrows between them. This reframing has turned out to be extraordinarily productive. It gave computer science a mathematical foundation for typed programming languages, gave set theory a rival foundation in topos theory, and in the twenty-first century produced homotopy type theory, a system in which the basic objects of logic are interpreted as spaces and paths. The history of the field is a sequence of discoveries that each revealed a new layer of the same correspondence: logic, computation, and geometry are, in a precise sense, the same subject seen from different angles.

Lambek's Correspondence: Proofs as Arrows (1968–1972)

The founding insight came from Joachim Lambek, a category theorist at McGill University. In the late 1960s he was thinking about the relationship between formal proofs and algebraic structures. In a 1968 paper and then in a 1969 note, he observed that a deductive system—a collection of formulas with inference rules—could be organized as a category. Formulas are objects; a proof of B from A is an arrow from A to B; composing proofs corresponds to chaining inferences; and the identity arrow is the trivial proof that A follows from A. This was the first precise statement that proofs themselves have categorical structure.

Lambek then connected this to the simply typed lambda calculus, a formal language for computable functions developed by Alonzo Church in the 1930s. In the lambda calculus, a term of type A $\rightarrow $ B is a function from A to B; applying it to an argument of type A yields a result of type B. Lambek saw that this is exactly the same structure as implication in logic: a proof of A implies B is a function from proofs of A to proofs of B. The correspondence became known as the Curry–Howard–Lambek correspondence, building on earlier observations by Haskell Curry (1934) and William Alvin Howard (1969) that proofs and programs are the same thing. In categorical terms, a typed lambda calculus is the internal language of a cartesian closed category—a category with products and function objects—and the correspondence says that the logic, the computation, and the category are three descriptions of one structure2. This gave categorical logic its first concrete case: the simply typed lambda calculus is intuitionistic propositional logic is the theory of cartesian closed categories.

Functorial Semantics and Algebraic Theories (1963–1970)

Before Lambek, William Lawvere had already begun rebuilding logic on categorical foundations. In his 1963 doctoral thesis at Columbia University, supervised by Samuel Eilenberg, Lawvere introduced what he called functorial semantics. The idea was to treat an algebraic theory—the axioms defining groups, rings, or any other equational variety—as a category whose objects are finite lists of variables and whose arrows are derived operations. A model of the theory is then a functor from this category into the category of sets, assigning to each formal operation an actual function. This was a radical move: instead of a theory being a set of axioms in a formal language, the theory is a category, and its models are functors. Lawvere's algebraic theories (later called Lawvere theories) gave a precise categorical account of universal algebra and showed that the syntax of equational logic has an intrinsic categorical shape3.

Hyperdoctrines and the Categorical Analysis of Quantifiers (1969–1970)

Lawvere's next step, in a 1969 paper and a 1970 lecture, was to extend this to full first-order logic. He introduced the notion of a hyperdoctrine: a functor assigning to each type or sort a category of predicates, with operations corresponding to substitution, conjunction, disjunction, implication, and the quantifiers. The key insight was that existential and universal quantification are adjoint functors1. In a hyperdoctrine, the existential quantifier along a projection is left adjoint to substitution, and the universal quantifier is right adjoint. This was the first categorical explanation of why quantifiers behave the way they do: they are adjoints, and their logical properties follow from general facts about adjunctions. Hyperdoctrines made first-order logic a branch of category theory and set the pattern for everything that followed: logical operations are categorical constructions, and logical laws are categorical theorems.

Topos Theory and Internal Language (1969–1972)

The most ambitious extension came from the collaboration between Lawvere and Myles Tierney in the late 1960s and early 1970s. Building on Alexander Grothendieck's work on sheaves and cohomology, Lawvere and Tierney isolated the notion of an elementary topos: a category with finite limits, exponentials, and a subobject classifier—an object Ω that classifies subobjects, playing the role that the set {true, false} plays in set theory. The category of sets is a topos; so is the category of sheaves on a topological space; so are many other categories. Lawvere and Tierney showed that every topos has an internal language, a formal language of types and terms in which the topos itself is the universe of discourse. This internal language is intuitionistic—the law of excluded middle need not hold—and higher-order, with quantification over all types14.

The significance was twofold. First, it gave a new foundation for mathematics: instead of building everything from sets, one could build from any topos, and the internal language would automatically be sound. Second, it gave logic a geometric interpretation: a topos is a generalized space, and its internal logic is the logic of that space. This was developed extensively in the 1970s and 1980s, notably in Michael Fourman's work on sheaf models and in the textbook Sheaves in Geometry and Logic by Saunders Mac Lane and Ieke Moerdijk (1992), which became the standard reference. The internal language of a topos is now a standard tool in algebraic geometry and in the study of independence results.

Dependent Type Theory and Categorical Semantics (1970s–1990s)

Per Martin-Löf's dependent type theory, developed from the early 1970s onward, extended the Curry–Howard correspondence to types that depend on terms—types like "the type of vectors of length n," where n is a natural number. This required a richer categorical semantics. In the 1980s and 1990s, several researchers, including John Cartmell, Robert Seely, and Thomas Streicher, worked out the categorical structure corresponding to dependent type theory. The key notion is a category with families (CwF), introduced by Peter Dybjer in 1996, which packages the context-extension structure of dependent types into a categorical framework. Seely's 1984 paper had already shown that locally cartesian closed categories provide a semantics for extensional dependent type theory, and the subsequent refinements by Dybjer, Streicher, and others made the correspondence precise and usable. This work became foundational for the design of proof assistants such as Coq and Agda, where the type theory is the programming language and the categorical semantics guarantees soundness.

Higher Categories and Homotopy Type Theory (2006–present)

The most recent turning point began with Vladimir Voevodsky's work on homotopy type theory around 2006. Voevodsky, a Fields Medalist for his work in algebraic geometry, was looking for a foundational system suitable for formalizing mathematics in computer proof assistants. He noticed that Martin-Löf type theory, interpreted in a certain way, has a homotopical semantics: types are spaces, terms are points, and proofs of equality are paths. This interpretation, developed with collaborators including Steve Awodey, Thierry Coquand, and Michael Warren, led to the univalence axiom, which states that equivalent types are identical. The resulting system, homotopy type theory (HoTT), was presented in the 2013 book Homotopy Type Theory: Univalent Foundations of Mathematics, written by a large collective of authors.

The categorical side of this story is the theory of higher categories, especially (∞,1)-categories, in which arrows between arrows are tracked up to homotopy. The homotopy hypothesis, formulated by Alexander Grothendieck in the 1980s and developed by Michael Batanin, Carlos Simpson, and others, says that homotopy types are the same as ∞-groupoids. HoTT makes this precise: the types of HoTT are the objects of an (∞,1)-topos, and the logic of HoTT is the internal logic of that higher category. This is still an active area: the precise categorical semantics of HoTT, the status of the univalence axiom, and the relationship between HoTT and classical homotopy theory are all open questions.

The Present State

Categorical logic today is a mature field with several active branches. The internal language of toposes remains central to algebraic geometry and to the study of constructive mathematics. Dependent type theory and its categorical semantics are the theoretical backbone of proof assistants and of programming language design; the category with families framework is standard in the semantics of dependent types. Homotopy type theory has opened a new frontier, connecting logic to homotopy theory and to higher category theory, and the search for a computational interpretation of univalence is ongoing. The Curry–Howard–Lambek correspondence, now more than fifty years old, remains the organizing principle: logic, computation, and category theory are three views of one structure, and the history of categorical logic is the history of discovering how deep that unity goes5.

References

  1. Categorical logic (introduction, Overview), Wikipedia
  2. Cartesian closed category, Wikipedia
  3. Lawvere theory, Wikipedia
  4. Elementary topos, Wikipedia
  5. Curry–Howard correspondence (Curry–Howard–Lambek correspondence), Wikipedia

The frameworks of Categorical Logic

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1963-Present

    Functorial semantics and algebraic theories

    How can the axioms defining a mathematical structure be described categorically?

    Fly to its tower in Nousfarer

  2. 1968-Present

    Proofs-as-arrows and the Curry–Howard–Lambek correspondence

    How is the relationship between formal proofs and computational procedures formalized?

    Fly to its tower in Nousfarer

  3. 1969-Present

    Hyperdoctrines and categorical quantifier theory

    How do logical quantifiers behave when viewed as categorical operations?

    Fly to its tower in Nousfarer

  4. 1969-Present

    Topos

    What mathematical structures can serve as a generalized universe for mathematics?

    Fly to its tower in Nousfarer

  5. 1984-Present

    Categorical semantics of dependent type theory

    How can logical systems handle types that depend on other types?

    Fly to its tower in Nousfarer

  6. 2006-Present

    Homotopy type theory

    How can logical statements be interpreted using the language of continuous shapes?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Functorial semantics and algebraic th…Proofs-as-arrows and the Curry–Howard…Hyperdoctrines and categorical quanti…ToposCategorical semantics of dependent ty…Homotopy type theory

Beyond the field

Where Categorical Logic's ideas came from in other fields, and what they led to there: the strongest 12 of 25 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Categorical Logic is a planet in Nousfarer

Its city has a tower for each of these 6 frameworks. Land, walk in, and climb one concept at a time.

Land on Categorical Logic

Related fields

Fields its ideas are linked to

More in Category Theory

See where Categorical Logic sits on the Map of Human Knowledge