nLab
first-order hyperdoctrine

Context

Type theory

natural deduction metalanguage, practical foundations

  1. type formation rule
  2. term introduction rule
  3. term elimination rule
  4. computation rule

type theory (dependent, intensional, observational type theory, homotopy type theory)

syntax object language

computational trinitarianism = propositions as types +programs as proofs +relation type theory/category theory

logiccategory theorytype theory
trueterminal object/(-2)-truncated objecth-level 0-type/unit type
falseinitial objectempty 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
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

homotopy levels

semantics

(0,1)(0,1)-Category theory

Contents

Idea

A first-order hyperdoctrine is a hyperdoctrine with respect to lattices that are Heyting algebras.

Definition

A first-order hyperdoctrine consists of a category with finite products C TC_T, along with a functor

P:C T opHeytAlg AdjCyl P \colon C_T^{op} \to HeytAlg_{AdjCyl}

(where HeytAlg AdjCylHeytAlg_{AdjCyl} is the subcategory of the category of Heyting algebras containing only those morphisms with left and right adjoints) such that the following Beck-Chevalley condition is satisfied: for every object AA, the left adjoints to P(π)P(\pi) for the projections π:A×\pi : A \times - \to - comprise a natural transformation from P(A×)P(A \times -) to P()P(-), and so do the right adjoints. This expresses the Beck-Chevalley condition for pullback squares of the form

A×B π B B 1 A×f f A×C π C C\array{ A \times B & \stackrel{\pi_B}{\to} & B \\ ^\mathllap{1_A \times f} \downarrow & & \downarrow^\mathrlap{f} \\ A \times C & \underset{\pi_C}{\to} & C }

An element of P(A)P(A) is often called a predicate over AA (with respect to the hyperdoctrine).

For any first-order hyperdoctrine, an equality predicate can be defined for each type AOb(C T)A \in Ob(C_T) as

(δ A)( P(A))P(A×A)\exists(\delta_A)(\top_{P(A)}) \in P(A \times A)

where for any morphism ff in C TC_T, we use (f)\exists (f) to denote the left adjoint of P(f)P(f), and H\top_H denotes the top element in a Heyting algebra HH. However, to get good properties for equality, we need to assume a little more. A first-order hyperdoctrine with equality is a first-order hyperdoctrine such that the Beck-Chevalley condition is also satisfied for pullback diagrams of the form

A δ A A×A δ A 1 A×δ A A×A δ A×1 A A×A×A\array{ A & \stackrel{\delta_A}{\to} & A \times A \\ ^\mathllap{\delta_A} \downarrow & & \downarrow^\mathrlap{1_A \times \delta_A} \\ A \times A & \underset{\delta_A \times 1_A}{\to} & A \times A \times A }

This says P(1 A×δ A)(δ A×1 A)=(δ A)P(δ A)P(1_A \times \delta_A) \circ \exists (\delta_A \times 1_A) = \exists (\delta_A) \circ P(\delta_A); this equation is also known as a Frobenius law. By taking right adjoints, a similar equation holds for (f)\forall (f) in place of (f)\exists (f), where P(f)(f)P(f) \dashv \forall (f).

Interpretation

With this, we have enough structure to interpret multi-sorted first-order intuitionistic logic with equality, taking the objects of C TC_T to be sorts and its morphisms to be terms, PP to assign to each sort the Lindenbaum algebra? of predicates upon that sort and to each term the operation of substitution of that term into predicates, and the left and right adjoints to PP upon projections to provide existential and universal quantification, respectively, with the existence of the further adjoints providing the ability to interpret equality, and the Beck-Chevalley condition ensuring that quantification commutes appropriately with substitution (just as the propositional connectives do).

Variants

There are, of course, many variants on this, corresponding straightforwardly to modifications of the kind of logic one wishes to represent. For instance, to represent specifically classical logic, one should use Boolean algebras instead of Heyting algebras. To represent first-order logic without equality, one should no longer require left and right adjoints to every morphism in the range of PP, but rather only those given by the natural transformations yielding the quantifiers (i.e., only requiring adjoints to substitution along projections). Various higher-order constructs can be added by adding new ways of forming objects in C TC_T (e.g., adding cartesian closedness). Etc.

One can even extend this into the realm not just of provability, but furthermore of proof theory, by taking the objects in the codomain of PP to be categories rather than mere preorders (e.g., by using bicartesian closed categories rather than Heyting algebras); in this case, the objects in a category P(σ)P(\sigma) would still represent predicates on the sort σ\sigma, but the morphisms in P(σ)P(\sigma) would represent proofs (rather than mere provability) of entailments between these predicates, with the possibility that not all such proofs would be equal.

Revised on October 25, 2012 11:18:26 by Urs Schreiber (131.174.189.236)