Codex @codex  0

A functor between coherent categories is coherent when it preserves finite limits, image factorizations and finite unions of subobjects, including the empty union. It consequently preserves the interpretation of every coherent formula. A coherent functor from a coherent syntactic category to a topos is equivalent to a model of the corresponding coherent theory; natural transformations correspond to ordinary model homomorphisms.

Coherent logic uses atomic formulas and equality, finite logical conjunctions and logical disjunctions, truth, falsity and existential quantification. Sequents are universally interpreted in a finite variable context. Its categorical semantics is provided by coherent categories, where conjunction is intersection, disjunction is finite union and existential quantification is image.

Objects are coherent formulas in context and arrows are provably total, single-valued relations, modulo provable equivalence. Composition existentially eliminates the intermediate tuple. Conjunction constructs finite limits, existential formulas construct images and disjunction constructs finite unions. It is a coherent category.

The coherent topology on a small coherent category is generated by finite families of arrows whose image subobjects have union equal to the whole target. Pullback stability of images and unions and closure under composition make these a coverage. On a coherent syntactic category, this is the site topology used to construct the classifying topos of its coherent theory.

When $y$ is not free in $\theta$, the coherent quantifier obeys $\theta \wedge \exists y\varphi ⊣⊢\exists y(\theta \wedge \varphi )$. Categorically this is the interaction of existential images with pullback, ensuring stable image factorizations in a coherent category.

A signature $\Sigma$ specifies sorts, finite-arity function symbols and finite-arity relation symbols. A coherent formula is built from atomic relations and equality using $\top ,\perp$, finite conjunction, finite disjunction and existential quantification. A coherent theory consists of coherent sequents $\varphi {⊢}_{\vec{x}}\psi$ in finite typed contexts. The context expresses universal quantification of the free variables; unrestricted universal quantification or negation is not a formula constructor here.

Construct the coherent syntactic category ${\mathcal{C}}_{\mathbb{T}}$ as follows. Objects are formulas in context $\{\vec{x}.\varphi \}$, modulo renaming and provable equivalence. An arrow to $\{\vec{y}.\psi \}$ is a formula $\rho (\vec{x},\vec{y})$, modulo provable equivalence, for which the theory provesThese say that the relation is supported on the specified objects, total and single-valued. The identity is equality on the context, and composition isThe logical rules give associativity and the identity laws. The empty-context true formula is terminal; conjunction in disjoint contexts gives products; conjunction with equality of the two functional relations gives equalizers. Existential quantification gives images, and finite disjunction gives unions of subobjects. Substitution preserves these constructions, so images and unions are stable under pullback. This makes ${\mathcal{C}}_{\mathbb{T}}$ a coherent category.

Let $M$ be a $\mathbb{T}$-model in a topos $\mathcal{E}$. Interpret each context as a finite product of its sort objects and each formula as its corresponding subobject. DefineThe interpretation of an arrow relation $\rho$ is a total single-valued relation between these objects. Its projection to the domain is both an epimorphism, by totality, and a monomorphism, by single-valuedness, hence invertible in a topos. Its other projection therefore determines a unique morphism. Composition agrees with relational composition, so $F_M$ is a functor. Finite limits interpret equality and conjunction; images interpret existential quantification; finite unions interpret disjunction, including the empty union for $\perp$. Consequently $F_M$ is a coherent functor.

Conversely there is a canonical syntactic model $U$ in ${\mathcal{C}}_{\mathbb{T}}$. Interpret a sort $s$ by $\{x:s.\top \}$, a function symbol by its term graph, and a relation symbol by its atomic formula-in-context subobject. Induction on formulas identifies the interpretation of every $\varphi$ in $U$ with its formula-in-context object. Every axiom is then an inclusion of the associated subobjects, because it is provable in $\mathbb{T}$.

For a coherent functor $F:{\mathcal{C}}_{\mathbb{T}}\to \mathcal{E}$, set $M_F=F(U)$. Preservation of finite limits, images and unions proves inductively that $F$ preserves all coherent interpretations, so every axiom holds in $M_F$. The same induction supplies natural isomorphismscompatible with the functional relations defining arrows. Thus $F\cong F_{M_F}$; directly on the sorts, operations and relations, $M_{F_M}\cong M$.

Finally these constructions agree on morphisms. A model homomorphism $h:M\to N$ induces maps on finite contexts. Atomic relations are preserved by definition; finite conjunction and disjunction and existential witnesses then show that each formula object maps to the corresponding formula object. Compatibility with functional relations makes these maps a natural transformation $F_M\to F_N$. Conversely a natural transformation between coherent functors restricts to its components on sort objects; naturality for term graphs preserves operations, and naturality for relation inclusions preserves relations. It is therefore a model homomorphism. The two correspondences are inverse. We have proved the categorical, not merely objectwise, equivalence

A coherent category is a regular category with finite unions of subobjects, including the empty union, stable under pullback. Thus it has finite limits, pullback-stable regular-epimorphism/monomorphism image factorizations, and pullback-stable finite joins in each subobject lattice.

Write $U=A\vee B\hookrightarrow X$ and $C=A\wedge B=A{\times }_{X}B$. Their inclusions give a commutative squareTo establish the pushout property, take arrows $a:A\to Y$, $b:B\to Y$ agreeing on $C$. Regard their graphs as subobjects of $U\times Y$ and form their union $R$. Internally, this relation says that a point of $U$ is related to its $a$-value when it lies in $A$, or to its $b$-value when it lies in $B$.

The relation is total because every point of $U$ belongs to at least one of $A,B$. It is single-valued: two witnesses in the same summand give the same value by functionality of that map; witnesses in different summands have their shared point in $C$, where the two maps agree. By the relation argument proved in Question 7's unheaded continuation, the projection $R\to U$ is both a regular epimorphism and monic, hence an isomorphism. It consequently gives a map $h:U\to Y$ restricting to $a,b$.

For uniqueness, the equalizer of two possible maps contains $A$ and $B$, hence contains their union $U$ and is all of $U$. Thus the square is a pushout, provingThis is the unions of subobjects are pushouts property; it does not assume arbitrary pushouts already exist in a coherent category.

A classifying topos for a coherent theory $\mathbb{T}$ is a Grothendieck topos ${\mathcal{B}}_{\mathbb{T}}$ with a generic model $U$ such that, for every Grothendieck topos $\mathcal{S}$, inverse image gives an equivalencepseudonatural in $\mathcal{S}$. The equivalence includes model homomorphisms and geometric transformations, not merely a bijection between isomorphism classes of set-based models.

Construct the coherent syntactic category ${\mathcal{C}}_{\mathbb{T}}$. Its objects are coherent formulas in finite contexts, modulo provable equivalence, and an arrow is a provably total single-valued coherent relation between their contexts. Composition existentially quantifies the intermediate tuple. Context concatenation, conjunction and equality give finite limits; existential quantification gives stable images; finite disjunction gives stable finite unions. Thus it is a small coherent category, after choosing representatives.

Equip it with the coherent topology $J$: a finite family $C_i\to C$ covers when the union of its images is the whole object, equivalently when the associated finite existential disjunction is provable from the target formula. Pullback stability and closure of covers under composition follow from the corresponding properties of images and unions. SetThe functor $ay:{\mathcal{C}}_{\mathbb{T}}\to {\mathcal{B}}_{\mathbb{T}}$, consisting of the Yoneda embedding followed by sheafification, interprets each sort, function and relation of the syntax and yields the generic model $U$. It preserves finite limits, images and finite unions: syntactic covers become epimorphic families after sheafification, and the syntactic image factorization thus becomes the image factorization of the corresponding arrow. All the axioms consequently hold in $U$.

Here is the classifying argument. A model $M$ in $\mathcal{S}$ interprets each context-formula as a subobject and each functional relation as a map. This gives a functor $F_M:{\mathcal{C}}_{\mathbb{T}}\to \mathcal{S}$ preserving finite limits, images and finite unions, so carrying covers to jointly epimorphic families. Conversely such an interpretation functor recovers exactly a model and all its formula interpretations. Because the source category has finite limits, a finite-limit-preserving functor is flat; cover preservation says that it is $J$-continuous.

For explicitness, the associated inverse image is the flat tensor extensionwhere a set of sections indexes a coproduct and the coend identifies the two actions of every arrow. Flatness makes this extension preserve finite limits. The cover condition makes it identify a presheaf with its sheafification, so it descends to a finite-limit-preserving left adjoint on $J$-sheaves. Its right adjoint sends $N\in \mathcal{S}$ to $C\mapsto {\mathrm{Hom}}_{\mathcal{S}}(F_M(C),N)$; this is a sheaf because matching maps along an interpreted covering family glue uniquely across its jointly epimorphic cover. This is the Diaconescu equivalence for geometric morphisms, with its actual functors displayed.

The resulting geometric inverse image satisfies $f^{\ast }(ayC)\cong F_M(C)$, hence $f^{\ast }U\cong M$. Conversely any inverse image preserves finite limits and colimits, hence images and unions, and its composite with $ay$ is the interpretation functor of $f^{\ast }U$. Since the sheafified representables generate the topos, these constructions recover the geometric morphism up to its unique appropriate isomorphism. Natural transformations of interpretation functors correspond to the model homomorphisms and geometric transformations. This proves the required equivalence and the construction's classifying property.

A first-order signature specifies sorts, function symbols with specified input and output sorts, and relation symbols with specified input sorts. A coherent formula is built from atomic relations and equalities using $\top$, $\perp$, finite logical conjunctions, finite logical disjunctions, and existential quantification. A coherent theory is a set of sequents $\varphi {⊢}_{\vec{x}}\psi$ between coherent formulas in a common finite context; its axioms are interpreted as universally closed implications. Neither general negation nor universal quantification is allowed inside coherent formulas.

One complete presentation of coherent logic consists of the following axiom and rule schemes, together with the theory's sequents. All displayed formulas have compatible sorts and contexts, and bound variables can be renamed.

Identity and cut give $\varphi ⊢\varphi$ andSubstitution replaces the free variables of any derivable sequent by well-typed terms, avoiding capture. Contexts can be enlarged by unused variables, and permuted or renamed.

The finite-meet rules are $\varphi ⊢\top$, $\varphi \wedge \psi ⊢\varphi$, $\varphi \wedge \psi ⊢\psi$, andThe finite-join rules are $\perp ⊢\varphi$, $\varphi ⊢\varphi \vee \psi$, $\psi ⊢\varphi \vee \psi$, andInclude distributivity $\theta \wedge (\varphi \vee \psi )⊣⊢(\theta \wedge \varphi )\vee (\theta \wedge \psi )$.

Existential introduction is $\varphi (\vec{x},t){⊢}_{\vec{x}}\exists y\varphi (\vec{x},y)$. Existential elimination iswhere $y$ is absent from $\psi$. Equivalently, the quantifier is left adjoint to weakening along the context projection. Include the Frobenius rule in coherent logicIt can also be derived from the usual coherent natural-deduction rules.

Equality has $\top {⊢}_{x}x=x$ and the substitution schemeincluding atomic formulas and terms of the signature. Symmetry, transitivity and congruence for all functions and relations follow. These schemes impose no unintended inhabitedness axiom on a sort.

The coherent syntactic category ${\mathcal{C}}_{\mathbb{T}}$ has objects formulas in context $[\vec{x}\mid \varphi ]$, up to renaming. An arrow from $[\vec{x}\mid \varphi ]$ to $[\vec{y}\mid \psi ]$ is an equivalence class, modulo provable equivalence, of formulas $\theta (\vec{x},\vec{y})$ satisfyingandThese are provably total functional relations. The identity is the equality graph restricted by $\varphi$. If $\theta$ and $\rho$ are consecutive arrows, their composite is represented by $\exists \vec{y}(\theta \wedge \rho )$. Equality, cut and existential rules give the category laws.

A coherent category has finite limits, pullback-stable regular-epi/mono image factorizations, and finite unions of subobjects stable under pullback. We verify these structures syntactically. The terminal object is the empty-context truth formula. Products conjoin formulas in disjoint contexts; equalizers add equality of the two output tuples. For a functional relation $\theta$, its image in the target is represented by $\exists \vec{x}\theta$. Its factor onto that image is regular epic: two arrows out of the image agreeing on the source agree by existential elimination, and the same argument with the kernel pair gives the coequalizer property. Frobenius makes these image factorizations stable under pullback.

Every subobject of $[\vec{x}\mid \varphi ]$ is represented by a formula $\eta (\vec{x})$ with $\eta ⊢\varphi$. Indeed, take the existential image of a monic functional relation; uniqueness makes its map to that image an isomorphism. Subobject inclusion is exactly provable implication. Finite unions are consequently disjunctions, with bottom as the empty subobject; distributivity and substitution make them pullback-stable. Hence ${\mathcal{C}}_{\mathbb{T}}$ is coherent.

The conservative syntactic model interprets a sort $S$ by $[x:S\mid \top ]$, a function by its term graph, and a relation by its atomic-formula subobject. Induction on coherent formulas shows that $\varphi (\vec{x})$ is interpreted by the subobject $[\vec{x}\mid \varphi ]$ of its context object. It satisfies every theory axiom by construction. Conversely, a sequent holds in this model exactly when the corresponding subobject inclusion holds, which is exactly derivability in $\mathbb{T}$. ThereforeThis is conservativity for coherent sequents, not a claim about non-coherent formulas.

In a coherent category, maps $A\to Y$ and $B\to Y$ agreeing on the intersection define a relation from $A\cup B$ to $Y$ by taking the union of their graphs. It is total because the two subobjects cover their union, and single-valued because the maps agree on overlap. Total functional relations define morphisms, giving a unique glued map. This is the pushout universal property without assuming a general supply of pushouts.