Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 74 (Topos Theory)

Take the definition of an elementary topos as a category with finite limits, exponential objects and a subobject classifier $\top :1\hookrightarrow \Omega$. Its power object is $PX={\Omega }^X$, and $Pf:PY\to PX$ is precomposition with $f:X\to Y$. Transposing a predicate on $X\times Y$ in either variable givesThus $P^{\mathrm{op}}:\mathcal{E}\to {\mathcal{E}}^{\mathrm{op}}$ is left adjoint to the contravariant power-object functor $P:{\mathcal{E}}^{\mathrm{op}}\to \mathcal{E}$.

Here are the remaining hypotheses for the crude monadicity theorem, obtained from those topos axioms. The unit of this adjunction is ${\eta }_X:X\to PPX$, internally ${\eta }_X(x)(S)=(x\in S)$. It is monic: if two such evaluations agree, evaluate on the singleton predicate $\{x\}$ classified by the diagonal to obtain $x=y$. If $Pf$ is invertible, naturality $PPf{\eta }_X={\eta }_{Y}f$ therefore makes $f$ monic. The characteristic map of this mono, regarded as a global element of $PY$, pulls back along $f$ to the everywhere-true predicate on $X$. Since $Pf$ is monic, that characteristic map was already everywhere true on $Y$. The classifier pullback then says that $f$ is invertible. Hence $P$ is a conservative functor.

It remains to check preservation of reflexive coequalizers in the opposite category. Equivalently, let $f,g:B\rightrightarrows A$ be a coreflexive pair, with $r:A\to B$ satisfying $rf=rg=1_B$, and let $e:E\hookrightarrow B$ be their equalizer. Both $f$ and $g$ are monic. For any mono $i$, there is a direct-image map ${\exists }_i$ between power objects: a subobject is sent to its composite with $i$. This uses only classification of monos, not the prior existence of general images or colimits. We have $Pi{\exists }_i=1$.

For a predicate $W\hookrightarrow B$, consider its direct image along $f$. Its pullbacks along the two sections areTo verify the second equality, $g(b)=f(w)$ with $w\in W$ implies $b=w$ after applying $r$, and therefore $f(b)=g(b)$; conversely $b\in W\cap E$ supplies that witness. This argument works for parameterized subobjects as well, so it is an equality of arrows between power objects.

Now if $h:PB\to Z$ satisfies $hPf=hPg$, then $h=h{\exists }_{e}Pe$. Hence $h{\exists }_e:PE\to Z$ is its unique factorization through $Pe$, uniqueness following from the section ${\exists }_e$. Thereforeis a coequalizer. Finite limits supply every required coreflexive equalizer. The right adjoint $P$ reflects isomorphisms and preserves the corresponding reflexive coequalizers, so $P$ is monadic. In particular ${\mathcal{E}}^{\mathrm{op}}$ is equivalent to the Eilenberg-Moore category of the double-power-object monad on $\mathcal{E}$.

Let $F:\mathcal{E}\to \mathcal{F}$ be a logical functor, and suppose $L⊣F$. Preservation of exponentials and the classifier gives $F{P}_{\mathcal{E}}\cong P_{\mathcal{F}}{F}^{\mathrm{op}}$, compatibly with the units, counits and resulting monads. Thus $F^{\mathrm{op}}$ is the algebra functor lifting the base functor $F$ through the two monadic power-object functors. The adjoint lifting theorem for monad algebra functors applies to the base adjunction $L⊣F$: its required coequalizers exist in ${\mathcal{E}}^{\mathrm{op}}$, because $\mathcal{E}$ has finite equalizers. It supplies a left adjoint $K⊣F^{\mathrm{op}}$. Taking opposites gives $F⊣K^{\mathrm{op}}$, the required right adjoint to $F$.

Preserving either of the two logical structures by itself is insufficient. For the exponential example take $F:\mathbf{Set}\to \mathbf{Set}$ constant at $1$. The constant-empty functor is its left adjoint, since both relevant hom-sets are singletons. Its canonical exponential comparison is $1\cong 1^1$, so it preserves exponentials. It has no right adjoint: a functor with a right adjoint would preserve the initial object, whereas $F(\varnothing )=1$.

For the classifier example take $G:(\mathbb{Z}/2)\text{-}\mathbf{Set}\to \mathbf{Set}$ to be fixed points. The trivial-action functor is left adjoint to $G$. In a group-action topos the classifier is the trivial-action two-element set, since invariant subsets have ordinary equivariant characteristic maps. Therefore $G$ preserves the classifier, its true arrow and the terminal object. But $G$ does not preserve the coequalizer of the identity and the nontrivial translation on the regular two-element group set: that coequalizer is $1$, while the fixed-point sets of the domain and codomain of the parallel pair are empty. Their set-theoretic coequalizer is empty, not $G(1)=1$. Thus $G$ has no right adjoint.

Write the Cartesian comonad as $(G,\epsilon ,\delta )$, with $G$ preserving finite limits. A coalgebra for a comonad is $(A,a)$ with $a:A\to GA$, ${\epsilon }_{A}a=1_A$ and ${\delta }_{A}a=Gaa$. Its forgetful functor $U:{\mathcal{E}}^G\to \mathcal{E}$ is faithful, creates finite limits, and has the cofree coalgebra right adjoint $R(X)=(GX,{\delta }_X)$. We construct the two remaining topos structures explicitly.

For exponential objects, take coalgebras $(A,a),(B,b)$ and start with $R(B^A)$. Put $X=G(B^A)$, with structure $\xi ={\delta }_{B^A}$, and letTranspose the following two maps $X\times A\to GB$ into maps $u,v:X\to (GB{)}^A$:using $G(X\times A)\cong GX\times GA$. The cofree adjunction transposes $u,v$ once more into coalgebra morphisms $R(B^A)\rightrightarrows R((GB{)}^A)$. Let $Q$ be their equalizer. A coalgebra map $(C,c)\to R(B^A)$ corresponds to an arbitrary ambient map $h:C\times A\to B$. It factors through $Q$ precisely whenwhich is exactly the condition that $h$ be a coalgebra morphism. Therefore $Q$ represents ${\mathcal{E}}^G(C\times A,B)$ and is the required exponential in a coalgebra topos.

For the subobject classifier, let $\kappa :G\Omega \to \Omega$ classify the mono $G\top :G1\cong 1\hookrightarrow G\Omega$. In the cofree coalgebra $R\Omega$, formBoth arrows are coalgebra morphisms. The cofree transpose of $\top :1\to \Omega$ factors through this equalizer and gives its true arrow. To verify classification, let $S\hookrightarrow X$ have ambient characteristic map $\chi :X\to \Omega$. It supports a subcoalgebra of $(X,x)$ exactly when it is invariant under $x$, equivalentlyThe counit proves the reverse containment in the first equation; the forward containment supplies the restricted structure map, whose coalgebra laws follow through the mono. Under the cofree adjunction, the second equation says exactly that $G\chi x:X\to R\Omega$ factors through ${\Omega }_G$. Pulling back its true arrow recovers $S$, since $\kappa G\chi x=\chi$. This proves the universal property of the subobject classifier of a coalgebra topos. Hence ${\mathcal{E}}^G$ is a topos.

Now let $f:\mathcal{E}\to \mathcal{F}$ be a geometric morphism, with $L=f^{\ast }⊣H=f_{\ast }$. The comonad $G=LH$ is Cartesian: $L$ preserves finite limits and the right adjoint $H$ preserves limits. Put $\mathcal{D}={\mathcal{E}}^G$, already a topos. The forgetful adjunction $U⊣R$ defines $p:\mathcal{E}\to \mathcal{D}$ with $p^{\ast }=U$, so $p^{\ast }$ is faithful.

The comparison functorpreserves finite limits. It has a right adjoint $J$, given on a coalgebra $(A,a)$ byIndeed, the transposed arrow $Y\to HA$ corresponds to a coalgebra map $KY\to (A,a)$ exactly when it equalizes these two maps. Applying the finite-limit-preserving $L$ shows that $LJ(A,a)$ is the equalizer ofThat equalizer is $a:A\to GA$. If $t:Z\to GA$ equalizes the pair, then $a{\epsilon }_{A}t={\epsilon }_{GA}Gat={\epsilon }_{GA}{\delta }_{A}t=t$, proving the claimed universal property. Consequently the counit $KJ(A,a)\to (A,a)$ is invertible. The fully faithful adjoint criterion makes $J$ full and faithful.

Thus $K⊣J$ defines a geometric embedding $i:\mathcal{D}\to \mathcal{F}$, and $UK=L$ identifies the composite with $f$. The requested factorization iswhere $p$ is a surjective geometric morphism and $i_{\ast }=J$ is full and faithful.

A Cartesian theory has a many-sorted first-order signature, with finite arities, and axioms expressed as sequents between Cartesian formulas. Those formulas use atomic relations and equality, truth and finite logical conjunctions. They also admit existential quantification when the quantified witness is provably unique: to form $\exists y\varphi (x,y)$, require $\varphi (x,y)\wedge \varphi (x,y^{\prime })⊢y=y^{\prime }$ relative to the theory. One can quantify a finite tuple in the same way. Arbitrary existential quantifiers, disjunction, negation and universal quantifiers are not formula constructors in this fragment. In particular falsity is not included as an additional finite-limit constructor. The universal force of a sequent comes from its free-variable context. This is the fragment whose categorical semantics requires exactly finite limits.

The Cartesian syntactic category ${\mathcal{C}}_{\mathbb{T}}$ has objects $\{\vec{x}\mid \varphi \}$, identifying harmless renamings and provably equivalent formulas-in-context. An arrow from $\{\vec{x}\mid \varphi \}$ to $\{\vec{y}\mid \psi \}$ is represented by a provably functional Cartesian relation $\theta (\vec{x},\vec{y})$: it entails $\varphi \wedge \psi$, is total on $\varphi$, and has a unique output tuple. Provable equivalence identifies arrows. Equality supplies identity arrows; composition quantifies the uniquely determined intermediate tuple in a conjunction. Totality and uniqueness prove that the composite is again functional.

The empty truth context is terminal. Products concatenate disjoint contexts and conjoin their formulas. A pullback of two functional relations adds the condition that their outputs agree; the common output is unique, so the existential quantification used to express it is Cartesian. This gives all finite limits and makes the usual equality diagrams into equalizers.

An internal model $M$ in a finite-limit category $\mathcal{E}$ interprets each sort by an object, functions by arrows and relations by subobjects. Equality is a diagonal and conjunction is a pullback intersection. A uniquely witnessed relation projects monomorphically onto the context, so its existential interpretation needs no general image operation: it is that mono. Evaluating formulas and functional relations yields a finite-limit-preserving functor $F_M:{\mathcal{C}}_{\mathbb{T}}\to \mathcal{E}$.

Conversely, the canonical syntactic model uses the single-sort truth contexts, term graphs and atomic subobjects. Its interpretation of a formula is the formula-in-context object itself. Applying any finite-limit-preserving functor supplies a model and preserves its axioms. These constructions are inverse up to the natural interpretation isomorphisms; model homomorphisms correspond to natural transformations. Therefore

For completeness, let a sequent in context be represented by subobjects $i:A\hookrightarrow C$ and $j:B\hookrightarrow C$ for its antecedent and consequent. Derivability is exactly the existence of a factorization $i=jv$ in the syntactic category. Consider the covariant representable functor ${\mathcal{C}}_{\mathbb{T}}(A,-)$, which preserves all existing limits, and hence corresponds to a set-valued model. In that model the element $i\in {\mathcal{C}}_{\mathbb{T}}(A,C)$ belongs to the antecedent, because it is the image of $1_A$. If the sequent holds, it also belongs to the consequent, so $i=jv$ for some $v:A\to B$. That is precisely a derivation of the sequent. Thus validity in all set-valued models implies Cartesian derivability. More concretely, every underivable sequent is refuted by this representable model. No assumption that every sort is inhabited is needed: some hom-sets may be empty.

The two introductory requests can be settled before the lettered applications. In the functor category $[C,\mathbf{Set}]$, finite limits and finite unions of subobjects are pointwise. The component of the diagonal at $c$ is ordinary equality on $F(c)$. Its only possible complement isThis forms a subfunctor exactly when each $F(u)$ sends unequal elements to unequal elements, equivalently when every $F(u)$ is injective. In that case $D$ and the diagonal are disjoint and their union is $F^2$ at every component. Conversely, a diagonal complement must have these components and be stable under every transition map. Hence $F$ is decidable exactly when every transition map is injective.

Regard a monoid $M$ as a one-object category; a covariant set-valued functor is a left M-set. Give $M\times A$ the diagonal left action $t\cdot (w,a)=(tw,t\cdot a)$. LetRight multiplication on the first coordinate commutes with the diagonal left action, so $m\cdot f$ remains equivariant. The formula obeys $m\cdot (n\cdot f)=(mn)\cdot f$ and $1\cdot f=f$. Evaluation isIt is equivariant because $\mathrm{ev}(m\cdot f,m\cdot a)=f(m,m\cdot a)=m\cdot f(1,a)$.

For an equivariant $h:C\times A\to B$, defineThis is equivariant in $(w,a)$, and $\hat{h}(m\cdot c)=m\cdot \hat{h}(c)$. Evaluation recovers $h$. Conversely, currying the evaluation of a map $C\to E$ recovers that map by its equivariance. This proves the exponential universal property and the natural identificationwith exactly the stated action. In particular, decidability in a set-valued functor category says that a left M-set is decidable if and only if each of its action maps is injective.

A decidable $B$ has injective action maps. First prove that evaluation at $1$ distinguishes equivariant functions. Suppose $f(1,a)=g(1,a)$ for every $a$. Fix $m\in M$ and choose $p,q$ with $pmq=p$. For each $a$, equivariance givesThe same equation holds for $g$, so these values agree. Cancel the injective action of $p$ on $B$ to obtain $f(m,a)=g(m,a)$. Hence $f=g$. This proves the hinted contrapositive and, more precisely, injectivity of the trace map $f\mapsto (a\mapsto f(1,a))$.

Now suppose $m\cdot f=m\cdot g$ in the exponential. Evaluating this equality at $(1,m\cdot a)$ givesCancel the action of $m$ on $B$. The trace maps agree, so the preceding argument gives $f=g$. Every action map on $B^A$ is therefore injective. By the introductory criterion, $B^A$ is decidable whenever $B$ is under the specified monoid condition. Neither cancellation in $M$ nor injectivity of its action on $A$ is assumed.

For the free monoid on $x,y$, use the functionThe strict inequality is important. For any prefix $v$, $|vw|>|v|+n$ is equivalent to $|w|>n$. Whenever it holds, $w$ is nonempty and prefixing $v$ does not change its final letter. When it fails, both values are zero. Thuswhich proves equivariance for the diagonal action on $M\times \mathbb{N}$ and the trivial action on $B$. Hence $f$ is an element of the exponential described above. Let $g$ be the constant-zero equivariant function. They differ at $(x,0)$.

But every word $wy$ ends in $y$, sofor every $w,n$. The action of $y$ on $B^A$ is not injective, and $B^A$ is not decidable, even though $B$ is decidable. This is a nondecidable exponential of decidable monoid sets. The monoid condition in part (a) also fails here: $|pmq|=|p|+|m|+|q|$ cannot equal $|p|$ for a nonempty word $m$.

For each object $X$, characteristic maps identify $\mathcal{E}(X,\Omega )$ with $\mathrm{Sub}(X)$. These subobject posets carry a natural Heyting algebra structure. Truth and falsity classify $X$ and the empty subobject. Intersections define $\wedge$, unions define $\vee$, and implication is characterized byThese operations commute with pullback, giving arrows on $\Omega$ and the internal Heyting algebra of truth values. Concretely, the order relation on $\Omega$ is the subobject where $p\wedge q=p$; its characteristic map is implication. Negation is $p\Rightarrow \perp$.

If $U\hookrightarrow 1$ has truth value $u:1\to \Omega$, its quasi-closed local operator isThis is double negation relative to the bottom value $u$. In the Heyting algebra interval $[u,1]$, relative implication is inherited and relative negation is $N_u(p)=p\Rightarrow u$. Also $N_u(p)=N_u(p\vee u)$. Therefore the displayed map is the composite of adjoining $u$ and relative double negation. It is inflationary, idempotent, fixes truth and preserves binary meets, so it is a Lawvere-Tierney topology. Its value at bottom is $u$.

The truth values of its sheaf topos are the fixed elements $p=q(U)(p)$. They have bottom $u$, inherited meet and join $q(U)(p\vee r)$. Their relative negation is $N_u(p)$, which is again fixed because $N_u^3=N_u$. The relative double-negation law holds on every fixed element, andThus every subobject in the sheaf topos has a complement: every quasi-closed subtopos is Boolean. This identifies its internal logic, not merely the global truth-value lattice.

Now work in $\mathcal{E}/\Omega$. The arrow $\top :1\hookrightarrow \Omega$ is a subterminal object there; internally it supplies a freely varying generic truth value $u$. Let $a_q$ be sheafification for a local operator for its quasi-closed topology, and let $\pi :\mathcal{E}/\Omega \to \mathcal{E}$ be the slice geometric morphism. The composite $h$ has inverse image $h^{\ast }=a_q{\pi }^{\ast }$.

To prove surjectivity, take any mono $S\hookrightarrow X$ in $\mathcal{E}$, classified by $p:X\to \Omega$. Its pullback along $\pi$ has predicate $p(x)$, independent of the generic $u$. If $h^{\ast }$ sends the mono to an isomorphism, it is $q$-dense in the slice, sofor all $(x,u)$. Pull back this identity along the graph $x\mapsto (x,p(x))$. Substituting $u=p(x)$ gives $q_{p(x)}(p(x))=p(x)$, and therefore $p(x)=1$. Thus the original mono was already invertible.

For parallel arrows $r,s:X\rightrightarrows Y$, equality of their inverse images makes the inverse image of their equalizer invertible. The preceding mono argument makes the equalizer invertible and hence $r=s$. Therefore $h^{\ast }$ is faithful, and the composite is a surjective geometric morphism. A fixed double-negation subtopos can erase information; allowing the generic relative bottom is what detects every original predicate.

For the completeness consequence, let $\mathbb{T}$ be coherent and use its classifying topos with the generic model. Its conservative syntactic interpretation makes an underivable coherent sequent fail as a subobject inclusion. Pulling this model into the Boolean cover constructed above preserves coherent formulas and still refutes that inclusion, because the inverse image is faithful and reflects containment. In the Boolean topos, the difference between antecedent and consequent is a nonzero complemented subobject. Slicing over that difference gives a nondegenerate Boolean topos with a global tuple satisfying the antecedent and the negation of the consequent.

Classical first-order deduction is sound in a Boolean topos. Hence $\mathbb{T}$ together with constants for that tuple, the antecedent and the negated consequent is classically consistent: a proof of contradiction would hold in the nondegenerate sliced model. The ordinary Henkin construction supplies a set model of this consistent theory. Briefly, extend it by witness constants, complete it to a maximal consistent theory, form the term structure modulo provable equality, and prove the truth lemma by induction on formulas. For possibly empty sorts use the standard encoding by sort predicates and functional graph relations, without asserting sort inhabitance; the constants for the chosen tuple assert only the needed witnesses. The resulting set model is a countermodel to the original sequent.

Consequently a coherent sequent valid in every set-valued model of a coherent theory is derivable in coherent logic. The Boolean cover supplies the crucial passage from the generic intuitionistic countermodel to consistency with classical negation; the final set-model step uses ordinary first-order completeness via its Henkin proof, rather than an assumption that every Boolean topos has points.

In a small regular category $\mathcal{C}$, the regular coverage has one-arrow covers: each regular epimorphism $\alpha :B\twoheadrightarrow A$ is a covering family by itself. Identity maps, composites and pullbacks of such arrows are again covers, so this is a basis for a Grothendieck topology. A presheaf is a sheaf precisely when every compatible section over a covering arrow descends uniquely along that arrow.

It is subcanonical. A section of the representable presheaf $yX=\mathcal{C}(-,X)$ over $B$ is a map $g:B\to X$. Its matching condition is $g{\pi }_1=g{\pi }_2$ on the kernel pair $B{\times }_{A}B$. Since a regular epimorphism is the coequalizer of its kernel pair, there is a unique $\bar{g}:A\to X$ with $\bar{g}\alpha =g$. This is exactly the sheaf condition for $yX$.

For a subfunctor $F^{\prime }\subseteq F$ of a regular-coverage sheaf, define local membership byThis is a subfunctor. If $t:C\to A$ and $\alpha$ witnesses membership, pull back $\alpha$ along $t$; the resulting cover of $C$ witnesses membership of $F(t)x$, because $F^{\prime }$ is stable under restriction.

It is a sheaf as well. Let $\beta :B\twoheadrightarrow A$ cover and let $y\in F^{\prime \prime }(B)$ satisfy the kernel-pair matching condition. The sheaf $F$ gives a unique $x\in F(A)$ with $F(\beta )x=y$. Choose a cover $\alpha :C\twoheadrightarrow B$ with $F(\alpha )y\in F^{\prime }(C)$. The composite $\beta \alpha$ is a cover of $A$ and witnesses $x\in F^{\prime \prime }(A)$. Uniqueness comes from $F$. Thus the inclusion $F^{\prime \prime }\hookrightarrow F$ is a mono between sheaves and is closed for the associated local operator.

Moreover, any closed subobject $S\subseteq F$ containing $F^{\prime }$ is itself a sheaf. If $x\in F^{\prime \prime }(A)$, its restriction along a witnessing cover lies in $S(B)$, and the sheaf condition for $S$ descends it to a section in $S(A)$. Its image in $F(A)$ is $x$ by uniqueness. Hence $F^{\prime \prime }$ is the least closed subobject containing $F^{\prime }$, andThis proves the local membership closure for the regular coverage, with a single regular epimorphism as witness.

Suppose $yA$ is the union, in the sheaf topos, of a family of subsheaves $F_i$. The union in presheaves is the pointwise union $F^{\prime }={\bigcup }_i{F}_i$; its closure is the union in sheaves. Thus $1_A\in F^{\prime \prime }(A)$. A witnessing cover $\alpha :B\twoheadrightarrow A$ belongs to $F_i(B)$ for one index $i$. The two restrictions of $\alpha$ to its kernel pair agree. Since $F_i$ is a subsheaf, this matching section descends in $F_i$ to $1_A\in F_i(A)$. Every map $t:C\to A$ is the restriction of $1_A$ along $t$, so $F_i=yA$. Therefore every representable sheaf is irreducible, even with respect to arbitrary unions. There are no empty covering families in this coverage, and $1_A$ also shows that the representable cannot be initial.

Finally, in the regular syntactic category of a regular theory, the context formula $\varphi$ defines an object $A$. Each formula $\varphi \wedge {\psi }_i$ defines a mono $A_i\hookrightarrow A$, and the associated representable subsheaf is its interpretation inside $yA$ in the generic model. A derivation of the coherent disjunction says that these finitely many subsheaves have union $yA$. Irreducibility gives $y{A}_i=yA$ for some $i$. The Yoneda embedding is full and faithful, since the coverage is subcanonical, and therefore reflects this isomorphism. Hence $A_i\hookrightarrow A$ is invertible in the syntactic category: $\varphi$ entails ${\psi }_i$. ThusThe disjunction is an outer coherent conclusion; the theory and all constituent formulas are regular. This disjunction property of regular theories follows from single-arrow descent, rather than from ordinary first-order compactness.