Independent scholarship · Open accessThe monthly digest

Full manuscript · browser edition

Higher-Order Logic in Infinity-Toposes

Continuous, single-column reading. Equations, tables, proofs, references and appendices stay in document order.

Contents · 28 sections

MANUSCRIPT FOR HIGHER CATEGORICAL SEMANTICS

Higher-Order Logic in ∞\infty-Toposes

Extending the Lambek–Scott correspondences

Abstract. We develop an ∞\infty-categorical counterpart to the relationships among typed calculi, topos semantics, and recursion in Lambek and Scott. The indexed slices of a Grothendieck ∞\infty-topos interpret substitution, dependent sums and products, identities, and propositional quantifiers. We prove an indexed comparison with its ordinary topos of 00-truncated objects, and give explicit examples in which truncation loses sections or their components, including a dependent product along a subterminal map of a finite presheaf site. Further results give a local condition under which dependent products commute with truncation, classify unrestricted and discrete sorts by different presheaf topoi, and describe descent, univalence, and torsors at the level of mapping spaces. We formulate natural-number elimination by contractibility of the space of solutions and prove the failure of absolute internal Church’s thesis in nondegenerate Grothendieck ∞\infty-toposes under classical external mathematics. The distinction between ordinary and higher semantics runs through each comparison.

Keywords. Categorical logic, ∞\infty-topos, dependent type theory, truncation, univalence, realizability.

MSC 2020. 03G30, 03B38, 18N60.

Introduction

Lambek and Scott organize categorical logic around three correspondences: typed λ\lambda-calculi and cartesian closed categories, intuitionistic type theories and toposes, and descriptions of numerical functions by arrows in categories equipped with recursion principles [1]. Their preface also points to dependent types and local cartesian closure as a distinct correspondence. A higher categorical development must explain what each of these comparisons becomes when maps have homotopies and families have nontrivial automorphisms. The resulting comparison depends on which operations preserve the truncated fragment.

We use the indexed family X↦E/XX\mapsto\mathcal E_{/X} of a Grothendieck ∞\infty-topos E\mathcal E. A context is an object XX, a type in context is a map to XX, and a term is a section. Substitution, dependent sum and dependent product form an adjoint triple. Propositional quantifiers are obtained by restricting to subobjects, with images used for existential quantification. Theorem 2 compares these constructions simultaneously on the full subcategory of set-valued types over set-valued contexts. This comparison explains which rules of ordinary extensional logic the higher model recovers.

Two separate tests delimit the comparison. In Section 3, spaces and spaces over the 22-sphere have equivalent ordinary logic on set-valued types, yet differ on sections of a constant higher type. We also give two explicit failures of interchanging 00-truncation and dependent product. One failure is detected by a nonsplit extension of finite groups. The other already occurs over a subterminal context on a finite presheaf site. Thus the ordinary comparison is an agreement of operations on a specified fragment, and information needed by dependent products can be lost by truncating the input to those operations.

The later sections follow three other aspects of the source. Descent and identity expose the role of coherence in the semantics of families. Univalent universes and classifying objects express classification by equivalence rather than by a choice of names. Natural-number recursion is formulated by a universal property of spaces of solutions, and realizability explains how an effectiveness condition can change which numerical maps exist. We use the book as a thematic point of departure and work at article scale. The proofs assemble standard topos and type-theoretic constructions around specific comparison and obstruction calculations.

Conventions.

All categories in the higher development are (∞,1)(\infty,1)-categories, all limits and colimits have their homotopy-coherent meanings, and S\mathcal S denotes the category of spaces. We write Map⁡C(A,B)\operatorname{Map}_{\mathcal C}(A,B) for the mapping space and C≃\mathcal C^\simeq for the maximal subgroupoid. A map is nn-truncated if its homotopy fibers after applying Map⁡C(T,−)\operatorname{Map}_{\mathcal C}(T,-) are nn-truncated spaces for every TT. In particular, a (−1)(-1)-truncated map is a monomorphism, and its fiber is either empty or contractible. Write τ≤nX\tau_{\le n}^{X} for relative nn-truncation in the slice over XX. We fix ambient universes and use bounded classifiers when discussing small families. The underlying external mathematics is standard set-theoretic mathematics. Logical principles ascribed to a model are statements of its internal language.

Substitution and indexed logic

An ∞\infty-topos is an accessible left exact localization of a presheaf ∞\infty-category of spaces. We use its local cartesian closure, image factorizations, and universal colimits [2, Ch. 6]. The terminal object in the slice E/X\mathcal E_{/X} is 1X=id⁡X1_X=\operatorname{id}_X. For a type p:A→Xp:A\to X, the space of terms is Map⁡E/X(1X,p)\operatorname{Map}_{\mathcal E_{/X}}(1_X,p), the homotopy fiber of Map⁡E(X,A)→Map⁡E(X,X)\operatorname{Map}_{\mathcal E}(X,A)\to \operatorname{Map}_{\mathcal E}(X,X) at id⁡X\operatorname{id}_X. This formulation includes the homotopy that makes an underlying map a section.

Simple typing can be read in the single category E\mathcal E: currying is the equivalence Map⁡E(T×A,B)≃Map⁡E(T,BA).\operatorname{Map}_{\mathcal E}(T\times A,B) \simeq \operatorname{Map}_{\mathcal E}(T,B^A). The evaluation map and its adjuncts give application and abstraction. Applying π0\pi_0 shows that the homotopy category of a cartesian closed ∞\infty-category is cartesian closed when equipped with these induced operations. A dependent context changes the base from TT to the total space of a family. Pullback in slices supplies the dependence that the nonindexed exponential does not encode.

The adjoint triple

For f:X→Yf:X\to Y, composition supplies Σf:E/X→E/Y\Sigma_f:\mathcal E_{/X}\to \mathcal E_{/Y} and pullback supplies f∗f^*. The pullback property gives Map⁡/Y(ΣfA,B)≃Map⁡/X(A,f∗B).\operatorname{Map}_{/Y}(\Sigma_f A,B) \simeq \operatorname{Map}_{/X}(A,f^*B). The functor f∗f^* preserves colimits by universality of colimits in E\mathcal E, and the slices are presentable. The adjoint functor theorem therefore gives its right adjoint Πf\Pi_f, characterized by Map⁡/X(f∗B,A)≃Map⁡/Y(B,ΠfA).\operatorname{Map}_{/X}(f^*B,A) \simeq \operatorname{Map}_{/Y}(B,\Pi_f A). The second formula interprets abstraction with a dependent domain as adjoint transposition. The unit and counit identify the operations that express the semantic β\beta and η\eta rules.

Proposition 1 (Base change and Frobenius). Suppose that image is a pullback square. There are natural equivalences g∗Σf≃Σf′(g′)∗,g∗Πf≃Πf′(g′)∗,Σf(A×Xf∗B)≃(ΣfA)×YB.\begin{aligned} g^*\Sigma_f &\simeq \Sigma_{f'}(g')^*,\\ g^*\Pi_f &\simeq \Pi_{f'}(g')^*,\\ \Sigma_f(A\times_X f^*B) &\simeq (\Sigma_f A)\times_Y B. \end{aligned}

Proof. The first equivalence is the pullback pasting law applied to the total space of AA. For a test object TT over Y′Y', the other Beck–Chevalley comparison follows from the chain Map⁡/Y′(T,g∗ΠfA)≃Map⁡/Y(ΣgT,ΠfA)≃Map⁡/X(f∗ΣgT,A)≃Map⁡/X(Σg′(f′)∗T,A)≃Map⁡/X′((f′)∗T,(g′)∗A)≃Map⁡/Y′(T,Πf′(g′)∗A).\begin{aligned} \operatorname{Map}_{/Y'}(T,g^*\Pi_f A) &\simeq \operatorname{Map}_{/Y}(\Sigma_g T,\Pi_f A)\\ &\simeq \operatorname{Map}_{/X}(f^*\Sigma_gT,A)\\ &\simeq \operatorname{Map}_{/X}(\Sigma_{g'}(f')^*T,A)\\ &\simeq \operatorname{Map}_{/X'}((f')^*T,(g')^*A)\\ &\simeq \operatorname{Map}_{/Y'}(T,\Pi_{f'}(g')^*A). \end{aligned} Here f∗Σg≃Σg′(f′)∗f^*\Sigma_g\simeq\Sigma_{g'}(f')^* is the first comparison for the transposed square. Yoneda gives the result. For Frobenius both total spaces are canonically the pullback A×YBA\times_Y B over YY. The comparisons are compatible with pasting: the pullback equivalences are the ones induced by the pasted universal cones, and taking adjoint mates respects pasting. ◻

Propositions and ordinary recovery

Let Sub⁡E(X)\operatorname{Sub}_{\mathcal E}(X) be the poset of (−1)(-1)-truncated maps to XX up to equivalence. Mapping spaces of such maps in the slice are empty or contractible. Restrictions of the preceding functors to predicates give ∃f(P)=τ≤−1YΣfP,∀f(P)=ΠfP.\exists_f(P)=\tau_{\le -1}^{Y}\Sigma_f P, \qquad \forall_f(P)=\Pi_f P. The formula for ∃f\exists_f is reflection into subobjects after composition. Its mapping property says that ∃f(P)≤Q\exists_f(P)\le Q if and only if P≤f∗QP\le f^*Q. For ∀f\forall_f, the mapping-space adjunction shows that its value is again a monomorphism and that f∗Q≤Pf^*Q\le P if and only if Q≤∀f(P)Q\le\forall_f(P). The image is stable under pullback, so the predicate comparisons follow from Proposition 1; for Frobenius at this level use that pulling back the image of ΣfP\Sigma_f P along Q↪YQ\hookrightarrow Y computes the image of P×Xf∗QP\times_X f^*Q in QQ. Composing the resulting mono with Q↪YQ\hookrightarrow Y gives intersection with QQ. This describes ordinary intuitionistic quantification in an arbitrary higher context, regardless of its truncation level.

Theorem 2 (Indexed recovery of the ordinary semantics). Let E\mathcal E be a Grothendieck ∞\infty-topos and let C=E≤0\mathcal C=\mathcal E_{\le 0} be its ordinary topos of 00-truncated objects. For X∈CX\in\mathcal C there are natural identifications (E/X)≤0≃C/X,Sub⁡E(X)≅Sub⁡C(X).(\mathcal E_{/X})_{\le 0}\simeq\mathcal C_{/X}, \qquad \operatorname{Sub}_{\mathcal E}(X) \cong\operatorname{Sub}_{\mathcal C}(X). For a map ff in C\mathcal C, the identifications intertwine substitution, Σf\Sigma_f, Πf\Pi_f, ∃f\exists_f and ∀f\forall_f with their ordinary versions. They also intertwine finite limits, relative exponentials, the diagonal equality predicate, and the subobject classifier. The comparison is natural in XX with respect to substitution and carries the base-change and Frobenius comparisons to the ordinary ones.

Proof. The 11-topos characterization identifies E≤0\mathcal E_{\le 0} with a Grothendieck topos [2, Thm. 6.4.1.5]. If XX is 00-truncated and A→XA\to X is relatively 00-truncated, then A→1A\to 1 is 00-truncated by closure under composition. Conversely, if both AA and XX are 00-truncated, the homotopy fibers of the map of discrete mapping spaces Map⁡(T,A)→Map⁡(T,X)\operatorname{Map}(T,A)\to\operatorname{Map}(T,X) are discrete. Full faithfulness of C↪E\mathcal C\hookrightarrow\mathcal E now identifies the slices. A mono over XX lies in this slice and its mapping property restricts to the ordinary mono property. Conversely, an ordinary mono has an invertible relative diagonal in C\mathcal C. Finite limits in C\mathcal C are computed in E\mathcal E, so the same diagonal is invertible there.

Pullback preserves truncated maps. If ff lies in C\mathcal C, it is 00-truncated, so its composite with a relatively 00-truncated map is again 00-truncated. The adjunction for Πf\Pi_f preserves truncated objects since its mapping spaces are tested by pulling back the source. The two adjunctions therefore restrict to the displayed ordinary slices. The reflection τ≤−1Y\tau_{\le -1}^{Y} applied after Σf\Sigma_f has the usual image universal property against the same subobjects. This proves the two claims about predicate quantifiers as well.

Finite limits and diagonals agree by the full embedding and closure under finite limits. Relative exponentials are characterized in the slice by the right adjoint to product; equivalently they can be formed as dependent products of the pullback of the codomain along the domain. The subobject classifier Ω\Omega is 00-truncated because Map⁡(T,Ω)\operatorname{Map}(T,\Omega) is the discrete space of subobjects of TT. Its representing property restricts to C\mathcal C, so the classifier and the power objects built from it agree. The base-change and Frobenius comparisons restrict because they are furnished by the same pullback and adjunction properties. ◻

Ordinary interpretation of an extensional higher-order language uses the data of this theorem: products and powers for types, subobjects for formulas, diagonals for equality, and quantifiers in context. Thus interpreting a signature whose sorts and contexts are 00-truncated gives the same terms and predicates in both models, up to the indicated identifications. This assertion concerns the semantics of that fragment. In particular, an identity type of an arbitrary higher type should not be treated as the diagonal predicate of a set.

What truncation discards

Write X↦cXX\mapsto cX for the constant-object functor S→E\mathcal S\to\mathcal E. Intrinsically, cX≃colim⁡X1cX\simeq\operatorname{colim}_{X}1. There are two different questions about recovering higher semantics. The first asks whether the truncated doctrine determines its higher ambient category. The second asks whether a higher family can be truncated before or after a computation in the slices.

Proposition 3 (The ordinary fragment does not determine the higher category). The ∞\infty-toposes S\mathcal S and S/S2\mathcal S_{/S^2} have equivalent ordinary toposes of 00-truncated objects, and their indexed set and predicate semantics agree under this equivalence. The two ∞\infty-toposes are inequivalent.

Proof. Straightening identifies spaces over S2S^2 with families S2→SS^2\to\mathcal S. The 00-truncated objects of the slice are the families with discrete fibers. A functor from a space to sets takes values on the subgroupoid of bijections, and factors through the fundamental groupoid of the space. As S2S^2 is connected and simply connected, its fundamental groupoid is terminal up to equivalence. Its category of set-valued families is therefore equivalent to Set\mathbf{Set}. Theorem 2 gives the indexed comparison.

In the slice, the terminal object is id⁡S2\operatorname{id}_{S^2} and cKcK is S2×K→S2S^2\times K\to S^2. The section space is Map⁡(S2,K)\operatorname{Map}(S^2,K). In S\mathcal S the section space of cKcK is KK. Take K=K(Z,2)K=K(\mathbb Z,2). The former has components H2(S2;Z)≅ZH^2(S^2;\mathbb Z)\cong\mathbb Z, while the latter is connected. The section space of cKcK depends only on the category since terminal objects and KK-indexed colimits do. An equivalence of the two higher categories is therefore impossible. ◻

Under the additional restriction to 11-localic ∞\infty-toposes, the ordinary topos does determine the higher topos up to equivalence [2, Prop. 6.4.5.7 and Def. 6.4.5.8].

For any f:X→Yf:X\to Y and family AA over XX, there is a canonical map τ≤0YΠfA⟶Πfτ≤0XA.\tau_{\le 0}^{Y}\Pi_f A \longrightarrow \Pi_f\tau_{\le 0}^{X}A. It comes from applying Πf\Pi_f to the truncation unit and factoring into a 00-truncated target. The theorem about restriction implies that this map is invertible if AA is already relatively 00-truncated. It does not imply that (1) is invertible for every AA over a 00-truncated base, or for every AA with connected fibers.

Example 4 (A coherent section obstructed by a group extension). Take f:BC2→1f:BC_2\to 1 in spaces and let A→BC2A\to BC_2 be the map BC4→BC2BC_4\to BC_2 induced by reduction modulo 22. Here CnC_n is the cyclic group of order nn. Its homotopy fiber is BC2BC_2, as is seen from the homotopy exact sequence and the surjectivity of C4→C2C_4\to C_2. Thus τ≤0BC2A\tau_{\le 0}^{BC_2} A is terminal in the slice and the right side of (1) is contractible. The untruncated ΠfA\Pi_f A is the space of sections of AA over BC2BC_2. A point in this space would induce a splitting of C4→C2C_4\to C_2 on fundamental groups. Basepoint choices only affect conjugation, which acts trivially here. The elements of order dividing 22 in C4C_4 both map to 00 in C2C_2, so such a splitting cannot exist. The left side of (1) is empty. The example can also be read as a space of homotopy fixed points with nonempty connected fibers and no coherent fixed point.

Example 5 (Failure over a subterminal context). Let DD be the finite poset of nonempty proper faces of a 22-simplex, and let C=D▹C=D^{\triangleright} be the result of adjoining a terminal object tt. Put E=Fun⁡(Cop,S)\mathcal E=\operatorname{Fun}(C^{\mathrm{op}},\mathcal S). Let UU be the subterminal presheaf with value ∗* on DD and value ∅\varnothing at tt. For f:U→1f:U\to 1, take A=U×cS1→UA=U\times cS^1\to U. Both contexts in ff are 00-truncated. Relative truncation is computed objectwise, so τ≤0UA≃1U\tau_{\le 0}^{U}A\simeq 1_U and (Πfτ≤0UA)(t)≃∗(\Pi_f\tau_{\le 0}^{U}A)(t)\simeq *.

Since tt is terminal, y(t)=1y(t)=1. Evaluate the untruncated product at tt, using Yoneda and adjunction: (ΠfA)(t)≃Map⁡/U(U,U×cS1)≃Map⁡E(U,cS1)≃lim⁡DopS1≃Map⁡(∣ND∣,S1).\begin{aligned} (\Pi_f A)(t) &\simeq \operatorname{Map}_{/U}(U,U\times cS^1)\\ &\simeq \operatorname{Map}_{\mathcal E}(U,cS^1)\\ &\simeq \lim_{D^{\mathrm{op}}} S^1 \simeq \operatorname{Map}(|ND|,S^1). \end{aligned} In the last line the diagram is constant. The restriction of UU to DopD^{\mathrm{op}} is terminal, and UU is its left Kan extension along Dop↪CopD^{\mathrm{op}}\hookrightarrow C^{\mathrm{op}}: the extension has value initial at tt since there are no arrows from objects of DD to tt in CopC^{\mathrm{op}}. This explains the reduction to the smaller index. The realization ∣ND∣|ND| is the barycentric subdivision of the boundary of a triangle and is equivalent to S1S^1. Its maps to S1S^1 have integer degree, so (τ≤0ΠfA)(t)(\tau_{\le 0}\Pi_f A)(t) has components indexed by Z\mathbb Z. The comparison at tt takes this discrete space to ∗* and loses the degrees. Here both bases are in the ordinary fragment. The higher information lies in the family over that fragment.

Finite locally constant index

Call f:X→Yf:X\to Y finite locally constant if some effective epimorphism ∐iYi→Y\coprod_i Y_i\to Y makes the pullback of ff over each YiY_i a finite coproduct of copies of 1Yi1_{Y_i}. The number of copies may vary with ii.

Proposition 6 (Truncating products with finite locally constant index). For a finite locally constant f:X→Yf:X\to Y, all relatively nn-truncations with n≥−1n\geq -1 commute with Πf\Pi_f: τ≤nYΠfA  ≃  Πfτ≤nXA.\tau_{\le n}^{Y}\Pi_f A \ \,\simeq\,\ \Pi_f\tau_{\le n}^{X}A.

Proof. The natural comparison factors the image of the truncation unit through the truncated source, as in (1). By Proposition 1 and stability of relative truncation under pullback, it suffices to prove the comparison after restriction to each YiY_i. These restrictions detect equivalences by effective-epimorphism descent, explained in Section 4. Over YiY_i the domain is a finite coproduct of copies of the terminal object. A type over that domain is a tuple of types over YiY_i by disjoint and universal coproducts. Substitution sends a type to the constant tuple, so the dependent product is the finite product of the tuple.

Truncation in a slice preserves finite products. For the nonempty case, take the product of the truncation units. Each unit has trivial relative nn-truncation over its target. The class of these maps is closed under composition and pullback, by the relative factorization system [2, §6.5.1]. The product of the units factors as successive pullbacks of the individual units. Its target is a product of nn-truncated types and is therefore nn-truncated. The product map thus exhibits the truncation by the uniqueness of this factorization. The empty product is terminal and is already truncated. This applies over each YiY_i and proves the claim. ◻

Descent for contexts and families

Write S\mathcal S for the ∞\infty-category of spaces. A Grothendieck ∞\infty-topos E\mathcal E is an accessible left exact localization of Fun⁡(Cop,S)\operatorname{Fun}(C^{\mathrm{op}},\mathcal S) for a small ∞\infty-category CC. In the presheaf category, restriction along an arrow of CC is part of the functorial data of a presheaf. In a localization, the local objects satisfy additional gluing conditions. There is also an intrinsic gluing statement, formulated in E\mathcal E itself, that applies to the dependent families of Section 2.

Theorem 7 (Descent for slices). Let D:I→ED:I\to\mathcal E be a small diagram with colimit XX. Restriction along its colimit cone induces an equivalence E/X ≃ lim⁡i∈IopE/D(i).\mathcal E_{/X}\ \simeq\ \lim_{i\in I^{\mathrm{op}}}\mathcal E_{/D(i)} . For an arrow i→ji\to j in II, the corresponding transition functor on the right is pullback along D(i)→D(j)D(i)\to D(j). The limit is in Cat∞\mathrm{Cat}_{\infty}, in an ambient size in which the slice categories are objects.

Proof. An object on the right consists of a diagram A→DA\to D whose naturality squares are pullbacks. Indeed, the equivalence identifying AiA_i with the restriction of AjA_j is equivalent to the assertion that the square for i→ji\to j is a pullback. The limit includes the higher coherences among those squares. One can formalize this description as the ∞\infty-category of cartesian sections of the pullback of the codomain fibration along DD. The inverse candidate extends this transformation to a map of colimit cones by setting AX=colim⁡i∈IAiA_X=\operatorname{colim}_{i\in I} A_i and taking the induced map AX→XA_X\to X. By the descent characterization of ∞\infty-topoi, the squares Ai→AXA_i\to A_X over D(i)→XD(i)\to X are pullbacks [2, Thms. 6.1.0.6 and 6.1.3.9]. Thus restriction of the candidate recovers the cartesian section. In the other direction, pulling the original colimit cone back along AX→XA_X\to X gives a colimit cone by universality of colimits. Both constructions act on morphisms through functorial pullback and colimit. Their comparison equivalences come from the two universal properties. ◻

For U→XU\to X, write U[n]=U×X⋯×XUU^{[n]}=U\times_X\cdots\times_X U with n+1n+1 factors. The simplicial object U[∙]U^{[\bullet]} uses projections as faces and diagonals as degeneracies. The arrow U→XU\to X is an effective epimorphism when the augmentation identifies ∣U[∙]∣\lvert U^{[\bullet]}\rvert with XX. Applying Theorem 7 gives E/X≃lim⁡[n]∈ΔE/U[n].\mathcal E_{/X}\simeq \lim_{[n]\in\Delta} \mathcal E_{/U^{[n]}} . At degree zero there is a family on UU. At degree one there is an equivalence between its two pullbacks to U×XUU\times_X U. At degree two there is a homotopy comparing the composite of two such equivalences with the third equivalence. The totalization records the full simplicial compatibility, including degenerate simplices. In an ordinary category some of these comparisons reduce to equations. Their role in (3) is to specify the maps and higher simplices of the category of gluing data.

In particular, let A,BA,B be families over XX and let An,BnA_n,B_n denote their restrictions. Then Map⁡E/X(A,B)≃lim⁡[n]∈ΔMap⁡E/U[n](An,Bn).\operatorname{Map}_{\mathcal E_{/X}}(A,B) \simeq \lim_{[n]\in\Delta} \operatorname{Map}_{\mathcal E_{/U^{[n]}}}(A_n,B_n). Mapping spaces commute with this limit of categories. One way to see this is to express a mapping space as the fiber at the two endpoints of the maximal subgroupoid of a functor category on Δ1\Delta^1. Taking that functor category, taking the maximal subgroupoid, and taking the endpoint fiber all preserve the limits involved. Taking A=id⁡XA=\operatorname{id}_X in (4) shows that terms of BB glue by the same descent formula. An equivalence of families can be tested after restriction to UU: all the other components are further pullbacks, and equivalences in the limit are detected componentwise.

Example 8 (An effective epimorphism with nontrivial overlaps). Let GG be a discrete group and BGBG the realization of its nerve. For the basepoint 1→BG1\to BG, the iterated homotopy fiber products are equivalent to GnG^n in degree nn. A tuple records the successive paths between copies of the basepoint. Inner face maps compose adjacent paths, and inserting a constant path gives a degeneracy. Thus the Čech object is equivalent to the bar simplicial space of GG, and 1→BG1\to BG is an effective epimorphism. A family on BGBG is thereby equivalent to a space FF equipped with a homotopy-coherent GG-action. The space FF is the fiber at the basepoint and the action is transport. The morphism space of two such families consists of coherently equivariant maps, as (4) describes.

Take F=GF=G with the left translation action. The family corresponds to the universal GG-cover EG→BGEG\to BG. It has sections over the basepoint. A global section would give a homotopy fixed point and hence a fixed element of the discrete fiber. For G≠1G\ne 1, every element of FF moves under some translation, so the global section space is empty. The descent formula locates the difference at degree one, where the local term has to agree with all of its translates.

Example 9 (A family on a homotopy pushout). The span 1←1⨿1→11\leftarrow 1\amalg 1\to 1, with the two fold maps, has pushout S1S^1 in S\mathcal S. Its double mapping cylinder has two vertices joined by two edges. Slice descent gives S/S1≃S×S×SS,\mathcal S_{/S^1}\simeq \mathcal S\times_{\mathcal S\times\mathcal S}\mathcal S , where the two functors to S×S\mathcal S\times\mathcal S are diagonals. A family is specified by fibers F0,F1F_0,F_1 and equivalences e0,e1:F0≃F1e_0,e_1:F_0\simeq F_1. After using e0e_0 to identify the fibers, the datum is a space F0F_0 with a self-equivalence e0−1e1e_0^{-1}e_1. The direction of the comparison corresponds to a choice of generator of π1(S1)\pi_1(S^1). For F0={0,1}F_0=\{0,1\} and e0−1e1e_0^{-1}e_1 the transposition, the resulting family is the connected two-sheeted cover. For discrete fibers, the section condition is the fixed-element condition for this permutation.

Descent is a condition on gluing in the base. A Čech nerve is built from one map by repeated pullbacks. A hypercover allows new covers of matching objects in higher degrees. Equation (3) follows from effective epimorphy in every Grothendieck ∞\infty-topos. Identifying the realization of every hypercover with its target is a hypercompleteness assertion [2, Thm. 6.5.3.12].

Identity types in the slices

Let p:A→Xp:A\to X be a type in context XX and form the diagonal ΔA/X:A→A×XA\Delta_{A/X}:A\to A\times_X A. Regard this arrow as the family of identities over pairs of elements of AA. Given a test context T→XT\to X and two terms a,b:T→Aa,b:T\to A over XX, the corresponding identity type over TT is Id⁡A/X(a,b)=(a,b)∗(ΔA/X).\operatorname{Id}_{A/X}(a,b)=(a,b)^*(\Delta_{A/X}). All pullbacks in (5) are homotopy pullbacks. In particular, the map from their total space to TT includes the endpoint comparison data.

Proposition 10 (Generalized paths). For a,ba,b as in (5), the space of sections of Id⁡A/X(a,b)→T\operatorname{Id}_{A/X}(a,b)\to T is equivalent to the path space from aa to bb in Map⁡E/X(T,A)\operatorname{Map}_{\mathcal E_{/X}}(T,A). The equivalence is natural under pullback of the test context.

Proof. Writing M=Map⁡E/X(T,A)M=\operatorname{Map}_{\mathcal E_{/X}}(T,A), the pullback universal property identifies the section space with the homotopy fiber of M→M×MM\to M\times M at (a,b)(a,b). For a Kan-complex model of MM, the endpoint evaluation MΔ1→M×MM^{\Delta^1}\to M\times M is a fibration and the inclusion of constant paths M→MΔ1M\to M^{\Delta^1} is an equivalence. Its ordinary fiber therefore computes the stated homotopy fiber. Precomposition in TT preserves this description. ◻

Example 11 (Parallel identities). In S\mathcal S, take X=1X=1, A=BGA=BG, and a=ba=b the basepoint. By Proposition 10 the identity type is ΩBG≃G\Omega BG\simeq G. Its cardinality is ∣G∣\lvert G\rvert when GG is finite. For nontrivial GG, this identity type has several components, violating the monomorphism condition on the diagonal. Applying (−1)(-1)-truncation in the slice over BG×BGBG\times BG gives the subobject of pairs connected by a path. In an ordinary topos, mapping spaces are discrete and the same diagonal formula gives the usual equality predicate.

Path induction and coherence

Write P→A×XAP\to A\times_X A for the family ΔA/X\Delta_{A/X} or for an equivalent representative of it in the slice. Reflexivity is a map r:A→Pr:A\to P over A×XAA\times_X A induced by this choice, with rr an equivalence on total spaces. Let q:C→Pq:C\to P be a family of conclusions and let dd be a section of r∗C→Ar^*C\to A, the reflexivity case. The square r∗C⟶C↓↓qA→rP\begin{array}{ccc} r^*C &\longrightarrow& C\\ \downarrow &&\downarrow q\\ A &\xrightarrow{r}& P \end{array} is a pullback. Since rr is an equivalence, pullback gives an equivalence between the section spaces Map⁡E/P(P,C) → ≃  Map⁡E/A(A,r∗C).\operatorname{Map}_{\mathcal E_{/P}}(P,C) \ \xrightarrow{\ \simeq\ }\ \operatorname{Map}_{\mathcal E_{/A}}(A,r^*C). Its fiber at dd is contractible. An element of this fiber is a section J(d)J(d) of CC together with a specified identification r∗J(d)≃dr^*J(d)\simeq d. This supplies the semantic elimination rule and its computation at reflexivity. Pulling any of the data back along a substitution X′→XX'\to X preserves the pullback square and the equivalence rr. The construction therefore applies to the substituted motive and reflexivity case as well.

The intrinsic interpretation uses equivalences with coherent comparisons, as seen in the specified identification in the fiber. The syntactic rule of intensional Martin-Löf type theory is formulated with a judgmental computation at reflexivity. Interpreting that form of the rule uses a presentation with chosen comprehension and stable type-former operations. In the simplicial-set model, for example, one works with Kan fibrations and a path-object factorization. The chosen reflexivity map is a trivial cofibration and the fibration representing a motive supplies a lift against it. Kapulkin and Lumsdaine construct a coherent simplicial interpretation, and Shulman’s model-topos theorem supplies strict univalent interpretations presenting every Grothendieck ∞\infty-topos [4, 5]. These presentation results address the judgmental equalities required of the model.

Dependent function extensionality

Let p:A→Xp:A\to X, q:B→Aq:B\to A, and let s,ts,t be sections of ΠpB→X\Pi_p B\to X. Denote by s^,t^\widehat s,\widehat t the corresponding sections of B→AB\to A under the adjunction of Section 2. There is an equivalence of families over XX Id⁡(ΠpB)/X(s,t)≃Πp(Id⁡B/A(s^,t^)).\operatorname{Id}_{(\Pi_pB)/X}(s,t) \simeq \Pi_p\bigl(\operatorname{Id}_{B/A}(\widehat s,\widehat t)\bigr). Indeed, over any T→XT\to X, the adjunction gives an equivalence Map⁡E/X(T,ΠpB)≃Map⁡E/A(T×XA,B).\operatorname{Map}_{\mathcal E_{/X}}(T,\Pi_p B) \simeq \operatorname{Map}_{\mathcal E_{/A}}(T\times_X A,B). It carries the two generalized sections to the pointwise generalized sections. Passing to path spaces and using Proposition 10 and the same adjunction identifies the spaces represented by the two sides of (6) at TT. The identification is natural in TT, so Yoneda gives (6). This argument proves the semantic equivalence at the level of the whole family, including its behavior under substitution.

Universes and univalence

A subobject classifier assigns to each context a space of truth values. An object classifier can assign a space of types, with paths that encode equivalences of types. To formulate a size-bounded version, fix a sufficiently large regular cardinal κ\kappa. A map A→XA\to X is relatively κ\kappa-compact if its pullback along every T→XT\to X with TT a κ\kappa-compact object has κ\kappa-compact total space. Here κ\kappa-compactness means that mapping out of the object commutes with κ\kappa-filtered colimits. Write (E/Xκ)≃(\mathcal E_{/X}^{\kappa})^{\simeq} for the maximal subgroupoid of the full subcategory of E/X\mathcal E_{/X} on these maps. In the ambient size convention of Theorem 7, the object-classifier theorem yields a universal family U~κ→Uκ\widetilde U_\kappa\to U_\kappa and equivalences natural in XX Map⁡E(X,Uκ) ≃ (E/Xκ)≃.\operatorname{Map}_{\mathcal E}(X,U_\kappa) \ \simeq\ (\mathcal E_{/X}^{\kappa})^{\simeq}. The map underlying (7) pulls back the universal family [2, §6.1.6, especially Thm. 6.1.6.8]. The classification claim specifies a size-bounded class of arrows. A syntactic universe also requires closure under the type formers that its formation rules specify.

Proposition 12 (Univalence of a classifying family). Let u,v:T→Uκu,v:T\to U_\kappa classify A→TA\to T and B→TB\to T. The canonical map Path⁡Map⁡E(T,Uκ)(u,v) ⟶ Eq⁡E/T(A,B)\operatorname{Path}_{\operatorname{Map}_{\mathcal E}(T,U_\kappa)}(u,v) \ \longrightarrow\ \operatorname{Eq}_{\mathcal E_{/T}}(A,B) is an equivalence, where the right side is the space of equivalences from AA to BB over TT. Equivalently, the identity family on UκU_\kappa over Uκ×UκU_\kappa\times U_\kappa represents the space of equivalences between the two pulled-back universal families.

Proof. An equivalence of spaces induces equivalences on path spaces between corresponding points. Apply this to (7). A path between two objects in the maximal subgroupoid of a category is an equivalence between those objects, with its higher homotopies. The equivalence in (7) maps a path of codes to transport in the universal family, which identifies the resulting path-space equivalence with the canonical map of the statement. The identity family represents the left side by Proposition 10, with base context 11. Naturality in T→Uκ×UκT\to U_\kappa\times U_\kappa gives the second claim. ◻

Proposition 13 (Descent for size-bounded families). For a small diagram D:I→ED:I\to\mathcal E with colimit XX, restriction induces an equivalence (E/Xκ)≃ ≃ lim⁡i∈Iop(E/D(i)κ)≃.(\mathcal E_{/X}^{\kappa})^{\simeq}\ \simeq\ \lim_{i\in I^{\mathrm{op}}} (\mathcal E_{/D(i)}^{\kappa})^{\simeq}. A family A→XA\to X is relatively κ\kappa-compact if its restriction to each D(i)D(i) is relatively κ\kappa-compact.

Proof. Mapping from the colimit into UκU_\kappa yields the limit of the mapping spaces from its stages. Applying (7) to these spaces gives the equivalence. To prove detection, take the restrictions of AA and their coherences induced by pullback. The displayed equivalence glues them to a relatively κ\kappa-compact map A′→XA'\to X. In the full slice this family has the same descent datum as AA. By Theorem 7, it is equivalent to AA, and relative κ\kappa-compactness is invariant under equivalence. ◻

For an effective epimorphism U→XU\to X, this proposition gives a local criterion involving only UU. All the Čech stages map to UU, so relative κ\kappa-compactness there propagates to the stages by pullback. With the whole descent datum specified, the classifying map X→UκX\to U_\kappa is recovered from its restrictions and their comparison paths. This realizes local type codes as ordinary maps into a single ambient object, to which the colimit universal property applies.

Example 14 (Codes for finite types carry permutations). In S\mathcal S, let un:1→Uκu_n:1\to U_\kappa classify a discrete nn-element space n‾\underline n. Its loop space in UκU_\kappa is Aut⁡(n‾)=Σn\operatorname{Aut}(\underline n)=\Sigma_n, a discrete group. The connected component of unu_n is equivalent to BΣnB\Sigma_n: the groupoid of spaces equivalent to n‾\underline n has a full subgroupoid on that one object, and inclusion is an equivalence of groupoids. In particular the nonidentity permutation on 2‾\underline 2 gives a noncontractible loop. Composing the classifying map of the nontrivial double cover S1→BΣ2S^1\to B\Sigma_2 with BΣ2→UκB\Sigma_2\to U_\kappa recovers Example 9. The same permutation appears there as monodromy and here as an identity between universe codes.

For a discrete group GG, the whole space of codes for families over BGBG with nn-element fibers is Map⁡S(BG,BΣn)\operatorname{Map}_{\mathcal S}(BG,B\Sigma_n). Both arguments are nerves of ordinary groupoids, so the mapping space is the nerve of the functor groupoid. Its objects are homomorphisms ρ:G→Σn\rho:G\to\Sigma_n, and an arrow ρ→ρ′\rho\to\rho' is a permutation σ\sigma with ρ′(g)=σρ(g)σ−1\rho'(g)=\sigma\rho(g)\sigma^{-1} for all gg. In particular the loop group at ρ\rho is the centralizer of ρ(G)\rho(G) in Σn\Sigma_n. This recovers both the classification by conjugacy and the automorphisms of each cover from the same mapping space.

The proposition-valued fragment gives the ordinary subobject classifier Ω\Omega. For each TT, the maximal subgroupoid of monomorphisms into TT is the discrete space of subobjects of TT. To see this, a map over TT into a monomorphism has either empty or contractible mapping space. If the map is an equivalence, its domain and codomain determine the same subobject. Thus Map⁡E(T,Ω)\operatorname{Map}_{\mathcal E}(T,\Omega) is 00-truncated, and paths between codes of propositions are equivalences of the corresponding subobjects. Equivalence of two propositions over TT is the same as implication in both directions over TT. This recovers propositional extensionality from the classifier and explains why permutation symmetries appear only once the classified families are allowed to have richer fibers [6, §3.3].

Finally, (7) classifies AA together with its context. For a chosen A→XA\to X in the size class, the space of a code a:X→Uκa:X\to U_\kappa together with an equivalence a∗U~κ≃Aa^*\widetilde U_\kappa\simeq A is contractible, since it is the fiber of (7) at AA. The connected component of the code in the mapping space has loop space Aut⁡E/X(A)\operatorname{Aut}_{\mathcal E_{/X}}(A) by Proposition 12.

Syntactic categories and classifiers

A syntactic category encodes the structural operations of a calculus in a universal property. For the simply typed cartesian closed calculus, an object is a type, and a morphism A→BA\to B is a term of type BB in a single variable of type AA, modulo definitional equality. Products encode finite contexts, including the empty context, and composition is substitution. Abstraction and application give mutually inverse functions Hom⁡(C×A,B)  ≅  Hom⁡(C,BA).\operatorname{Hom}(C\times A,B) \;\cong\; \operatorname{Hom}(C,B^A). The inverse equations are the β\beta- and η\eta-laws. Given interpretations of the generating types and constants in a cartesian closed category, recursive interpretation of terms gives the corresponding structure-preserving functor. Conversely, such a functor sends the generic types and constants to an interpretation. The two constructions recover one another by induction on expressions, with uniqueness relative to the chosen cartesian closed structure. This is the universal-property formulation of the simply typed part of the syntax–semantics correspondence.

In a homotopy-coherent semantic category the displayed universal property is an equivalence of spaces. In the dependent case, types over Γ\Gamma are objects of E/Γ\mathcal E_{/\Gamma}, and terms of A→ΓA\to\Gamma form the section space Map⁡E/Γ(id⁡Γ,A)\operatorname{Map}_{\mathcal E_{/\Gamma}}(\operatorname{id}_\Gamma,A). A path of sections is a homotopy over Γ\Gamma, and further paths encode higher identifications. Substitution is implemented by the functoriality of the slice construction. A presentation interpreting an ordinary judgmental equality still requires strictly stable operations at the level of the chosen syntax and its model. For example, the local-universes coherence theorem constructs split comprehension models under its stated hypotheses from weakly stable logical structure on a comprehension category [3]. Strict syntactic interpretability and an invariant universal property for the space of models address two separate questions. The following classifiers give universal properties for specific fragments and make their semantic morphisms explicit.

Finite-limit theories

Write P(C)=Fun⁡(Cop,S)\mathcal P(C)=\operatorname{Fun}(C^{\mathrm{op}},\mathcal S) for a small ∞\infty-category CC. For ∞\infty-topoi E\mathcal E and F\mathcal F, let Geom⁡(E,F)\operatorname{Geom}(\mathcal E,\mathcal F) be the space of geometric morphisms, computed as the maximal subgroupoid of the category of colimit-preserving left exact functors F→E\mathcal F\to\mathcal E. These functors are inverse images of geometric morphisms since the presentable adjoint functor theorem supplies right adjoints. We write D≃\mathcal D^{\simeq} for the maximal subgroupoid of an ∞\infty-category D\mathcal D. Corestriction to this subgroupoid retains equivalences of models and their higher homotopies.

Proposition 15 (Finite-limit presheaf classifier). For every small finitely complete ∞\infty-category CC and every ∞\infty-topos E\mathcal E, restriction along the Yoneda embedding gives a natural equivalence Geom⁡(E,P(C))  ≃  Fun⁡lex(C,E)≃.\operatorname{Geom}(\mathcal E,\mathcal P(C)) \;\simeq\; \operatorname{Fun}^{\mathrm{lex}}(C,\mathcal E)^{\simeq}. Under the equivalence, the universal model in P(C)\mathcal P(C) is the Yoneda embedding.

Proof. The free cocompletion theorem identifies colimit-preserving functors out of P(C)\mathcal P(C) with functors out of CC, by restriction along Yoneda [2, Theorem 5.1.5.6]. Yoneda preserves finite limits, so a left exact functor on presheaves restricts to a left exact functor on CC. Conversely, the colimit-preserving extension of a left exact functor C→EC\to\mathcal E is left exact by [2, Proposition 6.1.5.2]. Thus the equivalence restricts to the full subcategories in question and induces an equivalence on their cores. The identity inverse image restricts to Yoneda, giving the universal model. ◻

The preservation requirement controls which semantic constructions are included. Finite limits suffice to specify projections, pullback squares, and equations in finite-limit theories. Exponentials and dependent products require additional preservation conditions. For a counterexample, take the point of the presheaf topos on the ordinary arrow category [1][1] whose inverse image is evaluation at 11. For A=(∅→∗)A=(\varnothing\to *) and B=(∅→∅)B=(\varnothing\to\varnothing), in presheaf notation with the arrow directed from the value at 11 to the value at 00, both A(1)A(1) and B(1)B(1) are empty, while (BA)(1)≃Map⁡P([1])(y(1)×A,B)≃Map⁡P([1])(A,B)≃∅.\begin{aligned} (B^A)(1) &\simeq \operatorname{Map}_{\mathcal P([1])}(y(1)\times A,B) \\ &\simeq \operatorname{Map}_{\mathcal P([1])}(A,B) \simeq \varnothing. \end{aligned} Here y(1)y(1) is terminal. The exponential of the evaluated objects is ∗*. A classifying statement about dependent type theories with chosen rules therefore needs a category of models and morphisms designed to preserve those rules.

An accessible left exact localization can impose additional conditions on the models in the proposition. Suppose L ⁣:P(C)→FL\colon\mathcal P(C)\to\mathcal F is such a localization and ii its right adjoint. Then Geom⁡(E,F)\operatorname{Geom}(\mathcal E,\mathcal F) is equivalent to the subspace of those models whose colimit-preserving extensions invert every LL-equivalence. Indeed, a colimit-preserving F ⁣:P(C)→EF\colon\mathcal P(C)\to\mathcal E inverting those maps factors essentially uniquely through LL. The induced functor F‾≃Fi\overline F\simeq Fi preserves finite limits whenever FF does, since ii is a right adjoint. It also preserves colimits. A colimit of a diagram DD in F\mathcal F can be calculated as Lcolim⁡(iD)L\operatorname{colim}(iD), and applying F‾\overline F gives Fcolim⁡(iD)F\operatorname{colim}(iD). This describes a restricted class of theories by the semantic maps they invert and leaves the localization itself as an explicit hypothesis.

Two classifiers for one sort

Let K⊂S\mathcal K\subset\mathcal S be the essentially small full subcategory generated by a point under finite colimits. Equivalently, one can obtain its objects by iterating finite homotopy colimit constructions starting with a point. At each step one may choose a small collection of objects since the diagrams have finite shape and the mapping spaces are small. Passing to the closure under equivalence gives an essentially small full subcategory. Write Fin\mathrm{Fin} for the category of finite sets, considered inside spaces as discrete objects.

Theorem 16 (Unrestricted and discrete sorts). The following equivalences of spaces are natural in E\mathcal E: Geom⁡(E,P(Kop))≃E≃,Geom⁡(E,P(Finop))≃(E≤0)≃.\begin{aligned} \operatorname{Geom}(\mathcal E,\mathcal P(\mathcal K^{\mathrm{op}})) &\simeq \mathcal E^{\simeq},\\ \operatorname{Geom}(\mathcal E,\mathcal P(\mathrm{Fin}^{\mathrm{op}})) &\simeq (\mathcal E_{\leq 0})^{\simeq}. \end{aligned} Both equivalences are given by evaluating the corresponding finite-limit model at a point.

Proof. For X∈EX\in\mathcal E, the cotensor XKX^K is the limit of the constant diagram on XX indexed by the space KK. Consequently, Map⁡E(T,XK)  ≃  Map⁡S(K,Map⁡E(T,X)).\operatorname{Map}_{\mathcal E}(T,X^K) \;\simeq\; \operatorname{Map}_{\mathcal S} (K,\operatorname{Map}_{\mathcal E}(T,X)). The right side sends colimits in KK to limits, so K↦XKK\mapsto X^K is a left exact functor on Kop\mathcal K^{\mathrm{op}}. It is the right Kan extension of XX along the inclusion j ⁣:{∗}→Kopj\colon\{*\}\to\mathcal K^{\mathrm{op}}, since the indexing category (K↓j)(K\downarrow j) is the space of maps K→∗K\to * in Kop\mathcal K^{\mathrm{op}}, namely KK. If FF is left exact, the unit F→j∗j∗FF\to j_*j^*F is an equivalence at the point. The objects where the unit is an equivalence are closed under finite limits, since both functors preserve those limits. The point generates Kop\mathcal K^{\mathrm{op}} under finite limits, and hence the unit is an equivalence everywhere. The counit j∗j∗X→Xj^*j_*X\to X is an equivalence at once. This proves the first equivalence by Proposition 15.

For finite sets the right Kan extension of XX is again given by powers S↦XSS\mapsto X^S, now with SS discrete. The same argument using products shows that evaluation at a singleton classifies product-preserving functors on Finop\mathrm{Fin}^{\mathrm{op}}. To determine which are left exact, consider in Fin\mathrm{Fin} the pushout of the two copies of the fold 2→12\to 1. Its pushout object is 11. In a left exact model this gives X→ ∼ X×X×XX,X\xrightarrow{\ \sim\ } X\times_{X\times X}X, where the two maps to X×XX\times X are diagonals. The displayed map is the diagonal of the diagonal X→X×XX\to X\times X. Its being an equivalence means that this latter diagonal is a monomorphism, which characterizes 00-truncated objects. Conversely, when XX is 00-truncated, Map⁡E(T,X)\operatorname{Map}_{\mathcal E}(T,X) is discrete for every TT. Powers by finite sets then send finite colimits of sets to limits after applying Map⁡E(T,−)\operatorname{Map}_{\mathcal E}(T,-). Limits of discrete spaces agree with limits in sets, and the mapping-space criterion gives left exactness. Applying Proposition 15 proves the second identification. ◻

The fold diagram measures precisely where the theories diverge. Its pushout in spaces is S1S^1: the two points of the middle object give the two edges between the two outer points in the double mapping cylinder. The unrestricted classifier therefore assigns to this pushout the cotensor XS1≃X×X×XXX^{S^1}\simeq X\times_{X\times X}X, the object of free loops in XX. In the discrete theory, the corresponding pushout has value 11, and left exactness requires the resulting constant-loop map X→XS1X\to X^{S^1} to be an equivalence. For an explicit computation in spaces, if X=K(A,1)X=K(A,1) for an abelian group AA, then the components of the free loop space are indexed by AA. Evaluation at a point gives a fibration with fiber ΩX≃A\Omega X\simeq A, and its monodromy is conjugation, which is trivial here. Thus any nonzero AA obstructs the constant-loop map from being an equivalence. The difference between the classifiers is already detected by a single finite-limit condition, even though their generic object has the same product operations.

The truncation functor K→Fin\mathcal K\to\mathrm{Fin}, K↦π0KK\mapsto \pi_0K, preserves finite colimits and lands in finite sets because finite colimits of finite sets are finite. After taking opposites and applying Proposition 15, it determines a geometric morphism P(Finop)⟶P(Kop).\mathcal P(\mathrm{Fin}^{\mathrm{op}}) \longrightarrow \mathcal P(\mathcal K^{\mathrm{op}}). On model spaces, postcomposition with this morphism is exactly the inclusion of the core of the 00-truncated objects into the core of all objects. The functor from the discrete theory into the unrestricted one at the level of models is consequently realized by an explicit morphism of their classifying topoi.

Adding an inhabitation axiom

The same unrestricted sort can be constrained by an existential axiom. Let C=KopC=\mathcal K^{\mathrm{op}}, A=y(∗)A=y(*), and let I↪1I\hookrightarrow 1 be the image of A→1A\to 1 in P(C)\mathcal P(C). The terminal object is representable by the terminal object of CC, so I↪1I\hookrightarrow 1 determines a sieve on that object. Take the Grothendieck topology JJ generated by declaring it covering. The topos Shv⁡J(C)\operatorname{Shv}_J(C) classifies objects XX such that X→1X\to 1 is an effective epimorphism. In the internal language this condition is the truth of ∃x:X\exists x:X, with existence interpreted by propositional truncation.

To prove the claim, let F ⁣:P(C)→EF\colon\mathcal P(C)\to\mathcal E be the inverse image corresponding to XX. Inverse-image functors preserve effective epimorphisms since they preserve the formation and realization of Čech nerves. They also preserve monomorphisms by left exactness. By uniqueness of the effective epi–mono factorization, F(I)↪1F(I)\hookrightarrow 1 is the image of X→1X\to 1. If FF factors through sheafification, it inverts I↪1I\hookrightarrow 1, and so the image is all of 11.

For the converse, suppose F(I)↪1F(I)\hookrightarrow 1 is an equivalence. For any sieve on a representable, its image under FF is the image of the coproduct of the objects in the corresponding family of arrows under F∘yF\circ y. Indeed a sieve is covered by the representables mapping into it, and FF preserves images and coproducts. Thus the sieves inverted by FF are exactly the covering sieves of the relative canonical topology for the left exact functor F∘yF\circ y [2, Proposition 6.2.4.2]. By hypothesis that topology contains the generating cover of JJ, so FF inverts all its covering-sieve inclusions. The universal property of sheafification and the preceding localization argument give the factorization, with its space of choices contractible.

For example, take E=S/S1\mathcal E=\mathcal S_{/S^1} and let XX be the object given by the basepoint map ∗→S1*\to S^1. Its structure map is an effective epimorphism because it is surjective on components. A section would split the induced map on π1\pi_1, which is impossible. This distinguishes local inhabitation, represented by the sheaf classifier, from the additional data of a term of the type in the terminal context.

Classifying objects and torsors

A classifying object represents a functor on the objects of a fixed topos. This complements the preceding classifying topoi, whose universal property varies the ambient topos. Group torsors give a representability statement that displays all levels of equivalence data.

Let GG be a group object in E\mathcal E, presented by its reduced groupoid object B∙GB_\bullet G. Thus B0G=1B_0G=1, B1G=GB_1G=G, and the Segal identifications give BnG≃GnB_nG\simeq G^n. Define BG=∣B∙G∣BG=|B_\bullet G|, with its map 1→BG1\to BG induced from degree zero. By effectiveness of groupoid objects in an ∞\infty-topos, B∙GB_\bullet G is the Čech nerve of that map, which is an effective epimorphism. In particular G≃1×BG1G\simeq 1\times_{BG}1, compatibly with the group multiplication from the groupoid structure.

Definition 17. A right GG-torsor over XX is a coherently GG-equivariant map p ⁣:P→Xp\colon P\to X, with trivial action on XX, such that pp is an effective epimorphism and the action comparison P×G⟶P×XP,(u,g)⟼(u,ug)P\times G\longrightarrow P\times_X P, \qquad (u,g)\longmapsto(u,ug) is an equivalence. The action is encoded by its simplicial action groupoid with nn-simplices P×GnP\times G^n. Write Tors⁡G(X)\operatorname{Tors}_G(X) for the space of these torsors and their equivariant equivalences over XX.

The action comparison is often called the principal bundle condition. It states that once two points in a fiber have been chosen, the space of group elements taking the first point to the second is contractible. If pp has a section ss, restricting the comparison along the first coordinate ss identifies X×GX\times G with PP by (x,g)↦s(x)g(x,g)\mapsto s(x)g. In particular each torsor becomes trivial after its own effective epimorphism P→XP\to X, using the diagonal section of the pullback. This supplies local triviality without choosing an external topology on E\mathcal E.

Theorem 18 (Classification at the level of spaces). There is a natural equivalence Map⁡E(X,BG)  ≃  Tors⁡G(X).\operatorname{Map}_{\mathcal E}(X,BG) \;\simeq\; \operatorname{Tors}_G(X). The torsor corresponding to f ⁣:X→BGf\colon X\to BG is determined by the pullback square P⟶1↓↓X→ f BG.\begin{array}{ccc} P & \longrightarrow & 1 \\ \big\downarrow && \big\downarrow \\ X & \xrightarrow{\ f\ } & BG . \end{array}

Proof. Effectiveness identifies the Čech nerve of 1→BG1\to BG with the reduced action groupoid B∙GB_\bullet G. It follows that 1→BG1\to BG is a GG-torsor in the slice over BGBG. Base change preserves effective epimorphisms and the action comparison, so pullback along ff gives a torsor over XX.

In the other direction, the action comparison identifies the action groupoid of PP with the Čech nerve of pp. In degree one this is the principal bundle condition, and the Segal maps give the equivalence in all degrees. Projection to GnG^n defines a simplicial map from that nerve to B∙GB_\bullet G. Realization gives a classifying map X→BGX\to BG, because the augmentation of the Čech nerve realizes to XX. The simplicial map together with the augmentation gives an equivariant map from the given PP to X×BG1X\times_{BG}1 over XX. More explicitly, the realization maps give a map of the action groupoids into X×BGB∙GX\times_{BG}B_\bullet G, and equivariance follows from its compatibility with the projection to B∙GB_\bullet G.

An equivariant map between torsors over the same base is an equivalence. To see this, pull back along the source torsor. The diagonal section trivializes the source, and its image under the equivariant map trivializes the target. In these coordinates the comparison is the identity. Base change along the effective epimorphism detects equivalences by descent, proving the assertion. Thus the comparison P→X×BG1P\to X\times_{BG}1 is an equivalence.

Finally, the action groupoid of a pullback torsor for ff is the base change of B∙GB_\bullet G along ff. Its realization recovers ff since realizations are universal in E\mathcal E. The comparisons are natural, being induced by pullbacks, simplicial maps and their colimits. They give inverse equivalences on the spaces, including higher homotopies. This is the internal principal bundle classification of [7, Section 3]. ◻

Example 19 (From principal bundles to higher cohomology). Let AA be a discrete abelian group and take E=S\mathcal E=\mathcal S, with G=K(A,n)G=K(A,n) for n≥1n\geq 1 in its loop group structure from K(A,n+1)K(A,n+1). The delooping is K(A,n+1)K(A,n+1), so the components of Tors⁡G(X)\operatorname{Tors}_{G}(X) are Hn+1(X;A)H^{n+1}(X;A). For a CW model of XX, the higher groups at the trivial torsor satisfy πjTors⁡G(X)  ≅  Hn+1−j(X;A)(1≤j≤n+1).\pi_j\operatorname{Tors}_{G}(X) \;\cong\;H^{n+1-j}(X;A) \qquad (1\leq j\leq n+1). Indeed, based maps Sj→Map⁡(X,K(A,n+1))S^j\to\operatorname{Map}(X,K(A,n+1)) correspond to based maps from Sj∧X+S^j\wedge X_+, and cohomology of that smash product is given by the suspension isomorphism. The higher groups vanish above n+1n+1. For X=Sn+1X=S^{n+1}, the component set and the group in degree n+1n+1 are both AA, while the other positive-degree groups are zero. Every component has the same homotopy groups by translation in the abelian group object Map⁡(X,K(A,n+1))\operatorname{Map}(X,K(A,n+1)). Over a point and for a discrete group GG, the classification similarly gives the space BGBG with one component and automorphism group GG. Thus the sets of equivalence classes recover familiar classifications and the spaces additionally record symmetries of each model.

Truth, choice, and localization

A proposition over a context XX is a (−1)(-1)-truncated map to XX. The higher analogue of a predicate equipped with witnesses is an arbitrary map p:A→Xp:A\to X. In the latter, the homotopy type of the fiber records both the witnesses and the identifications among them. Passing from this type to its truth value is a relative operation. It takes place in E/X\mathcal E_{/X}, so it uses the geometry of the context as well as that of the domain.

The support of a family

Definition 20. The support supp⁡X(A)\operatorname{supp}_{X}(A) of A→XA\to X is its relative (−1)(-1)-truncation. Write the image factorization as where the first arrow is effective epimorphic and the second is a monomorphism. If U↪XU\hookrightarrow X is a proposition, write ⊥X\bot_X and ⊤X\top_X for the least and greatest propositions over XX.

The support has the following elementary calculus. It applies to families whose fibers have arbitrary homotopy types.

Proposition 21. Let f:Y→Xf:Y\to X be a map in an ∞\infty-topos.

  1. For A→XA\to X and a proposition U→XU\to X, precomposition gives an equivalence Map⁡/X(supp⁡X(A),U)≃Map⁡/X(A,U).\operatorname{Map}_{/X}(\operatorname{supp}_X(A),U) \simeq \operatorname{Map}_{/X}(A,U).

  2. There is a natural equivalence f∗supp⁡X(A)≃supp⁡Y(f∗A)f^*\operatorname{supp}_X(A)\simeq \operatorname{supp}_Y(f^*A).

  3. The support of the slice coproduct P⨿QP\amalg Q is their join in Sub⁡(X)\operatorname{Sub}(X) when P,QP,Q are propositions. For B→YB\to Y, the support of the composite B→Y→XB\to Y\to X is ∃fsupp⁡Y(B)\exists_f\operatorname{supp}_Y(B).

Proof. The first assertion is orthogonality of effective epimorphisms and monomorphisms applied to A↠supp⁡X(A)A\twoheadrightarrow\operatorname{supp}_X(A) and U↪XU\hookrightarrow X. For the second, pull back the image factorization. Both classes of maps are stable under pullback, so the new factorization has the universal property of the image. A map from P⨿QP\amalg Q to a proposition exists exactly when the two summands admit maps to it. This is the least-upper-bound property. For the composite, a map over XX from BB to a proposition UU is adjoint to a map from BB to f∗Uf^*U over YY. Since f∗Uf^*U is a proposition, this factors through supp⁡Y(B)\operatorname{supp}_Y(B). The resulting equivalence of conditions is the defining adjunction of ∃f\exists_f. ◻

Full support is equivalent to effective epimorphicity of A→XA\to X. In a sheaf model this is the local availability of witnesses, tested after base change to each stage and passage to a cover. A section X→AX\to A is a witness compatible over the entire context. These two conditions agree for a proposition AA but differ for general families. In fact a mono with full support is an equivalence. For other families, the unit into the support permits elimination into propositions and produces a map into a given type only when suitably coherent additional data are available.

Example 22 (A disjunction with no global tag). Use space-valued sheaves on R\mathbb R. Let UU and VV be the subterminals represented by the opens (−∞,1)(-\infty,1) and (−1,∞)(-1,\infty). They join to 11 because the two opens cover the line. Thus U⨿V→1U\amalg V\to 1 has full support. A global section of this coproduct would pull the disjoint summands back to complementary opens WU,WVW_U,W_V covering the line, with WU⊆UW_U\subseteq U and WV⊆VW_V\subseteq V. By connectedness one would be the whole line, contrary to each containment. The calculation works in the ordinary sheaf topos as well: the obstruction concerns gluing the tags and already occurs for a 00-truncated family.

Relative truncation is compatible with change of base, as in Proposition 21. Preservation of finite limits by a truncation functor is a separate condition. In spaces, for a nontrivial discrete group GG, the homotopy pullback of the two basepoints ∗→BG←∗*\to BG\leftarrow * is GG as a discrete space. Truncating the diagram objectwise by τ≤0\tau_{\leq 0} first yields ∗→∗←∗*\to *\leftarrow *, whose pullback is ∗*. Thus the functor of components can preserve the meanings of ordinary predicates while changing a finite-limit construction on higher types. This applies already to the self-intersection of a single point. The same diagram also exhibits failure of left exactness of propositional truncation if BGBG is replaced by the discrete two-element space and the basepoints select its two distinct elements.

Boolean propositions and the strength of choice

Definition 23. Say that the predicate logic of E\mathcal E is Boolean when every subobject lattice Sub⁡E(X)\operatorname{Sub}_{\mathcal E}(X) is Boolean. Write ¬P\neg P for the Heyting implication P⇒⊥XP\Rightarrow\bot_X.

This condition is exactly excluded middle for propositions in every context. It is encoded by the universal predicate t:1↪Ωt:1\hookrightarrow\Omega, where Ω\Omega is the subobject classifier. If t∨¬t=⊤Ωt\vee\neg t=\top_\Omega, any predicate satisfies the law by pullback along its classifying map. Indeed pullback preserves the initial object, unions, and predicate implication. For the last assertion use preservation of finite limits together with base change for the right adjoints to substitution in the slices. The converse applies excluded middle to tt itself.

Under classical external logic, the predicate logic of S\mathcal S is Boolean. A monomorphism of spaces includes a union of connected components: its fibers over points are empty or contractible, and path transport maintains this condition or exchanges the contractible fibers by equivalences. The complementary union yields its negation. There is still a difference between truth and witness selection. If GG is nontrivial, the basepoint ∗→BG*\to BG is effective epimorphic by connectedness. A section would make BGBG a retract of ∗* and hence contractible. This fails since π1(BG)≅G\pi_1(BG)\cong G.

Even a choice principle restricted to sets can fail with Boolean predicate logic. Take E=Fun⁡(BG,S)\mathcal E=\operatorname{Fun}(BG,\mathcal S), the ∞\infty-topos of GG-spaces. A subobject of a GG-space is an invariant union of components. To see this, classify the underlying mono by its subset of components. Each arrow of BGBG gives a permutation on components, and equivariance makes the subset invariant. Conversely a union of components for an invariant subset is closed under this transport, with its equivariance induced from the given GG-space. The complement is invariant, proving Booleanity. The free transitive GG-set GG, viewed as a discrete GG-space, has full support over 11 by objectwise computation of colimits and finite limits. A section of G→1G\to 1 would be an invariant element of the discrete GG-set. There is none for G≠1G\ne 1. The terminal object and the free transitive GG-set both belong to the ordinary topos of GG-sets, so the example also refutes that every epi of sets splits in this model.

For comparison, a space-valued sheaf topos on a space ZZ has Sub⁡(1)\operatorname{Sub}(1) identified with the frame of opens. Here ¬U=int⁡(Z∖U)\neg U=\operatorname{int}(Z\setminus U) because this is the largest open disjoint from UU. On Z=RZ=\mathbb R, the formula U∨¬UU\vee\neg U for U=(0,∞)U=(0,\infty) omits the origin. This gives an intuitionistic model even when the metatheory used to build the sheaf topos is classical. Internal Booleanity and the external rules used in constructing the category have different domains of application.

An explicit dense localization

A left exact localization L:E⇄D:iL:\mathcal E\rightleftarrows \mathcal D:i is an adjunction with fully faithful right adjoint and finite-limit-preserving left adjoint. In the presentable setting we take LL accessible. Such a reflector preserves images because the factorization into an effective epimorphism and a mono is preserved. It preserves monos by transporting their diagonals through finite limits. It preserves effective epis by transporting the simplicial Čech nerve through finite limits and its realization through colimits. Thus if A→XA\to X is any family, there is an equivalence Lsupp⁡X(A)≃supp⁡LX(LA),L\operatorname{supp}_X(A)\simeq\operatorname{supp}_{LX}(LA), viewed as objects over LXLX. A localization can send a proper support to the top support, as the following small sheaf model shows.

Example 24 (Localizing at the dense open of Sierpiński space). Let Z={0,1}Z=\{0,1\} with opens ∅,U={1},Z\varnothing, U=\{1\}, Z. Its space-valued sheaves are diagrams A→BA\to B of spaces, with AA the value on ZZ and BB the value on UU. Every open cover of a nonempty open contains that open itself, so the only additional condition imposes a terminal value on ∅\varnothing. The subterminal U↪1U\hookrightarrow 1 is the map of diagrams (∅⟶∗)  ⟶  (∗⟶∗).(\varnothing\longrightarrow *) \;\longrightarrow\; (*\longrightarrow *). A diagram A→BA\to B is local for this map exactly when A→BA\to B is an equivalence, since mapping out of the two diagrams computes sections over ZZ and UU respectively. The local diagrams identify with S\mathcal S via evaluation at UU, with inverse up to equivalence given by the constant diagram. Evaluation is the reflector: maps into (C→idC)(C\xrightarrow{\mathrm{id}}C) are determined, up to contractible choice, by the map B→CB\to C. The reflector preserves limits as limits of diagrams are computed pointwise. Consequently this geometric localization preserves all higher homotopy in the value on UU. It turns U↪1U\hookrightarrow 1 into an equivalence, although U∨¬U=UU\vee\neg U=U before localization.

The double-negation action of this reflector can be computed in arbitrary contexts. Fix r:A→Br:A\to B, and identify one of its subobjects by a pair of unions of components M⊆AM\subseteq A and N⊆BN\subseteq B with M⊆r−1(N)M\subseteq r^{-1}(N). In the following formulas complements inside a space are complementary unions of components. Any subobject disjoint from (M,N)(M,N) has its second entry contained in B∖NB\setminus N, hence its first entry contained in r−1(B∖N)r^{-1}(B\setminus N). This latter pair is itself a subobject disjoint from (M,N)(M,N). Therefore ¬(M,N)=(r−1(B∖N),B∖N),¬¬(M,N)=(r−1N,N).\begin{aligned} \neg(M,N)&=(r^{-1}(B\setminus N),B\setminus N),\\ \neg\neg(M,N)&=(r^{-1}N,N). \end{aligned} Here r−1r^{-1} denotes the homotopy pullback of a mono. Reflecting (M,N)↪(A,B)(M,N)\hookrightarrow(A,B) gives N↪BN\hookrightarrow B. Pulling its image under the right adjoint back along the unit of the adjunction gives precisely (r−1N,N)(r^{-1}N,N). Thus double negation on predicates agrees with this localization in every context, even when AA and BB have nontrivial higher homotopy. The closure of a subobject and the higher data local to UU can both be read directly from the localization. Compare the general treatment of topological localizations in [2, §6.2] and left exact modalities in [8].

Example 25 (A reflector that changes implications). The same diagram category has a different accessible left exact localization. Evaluation at ZZ has fully faithful right adjoint C↦(C→∗)C\mapsto(C\to *), as a map of diagrams to this target is specified by its value on the first entry. The left adjoint, denoted KK, sends both UU and 00 to the empty space. Since UU was dense, ¬U=0\neg U=0 in the source, so there is a strict inequality K(¬U)=∅<∗=¬K(U)K(\neg U)=\varnothing \quad < \quad *=\neg K(U) in the subobject lattice of the terminal space. This also computes a failure to preserve an exponential. The Heyting implication U⇒0U\Rightarrow0 is the exponential 0U0^U, since both operands are subterminal and the exponential has the adjunction for implication. In the target the corresponding exponential is ∅∅≃∗\varnothing^{\varnothing}\simeq *. Evaluation at ZZ preserves stable images by the argument above, whereas implication uses a right adjoint and the displayed strict inequality shows precisely where its preservation can fail. This matters when a geometric localization is used to move an interpretation of logic between models: a proof that uses implication may require an additional preservation argument beyond left exactness.

Recursion and computability

The natural numbers object organizes the categorical study of recursion in Lambek and Scott [1]. In an ∞\infty-topos, its elimination principle applies to families with arbitrary homotopy types. The natural numbers themselves still form a set internally. The higher structure appears in the spaces of sections and in the comparisons that express the recursion equations. This distinction also allows us to locate the additional mathematical structure necessary for a realizability interpretation.

The recursion space

Let E\mathcal E be a Grothendieck ∞\infty-topos, write 11 for its terminal object, and put N=∐n∈N1,z=i0,sin=in+1,N=\coprod_{n\in\mathbb N}1, \qquad z=i_0, \qquad s i_n=i_{n+1}, where ini_n is the nnth coproduct injection. Here N\mathbb N in the index denotes the external set and NN denotes an object of E\mathcal E. The relation sin=in+1s i_n=i_{n+1} denotes the comparison supplied by the coproduct property. The general relation between inductive types and homotopy-initial algebras is treated by Awodey, Gambino, and Sojakova [9].

Proposition 26 (Homotopy-initial natural numbers). The object NN is 00-truncated. Given a:1→Aa:1\to A and b:A→Ab:A\to A, the space of triples (f,α,β),f:N→A,α:fz≃a,β:fs≃bf(f,\alpha,\beta),\qquad f:N\to A,\quad \alpha:fz\simeq a,\quad \beta:fs\simeq bf is contractible. In particular (N,[z,s])(N,[z,s]) is initial among algebras for 1⨿(−)1\amalg(-) with homotopy-commuting morphisms of algebras.

Proof. Universality of coproducts gives N×N≃∐m,n∈N1N\times N\simeq\coprod_{m,n\in\mathbb N}1. The pullback of the diagonal N→N×NN\to N\times N to the summand indexed by (m,n)(m,n) is the pullback 1×N11\times_N1 of the injections imi_m and ini_n. By disjointness it is initial when m≠nm\ne n, and equivalent to 11 when m=nm=n. A pullback of a diagonal along an arbitrary map to N×NN\times N decomposes into the corresponding pullbacks over these summands. Thus the diagonal is a monomorphism, which is the criterion for 00-truncatedness.

Set K=Map⁡E(1,A)K=\operatorname{Map}_{\mathcal E}(1,A). The coproduct property identifies Map⁡E(N,A)\operatorname{Map}_{\mathcal E}(N,A) with ∏n∈NK\prod_{n\in\mathbb N}K. In this description the desired space consists of sequences (xn)(x_n) with paths x0⇝ax_0\leadsto a and xn+1⇝bxnx_{n+1}\leadsto b x_n for every nn. The paths are part of the points of this space. The space of the first entry with its path to aa is a based path space with variable starting point and is contractible. At each finite stage, forgetting the last entry and its path has contractible homotopy fibers, since extending the sequence is choosing a point of KK together with a path from that point to a specified point of KK. Each finite stage is therefore contractible. The desired space is the inverse limit of these finite stages in S\mathcal S, so is itself contractible.

For an endofunctor FF, take the category of algebras to be the pullback of the arrow category along X↦(FX,X)X\mapsto (FX,X). The mapping space from u:FX→Xu:FX\to X to v:FY→Yv:FY\to Y is then the homotopy equalizer of the maps f↦fuf\mapsto f u and f↦vFff\mapsto v Ff from Map⁡E(X,Y)\operatorname{Map}_{\mathcal E}(X,Y) to Map⁡E(FX,Y)\operatorname{Map}_{\mathcal E}(FX,Y). For F=1⨿(−)F=1\amalg(-) and the source (N,[z,s])(N,[z,s]), the two components of the equalizer are exactly α\alpha and β\beta. ◻

Contractibility is stronger than uniqueness of the homotopy class of the underlying arrow. For instance, in S\mathcal S, choose A=S1A=S^1, let aa be its base point, and take bb to be the identity. The underlying arrow space (S1)N(S^1)^{\mathbb N} has nontrivial loops. The base path and all step paths in Proposition 26 supply the data that make the space of solutions contractible.

Dependent recursion and parameters

For a family p:E→Np:E\to N, an initial datum is a point a:1→Ea:1\to E over zz, and a successor datum is a map d:E→Ed:E\to E over ss. The latter consists of dd and a chosen homotopy pd≃spp d\simeq s p. A dependent solution is a section σ\sigma of pp, a comparison σz≃a\sigma z\simeq a over zz, and a comparison σs≃dσ\sigma s\simeq d\sigma over ss.

Proposition 27 (Dependent elimination). The space of dependent solutions is contractible. The same construction holds in every slice E/Γ\mathcal E_{/\Gamma}, with natural numbers object Γ×N→Γ\Gamma\times N\to\Gamma, and is stable under pullback of contexts.

Proof. Let En=in∗EE_n=i_n^*E and Kn=Map⁡E(1,En)K_n=\operatorname{Map}_{\mathcal E}(1,E_n). Regard 11 with structure map ini_n as the nnth object of a discrete diagram in E/N\mathcal E_{/N}. Its coproduct is idN\mathrm{id}_N, because coproducts in a slice are computed on the domains. Therefore Map⁡E/N(idN,p)≃∏n∈NKn.\operatorname{Map}_{\mathcal E_{/N}}(\mathrm{id}_N,p) \simeq\prod_{n\in\mathbb N}K_n . The successor datum and the chosen comparison for sins i_n induce maps dn:Kn→Kn+1d_n:K_n\to K_{n+1}. The base datum gives a point of K0K_0. In these coordinates the solution space consists of xn∈Knx_n\in K_n with paths x0⇝ax_0\leadsto a and xn+1⇝dn(xn)x_{n+1}\leadsto d_n(x_n). Again, each finite stage is contractible by taking the path space with variable starting point, and the solution space is their inverse limit.

Apply the argument in E/Γ\mathcal E_{/\Gamma}, whose terminal object is idΓ\mathrm{id}_\Gamma. Universality of coproducts identifies the sum of its copies of idΓ\mathrm{id}_\Gamma with Γ×N\Gamma\times N over Γ\Gamma. A change of context preserves this coproduct and sends the recursion data and their comparisons to those for the pulled-back family. It sends a solution to a solution and identifies the distinguished solution up to the contractible space described above. ◻

If pp is a monomorphism, the dependent conclusion is induction for a predicate on NN. A proof at zero and a proof of successor closure give a section of that monomorphism, hence the predicate holds everywhere. If pp has higher fibers, the same proof yields a coherent family of terms. For an ordinary example with parameters, let a:Γ→Na:\Gamma\to N and b:Γ×N×N→Nb:\Gamma\times N\times N\to N be the base and step maps for primitive recursion. Over Γ\Gamma, recurse with state (n,x)(n,x), initial state (0,a)(0,a), and transition (n,x)↦(s(n),b(−,n,x))(n,x)\mapsto(s(n),b(-,n,x)). The first coordinate of the resulting map is the identity on the numerical index by uniqueness of recursion. The second coordinate defines rr with r(γ,0)=a(γ)r(\gamma,0)=a(\gamma) and r(γ,s(n))=b(γ,n,r(γ,n))r(\gamma,s(n))=b(\gamma,n,r(\gamma,n)). The equality notation here is justified by the 00-truncated target. In a type-theoretic presentation, judgmental computation rules require the corresponding coherent choices of model structure.

In particular, define addition by using the first numerical input as initial value and incrementing the state at each iteration. Multiplication uses zero as initial value and adds the first input at each iteration. On an external numerals pair (m,n)(m,n), these maps land in the summands indexed by m+nm+n and mnmn, respectively. The claim follows by ordinary induction on the second index. Conversely these values determine the arrows by the coproduct property of N×NN\times N. The same reasoning extends to a primitive recursive definition built from zero, successor, projections, composition, and primitive recursion. Inverse images of geometric morphisms preserve the sums of copies of 11, the finite products, and the input maps of recursion. They therefore preserve these arithmetic operations. This preservation concerns the specified operations and their equations.

Example 28 (Higher-order numerical recursion). Let F=NNF=N^N and let 1N=sz:1→N1_N=s z:1\to N be the numeral one. In context FF, the generic function ff is evaluation. Take f(1N)f(1_N) as initial value and ff as transition for a recursion with target NN. Transposing the resulting map F×N→NF\times N\to N defines an arrow Φ:F→F\Phi:F\to F satisfying Φ(f)(0)=f(1N),Φ(f)(s(n))=f(Φ(f)(n)).\Phi(f)(0)=f(1_N), \qquad \Phi(f)(s(n))=f\bigl(\Phi(f)(n)\bigr). Recursion with target FF now gives h:N→Fh:N\to F with h(0)=sh(0)=s and h(s(m))=Φ(h(m))h(s(m))=\Phi(h(m)). Its uncurried map a:N×N→Na:N\times N\to N satisfies a(0,n)=s(n),a(s(m),0)=a(m,1N),a(s(m),s(n))=a(m,a(s(m),n)).\begin{aligned} a(0,n)&=s(n),\\ a(s(m),0)&=a(m,1_N),\\ a(s(m),s(n))&=a(m,a(s(m),n)). \end{aligned} These equations give the Ackermann–Péter function on external numerals, as follows by induction first on mm and then on nn. This function lies beyond numerical primitive recursion [10, §1.4]. The outer state FF is itself a type of functions, so the categorical construction uses recursion at a higher simple type. The object FF is 00-truncated by the exponential adjunction and the truncation of NN. Thus this example already belongs to the ordinary fragment.

Absolute Church’s thesis

Fix a standard external enumeration (φe)e∈N(\varphi_e)_{e\in\mathbb N} of the partial recursive functions. Write H(e,n,t,m)H(e,n,t,m) for the decidable relation saying that tt is a code of a terminating computation of program ee on input nn with output mm. For a Grothendieck ∞\infty-topos, interpret this predicate as the subobject of N4N^4 obtained by taking the coproduct of the summands on which the external relation holds. The object N4N^4 here is the fourfold product, and NNN^N below is the exponential. The corresponding form of Church’s thesis is the internal proposition ∀f:NN ∃e:N ∀n:N ∃t:N H(e,n,t,f(n)). \forall f:N^N\ \exists e:N\ \forall n:N\ \exists t:N\, H(e,n,t,f(n)). The numerical relation can equivalently be interpreted from its primitive recursive characteristic function. The geometric inverse image S→E\mathcal S\to\mathcal E preserves finite products and the coproducts defining numerical operations, so the two descriptions agree on every numeral tuple and hence on their coproduct. Existential quantification in (8) is propositional.

Proposition 29 (Failure for Grothendieck semantics). In the classical external metatheory, the truth value of (8) is the initial subobject of 11 in every Grothendieck ∞\infty-topos. In a nondegenerate ∞\infty-topos this proposition is false.

Proof. There exists an external function g:N→Ng:\mathbb N\to\mathbb N not computed by any φe\varphi_e. For example, use the characteristic function of the diagonal halting set. The map gˉ:N→N\bar g:N\to N defined on each summand by in↦ig(n)i_n\mapsto i_{g(n)} supplies an internal instance of ff. Let P↪NP\hookrightarrow N be the subobject of indices satisfying ∀n ∃t H(e,n,t,gˉ(n))\forall n\,\exists t\,H(e,n,t,\bar g(n)). For each external ee, choose an nn at which φe\varphi_e is undefined or differs from gg. With these two numerals substituted and with the output g(n)g(n) fixed, the subobject of possible tt is initial by the interpretation of HH and the disjointness of summands. Its existential image in 11 is initial. Universal elimination shows that ie∗Pi_e^*P is therefore also initial. Universality of coproducts now gives P≃∐eie∗P≃0P\simeq\coprod_e i_e^*P\simeq 0, so the existential image of PP in 11 is initial. The universal assertion (8) is contained in this instance and therefore is initial as well. ◻

This argument accounts for local existence in sheaf semantics. A local index is allowed to vary with the context. The proof reduces that index to numeral summands, and every summand gives an empty predicate for the fixed counterexample gˉ\bar g. In S\mathcal S the same phenomenon is visible directly since NNN^N is the discrete space of all set-theoretic numerical functions. A recursion principle can introduce a map from specified base and step data even when other maps admitted by the semantics have no program index.

The effective topos as a boundary example

Take the ordinary effective topos Eff\mathrm{Eff} based on Kleene’s first partial combinatory algebra. Its full subcategory of assemblies has objects (X,RX)(X,R_X) with a nonempty set RX(x)⊆NR_X(x)\subseteq\mathbb N of realizers for each xx. A morphism f:(X,RX)→(Y,RY)f:(X,R_X)\to(Y,R_Y) is a function equipped, in the sense of existence, with a single partial recursive tracker φe\varphi_e. The condition is that for every xx and every r∈RX(x)r\in R_X(x), the computation φe(r)\varphi_e(r) is defined and belongs to RY(f(x))R_Y(f(x)). Different trackers for a fixed underlying function give the same morphism. The natural numbers object NEffN_{\mathrm{Eff}} is the assembly with R(n)={n}R(n)=\{n\} [12, Ch. 3].

Fullness of the assembly inclusion reduces every endomorphism of NEffN_{\mathrm{Eff}} to a tracked function. The tracker condition for this assembly is φe(n)=f(n)\varphi_e(n)=f(n) on every input. Conversely, any total recursive numerical function supplies its own tracker. Thus the external endomorphisms of NEffN_{\mathrm{Eff}} are exactly the total recursive functions. For the internal assertion with quantification over the exponential, Hyland separately proves Church’s thesis in Eff\mathrm{Eff} [11, Prop. 10.2]. The argument via tracked arrows identifies the external endomorphism set, while the internal theorem governs generalized elements and their witnesses.

There is a direct obstruction to applying Proposition 26 to Eff\mathrm{Eff} as an ordinary category. If the countable coproduct ∐n∈N1\coprod_{n\in\mathbb N}1 existed, its shift would make it an ordinary natural numbers object by the same recursion proof using sets of arrows. The resulting isomorphism to NEffN_{\mathrm{Eff}} would preserve all numeral injections. Choosing their images in NEffN_{\mathrm{Eff}} independently would define an endomorphism for every external function N→N\mathbb N\to\mathbb N, contrary to tracking. This recovers the countable-coproduct obstruction of van Oosten [12, Prop. 3.2.3]. In particular Eff\mathrm{Eff} cannot be the full subcategory of 00-truncated objects in any Grothendieck ∞\infty-topos, since the countable coproduct of terminal objects constructed above is already 00-truncated.

The argument uses the Grothendieck hypothesis through external coproducts. Rasekh constructs natural numbers objects for a specified elementary higher topos framework by a different argument that avoids assuming these coproducts [13]. A higher analogue of realizability intended to validate absolute Church’s thesis must specify a framework outside the hypotheses of Proposition 29, or change the numerical predicate or quantifier in the thesis. The comparison in Section 11 addresses the additional choices in passing from ordinary realized predicates to higher families.

Higher realizability and the scope of Church’s thesis

The ordinary effective topos and the Grothendieck semantics of Section 10 admit different functions on natural numbers. This gives a criterion for comparing a proposed higher realizability model with its ordinary fragment. Suppose the model has set-valued natural numbers and the indexed operations of Theorem 2 restrict to its 00-truncated types. Interpreting arithmetic via the same natural numbers object and numerical predicates, the truth of (8) is computed by those restricted operations. Each numerical type and context in that sentence is a set, and every existential is an image. Hence the arithmetic sentence has the same truth value in the higher model and in its ordinary fragment. The argument also applies to an elementary higher model with the same restriction, without assuming that model is a Grothendieck ∞\infty-topos.

The distinctions among existing constructions determine which such transfer statements apply. Uemura constructs a cubical-assembly model with a univalent impredicative universe and shows a failure of a form of propositional resizing [14]. Swan and Uemura establish that the ordinary realizability interpretation of Church’s thesis and the homotopical interpretation in cubical assemblies can disagree. They construct a left exact modality whose reflective subuniverse validates the homotopical thesis [15]. The existence of the modality and the calculation of the ordinary fragment are independent questions about such a model. The transfer applies when an equivalence of ordinary fragments identifies the arithmetic data.

Awodey and Emmenegger give a candidate effective 22-topos with 00-types equivalent to the effective topos [16]. The comparison with cubical assemblies in their work exhibits a concrete reason to pay attention to exact completion: forming an ordinary exact completion and then introducing a cubical direction can change which ordinary types are recovered after passage to homotopy. Their recovery theorem at the 22-topos level concerns the ordinary fragment and gives a finite-dimensional comparison for the extension to all levels. In particular, a claim about a higher effective model should specify its underlying category, its universe assumptions, and the identification of its 00-types before invoking ordinary realizability theorems in that model.

One can see the arithmetic preservation requirement independently of the geometry of the model. Suppose f,g:X→NNf,g:X\to N^N are two generalized sections and that a proposition over XX asserts the existence of an index computing both. On the support of that proposition the two composites X×N→NX\times N\to N agree. Pull back along the effective epimorphism supplying the shared index. Over the product of its domain with NN, take the fiber product of the two covers supplying halting runs for that input. On this last cover determinism of the machine forces equality of outputs. Equality descends through both covers because it is interpreted by a mono. This argument uses the run existentials separately in the context of an input, so it requires no choice of a run simultaneously for all inputs. By the exponential adjunction the two original generalized sections agree on that support. The resulting identity is an extensional property of program behavior. An assignment of programs implementing ff can carry additional data, such as distinct codes for a single function, which this identity and the truth of the corresponding instance of (8) discard. Determining the space of implementations requires the ambient higher model.

Scope of the comparison

Theorem 2 identifies the set-valued language of an ordinary topos within the higher language while allowing the latter to form identities and dependent products of higher types. The ambient category controls the resulting families: an identity can carry a group of loops, an existential can be true without a global term, and an ordinary context can support a product whose components depend on higher gluing. Each assertion has an example above with the context, family, and operation specified.

There are two distinct extensions of the classical term-model program here. The classifying topoi in Theorem 16 give explicit universal models for geometric fragments. Classifying stronger dependent theories with judgmental computation rules requires specifying their syntactic presentations and the morphisms that preserve their operations. Likewise, an effective version of the higher theory needs a framework that keeps the intended computational structure. The Grothendieck assumptions yield the comparison and descent theorems of this article, and Proposition 29 gives a precise limit on their use for absolute Church’s thesis.

Use of automation.

AI tools assisted in drafting, organizing, and checking this manuscript. Arguments are presented as mathematical proofs in the text. No proof assistant verification is claimed. The cited sources and the LaTeX source allow the constructions and calculations to be reviewed directly.

References

  1. J. Lambek and P. J. Scott. Introduction to Higher Order Categorical Logic. Cambridge Studies in Advanced Mathematics 7, Cambridge University Press, 1986. Corrected paperback, 1988. Publisher front matter.

  2. J. Lurie. Higher Topos Theory. Annals of Mathematics Studies 170, Princeton University Press, 2009. Author’s text.

  3. P. LeFanu Lumsdaine and M. A. Warren. The local universes modelan overlooked coherence construction for dependent type theories. ACM Trans. Comput. Log. 16(3), article 23, 2015. arXiv:1411.1736.

  4. K. Kapulkin and P. LeFanu Lumsdaine. The simplicial model of Univalent Foundations (after Voevodsky). J. Eur. Math. Soc. 23 (2021), 2071–2126. Journal article.

  5. M. Shulman. All (∞,1)(\infty,1)-toposes have strict univalent universes. . arXiv:1904.07004.

  6. The Univalent Foundations Program. Homotopy Type Theory: Univalent Foundations of Mathematics. Institute for Advanced Study, 2013. Open book.

  7. T. Nikolaus, U. Schreiber, and D. Stevenson. Principal ∞\infty-bundlesGeneral theory. J. Homotopy Relat. Struct. 10 (2015), 749–801. arXiv:1207.0248.

  8. E. Rijke, M. Shulman, and B. Spitters. Modalities in homotopy type theory. Log. Methods Comput. Sci. 16(1), article 2, 2020. Journal article.

  9. S. Awodey, N. Gambino, and K. Sojakova. Homotopy-initial algebras in type theory. J. ACM 63(6), article 51, 2017. Open repository copy.

  10. W. Dean and A. Naibo. Recursive Functions. In The Stanford Encyclopedia of Philosophy, Summer 2025 edition. Archived entry.

  11. J. M. E. Hyland. The effective topos. In The L. E. J. Brouwer Centenary Symposium, Studies in Logic and the Foundations of Mathematics 110, 165–216, North-Holland, 1982. Author’s copy.

  12. J. van Oosten. Realizability: An Introduction to its Categorical Side. Studies in Logic and the Foundations of Mathematics 152, Elsevier, 2008. Publisher record.

  13. N. Rasekh. Every elementary higher topos has a natural number object. Theory Appl. Categ. 37 (2021), 337–377. Journal article.

  14. T. Uemura. Cubical assemblies, a univalent and impredicative universe, and a failure of propositional resizing. LIPIcs 130, TYPES 2018, article 7, 2019. doi:10.4230/LIPIcs.TYPES.2018.7.

  15. A. W. Swan and T. Uemura. On Church’s thesis in cubical assemblies. Math. Structures Comput. Sci. 31 (2021), 1185–1204. doi:10.1017/S0960129522000068.

  16. S. Awodey and J. Emmenegger. Toward the effective 2-topos. Math. Structures Comput. Sci. 35 (2025), e32. doi:10.1017/S0960129525100352.

Complete flattened LaTeX source
\documentclass[10pt,twocolumn,letterpaper]{article}

\usepackage[margin=0.68in,top=0.76in,bottom=0.68in]{geometry}

\usepackage[T1]{fontenc}

\usepackage{lmodern}

\usepackage{amsmath,amssymb,amsthm}

\usepackage{microtype}

\usepackage{booktabs,tabularx}

\usepackage{tikz-cd}

\usepackage{xcolor}

\usepackage{fancyhdr}

\usepackage{balance}

\usepackage{hyperref}


\definecolor{Ink}{HTML}{18253A}
\definecolor{Link}{HTML}{174875}
\hypersetup{colorlinks=true,linkcolor=Link,citecolor=Link,urlcolor=Link,
  pdftitle={Higher-Order Logic in Infinity-Toposes},
  pdfsubject={Categorical logic, homotopy type theory, and the Lambek--Scott correspondences}}
\setlength{\columnsep}{0.27in}
\setlength{\headheight}{13pt}
\setcounter{secnumdepth}{2}
\numberwithin{equation}{section}
\allowdisplaybreaks[1]

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\footnotesize\sffamily\textcolor{Ink}{Higher-Order Logic in \(\infty\)-Toposes}}
\fancyhead[R]{\footnotesize\sffamily\textcolor{Ink}{\thepage}}
\renewcommand{\headrulewidth}{0.35pt}
\fancypagestyle{plain}{\fancyhf{}\fancyfoot[C]{\footnotesize\thepage}
  \renewcommand{\headrulewidth}{0pt}}

\begin{document}
\twocolumn[{
\begin{center}
  \vspace*{-0.2em}
  {\small\sffamily\textcolor{Link}{MANUSCRIPT FOR HIGHER CATEGORICAL SEMANTICS}}\par
  \vspace{0.8em}
  {\LARGE\bfseries\color{Ink} Higher-Order Logic in \(\infty\)-Toposes\par}
  \vspace{0.35em}
  {\large Extending the Lambek--Scott correspondences\par}
\end{center}
\begin{quote}
\small
\textbf{Abstract.}
We develop an \(\infty\)-categorical counterpart to the relationships
among typed calculi, topos semantics, and recursion in Lambek and Scott.
The indexed slices of a Grothendieck \(\infty\)-topos interpret substitution,
dependent sums and products, identities, and propositional quantifiers.
We prove an indexed comparison with its ordinary topos of \(0\)-truncated
objects, and give explicit examples in which truncation loses sections or
their components, including a dependent product along a subterminal map of
a finite presheaf site. Further results give a local condition under which
dependent products commute with truncation, classify unrestricted and
discrete sorts by different presheaf topoi, and describe descent, univalence,
and torsors at the level of mapping spaces. We formulate natural-number
elimination by contractibility of the space of solutions and prove the
failure of absolute internal Church's thesis in nondegenerate Grothendieck
\(\infty\)-toposes under classical external mathematics. The distinction
between ordinary and higher semantics runs through each comparison.

\medskip
\textbf{Keywords.} Categorical logic, \(\infty\)-topos, dependent type theory,
truncation, univalence, realizability.

\textbf{MSC 2020.} 03G30, 03B38, 18N60.
\end{quote}
\vspace{0.7em}
}]
\thispagestyle{plain}

\section{Introduction}\label{sec:intro}

Lambek and Scott organize categorical logic around three correspondences:
typed $\lambda$-calculi and cartesian closed categories, intuitionistic
type theories and toposes, and descriptions of numerical functions by
arrows in categories equipped with recursion principles
\cite{lambek-scott}. Their preface also points to dependent types and
local cartesian closure as a distinct correspondence. A higher
categorical development must explain what each of these comparisons
becomes when maps have homotopies and families have nontrivial
automorphisms. The resulting comparison depends on which operations preserve the
truncated fragment.

We use the indexed family $X\mapsto\mathcal E_{/X}$ of a Grothendieck
$\infty$-topos $\mathcal E$. A context is an object $X$, a type in context
is a map to $X$, and a term is a section. Substitution, dependent sum and
dependent product form an adjoint triple. Propositional quantifiers
are obtained by restricting to subobjects, with images used for
existential quantification. Theorem~\ref{thm:bridge} compares these
constructions simultaneously on the full subcategory of set-valued
types over set-valued contexts. This comparison explains which rules of
ordinary extensional logic the higher model recovers.

Two separate tests delimit the comparison. In
Section~\ref{sec:truncation-loss}, spaces and spaces over the $2$-sphere
have equivalent ordinary logic on set-valued types, yet differ on
sections of a constant higher type. We also give two explicit failures
of interchanging $0$-truncation and dependent product. One failure is
detected by a nonsplit extension of finite groups. The other already
occurs over a subterminal context on a finite presheaf site. Thus the
ordinary comparison is an agreement of operations on a specified
fragment, and information needed by dependent products can be lost by
truncating the input to those operations.

The later sections follow three other aspects of the source. Descent
and identity expose the role of coherence in the semantics of
families. Univalent universes and classifying objects express
classification by equivalence rather than by a choice of names.
Natural-number recursion is formulated by a universal property of
spaces of solutions, and realizability explains how an effectiveness
condition can change which numerical maps exist. We use the book as a
thematic point of departure and work at article scale. The proofs
assemble standard topos and type-theoretic constructions around
specific comparison and obstruction calculations. 

\paragraph{Conventions.}
All categories in the higher development are $(\infty,1)$-categories,
all limits and colimits have their homotopy-coherent meanings, and
$\mathcal S$ denotes the category of spaces. We write
$\operatorname{Map}_{\mathcal C}(A,B)$ for the mapping space and
$\mathcal C^\simeq$ for the maximal subgroupoid. A map is
$n$-truncated if its homotopy fibers after applying
$\operatorname{Map}_{\mathcal C}(T,-)$ are $n$-truncated spaces for
every $T$. In particular, a $(-1)$-truncated map is a monomorphism,
and its fiber is either empty or contractible. Write
$\tau_{\le n}^{X}$ for relative $n$-truncation in the slice over $X$.
We fix ambient universes and use bounded classifiers when discussing
small families. The underlying external mathematics is standard
set-theoretic mathematics. Logical principles ascribed to a model
are statements of its internal language.

\section{Substitution and indexed logic}\label{sec:logic-fibers}

An $\infty$-topos is an accessible left exact localization of a
presheaf $\infty$-category of spaces. We use its local cartesian
closure, image factorizations, and universal colimits
\cite[Ch.~6]{lurie-htt}. The terminal object in the slice
$\mathcal E_{/X}$ is $1_X=\operatorname{id}_X$. For a type
$p:A\to X$, the space of terms is
$\operatorname{Map}_{\mathcal E_{/X}}(1_X,p)$, the homotopy fiber of
$\operatorname{Map}_{\mathcal E}(X,A)\to
\operatorname{Map}_{\mathcal E}(X,X)$ at $\operatorname{id}_X$.
This formulation includes the homotopy that makes an underlying map a
section.

Simple typing can be read in the single category $\mathcal E$:
currying is the equivalence
\[
\operatorname{Map}_{\mathcal E}(T\times A,B)
\simeq \operatorname{Map}_{\mathcal E}(T,B^A).
\]
The evaluation map and its adjuncts give application and abstraction.
Applying $\pi_0$ shows that the homotopy category of a cartesian closed
$\infty$-category is cartesian closed when equipped with these
induced operations. A dependent context changes the base from $T$ to
the total space of a family. Pullback in slices supplies the
dependence that the nonindexed exponential does not encode.

\subsection{The adjoint triple}

For $f:X\to Y$, composition supplies $\Sigma_f:\mathcal E_{/X}\to
\mathcal E_{/Y}$ and pullback supplies $f^*$. The pullback property
gives
\[
\operatorname{Map}_{/Y}(\Sigma_f A,B)
\simeq \operatorname{Map}_{/X}(A,f^*B).
\]
The functor $f^*$ preserves colimits by universality of colimits in
$\mathcal E$, and the slices are presentable. The adjoint functor
theorem therefore gives its right adjoint $\Pi_f$, characterized by
\[
\operatorname{Map}_{/X}(f^*B,A)
\simeq \operatorname{Map}_{/Y}(B,\Pi_f A).
\]
The second formula interprets abstraction with a dependent domain as
adjoint transposition. The unit and counit identify the operations
that express the semantic $\beta$ and $\eta$ rules.

\begin{proposition}[Base change and Frobenius]\label{prop:bc-frob}
Suppose that
\[
\begin{tikzcd}[column sep=2.5em,row sep=1.8em]
X' \arrow[r,"g'"] \arrow[d,"f'"'] & X \arrow[d,"f"]\\
Y' \arrow[r,"g"'] & Y
\end{tikzcd}
\]
is a pullback square. There are natural equivalences
\begin{align*}
g^*\Sigma_f &\simeq \Sigma_{f'}(g')^*,\\
g^*\Pi_f &\simeq \Pi_{f'}(g')^*,\\
\Sigma_f(A\times_X f^*B)
   &\simeq (\Sigma_f A)\times_Y B.
\end{align*}
\end{proposition}

\begin{proof}
The first equivalence is the pullback pasting law applied to the total
space of $A$. For a test object $T$ over $Y'$, the other
Beck--Chevalley comparison follows from the chain
\begin{align*}
\operatorname{Map}_{/Y'}(T,g^*\Pi_f A)
&\simeq \operatorname{Map}_{/Y}(\Sigma_g T,\Pi_f A)\\
&\simeq \operatorname{Map}_{/X}(f^*\Sigma_gT,A)\\
&\simeq \operatorname{Map}_{/X}(\Sigma_{g'}(f')^*T,A)\\
&\simeq \operatorname{Map}_{/X'}((f')^*T,(g')^*A)\\
&\simeq \operatorname{Map}_{/Y'}(T,\Pi_{f'}(g')^*A).
\end{align*}
Here $f^*\Sigma_g\simeq\Sigma_{g'}(f')^*$ is the first
comparison for the transposed square. Yoneda gives the result. For
Frobenius both total spaces are canonically the pullback
$A\times_Y B$ over $Y$. The comparisons are compatible with pasting:
the pullback equivalences are the ones induced by the pasted universal
cones, and taking adjoint mates respects pasting.
\end{proof}

\subsection{Propositions and ordinary recovery}

Let $\operatorname{Sub}_{\mathcal E}(X)$ be the poset of
$(-1)$-truncated maps to $X$ up to equivalence. Mapping spaces of such
maps in the slice are empty or contractible. Restrictions of the
preceding functors to predicates give
\[
\exists_f(P)=\tau_{\le -1}^{Y}\Sigma_f P,
\qquad
\forall_f(P)=\Pi_f P.
\]
The formula for $\exists_f$ is reflection into subobjects after
composition. Its mapping property says that $\exists_f(P)\le Q$ if
and only if $P\le f^*Q$. For $\forall_f$, the mapping-space adjunction
shows that its value is again a monomorphism and that
$f^*Q\le P$ if and only if $Q\le\forall_f(P)$. The image is
stable under pullback, so the predicate comparisons follow from
Proposition~\ref{prop:bc-frob}; for Frobenius at this level use that
pulling back the image of $\Sigma_f P$ along $Q\hookrightarrow Y$
computes the image of $P\times_X f^*Q$ in $Q$. Composing the
resulting mono with $Q\hookrightarrow Y$ gives intersection with $Q$.
This describes ordinary intuitionistic quantification in an arbitrary
higher context, regardless of its truncation level.

\begin{theorem}[Indexed recovery of the ordinary semantics]
\label{thm:bridge}
Let $\mathcal E$ be a Grothendieck $\infty$-topos and let
$\mathcal C=\mathcal E_{\le 0}$ be its ordinary topos of
$0$-truncated objects. For $X\in\mathcal C$ there are natural
identifications
\[
(\mathcal E_{/X})_{\le 0}\simeq\mathcal C_{/X},
\qquad
\operatorname{Sub}_{\mathcal E}(X)
\cong\operatorname{Sub}_{\mathcal C}(X).
\]
For a map $f$ in $\mathcal C$, the identifications intertwine
substitution, $\Sigma_f$, $\Pi_f$, $\exists_f$ and $\forall_f$ with their
ordinary versions. They also intertwine finite limits, relative
exponentials, the diagonal equality predicate, and the subobject
classifier. The comparison is natural in $X$ with respect to
substitution and carries the base-change and Frobenius comparisons to
the ordinary ones.
\end{theorem}

\begin{proof}
The $1$-topos characterization identifies $\mathcal E_{\le 0}$
with a Grothendieck topos \cite[Thm.~6.4.1.5]{lurie-htt}.
If $X$ is $0$-truncated and $A\to X$ is relatively $0$-truncated,
then $A\to 1$ is $0$-truncated by closure under composition.
Conversely, if both $A$ and $X$ are $0$-truncated, the homotopy
fibers of the map of discrete mapping spaces
$\operatorname{Map}(T,A)\to\operatorname{Map}(T,X)$ are discrete.
Full faithfulness of $\mathcal C\hookrightarrow\mathcal E$ now
identifies the slices. A mono over $X$ lies in this slice and its
mapping property restricts to the ordinary mono property. Conversely,
an ordinary mono has an invertible relative diagonal in $\mathcal C$.
Finite limits in $\mathcal C$ are computed in $\mathcal E$, so the
same diagonal is invertible there.

Pullback preserves truncated maps. If $f$ lies in $\mathcal C$,
it is $0$-truncated, so its composite with a relatively
$0$-truncated map is again $0$-truncated. The adjunction for
$\Pi_f$ preserves truncated objects since its mapping spaces are
tested by pulling back the source. The two adjunctions therefore
restrict to the displayed ordinary slices. The reflection
$\tau_{\le -1}^{Y}$ applied after $\Sigma_f$ has the usual image
universal property against the same subobjects. This proves the two
claims about predicate quantifiers as well.

Finite limits and diagonals agree by the full embedding and closure
under finite limits. Relative exponentials are characterized in
the slice by the right adjoint to product; equivalently they can be
formed as dependent products of the pullback of the codomain along
the domain. The subobject classifier $\Omega$ is $0$-truncated
because $\operatorname{Map}(T,\Omega)$ is the discrete space of
subobjects of $T$. Its representing property restricts to
$\mathcal C$, so the classifier and the power objects built from it
agree. The base-change and Frobenius comparisons restrict because
they are furnished by the same pullback and adjunction properties.
\end{proof}

Ordinary interpretation of an extensional higher-order language
uses the data of this theorem: products and powers for types,
subobjects for formulas, diagonals for equality, and quantifiers
in context. Thus interpreting a signature whose sorts and contexts
are $0$-truncated gives the same terms and predicates in both
models, up to the indicated identifications. This assertion concerns
the semantics of that fragment. In particular, an identity type of
an arbitrary higher type should not be treated as the diagonal
predicate of a set.

\section{What truncation discards}\label{sec:truncation-loss}

Write $X\mapsto cX$ for the constant-object functor
$\mathcal S\to\mathcal E$. Intrinsically,
$cX\simeq\operatorname{colim}_{X}1$. There are two different
questions about recovering higher semantics. The first asks whether
the truncated doctrine determines its higher ambient category. The
second asks whether a higher family can be truncated before or after
a computation in the slices.

\begin{proposition}[The ordinary fragment does not determine the
higher category]\label{prop:shadow}
The $\infty$-toposes $\mathcal S$ and $\mathcal S_{/S^2}$ have
equivalent ordinary toposes of $0$-truncated objects, and their
indexed set and predicate semantics agree under this equivalence.
The two $\infty$-toposes are inequivalent.
\end{proposition}

\begin{proof}
Straightening identifies spaces over $S^2$ with families
$S^2\to\mathcal S$. The $0$-truncated objects of the slice
are the families with discrete fibers. A functor from a space to
sets takes values on the subgroupoid of bijections, and factors
through the fundamental groupoid of the space. As $S^2$ is connected
and simply connected, its fundamental groupoid is terminal up to
equivalence. Its category of set-valued families is therefore
equivalent to $\mathbf{Set}$. Theorem~\ref{thm:bridge} gives
the indexed comparison.

In the slice, the terminal object is $\operatorname{id}_{S^2}$
and $cK$ is $S^2\times K\to S^2$. The section space is
$\operatorname{Map}(S^2,K)$. In $\mathcal S$ the section space of
$cK$ is $K$. Take $K=K(\mathbb Z,2)$. The former has
components $H^2(S^2;\mathbb Z)\cong\mathbb Z$, while the latter
is connected. The section space of $cK$ depends only on the
category since terminal objects and $K$-indexed colimits do.
An equivalence of the two higher categories is therefore
impossible.
\end{proof}

Under the additional restriction to $1$-localic $\infty$-toposes,
the ordinary topos does determine the higher topos up to equivalence
\cite[Prop.~6.4.5.7 and Def.~6.4.5.8]{lurie-htt}.

For any $f:X\to Y$ and family $A$ over $X$, there is a canonical
map
\begin{equation}
\tau_{\le 0}^{Y}\Pi_f A
\longrightarrow
\Pi_f\tau_{\le 0}^{X}A.\label{eq:trunc-pi}
\end{equation}
It comes from applying $\Pi_f$ to the truncation unit and
factoring into a $0$-truncated target. The theorem about restriction
implies that this map is invertible if $A$ is already relatively
$0$-truncated. It does not imply that \eqref{eq:trunc-pi} is
invertible for every $A$ over a $0$-truncated base, or for every $A$
with connected fibers.

\begin{example}[A coherent section obstructed by a group extension]
\label{ex:group-obstruction}
Take $f:BC_2\to 1$ in spaces and let $A\to BC_2$ be the map
$BC_4\to BC_2$ induced by reduction modulo $2$. Here $C_n$ is the
cyclic group of order $n$. Its homotopy fiber is $BC_2$, as is seen
from the homotopy exact sequence and the surjectivity of
$C_4\to C_2$. Thus $\tau_{\le 0}^{BC_2} A$ is terminal in the
slice and the right side of \eqref{eq:trunc-pi} is contractible.
The untruncated $\Pi_f A$ is the space of sections of $A$ over
$BC_2$. A point in this space would induce a splitting of
$C_4\to C_2$ on fundamental groups. Basepoint choices only affect
conjugation, which acts trivially here. The elements of order
dividing $2$ in $C_4$ both map to $0$ in $C_2$, so such a
splitting cannot exist. The left side of \eqref{eq:trunc-pi}
is empty. The example can also be read as a space of homotopy
fixed points with nonempty connected fibers and no coherent fixed
point.
\end{example}

\begin{example}[Failure over a subterminal context]
\label{ex:finite-obstruction}
Let $D$ be the finite poset of nonempty proper faces of a
$2$-simplex, and let $C=D^{\triangleright}$ be the result of
adjoining a terminal object $t$. Put
$\mathcal E=\operatorname{Fun}(C^{\mathrm{op}},\mathcal S)$.
Let $U$ be the subterminal presheaf with value $*$ on $D$ and
value $\varnothing$ at $t$. For $f:U\to 1$, take
$A=U\times cS^1\to U$. Both contexts in $f$ are $0$-truncated.
Relative truncation is computed objectwise, so
$\tau_{\le 0}^{U}A\simeq 1_U$ and
$(\Pi_f\tau_{\le 0}^{U}A)(t)\simeq *$.

Since $t$ is terminal, $y(t)=1$. Evaluate the untruncated product
at $t$, using Yoneda and adjunction:
\begin{align*}
(\Pi_f A)(t)
&\simeq \operatorname{Map}_{/U}(U,U\times cS^1)\\
&\simeq \operatorname{Map}_{\mathcal E}(U,cS^1)\\
&\simeq \lim_{D^{\mathrm{op}}} S^1
\simeq \operatorname{Map}(|ND|,S^1).
\end{align*}
In the last line the diagram is constant. The restriction of $U$
to $D^{\mathrm{op}}$ is terminal, and $U$ is its left Kan
extension along $D^{\mathrm{op}}\hookrightarrow C^{\mathrm{op}}$:
the extension has value initial at $t$ since there are no arrows
from objects of $D$ to $t$ in $C^{\mathrm{op}}$. This explains
the reduction to the smaller index. The realization $|ND|$ is the
barycentric subdivision of the boundary of a triangle and is
equivalent to $S^1$. Its maps to $S^1$ have integer degree, so
$(\tau_{\le 0}\Pi_f A)(t)$ has components indexed by
$\mathbb Z$. The comparison at $t$ takes this discrete space
to $*$ and loses the degrees. Here both bases are in the ordinary fragment. The higher information
lies in the family over that fragment.
\end{example}

\subsection{Finite locally constant index}

Call $f:X\to Y$ \emph{finite locally constant} if some
effective epimorphism $\coprod_i Y_i\to Y$ makes the pullback
of $f$ over each $Y_i$ a finite coproduct of copies of $1_{Y_i}$.
The number of copies may vary with $i$.

\begin{proposition}[Truncating products with finite locally constant index]
\label{prop:finite-index}
For a finite locally constant $f:X\to Y$, all relatively
$n$-truncations with $n\geq -1$ commute with $\Pi_f$:
\[
\tau_{\le n}^{Y}\Pi_f A
\ \,\simeq\,\ \Pi_f\tau_{\le n}^{X}A.
\]
\end{proposition}

\begin{proof}
The natural comparison factors the image of the truncation unit
through the truncated source, as in \eqref{eq:trunc-pi}. By
Proposition~\ref{prop:bc-frob} and stability of relative
truncation under pullback, it suffices to prove the comparison
after restriction to each $Y_i$. These restrictions detect
equivalences by effective-epimorphism descent, explained in
Section~\ref{sec:descent}. Over $Y_i$ the domain is a finite
coproduct of copies of the terminal object. A type over that
domain is a tuple of types over $Y_i$ by disjoint and universal
coproducts. Substitution sends a type to the constant tuple,
so the dependent product is the finite product of the tuple.

Truncation in a slice preserves finite products.
For the nonempty case, take the product of the truncation units.
Each unit has trivial relative $n$-truncation over its target.
The class of these maps is closed under composition and
pullback, by the relative factorization system
\cite[\S6.5.1]{lurie-htt}. The product of the units factors as
successive pullbacks of the individual units. Its target is a
product of $n$-truncated types and is therefore $n$-truncated.
The product map thus exhibits the truncation by the uniqueness
of this factorization. The empty product is terminal and is
already truncated. This applies over each $Y_i$ and proves the
claim.
\end{proof}



\section{Descent for contexts and families}\label{sec:descent}

Write \(\mathcal S\) for the \(\infty\)-category of spaces. A Grothendieck
\(\infty\)-topos \(\mathcal E\) is an accessible left exact localization
of \(\operatorname{Fun}(C^{\mathrm{op}},\mathcal S)\) for a small
\(\infty\)-category \(C\). In the presheaf category, restriction along an
arrow of \(C\) is part of the functorial data of a presheaf. In a
localization, the local objects satisfy additional gluing conditions.
There is also an intrinsic gluing statement, formulated in \(\mathcal E\)
itself, that applies to the dependent families of
Section~\ref{sec:logic-fibers}.

\begin{theorem}[Descent for slices]\label{thm:slice-descent}
Let \(D:I\to\mathcal E\) be a small diagram with colimit \(X\).
Restriction along its colimit cone induces an equivalence
\begin{equation}
 \mathcal E_{/X}\ \simeq\
 \lim_{i\in I^{\mathrm{op}}}\mathcal E_{/D(i)} .
 \label{eq:slice-descent}
\end{equation}
For an arrow \(i\to j\) in \(I\), the corresponding transition functor
on the right is pullback along \(D(i)\to D(j)\). The limit is in
\(\mathrm{Cat}_{\infty}\), in an ambient size in which the slice
categories are objects.
\end{theorem}

\begin{proof}
An object on the right consists of a diagram \(A\to D\) whose naturality
squares are pullbacks. Indeed, the equivalence identifying \(A_i\) with
the restriction of \(A_j\) is equivalent to the assertion that the
square for \(i\to j\) is a pullback. The limit includes the higher
coherences among those squares. One can formalize this description as
the \(\infty\)-category of cartesian sections of the pullback of the
codomain fibration along \(D\). The inverse candidate extends this
transformation to a map of colimit cones by setting
\(A_X=\operatorname{colim}_{i\in I} A_i\) and taking the induced map
\(A_X\to X\). By the descent characterization of \(\infty\)-topoi,
the squares \(A_i\to A_X\) over \(D(i)\to X\) are pullbacks
\cite[Thms.~6.1.0.6 and 6.1.3.9]{lurie-htt}. Thus restriction of the
candidate recovers the cartesian section. In the other direction,
pulling the original colimit cone back along \(A_X\to X\) gives a
colimit cone by universality of colimits. Both constructions act on
morphisms through functorial pullback and colimit. Their comparison
equivalences come from the two universal properties.
\end{proof}

For \(U\to X\), write \(U^{[n]}=U\times_X\cdots\times_X U\) with
\(n+1\) factors. The simplicial object \(U^{[\bullet]}\) uses
projections as faces and diagonals as degeneracies. The arrow \(U\to X\)
is an \emph{effective epimorphism} when the augmentation identifies
\(\lvert U^{[\bullet]}\rvert\) with \(X\). Applying
Theorem~\ref{thm:slice-descent} gives
\begin{equation}
 \mathcal E_{/X}\simeq \lim_{[n]\in\Delta}
                  \mathcal E_{/U^{[n]}} .
 \label{eq:cech-slice-descent}
\end{equation}
At degree zero there is a family on \(U\). At degree one there is an
equivalence between its two pullbacks to \(U\times_X U\). At degree two
there is a homotopy comparing the composite of two such equivalences
with the third equivalence. The totalization records the full
simplicial compatibility, including degenerate simplices. In an
ordinary category some of these comparisons reduce to equations.
Their role in \eqref{eq:cech-slice-descent} is to specify the maps and
higher simplices of the category of gluing data.

In particular, let \(A,B\) be families over \(X\) and let \(A_n,B_n\)
denote their restrictions. Then
\begin{equation}
 \operatorname{Map}_{\mathcal E_{/X}}(A,B)
 \simeq \lim_{[n]\in\Delta}
       \operatorname{Map}_{\mathcal E_{/U^{[n]}}}(A_n,B_n).
 \label{eq:cech-map-descent}
\end{equation}
Mapping spaces commute with this limit of categories. One way to see
this is to express a mapping space as the fiber at the two endpoints
of the maximal subgroupoid of a functor category on \(\Delta^1\).
Taking that functor category, taking the maximal subgroupoid, and
taking the endpoint fiber all preserve the limits involved. Taking
\(A=\operatorname{id}_X\) in \eqref{eq:cech-map-descent} shows that
terms of \(B\) glue by the same descent formula. An equivalence of
families can be tested after restriction to \(U\): all the other
components are further pullbacks, and equivalences in the limit are
detected componentwise.

\begin{example}[An effective epimorphism with nontrivial overlaps]
\label{ex:group-descent}
Let \(G\) be a discrete group and \(BG\) the realization of its nerve.
For the basepoint \(1\to BG\), the iterated homotopy fiber products
are equivalent to \(G^n\) in degree \(n\). A tuple records the
successive paths between copies of the basepoint. Inner face maps
compose adjacent paths, and inserting a constant path gives a
degeneracy. Thus the Čech object is equivalent to the bar simplicial
space of \(G\), and \(1\to BG\) is an effective epimorphism. A family on
\(BG\) is thereby equivalent to a space \(F\) equipped with a
homotopy-coherent \(G\)-action. The space \(F\) is the fiber at the
basepoint and the action is transport. The morphism space of two such
families consists of coherently equivariant maps, as
\eqref{eq:cech-map-descent} describes.

Take \(F=G\) with the left translation action. The family corresponds
to the universal \(G\)-cover \(EG\to BG\). It has sections over the
basepoint. A global section would give a homotopy fixed point and
hence a fixed element of the discrete fiber. For \(G\ne 1\), every
element of \(F\) moves under some translation, so the global section
space is empty. The descent formula locates the difference at
degree one, where the local term has to agree with all of its
translates.
\end{example}

\begin{example}[A family on a homotopy pushout]\label{ex:circle-descent}
The span \(1\leftarrow 1\amalg 1\to 1\), with the two fold maps, has
pushout \(S^1\) in \(\mathcal S\). Its double mapping cylinder has two
vertices joined by two edges. Slice descent gives
\[
  \mathcal S_{/S^1}\simeq
  \mathcal S\times_{\mathcal S\times\mathcal S}\mathcal S ,
\]
where the two functors to \(\mathcal S\times\mathcal S\) are diagonals.
A family is specified by fibers \(F_0,F_1\) and equivalences
\(e_0,e_1:F_0\simeq F_1\). After using \(e_0\) to identify the fibers,
the datum is a space \(F_0\) with a self-equivalence
\(e_0^{-1}e_1\). The direction of the comparison corresponds to a
choice of generator of \(\pi_1(S^1)\). For \(F_0=\{0,1\}\) and
\(e_0^{-1}e_1\) the transposition, the resulting family is the
connected two-sheeted cover. For discrete fibers, the section
condition is the fixed-element condition for this permutation.
\end{example}

Descent is a condition on gluing in the base. A Čech nerve is built
from one map by repeated pullbacks. A hypercover allows new covers of
matching objects in higher degrees. Equation
\eqref{eq:cech-slice-descent} follows from effective epimorphy in
every Grothendieck \(\infty\)-topos. Identifying the realization of
every hypercover with its target is a hypercompleteness assertion
\cite[Thm.~6.5.3.12]{lurie-htt}.

\section{Identity types in the slices}\label{sec:dependent-types}

Let \(p:A\to X\) be a type in context \(X\) and form the diagonal
\(\Delta_{A/X}:A\to A\times_X A\). Regard this arrow as the family of
identities over pairs of elements of \(A\). Given a test context
\(T\to X\) and two terms \(a,b:T\to A\) over \(X\), the corresponding
identity type over \(T\) is
\begin{equation}
  \operatorname{Id}_{A/X}(a,b)=(a,b)^*(\Delta_{A/X}).
  \label{eq:identity-diagonal}
\end{equation}
All pullbacks in \eqref{eq:identity-diagonal} are homotopy pullbacks.
In particular, the map from their total space to \(T\) includes the
endpoint comparison data.

\begin{proposition}[Generalized paths]\label{prop:generalized-paths}
For \(a,b\) as in \eqref{eq:identity-diagonal}, the space of sections
of \(\operatorname{Id}_{A/X}(a,b)\to T\) is equivalent to the path space
from \(a\) to \(b\) in \(\operatorname{Map}_{\mathcal E_{/X}}(T,A)\).
The equivalence is natural under pullback of the test context.
\end{proposition}

\begin{proof}
Writing \(M=\operatorname{Map}_{\mathcal E_{/X}}(T,A)\), the
pullback universal property identifies the section space with the
homotopy fiber of \(M\to M\times M\) at \((a,b)\).
For a Kan-complex model of \(M\), the endpoint evaluation
\(M^{\Delta^1}\to M\times M\) is a fibration and the inclusion of
constant paths \(M\to M^{\Delta^1}\) is an equivalence. Its
ordinary fiber therefore computes the stated homotopy fiber.
Precomposition in \(T\) preserves this description.
\end{proof}

\begin{example}[Parallel identities]
In \(\mathcal S\), take \(X=1\), \(A=BG\), and \(a=b\) the basepoint.
By Proposition~\ref{prop:generalized-paths} the identity type is
\(\Omega BG\simeq G\). Its cardinality is \(\lvert G\rvert\) when \(G\)
is finite. For nontrivial \(G\), this identity type has several
components, violating the monomorphism condition on the diagonal.
Applying \((-1)\)-truncation in the slice over \(BG\times BG\) gives
the subobject of pairs connected by a path. In an ordinary topos,
mapping spaces are discrete and the same
diagonal formula gives the usual equality predicate.
\end{example}

\subsection{Path induction and coherence}

Write \(P\to A\times_X A\) for the family
\(\Delta_{A/X}\) or for an equivalent representative of it in the
slice. Reflexivity is a map \(r:A\to P\) over \(A\times_X A\) induced by
this choice, with \(r\) an equivalence on total spaces. Let
\(q:C\to P\) be a family of conclusions and let \(d\) be a section of
\(r^*C\to A\), the reflexivity case. The square
\[
\begin{array}{ccc}
 r^*C &\longrightarrow& C\\
 \downarrow &&\downarrow q\\
 A &\xrightarrow{r}& P
\end{array}
\]
is a pullback. Since \(r\) is an equivalence, pullback gives an
equivalence between the section spaces
\[
 \operatorname{Map}_{\mathcal E_{/P}}(P,C)
 \ \xrightarrow{\ \simeq\ }\
 \operatorname{Map}_{\mathcal E_{/A}}(A,r^*C).
\]
Its fiber at \(d\) is contractible. An element of this fiber is a
section \(J(d)\) of \(C\) together with a specified identification
\(r^*J(d)\simeq d\). This supplies the semantic elimination rule and
its computation at reflexivity. Pulling any of the data back along a
substitution \(X'\to X\) preserves the pullback square and the
equivalence \(r\). The construction therefore applies to the
substituted motive and reflexivity case as well.

The intrinsic interpretation uses equivalences with coherent
comparisons, as seen in the specified identification in the fiber.
The syntactic rule of intensional Martin-Löf type theory is formulated
with a \emph{judgmental} computation at reflexivity. Interpreting that
form of the rule uses a presentation with chosen comprehension and
stable type-former operations. In the simplicial-set model, for
example, one works with Kan fibrations and a path-object
factorization. The chosen reflexivity map is a trivial cofibration
and the fibration representing a motive supplies a lift against it.
Kapulkin and Lumsdaine construct a coherent simplicial interpretation,
and Shulman's model-topos theorem supplies strict univalent
interpretations presenting every Grothendieck \(\infty\)-topos
\cite{kapulkin-lumsdaine,shulman-univalence}. These presentation
results address the judgmental equalities required of the model.

\subsection{Dependent function extensionality}

Let \(p:A\to X\), \(q:B\to A\), and let \(s,t\) be sections of
\(\Pi_p B\to X\). Denote by \(\widehat s,\widehat t\) the corresponding
sections of \(B\to A\) under the adjunction of
Section~\ref{sec:logic-fibers}. There is an equivalence of families
over \(X\)
\begin{equation}
 \operatorname{Id}_{(\Pi_pB)/X}(s,t)
 \simeq
 \Pi_p\bigl(\operatorname{Id}_{B/A}(\widehat s,\widehat t)\bigr).
 \label{eq:dependent-function-extensionality}
\end{equation}
Indeed, over any \(T\to X\), the adjunction gives an equivalence
\[
 \operatorname{Map}_{\mathcal E_{/X}}(T,\Pi_p B)
 \simeq
 \operatorname{Map}_{\mathcal E_{/A}}(T\times_X A,B).
\]
It carries the two generalized sections to the pointwise generalized
sections. Passing to path spaces and using
Proposition~\ref{prop:generalized-paths} and the same adjunction
identifies the spaces represented by the two sides of
\eqref{eq:dependent-function-extensionality} at \(T\). The
identification is natural in \(T\), so Yoneda gives
\eqref{eq:dependent-function-extensionality}. This argument proves the
semantic equivalence at the level of the whole family, including its
behavior under substitution.

\section{Universes and univalence}\label{sec:univalence}

A subobject classifier assigns to each context a space of truth
values. An object classifier can assign a space of types, with paths
that encode equivalences of types. To formulate a size-bounded version,
fix a sufficiently large regular cardinal \(\kappa\). A map
\(A\to X\) is \emph{relatively \(\kappa\)-compact} if its pullback along
every \(T\to X\) with \(T\) a \(\kappa\)-compact object has
\(\kappa\)-compact total space. Here \(\kappa\)-compactness means that
mapping out of the object commutes with \(\kappa\)-filtered colimits.
Write \((\mathcal E_{/X}^{\kappa})^{\simeq}\) for the maximal
subgroupoid of the full subcategory of
\(\mathcal E_{/X}\) on these maps. In the ambient size convention of
Theorem~\ref{thm:slice-descent}, the object-classifier theorem yields a
universal family \(\widetilde U_\kappa\to U_\kappa\) and equivalences
natural in \(X\)
\begin{equation}
 \operatorname{Map}_{\mathcal E}(X,U_\kappa)
 \ \simeq\  (\mathcal E_{/X}^{\kappa})^{\simeq}.
 \label{eq:object-classifier}
\end{equation}
The map underlying \eqref{eq:object-classifier} pulls back the universal
family \cite[\S6.1.6, especially Thm.~6.1.6.8]{lurie-htt}.
The classification claim specifies a size-bounded class of arrows.
A syntactic universe also requires closure under the type formers that
its formation rules specify.

\begin{proposition}[Univalence of a classifying family]\label{prop:univalence}
Let \(u,v:T\to U_\kappa\) classify \(A\to T\) and \(B\to T\). The
canonical map
\[
 \operatorname{Path}_{\operatorname{Map}_{\mathcal E}(T,U_\kappa)}(u,v)
 \ \longrightarrow\
 \operatorname{Eq}_{\mathcal E_{/T}}(A,B)
\]
is an equivalence, where the right side is the space of equivalences
from \(A\) to \(B\) over \(T\). Equivalently, the identity family on
\(U_\kappa\) over \(U_\kappa\times U_\kappa\) represents the space
of equivalences between the two pulled-back universal families.
\end{proposition}

\begin{proof}
An equivalence of spaces induces equivalences on path spaces between
corresponding points. Apply this to
\eqref{eq:object-classifier}. A path between two objects in the
maximal subgroupoid of a category is an equivalence between those
objects, with its higher homotopies. The equivalence in
\eqref{eq:object-classifier} maps a path of codes to transport in the
universal family, which identifies the resulting path-space
equivalence with the canonical map of the statement. The identity
family represents the left side by
Proposition~\ref{prop:generalized-paths}, with base context \(1\).
Naturality in \(T\to U_\kappa\times U_\kappa\) gives the second claim.
\end{proof}

\begin{proposition}[Descent for size-bounded families]
\label{prop:small-descent}
For a small diagram \(D:I\to\mathcal E\) with colimit \(X\),
restriction induces an equivalence
\[
 (\mathcal E_{/X}^{\kappa})^{\simeq}\ \simeq\
 \lim_{i\in I^{\mathrm{op}}}
          (\mathcal E_{/D(i)}^{\kappa})^{\simeq}.
\]
A family \(A\to X\) is relatively \(\kappa\)-compact if its
restriction to each \(D(i)\) is relatively \(\kappa\)-compact.
\end{proposition}

\begin{proof}
Mapping from the colimit into \(U_\kappa\) yields the limit of the
mapping spaces from its stages. Applying
\eqref{eq:object-classifier} to these spaces gives the equivalence.
To prove detection, take the restrictions of \(A\) and their
coherences induced by pullback. The displayed equivalence glues
them to a relatively \(\kappa\)-compact map \(A'\to X\). In the full
slice this family has the same descent datum as \(A\). By
Theorem~\ref{thm:slice-descent}, it is equivalent to \(A\), and
relative \(\kappa\)-compactness is invariant under equivalence.
\end{proof}

For an effective epimorphism \(U\to X\), this proposition gives a
local criterion involving only \(U\). All the Čech stages map to
\(U\), so relative \(\kappa\)-compactness there propagates to the
stages by pullback. With the whole descent datum specified, the
classifying map \(X\to U_\kappa\) is recovered from its restrictions
and their comparison paths. This realizes local type codes as
ordinary maps into a single ambient object, to which the colimit
universal property applies.

\begin{example}[Codes for finite types carry permutations]\label{ex:finite-universe}
In \(\mathcal S\), let \(u_n:1\to U_\kappa\) classify a discrete
\(n\)-element space \(\underline n\). Its loop space in \(U_\kappa\)
is \(\operatorname{Aut}(\underline n)=\Sigma_n\), a discrete group.
The connected component of \(u_n\) is equivalent to \(B\Sigma_n\):
the groupoid of spaces equivalent to \(\underline n\) has a full
subgroupoid on that one object, and inclusion is an equivalence of
groupoids. In particular the nonidentity permutation on
\(\underline 2\) gives a noncontractible loop. Composing the
classifying map of the nontrivial double cover
\(S^1\to B\Sigma_2\) with \(B\Sigma_2\to U_\kappa\) recovers
Example~\ref{ex:circle-descent}. The same permutation appears there
as monodromy and here as an identity between universe codes.
\end{example}

For a discrete group \(G\), the whole space of codes for families
over \(BG\) with \(n\)-element fibers is
\(\operatorname{Map}_{\mathcal S}(BG,B\Sigma_n)\). Both arguments
are nerves of ordinary groupoids, so the mapping space is the
nerve of the functor groupoid. Its objects are homomorphisms
\(\rho:G\to\Sigma_n\), and an arrow \(\rho\to\rho'\) is a permutation
\(\sigma\) with \(\rho'(g)=\sigma\rho(g)\sigma^{-1}\) for all \(g\).
In particular the loop group at \(\rho\) is the centralizer of
\(\rho(G)\) in \(\Sigma_n\). This recovers both the classification
by conjugacy and the automorphisms of each cover from the same
mapping space.

The proposition-valued fragment gives the ordinary subobject
classifier \(\Omega\). For each \(T\), the maximal subgroupoid of
monomorphisms into \(T\) is the discrete space of subobjects of \(T\).
To see this, a map over \(T\) into a monomorphism has either empty
or contractible mapping space. If the map is an equivalence, its
domain and codomain determine the same subobject. Thus
\(\operatorname{Map}_{\mathcal E}(T,\Omega)\) is \(0\)-truncated, and
paths between codes of propositions are equivalences of the
corresponding subobjects. Equivalence of two propositions over \(T\)
is the same as implication in both directions over \(T\). This
recovers propositional extensionality from the classifier and
explains why permutation symmetries appear only once the classified
families are allowed to have richer fibers
\cite[\S3.3]{hott-book}.

Finally, \eqref{eq:object-classifier} classifies \(A\) together with
its context. For a chosen \(A\to X\) in the size class, the space of
a code \(a:X\to U_\kappa\) \emph{together with an equivalence}
\(a^*\widetilde U_\kappa\simeq A\) is contractible, since it is the
fiber of \eqref{eq:object-classifier} at \(A\). The connected component
of the code in the mapping space has loop space
\(\operatorname{Aut}_{\mathcal E_{/X}}(A)\) by
Proposition~\ref{prop:univalence}.




\section{Syntactic categories and classifiers}
\label{sec:classifying-topoi}

A syntactic category encodes the structural operations of a calculus in a universal property. For the simply typed cartesian closed calculus, an object is a type, and a morphism \(A\to B\) is a term of type \(B\) in a single variable of type \(A\), modulo definitional equality. Products encode finite contexts, including the empty context, and composition is substitution. Abstraction and application give mutually inverse functions
\[
 \operatorname{Hom}(C\times A,B)
 \;\cong\;
 \operatorname{Hom}(C,B^A).
\]
The inverse equations are the \(\beta\)- and \(\eta\)-laws. Given interpretations of the generating types and constants in a cartesian closed category, recursive interpretation of terms gives the corresponding structure-preserving functor. Conversely, such a functor sends the generic types and constants to an interpretation. The two constructions recover one another by induction on expressions, with uniqueness relative to the chosen cartesian closed structure. This is the universal-property formulation of the simply typed part of the syntax--semantics correspondence.

In a homotopy-coherent semantic category the displayed universal property is an equivalence of spaces. In the dependent case, types over \(\Gamma\) are objects of \(\mathcal E_{/\Gamma}\), and terms of \(A\to\Gamma\) form the section space
\(\operatorname{Map}_{\mathcal E_{/\Gamma}}(\operatorname{id}_\Gamma,A)\).
A path of sections is a homotopy over \(\Gamma\), and further paths encode higher identifications. Substitution is implemented by the functoriality of the slice construction. A presentation interpreting an ordinary judgmental equality still requires strictly stable operations at the level of the chosen syntax and its model. For example, the local-universes coherence theorem constructs split comprehension models under its stated hypotheses from weakly stable logical structure on a comprehension category \cite{lumsdaine-warren}. Strict syntactic interpretability and an invariant universal property for the space of models address two separate questions. The following classifiers give universal properties for specific fragments and make their semantic morphisms explicit.

\subsection{Finite-limit theories}

Write \(\mathcal P(C)=\operatorname{Fun}(C^{\mathrm{op}},\mathcal S)\) for a small \(\infty\)-category \(C\). For \(\infty\)-topoi \(\mathcal E\) and \(\mathcal F\), let \(\operatorname{Geom}(\mathcal E,\mathcal F)\) be the space of geometric morphisms, computed as the maximal subgroupoid of the category of colimit-preserving left exact functors \(\mathcal F\to\mathcal E\). These functors are inverse images of geometric morphisms since the presentable adjoint functor theorem supplies right adjoints. We write \(\mathcal D^{\simeq}\) for the maximal subgroupoid of an \(\infty\)-category \(\mathcal D\). Corestriction to this subgroupoid retains equivalences of models and their higher homotopies.

\begin{proposition}[Finite-limit presheaf classifier]
\label{prop:lex-presheaf-classifier}
For every small finitely complete \(\infty\)-category \(C\) and every \(\infty\)-topos \(\mathcal E\), restriction along the Yoneda embedding gives a natural equivalence
\[
 \operatorname{Geom}(\mathcal E,\mathcal P(C))
 \;\simeq\;
 \operatorname{Fun}^{\mathrm{lex}}(C,\mathcal E)^{\simeq}.
\]
Under the equivalence, the universal model in \(\mathcal P(C)\) is the Yoneda embedding.
\end{proposition}

\begin{proof}
The free cocompletion theorem identifies colimit-preserving functors out of \(\mathcal P(C)\) with functors out of \(C\), by restriction along Yoneda \cite[Theorem~5.1.5.6]{lurie-htt}. Yoneda preserves finite limits, so a left exact functor on presheaves restricts to a left exact functor on \(C\). Conversely, the colimit-preserving extension of a left exact functor \(C\to\mathcal E\) is left exact by \cite[Proposition~6.1.5.2]{lurie-htt}. Thus the equivalence restricts to the full subcategories in question and induces an equivalence on their cores. The identity inverse image restricts to Yoneda, giving the universal model.
\end{proof}

The preservation requirement controls which semantic constructions are included.
Finite limits suffice to specify projections, pullback squares, and equations in
finite-limit theories. Exponentials and dependent products require additional
preservation conditions. For a counterexample, take the point of the presheaf
topos on the ordinary arrow category \([1]\) whose inverse image is evaluation at
\(1\). For \(A=(\varnothing\to *)\) and \(B=(\varnothing\to\varnothing)\), in presheaf notation with the arrow directed from the value at \(1\) to the value at \(0\), both \(A(1)\) and \(B(1)\) are empty, while
\[
 \begin{aligned}
  (B^A)(1)
  &\simeq \operatorname{Map}_{\mathcal P([1])}(y(1)\times A,B) \\
  &\simeq \operatorname{Map}_{\mathcal P([1])}(A,B)
   \simeq \varnothing.
 \end{aligned}
\]
Here \(y(1)\) is terminal. The exponential of the evaluated objects is \(*\). A classifying statement about dependent type theories with chosen rules therefore needs a category of models and morphisms designed to preserve those rules.

An accessible left exact localization can impose additional conditions on the
models in the proposition. Suppose \(L\colon\mathcal P(C)\to\mathcal F\)
is such a localization and \(i\) its right adjoint. Then \(\operatorname{Geom}(\mathcal E,\mathcal F)\) is equivalent to the subspace of those models whose colimit-preserving extensions invert every \(L\)-equivalence. Indeed, a colimit-preserving \(F\colon\mathcal P(C)\to\mathcal E\) inverting those maps factors essentially uniquely through \(L\). The induced functor \(\overline F\simeq Fi\) preserves finite limits whenever \(F\) does, since \(i\) is a right adjoint. It also preserves colimits. A colimit of a diagram \(D\) in \(\mathcal F\) can be calculated as \(L\operatorname{colim}(iD)\), and applying \(\overline F\) gives \(F\operatorname{colim}(iD)\). This describes a restricted class of theories by the semantic maps they invert and leaves the localization itself as an explicit hypothesis.

\subsection{Two classifiers for one sort}

Let \(\mathcal K\subset\mathcal S\) be the essentially small full subcategory generated by a point under finite colimits. Equivalently, one can obtain its objects by iterating finite homotopy colimit constructions starting with a point. At each step one may choose a small collection of objects since the diagrams have finite shape and the mapping spaces are small. Passing to the closure under equivalence gives an essentially small full subcategory. Write \(\mathrm{Fin}\) for the category of finite sets, considered inside spaces as discrete objects.

\begin{theorem}[Unrestricted and discrete sorts]
\label{thm:unrestricted-and-discrete}
The following equivalences of spaces are natural in \(\mathcal E\):
\begin{align*}
 \operatorname{Geom}(\mathcal E,\mathcal P(\mathcal K^{\mathrm{op}}))
 &\simeq \mathcal E^{\simeq},\\
 \operatorname{Geom}(\mathcal E,\mathcal P(\mathrm{Fin}^{\mathrm{op}}))
 &\simeq (\mathcal E_{\leq 0})^{\simeq}.
\end{align*}
Both equivalences are given by evaluating the corresponding finite-limit model at a point.
\end{theorem}

\begin{proof}
For \(X\in\mathcal E\), the cotensor \(X^K\) is the limit of the constant diagram on \(X\) indexed by the space \(K\). Consequently,
\[
 \operatorname{Map}_{\mathcal E}(T,X^K)
 \;\simeq\;
 \operatorname{Map}_{\mathcal S}
        (K,\operatorname{Map}_{\mathcal E}(T,X)).
\]
The right side sends colimits in \(K\) to limits, so \(K\mapsto X^K\) is a left exact functor on \(\mathcal K^{\mathrm{op}}\). It is the right Kan extension of \(X\) along the inclusion \(j\colon\{*\}\to\mathcal K^{\mathrm{op}}\), since the indexing category \((K\downarrow j)\) is the space of maps \(K\to *\) in \(\mathcal K^{\mathrm{op}}\), namely \(K\). If \(F\) is left exact, the unit \(F\to j_*j^*F\) is an equivalence at the point. The objects where the unit is an equivalence are closed under finite limits, since both functors preserve those limits. The point generates \(\mathcal K^{\mathrm{op}}\) under finite limits, and hence the unit is an equivalence everywhere. The counit \(j^*j_*X\to X\) is an equivalence at once. This proves the first equivalence by Proposition~\ref{prop:lex-presheaf-classifier}.

For finite sets the right Kan extension of \(X\) is again given by powers \(S\mapsto X^S\), now with \(S\) discrete. The same argument using products shows that evaluation at a singleton classifies product-preserving functors on \(\mathrm{Fin}^{\mathrm{op}}\). To determine which are left exact, consider in \(\mathrm{Fin}\) the pushout of the two copies of the fold \(2\to 1\). Its pushout object is \(1\). In a left exact model this gives
\[
 X\xrightarrow{\ \sim\ } X\times_{X\times X}X,
\]
where the two maps to \(X\times X\) are diagonals. The displayed map is the diagonal of the diagonal \(X\to X\times X\). Its being an equivalence means that this latter diagonal is a monomorphism, which characterizes \(0\)-truncated objects. Conversely, when \(X\) is \(0\)-truncated, \(\operatorname{Map}_{\mathcal E}(T,X)\) is discrete for every \(T\). Powers by finite sets then send finite colimits of sets to limits after applying \(\operatorname{Map}_{\mathcal E}(T,-)\). Limits of discrete spaces agree with limits in sets, and the mapping-space criterion gives left exactness. Applying Proposition~\ref{prop:lex-presheaf-classifier} proves the second identification.
\end{proof}

The fold diagram measures precisely where the theories diverge. Its pushout in spaces is \(S^1\): the two points of the middle object give the two edges between the two outer points in the double mapping cylinder. The unrestricted classifier therefore assigns to this pushout the cotensor \(X^{S^1}\simeq X\times_{X\times X}X\), the object of free loops in \(X\). In the discrete theory, the corresponding pushout has value \(1\), and left
exactness requires the resulting constant-loop map \(X\to X^{S^1}\) to be an
equivalence. For an explicit computation in spaces, if \(X=K(A,1)\) for an abelian group \(A\), then the components of the free loop space are indexed by \(A\). Evaluation at a point gives a fibration with fiber \(\Omega X\simeq A\), and its monodromy is conjugation, which is trivial here. Thus any nonzero \(A\) obstructs the constant-loop map from being an equivalence. The difference between the classifiers is already detected by a single finite-limit condition, even though their generic object has the same product operations.

The truncation functor \(\mathcal K\to\mathrm{Fin}\), \(K\mapsto \pi_0K\), preserves finite colimits and lands in finite sets because finite colimits of finite sets are finite. After taking opposites and applying Proposition~\ref{prop:lex-presheaf-classifier}, it determines a geometric morphism
\[
 \mathcal P(\mathrm{Fin}^{\mathrm{op}})
 \longrightarrow \mathcal P(\mathcal K^{\mathrm{op}}).
\]
On model spaces, postcomposition with this morphism is exactly the inclusion of the core of the \(0\)-truncated objects into the core of all objects. The functor from the discrete theory into the unrestricted one at the level of models is consequently realized by an explicit morphism of their classifying topoi.

\subsection{Adding an inhabitation axiom}

The same unrestricted sort can be constrained by an existential axiom. Let
\(C=\mathcal K^{\mathrm{op}}\), \(A=y(*)\), and let \(I\hookrightarrow 1\) be the
image of \(A\to 1\) in \(\mathcal P(C)\). The terminal object is representable
by the terminal object of \(C\), so \(I\hookrightarrow 1\) determines a sieve
on that object. Take the Grothendieck topology \(J\) generated by declaring it
covering. The topos \(\operatorname{Shv}_J(C)\) classifies objects \(X\) such
that \(X\to 1\) is an effective epimorphism. In the internal language this
condition is the truth of \(\exists x:X\), with existence interpreted by
propositional truncation.

To prove the claim, let \(F\colon\mathcal P(C)\to\mathcal E\) be the
inverse image corresponding to \(X\). Inverse-image functors preserve
effective epimorphisms since they preserve the formation and realization of
\v{C}ech nerves. They also preserve monomorphisms by left exactness. By
uniqueness of the effective epi--mono factorization, \(F(I)\hookrightarrow 1\)
is the image of \(X\to 1\). If \(F\) factors through sheafification, it
inverts \(I\hookrightarrow 1\), and so the image is all of \(1\).

For the converse, suppose \(F(I)\hookrightarrow 1\) is an equivalence.
For any sieve on a representable, its image under \(F\) is the image of the
coproduct of the objects in the corresponding family of arrows under
\(F\circ y\). Indeed a sieve is covered by the representables mapping into it,
and \(F\) preserves images and coproducts. Thus the sieves inverted by \(F\)
are exactly the covering sieves of the relative canonical topology for the
left exact functor \(F\circ y\)
\cite[Proposition~6.2.4.2]{lurie-htt}. By hypothesis that topology contains
the generating cover of \(J\), so \(F\) inverts all its covering-sieve
inclusions. The universal property of sheafification and the preceding
localization argument give the factorization, with its space of choices
contractible.

For example, take \(\mathcal E=\mathcal S_{/S^1}\) and let \(X\) be the object
given by the basepoint map \(*\to S^1\). Its structure map is an effective
epimorphism because it is surjective on components. A section would split
the induced map on \(\pi_1\), which is impossible. This distinguishes local
inhabitation, represented by the sheaf classifier, from the additional data
of a term of the type in the terminal context.

\section{Classifying objects and torsors}
\label{sec:torsor-classifier}

A classifying object represents a functor on the objects of a fixed topos. This complements the preceding classifying topoi, whose universal property varies the ambient topos. Group torsors give a representability statement that displays all levels of equivalence data.

Let \(G\) be a group object in \(\mathcal E\), presented by its reduced groupoid object \(B_\bullet G\). Thus \(B_0G=1\), \(B_1G=G\), and the Segal identifications give \(B_nG\simeq G^n\). Define \(BG=|B_\bullet G|\), with its map \(1\to BG\) induced from degree zero. By effectiveness of groupoid objects in an \(\infty\)-topos, \(B_\bullet G\) is the \v{C}ech nerve of that map, which is an effective epimorphism. In particular \(G\simeq 1\times_{BG}1\), compatibly with the group multiplication from the groupoid structure.

\begin{definition}
A right \(G\)-torsor over \(X\) is a coherently \(G\)-equivariant map \(p\colon P\to X\), with trivial action on \(X\), such that \(p\) is an effective epimorphism and the action comparison
\[
 P\times G\longrightarrow P\times_X P,
 \qquad (u,g)\longmapsto(u,ug)
\]
is an equivalence. The action is encoded by its simplicial action groupoid with \(n\)-simplices \(P\times G^n\). Write \(\operatorname{Tors}_G(X)\) for the space of these torsors and their equivariant equivalences over \(X\).
\end{definition}

The action comparison is often called the principal bundle condition. It states that once two points in a fiber have been chosen, the space of group elements taking the first point to the second is contractible. If \(p\) has a section \(s\), restricting the comparison along the first coordinate \(s\) identifies \(X\times G\) with \(P\) by \((x,g)\mapsto s(x)g\). In particular each torsor becomes trivial after its own effective epimorphism \(P\to X\), using the diagonal section of the pullback. This supplies local triviality without choosing an external topology on \(\mathcal E\).

\begin{theorem}[Classification at the level of spaces]
\label{thm:classifying-torsors}
There is a natural equivalence
\[
 \operatorname{Map}_{\mathcal E}(X,BG)
 \;\simeq\; \operatorname{Tors}_G(X).
\]
The torsor corresponding to \(f\colon X\to BG\) is determined by the
pullback square
\[
 \begin{array}{ccc}
  P & \longrightarrow & 1 \\
  \big\downarrow && \big\downarrow \\
  X & \xrightarrow{\ f\ } & BG .
 \end{array}
\]
\end{theorem}

\begin{proof}
Effectiveness identifies the \v{C}ech nerve of \(1\to BG\) with the reduced action groupoid \(B_\bullet G\). It follows that \(1\to BG\) is a \(G\)-torsor in the slice over \(BG\). Base change preserves effective epimorphisms and the action comparison, so pullback along \(f\) gives a torsor over \(X\).

In the other direction, the action comparison identifies the action groupoid of \(P\) with the \v{C}ech nerve of \(p\). In degree one this is the principal bundle condition, and the Segal maps give the equivalence in all degrees. Projection to \(G^n\) defines a simplicial map from that nerve to \(B_\bullet G\). Realization gives a classifying map \(X\to BG\), because the augmentation of the \v{C}ech nerve realizes to \(X\). The simplicial map together with the augmentation gives an equivariant map from the given \(P\) to \(X\times_{BG}1\) over \(X\). More explicitly, the realization maps give a map of the action groupoids into \(X\times_{BG}B_\bullet G\), and equivariance follows from its compatibility with the projection to \(B_\bullet G\).

An equivariant map between torsors over the same base is an equivalence. To see this, pull back along the source torsor. The diagonal section trivializes the source, and its image under the equivariant map trivializes the target. In these coordinates the comparison is the identity. Base change along the effective epimorphism detects equivalences by descent, proving the assertion. Thus the comparison \(P\to X\times_{BG}1\) is an equivalence.

Finally, the action groupoid of a pullback torsor for \(f\) is the base change of \(B_\bullet G\) along \(f\). Its realization recovers \(f\) since realizations are universal in \(\mathcal E\). The comparisons are natural, being induced by pullbacks, simplicial maps and their colimits. They give inverse equivalences on the spaces, including higher homotopies. This is the internal principal bundle classification of \cite[Section~3]{nikolaus-schreiber-stevenson}.
\end{proof}

\begin{example}[From principal bundles to higher cohomology]
Let \(A\) be a discrete abelian group and take \(\mathcal E=\mathcal S\), with \(G=K(A,n)\) for \(n\geq 1\) in its loop group structure from \(K(A,n+1)\). The delooping is \(K(A,n+1)\), so the components of \(\operatorname{Tors}_{G}(X)\) are \(H^{n+1}(X;A)\). For a CW model of \(X\), the higher groups at the trivial torsor satisfy
\[
 \pi_j\operatorname{Tors}_{G}(X)
 \;\cong\;H^{n+1-j}(X;A)
 \qquad (1\leq j\leq n+1).
\]
Indeed, based maps \(S^j\to\operatorname{Map}(X,K(A,n+1))\) correspond to based maps from \(S^j\wedge X_+\), and cohomology of that smash product is given by the suspension isomorphism. The higher groups vanish above \(n+1\). For \(X=S^{n+1}\), the component set and the group in degree \(n+1\) are both \(A\), while the other positive-degree groups are zero. Every component has the same homotopy groups by translation in the abelian group object \(\operatorname{Map}(X,K(A,n+1))\). Over a point and for a discrete group \(G\), the classification similarly gives the space \(BG\) with one component and automorphism group \(G\). Thus the sets of equivalence classes recover familiar classifications and the spaces additionally record symmetries of each model.
\end{example}



\section{Truth, choice, and localization}
\label{sec:truth-modalities}

A proposition over a context $X$ is a $(-1)$-truncated map to $X$. The
higher analogue of a predicate equipped with witnesses is an arbitrary
map $p:A\to X$. In the latter, the homotopy type of the fiber records
both the witnesses and the identifications among them. Passing from
this type to its truth value is a relative operation. It takes place
in $\mathcal E_{/X}$, so it uses the geometry of the context as well
as that of the domain.

\subsection{The support of a family}

\begin{definition}
The \emph{support} $\operatorname{supp}_{X}(A)$ of $A\to X$ is its
relative $(-1)$-truncation. Write the image factorization as
\[
 A\twoheadrightarrow \operatorname{supp}_{X}(A)\lhook\joinrel\longrightarrow X,
\]
where the first arrow is effective epimorphic and the second is a
monomorphism. If $U\hookrightarrow X$ is a proposition, write
$\bot_X$ and $\top_X$ for the least and greatest propositions over
$X$.
\end{definition}

The support has the following elementary calculus. It applies to
families whose fibers have arbitrary homotopy types.

\begin{proposition}
\label{prop:logic-support}
Let $f:Y\to X$ be a map in an $\infty$-topos.
\begin{enumerate}
\item For $A\to X$ and a proposition $U\to X$, precomposition
      gives an equivalence
      \[
      \operatorname{Map}_{/X}(\operatorname{supp}_X(A),U)
      \simeq \operatorname{Map}_{/X}(A,U).
      \]
\item There is a natural equivalence
      $f^*\operatorname{supp}_X(A)\simeq
      \operatorname{supp}_Y(f^*A)$.
\item The support of the slice coproduct $P\amalg Q$ is their join in
      $\operatorname{Sub}(X)$ when $P,Q$ are propositions. For
      $B\to Y$, the support of the composite $B\to Y\to X$ is
      $\exists_f\operatorname{supp}_Y(B)$.
\end{enumerate}
\end{proposition}
\begin{proof}
The first assertion is orthogonality of effective epimorphisms and
monomorphisms applied to $A\twoheadrightarrow\operatorname{supp}_X(A)$
and $U\hookrightarrow X$. For the second, pull back the image
factorization. Both classes of maps are stable under pullback, so the
new factorization has the universal property of the image. A map from
$P\amalg Q$ to a proposition exists exactly when the
two summands admit maps to it. This is the least-upper-bound property.
For the composite, a map over $X$ from $B$ to a proposition $U$ is
adjoint to a map from $B$ to $f^*U$ over $Y$. Since $f^*U$ is a
proposition, this factors through $\operatorname{supp}_Y(B)$. The
resulting equivalence of conditions is the defining adjunction of
$\exists_f$.
\end{proof}

Full support is equivalent to effective epimorphicity of $A\to X$.
In a sheaf model this is the local availability of witnesses, tested
after base change to each stage and passage to a cover. A section
$X\to A$ is a witness compatible over the entire context. These two
conditions agree for a proposition $A$ but differ for general
families. In fact a mono with full support is an equivalence. For other
families, the unit into the support permits elimination into
propositions and produces a map into a given type only when suitably
coherent additional data are available.

\begin{example}[A disjunction with no global tag]
\label{ex:logic-tagged}
Use space-valued sheaves on $\mathbb R$. Let $U$ and $V$ be the
subterminals represented by the opens $(-\infty,1)$ and
$(-1,\infty)$. They join to $1$ because the two opens cover the line.
Thus $U\amalg V\to 1$ has full support. A global section of this
coproduct would pull the disjoint summands back to complementary
opens $W_U,W_V$ covering the line, with $W_U\subseteq U$ and
$W_V\subseteq V$. By connectedness one would be the whole line,
contrary to each containment. The calculation works in the ordinary
sheaf topos as well: the obstruction concerns gluing the tags and
already occurs for a $0$-truncated family.
\end{example}

Relative truncation is compatible with change of base, as in
Proposition~\ref{prop:logic-support}. Preservation of finite limits
by a truncation functor is a separate condition. In spaces, for a
nontrivial discrete group $G$, the homotopy pullback of the two
basepoints $*\to BG\leftarrow *$ is $G$ as a discrete space.
Truncating the diagram objectwise by $\tau_{\leq 0}$ first yields
$*\to *\leftarrow *$, whose pullback is $*$. Thus the functor of
components can preserve the meanings of ordinary predicates while
changing a finite-limit construction on higher types. This applies
already to the self-intersection of a single point. The same diagram
also exhibits failure of left exactness of propositional truncation
if $BG$ is replaced by the discrete two-element space and the
basepoints select its two distinct elements.

\subsection{Boolean propositions and the strength of choice}

\begin{definition}
Say that the predicate logic of $\mathcal E$ is \emph{Boolean}
when every subobject lattice $\operatorname{Sub}_{\mathcal E}(X)$
is Boolean. Write $\neg P$ for the Heyting implication
$P\Rightarrow\bot_X$.
\end{definition}

This condition is exactly excluded middle for propositions in every
context. It is encoded by the universal predicate
$t:1\hookrightarrow\Omega$, where $\Omega$ is the subobject
classifier. If $t\vee\neg t=\top_\Omega$, any predicate satisfies
the law by pullback along its classifying map. Indeed pullback
preserves the initial object, unions, and predicate implication. For
the last assertion use preservation of finite limits together with
base change for the right adjoints to substitution in the slices.
The converse applies excluded middle to $t$ itself.

Under classical external logic, the predicate logic of $\mathcal S$
is Boolean. A monomorphism of spaces includes a union of connected
components: its fibers over points are empty or contractible, and
path transport maintains this condition or exchanges the contractible
fibers by equivalences. The complementary union yields its negation.
There is still a difference between truth and witness selection. If
$G$ is nontrivial, the basepoint $*\to BG$ is effective epimorphic
by connectedness. A section would make $BG$ a retract of $*$ and
hence contractible. This fails since $\pi_1(BG)\cong G$.

Even a choice principle restricted to sets can fail with Boolean
predicate logic. Take $\mathcal E=\operatorname{Fun}(BG,\mathcal S)$,
the $\infty$-topos of $G$-spaces. A subobject of a $G$-space is an
invariant union of components. To see this, classify the underlying
mono by its subset of components. Each arrow of $BG$ gives a
permutation on components, and equivariance makes the subset
invariant. Conversely a union of components for an invariant subset
is closed under this transport, with its equivariance induced from
the given $G$-space. The complement is invariant, proving
Booleanity. The free transitive $G$-set $G$, viewed as a discrete
$G$-space, has full support over $1$ by objectwise computation of
colimits and finite limits. A section of $G\to 1$ would be an
invariant element of the discrete $G$-set. There is none for
$G\ne 1$. The terminal object and the free transitive $G$-set both
belong to the ordinary topos of $G$-sets, so the example also
refutes that every epi of sets splits in this model.

For comparison, a space-valued sheaf topos on a space $Z$ has
$\operatorname{Sub}(1)$ identified with the frame of opens. Here
$\neg U=\operatorname{int}(Z\setminus U)$ because this is the
largest open disjoint from $U$. On $Z=\mathbb R$, the formula
$U\vee\neg U$ for $U=(0,\infty)$ omits the origin. This gives an
intuitionistic model even when the metatheory used to build the sheaf
topos is classical. Internal Booleanity and the external rules used
in constructing the category have different domains of application.

\subsection{An explicit dense localization}

A left exact localization $L:\mathcal E\rightleftarrows
\mathcal D:i$ is an adjunction with fully faithful right adjoint and
finite-limit-preserving left adjoint. In the presentable setting we
take $L$ accessible. Such a reflector preserves images because the
factorization into an effective epimorphism and a mono is preserved.
It preserves monos by transporting their diagonals through finite
limits. It preserves effective epis by transporting the simplicial
\v{C}ech nerve through finite limits and its realization through
colimits. Thus if $A\to X$ is any family, there is an equivalence
\[
 L\operatorname{supp}_X(A)\simeq\operatorname{supp}_{LX}(LA),
\]
viewed as objects over $LX$. A localization can send a proper
support to the top support, as the following small sheaf model shows.

\begin{example}[Localizing at the dense open of Sierpi\'nski space]
\label{ex:logic-dense}
Let $Z=\{0,1\}$ with opens $\varnothing, U=\{1\}, Z$. Its
space-valued sheaves are diagrams $A\to B$ of spaces, with $A$
the value on $Z$ and $B$ the value on $U$. Every open cover of a
nonempty open contains that open itself, so the only additional
condition imposes a terminal value on $\varnothing$.
The subterminal $U\hookrightarrow 1$ is the map of diagrams
\[
 (\varnothing\longrightarrow *)
 \;\longrightarrow\; (*\longrightarrow *).
\]
A diagram $A\to B$ is local for this map exactly when $A\to B$
is an equivalence, since mapping out of the two diagrams computes
sections over $Z$ and $U$ respectively. The local diagrams identify
with $\mathcal S$ via evaluation at $U$, with inverse up to
equivalence given by the constant diagram. Evaluation is the
reflector: maps into $(C\xrightarrow{\mathrm{id}}C)$ are determined,
up to contractible choice, by the map $B\to C$. The reflector
preserves limits as limits of diagrams are computed pointwise.
Consequently this geometric localization preserves all higher
homotopy in the value on $U$. It turns $U\hookrightarrow 1$ into
an equivalence, although $U\vee\neg U=U$ before localization.
\end{example}

The double-negation action of this reflector can be computed in
arbitrary contexts. Fix $r:A\to B$, and identify one of its
subobjects by a pair of unions of components $M\subseteq A$ and
$N\subseteq B$ with $M\subseteq r^{-1}(N)$. In the following
formulas complements inside a space are complementary unions of
components. Any subobject disjoint from $(M,N)$ has its second
entry contained in $B\setminus N$, hence its first entry contained
in $r^{-1}(B\setminus N)$. This latter pair is itself a subobject
disjoint from $(M,N)$. Therefore
\[
\begin{aligned}
 \neg(M,N)&=(r^{-1}(B\setminus N),B\setminus N),\\
 \neg\neg(M,N)&=(r^{-1}N,N).
\end{aligned}
\]
Here $r^{-1}$ denotes the homotopy pullback of a mono. Reflecting
$(M,N)\hookrightarrow(A,B)$ gives $N\hookrightarrow B$. Pulling
its image under the right adjoint back along the unit of the
adjunction gives precisely $(r^{-1}N,N)$. Thus double negation on
predicates agrees with this localization in every context, even when
$A$ and $B$ have nontrivial higher homotopy. The closure of a
subobject and the higher data local to $U$ can both be read directly
from the localization. Compare the general treatment of topological
localizations in \cite[\S6.2]{lurie-htt} and left exact modalities in
\cite{rijke-shulman-spitters}.

\begin{example}[A reflector that changes implications]
The same diagram category has a different accessible left exact
localization. Evaluation at $Z$ has fully faithful right adjoint
$C\mapsto(C\to *)$, as a map of diagrams to this target is
specified by its value on the first entry. The left adjoint, denoted
$K$, sends both $U$ and $0$ to the empty space. Since $U$ was dense,
$\neg U=0$ in the source, so there is a strict inequality
\[
 K(\neg U)=\varnothing \quad < \quad *=\neg K(U)
\]
in the subobject lattice of the terminal space. This also computes
a failure to preserve an exponential. The Heyting implication
$U\Rightarrow0$ is the exponential $0^U$, since both operands
are subterminal and the exponential has the adjunction for
implication. In the target the corresponding exponential is
$\varnothing^{\varnothing}\simeq *$. Evaluation at $Z$ preserves
stable images by the argument above, whereas implication uses a
right adjoint and the displayed strict inequality shows precisely
where its preservation can fail. This matters when a geometric
localization is used to move an interpretation of logic between
models: a proof that uses implication may require an additional
preservation argument beyond left exactness.
\end{example}




\section{Recursion and computability}
\label{sec:recursion}

The natural numbers object organizes the categorical study of recursion in
Lambek and Scott \cite{lambek-scott}. In an $\infty$-topos, its elimination
principle applies to families with arbitrary homotopy types. The natural
numbers themselves still form a set internally. The higher structure appears in
the spaces of sections and in the comparisons that express the recursion
equations. This distinction also allows us to locate the additional
mathematical structure necessary for a realizability interpretation.

\subsection{The recursion space}

Let $\mathcal E$ be a Grothendieck $\infty$-topos, write $1$ for its terminal
object, and put
\[
N=\coprod_{n\in\mathbb N}1,
\qquad
z=i_0,
\qquad
s i_n=i_{n+1},
\]
where $i_n$ is the $n$th coproduct injection. Here $\mathbb N$ in the index
denotes the external set and $N$ denotes an object of $\mathcal E$. The
relation $s i_n=i_{n+1}$ denotes the comparison supplied by the coproduct
property. The general relation between inductive types and homotopy-initial
algebras is treated by Awodey, Gambino, and Sojakova
\cite{awodey-gambino-sojakova}.

\begin{proposition}[Homotopy-initial natural numbers]
\label{prop:recursion-nno}
The object $N$ is $0$-truncated. Given $a:1\to A$ and $b:A\to A$, the
space of triples
\[
(f,\alpha,\beta),\qquad
f:N\to A,\quad
\alpha:fz\simeq a,\quad
\beta:fs\simeq bf
\]
is contractible. In particular $(N,[z,s])$ is initial among algebras for
$1\amalg(-)$ with homotopy-commuting morphisms of algebras.
\end{proposition}

\begin{proof}
Universality of coproducts gives
$N\times N\simeq\coprod_{m,n\in\mathbb N}1$. The pullback of the diagonal
$N\to N\times N$ to the summand indexed by $(m,n)$ is the pullback
$1\times_N1$ of the injections $i_m$ and $i_n$. By disjointness it is
initial when $m\ne n$, and equivalent to $1$ when $m=n$. A pullback of a
diagonal along an arbitrary map to $N\times N$ decomposes into the
corresponding pullbacks over these summands. Thus the diagonal is a
monomorphism, which is the criterion for $0$-truncatedness.

Set $K=\operatorname{Map}_{\mathcal E}(1,A)$. The coproduct property
identifies $\operatorname{Map}_{\mathcal E}(N,A)$ with
$\prod_{n\in\mathbb N}K$. In this description the desired space consists
of sequences $(x_n)$ with paths $x_0\leadsto a$ and
$x_{n+1}\leadsto b x_n$ for every $n$. The paths are part of the points
of this space. The space of the first entry with its path to $a$ is a
based path space with variable starting point and is contractible. At
each finite stage, forgetting the last entry and its path has
contractible homotopy fibers, since extending the sequence is choosing a
point of $K$ together with a path from that point to a specified point of
$K$. Each finite stage is therefore contractible. The desired space is
the inverse limit of these finite stages in $\mathcal S$, so is itself
contractible.

For an endofunctor $F$, take the category of algebras to be the
pullback of the arrow category along $X\mapsto (FX,X)$. The mapping
space from $u:FX\to X$ to $v:FY\to Y$ is then the homotopy equalizer of
the maps $f\mapsto f u$ and $f\mapsto v Ff$ from
$\operatorname{Map}_{\mathcal E}(X,Y)$ to
$\operatorname{Map}_{\mathcal E}(FX,Y)$. For $F=1\amalg(-)$ and the
source $(N,[z,s])$, the two components of the equalizer are exactly
$\alpha$ and $\beta$.
\end{proof}

Contractibility is stronger than uniqueness of the homotopy class of the
underlying arrow. For instance, in $\mathcal S$, choose
$A=S^1$, let $a$ be its base point, and take $b$ to be the identity.
The underlying arrow space $(S^1)^{\mathbb N}$ has nontrivial loops.
The base path and all step paths in
Proposition~\ref{prop:recursion-nno} supply the data that make the space
of solutions contractible.

\subsection{Dependent recursion and parameters}

For a family $p:E\to N$, an initial datum is a point
$a:1\to E$ over $z$, and a successor datum is a map $d:E\to E$ over
$s$. The latter consists of $d$ and a chosen homotopy $p d\simeq s p$.
A dependent solution is a section $\sigma$ of $p$, a comparison
$\sigma z\simeq a$ over $z$, and a comparison
$\sigma s\simeq d\sigma$ over $s$.

\begin{proposition}[Dependent elimination]
\label{prop:recursion-dependent}
The space of dependent solutions is contractible. The same construction
holds in every slice $\mathcal E_{/\Gamma}$, with natural numbers object
$\Gamma\times N\to\Gamma$, and is stable under pullback of contexts.
\end{proposition}

\begin{proof}
Let $E_n=i_n^*E$ and $K_n=\operatorname{Map}_{\mathcal E}(1,E_n)$.
Regard $1$ with structure map $i_n$ as the $n$th object of a discrete
diagram in $\mathcal E_{/N}$. Its coproduct is $\mathrm{id}_N$,
because coproducts in a slice are computed on the domains. Therefore
\[
\operatorname{Map}_{\mathcal E_{/N}}(\mathrm{id}_N,p)
\simeq\prod_{n\in\mathbb N}K_n .
\]
The successor datum and the chosen comparison for $s i_n$ induce maps
$d_n:K_n\to K_{n+1}$. The base datum gives a point of $K_0$.
In these coordinates the solution space consists of $x_n\in K_n$
with paths $x_0\leadsto a$ and $x_{n+1}\leadsto d_n(x_n)$.
Again, each finite stage is contractible by taking the path space with
variable starting point, and the solution space is their inverse limit.

Apply the argument in $\mathcal E_{/\Gamma}$, whose terminal object
is $\mathrm{id}_\Gamma$. Universality of coproducts identifies the
sum of its copies of $\mathrm{id}_\Gamma$ with $\Gamma\times N$ over
$\Gamma$. A change of context preserves this coproduct and sends
the recursion data and their comparisons to those for the pulled-back
family. It sends a solution to a solution and identifies the distinguished
solution up to the contractible space described above.
\end{proof}

If $p$ is a monomorphism, the dependent conclusion is induction for a
predicate on $N$. A proof at zero and a proof of successor closure give
a section of that monomorphism, hence the predicate holds everywhere.
If $p$ has higher fibers, the same proof yields a coherent family of
terms. For an ordinary example with parameters, let
$a:\Gamma\to N$ and $b:\Gamma\times N\times N\to N$ be the base and
step maps for primitive recursion. Over $\Gamma$, recurse with state
$(n,x)$, initial state $(0,a)$, and transition
$(n,x)\mapsto(s(n),b(-,n,x))$. The first coordinate of the resulting
map is the identity on the numerical index by uniqueness of recursion.
The second coordinate defines $r$ with
$r(\gamma,0)=a(\gamma)$ and
$r(\gamma,s(n))=b(\gamma,n,r(\gamma,n))$.
The equality notation here is justified by the $0$-truncated target.
In a type-theoretic presentation, judgmental computation rules require
the corresponding coherent choices of model structure.

In particular, define addition by using the first numerical input
as initial value and incrementing the state at each iteration.
Multiplication uses zero as initial value and adds the first input
at each iteration. On an external numerals pair $(m,n)$, these maps
land in the summands indexed by $m+n$ and $mn$, respectively. The
claim follows by ordinary induction on the second index. Conversely
these values determine the arrows by the coproduct property of
$N\times N$. The same reasoning extends to a primitive recursive
definition built from zero, successor, projections, composition, and
primitive recursion. Inverse images of geometric morphisms preserve
the sums of copies of $1$, the finite products, and the input maps
of recursion. They therefore preserve these arithmetic operations.
This preservation concerns the specified operations and their
equations.

\begin{example}[Higher-order numerical recursion]
Let $F=N^N$ and let $1_N=s z:1\to N$ be the numeral one. In context
$F$, the generic function $f$ is evaluation. Take $f(1_N)$ as
initial value and $f$ as transition for a recursion with target $N$.
Transposing the resulting map $F\times N\to N$ defines an arrow
$\Phi:F\to F$ satisfying
\[
\Phi(f)(0)=f(1_N),
\qquad
\Phi(f)(s(n))=f\bigl(\Phi(f)(n)\bigr).
\]
Recursion with target $F$ now gives $h:N\to F$ with $h(0)=s$ and
$h(s(m))=\Phi(h(m))$. Its uncurried map $a:N\times N\to N$
satisfies
\begin{align*}
a(0,n)&=s(n),\\
a(s(m),0)&=a(m,1_N),\\
a(s(m),s(n))&=a(m,a(s(m),n)).
\end{align*}
These equations give the Ackermann--P\'eter function on external
numerals, as follows by induction first on $m$ and then on $n$.
This function lies beyond numerical primitive recursion
\cite[\S1.4]{dean-naibo-recursive-functions}. The outer state $F$ is
itself a type of functions, so the categorical construction uses
recursion at a higher simple type. The object $F$ is $0$-truncated
by the exponential adjunction and the truncation of $N$. Thus this
example already belongs to the ordinary fragment.
\end{example}

\subsection{Absolute Church's thesis}

Fix a standard external enumeration $(\varphi_e)_{e\in\mathbb N}$
of the partial recursive functions. Write $H(e,n,t,m)$ for the
decidable relation saying that $t$ is a code of a terminating
computation of program $e$ on input $n$ with output $m$.
For a Grothendieck $\infty$-topos, interpret this predicate as the
subobject of $N^4$ obtained by taking the coproduct of the summands
on which the external relation holds. The object $N^4$ here is the
fourfold product, and $N^N$ below is the exponential. The corresponding
form of Church's thesis is the internal proposition
\begin{equation}
\label{eq:abs-church}
\forall f:N^N\ \exists e:N\ \forall n:N\ \exists t:N\,
H(e,n,t,f(n)).
\end{equation}
The numerical relation can equivalently be interpreted from its
primitive recursive characteristic function. The geometric inverse image
$\mathcal S\to\mathcal E$ preserves finite products and the
coproducts defining numerical operations, so the two descriptions agree
on every numeral tuple and hence on their coproduct. Existential
quantification in \eqref{eq:abs-church} is propositional.

\begin{proposition}[Failure for Grothendieck semantics]
\label{prop:recursion-ct}
In the classical external metatheory, the truth value of
\eqref{eq:abs-church} is the initial subobject of $1$ in every
Grothendieck $\infty$-topos. In a nondegenerate $\infty$-topos this
proposition is false.
\end{proposition}

\begin{proof}
There exists an external function $g:\mathbb N\to\mathbb N$ not
computed by any $\varphi_e$. For example, use the characteristic
function of the diagonal halting set. The map
$\bar g:N\to N$ defined on each summand by $i_n\mapsto i_{g(n)}$
supplies an internal instance of $f$. Let $P\hookrightarrow N$ be
the subobject of indices satisfying
$\forall n\,\exists t\,H(e,n,t,\bar g(n))$.
For each external $e$, choose an $n$ at which $\varphi_e$ is
undefined or differs from $g$. With these two numerals substituted
and with the output $g(n)$ fixed, the subobject of possible $t$ is
initial by the interpretation of $H$ and the disjointness of summands.
Its existential image in $1$ is initial. Universal elimination shows
that $i_e^*P$ is therefore also initial. Universality of coproducts
now gives $P\simeq\coprod_e i_e^*P\simeq 0$, so the existential image
of $P$ in $1$ is initial. The universal assertion
\eqref{eq:abs-church} is contained in this instance and therefore is
initial as well.
\end{proof}

This argument accounts for local existence in sheaf semantics.
A local index is allowed to vary with the context. The proof reduces
that index to numeral summands, and every summand gives an empty
predicate for the fixed counterexample $\bar g$. In $\mathcal S$
the same phenomenon is visible directly since $N^N$ is the discrete
space of all set-theoretic numerical functions. A recursion principle
can introduce a map from specified base and step data even when
other maps admitted by the semantics have no program index.

\subsection{The effective topos as a boundary example}

Take the ordinary effective topos $\mathrm{Eff}$ based on Kleene's
first partial combinatory algebra. Its full subcategory of assemblies
has objects $(X,R_X)$ with a nonempty set $R_X(x)\subseteq\mathbb N$
of realizers for each $x$. A morphism $f:(X,R_X)\to(Y,R_Y)$ is
a function equipped, in the sense of existence, with a single partial
recursive tracker $\varphi_e$. The condition is that for every
$x$ and every $r\in R_X(x)$, the computation $\varphi_e(r)$ is
defined and belongs to $R_Y(f(x))$. Different trackers for a fixed
underlying function give the same morphism. The natural numbers object
$N_{\mathrm{Eff}}$ is the assembly with $R(n)=\{n\}$
\cite[Ch.~3]{van-oosten-realizability}.

Fullness of the assembly inclusion reduces every endomorphism of
$N_{\mathrm{Eff}}$ to a tracked function. The tracker condition
for this assembly is $\varphi_e(n)=f(n)$ on every input.
Conversely, any total recursive numerical function supplies its own
tracker. Thus the external endomorphisms of $N_{\mathrm{Eff}}$ are
exactly the total recursive functions. For the internal assertion
with quantification over the exponential, Hyland separately proves
Church's thesis in $\mathrm{Eff}$ \cite[Prop.~10.2]{hyland-effective}.
The argument via tracked arrows identifies the external endomorphism
set, while the internal theorem governs generalized elements and
their witnesses.

There is a direct obstruction to applying
Proposition~\ref{prop:recursion-nno} to $\mathrm{Eff}$ as an ordinary
category. If the countable coproduct $\coprod_{n\in\mathbb N}1$
existed, its shift would make it an ordinary natural numbers object
by the same recursion proof using sets of arrows. The resulting
isomorphism to $N_{\mathrm{Eff}}$ would preserve all numeral injections.
Choosing their images in $N_{\mathrm{Eff}}$ independently would define
an endomorphism for every external function $\mathbb N\to\mathbb N$,
contrary to tracking. This recovers the countable-coproduct obstruction
of van Oosten \cite[Prop.~3.2.3]{van-oosten-realizability}. In
particular $\mathrm{Eff}$ cannot be the full subcategory of
$0$-truncated objects in any Grothendieck $\infty$-topos, since the
countable coproduct of terminal objects constructed above is already
$0$-truncated.

The argument uses the Grothendieck hypothesis through external
coproducts. Rasekh constructs natural numbers objects for a specified
elementary higher topos framework by a different argument that avoids
assuming these coproducts \cite{rasekh-nno}. A higher analogue of
realizability intended to validate absolute Church's thesis must
specify a framework outside the hypotheses of
Proposition~\ref{prop:recursion-ct}, or change the numerical predicate
or quantifier in the thesis. The comparison in
Section~\ref{sec:effective-lifts} addresses the additional choices
in passing from ordinary realized predicates to higher families.



\section{Higher realizability and the scope of Church's thesis}
\label{sec:effective-lifts}

The ordinary effective topos and the Grothendieck semantics of
Section~\ref{sec:recursion} admit different functions on natural numbers.
This gives a criterion for comparing a proposed higher realizability
model with its ordinary fragment. Suppose the model has set-valued
natural numbers and the indexed operations of Theorem~\ref{thm:bridge}
restrict to its $0$-truncated types. Interpreting arithmetic via the
same natural numbers object and numerical predicates, the truth of
\eqref{eq:abs-church} is computed by those restricted operations.
Each numerical type and context in that sentence is a set, and every
existential is an image. Hence the arithmetic sentence has the same
truth value in the higher model and in its ordinary fragment. The
argument also applies to an elementary higher model with the same
restriction, without assuming that model is a Grothendieck
$\infty$-topos.

The distinctions among existing constructions determine which such
transfer statements apply. Uemura constructs a cubical-assembly
model with a univalent impredicative universe and shows a failure of
a form of propositional resizing \cite{uemura-cubical}. Swan and
Uemura establish that the ordinary realizability interpretation of
Church's thesis and the homotopical interpretation in cubical
assemblies can disagree. They construct a left exact modality whose
reflective subuniverse validates the homotopical thesis
\cite{swan-uemura-church}. The existence of the modality and the
calculation of the ordinary fragment are independent questions about
such a model. The transfer applies when an equivalence of ordinary
fragments identifies the arithmetic data.

Awodey and Emmenegger give a candidate effective $2$-topos with
$0$-types equivalent to the effective topos
\cite{awodey-emmenegger-effective}. The comparison with cubical
assemblies in their work exhibits a concrete reason to pay attention
to exact completion: forming an ordinary exact completion and then
introducing a cubical direction can change which ordinary types are
recovered after passage to homotopy. Their recovery theorem at the
$2$-topos level concerns the ordinary fragment and gives a
finite-dimensional comparison for the extension to all levels.
In particular, a claim about a higher effective model should specify
its underlying category, its universe assumptions, and the
identification of its $0$-types before invoking ordinary
realizability theorems in that model.


One can see the arithmetic preservation requirement independently
of the geometry of the model. Suppose $f,g:X\to N^N$
are two generalized sections and that a proposition over $X$ asserts
the existence of an index computing both. On the support of that
proposition the two composites $X\times N\to N$
agree. Pull back along the effective epimorphism supplying the
shared index. Over the product of its domain with $N$,
take the fiber product of the two covers supplying halting runs
for that input. On this last cover determinism of the machine
forces equality of outputs. Equality descends through both covers
because it is interpreted by a mono. This argument uses the run
existentials separately in the context of an input, so it requires
no choice of a run simultaneously for all inputs. By the exponential
adjunction the two original generalized sections agree on that
support. The resulting identity is an extensional property of
program behavior. An assignment of programs implementing $f$ can
carry additional data, such as distinct codes for a single function,
which this identity and the truth of the corresponding instance of \eqref{eq:abs-church} discard.
Determining the space of implementations requires the ambient higher
model.



\section{Scope of the comparison}

Theorem~\ref{thm:bridge} identifies the set-valued language of an
ordinary topos within the higher language while allowing the latter to
form identities and dependent products of higher types. The ambient
category controls the resulting families: an identity can carry a group
of loops, an existential can be true without a global term, and an
ordinary context can support a product whose components depend on
higher gluing. Each assertion has an example above with the context,
family, and operation specified.

There are two distinct extensions of the classical term-model program
here. The classifying topoi in
Theorem~\ref{thm:unrestricted-and-discrete} give explicit universal
models for geometric fragments. Classifying stronger dependent
theories with judgmental computation rules requires specifying their
syntactic presentations and the morphisms that preserve their operations.
Likewise, an effective version of the higher theory needs a framework
that keeps the intended computational structure. The Grothendieck
assumptions yield the comparison and descent theorems of this article,
and Proposition~\ref{prop:recursion-ct} gives a precise limit on their
use for absolute Church's thesis.

\paragraph{Use of automation.}
AI tools assisted in drafting, organizing, and checking this manuscript.
Arguments are presented as mathematical proofs in the text. No proof
assistant verification is claimed. The cited sources and the LaTeX
source allow the constructions and calculations to be reviewed directly.


\balance

\begin{thebibliography}{99}\small

\bibitem{lambek-scott}
J. Lambek and P. J. Scott.
\newblock \emph{Introduction to Higher Order Categorical Logic}.
\newblock Cambridge Studies in Advanced Mathematics 7, Cambridge
University Press, 1986. Corrected paperback, 1988.
\href{https://assets.cambridge.org/97805213/56534/frontmatter/9780521356534_frontmatter.pdf}{Publisher front matter}.

\bibitem{lurie-htt}
J. Lurie.
\newblock \emph{Higher Topos Theory}.
\newblock Annals of Mathematics Studies 170, Princeton University Press,
2009. \href{https://www.math.ias.edu/~lurie/papers/HTT.pdf}{Author's text}.

\bibitem{lumsdaine-warren}
P. LeFanu Lumsdaine and M. A. Warren.
\newblock The local universes model\textemdash an overlooked coherence
construction for dependent type theories.
\newblock \emph{ACM Trans. Comput. Log.} 16(3), article 23, 2015.
\href{https://arxiv.org/abs/1411.1736}{arXiv:1411.1736}.

\bibitem{kapulkin-lumsdaine}
K. Kapulkin and P. LeFanu Lumsdaine.
\newblock The simplicial model of Univalent Foundations (after Voevodsky).
\newblock \emph{J. Eur. Math. Soc.} 23 (2021), 2071--2126.
\href{https://ems.press/journals/jems/articles/274693}{Journal article}.

\bibitem{shulman-univalence}
M. Shulman.
\newblock All \((\infty,1)\)-toposes have strict univalent universes.
\newblock 2019. \href{https://arxiv.org/abs/1904.07004}{arXiv:1904.07004}.

\bibitem{hott-book}
The Univalent Foundations Program.
\newblock \emph{Homotopy Type Theory\textup{:} Univalent Foundations of
Mathematics}.
\newblock Institute for Advanced Study, 2013.
\href{https://homotopytypetheory.org/book/}{Open book}.

\bibitem{nikolaus-schreiber-stevenson}
T. Nikolaus, U. Schreiber, and D. Stevenson.
\newblock Principal \(\infty\)-bundles\textemdash General theory.
\newblock \emph{J. Homotopy Relat. Struct.} 10 (2015), 749--801.
\href{https://arxiv.org/abs/1207.0248}{arXiv:1207.0248}.

\bibitem{rijke-shulman-spitters}
E. Rijke, M. Shulman, and B. Spitters.
\newblock Modalities in homotopy type theory.
\newblock \emph{Log. Methods Comput. Sci.} 16(1), article 2, 2020.
\href{https://lmcs.episciences.org/6015}{Journal article}.

\bibitem{awodey-gambino-sojakova}
S. Awodey, N. Gambino, and K. Sojakova.
\newblock Homotopy-initial algebras in type theory.
\newblock \emph{J. ACM} 63(6), article 51, 2017.
\href{https://eprints.whiterose.ac.uk/id/eprint/105765/}{Open repository copy}.

\bibitem{dean-naibo-recursive-functions}
W. Dean and A. Naibo.
\newblock Recursive Functions.
\newblock In \emph{The Stanford Encyclopedia of Philosophy}, Summer
2025 edition. \href{https://plato.stanford.edu/archives/sum2025/entries/recursive-functions/}
{Archived entry}.

\bibitem{hyland-effective}
J. M. E. Hyland.
\newblock The effective topos.
\newblock In \emph{The L. E. J. Brouwer Centenary Symposium},
Studies in Logic and the Foundations of Mathematics 110, 165--216,
North-Holland, 1982.
\href{https://www.dpmms.cam.ac.uk/~jmeh1/Research/Pub81-90/hyland-effectivetopos.pdf}{Author's copy}.

\bibitem{van-oosten-realizability}
J. van Oosten.
\newblock \emph{Realizability\textup{:} An Introduction to its Categorical Side}.
\newblock Studies in Logic and the Foundations of Mathematics 152,
Elsevier, 2008.
\href{https://shop.elsevier.com/books/realizability/van-oosten/978-0-444-51584-1}{Publisher record}.

\bibitem{rasekh-nno}
N. Rasekh.
\newblock Every elementary higher topos has a natural number object.
\newblock \emph{Theory Appl. Categ.} 37 (2021), 337--377.
\href{https://tac.mta.ca/tac/volumes/37/13/37-13abs.html}{Journal article}.

\bibitem{uemura-cubical}
T. Uemura.
\newblock Cubical assemblies, a univalent and impredicative universe,
and a failure of propositional resizing.
\newblock \emph{LIPIcs} 130, TYPES 2018, article 7, 2019.
\href{https://doi.org/10.4230/LIPIcs.TYPES.2018.7}{doi:10.4230/LIPIcs.TYPES.2018.7}.

\bibitem{swan-uemura-church}
A. W. Swan and T. Uemura.
\newblock On Church's thesis in cubical assemblies.
\newblock \emph{Math. Structures Comput. Sci.} 31 (2021), 1185--1204.
\href{https://doi.org/10.1017/S0960129522000068}{doi:10.1017/S0960129522000068}.

\bibitem{awodey-emmenegger-effective}
S. Awodey and J. Emmenegger.
\newblock Toward the effective 2-topos.
\newblock \emph{Math. Structures Comput. Sci.} 35 (2025), e32.
\href{https://doi.org/10.1017/S0960129525100352}{doi:10.1017/S0960129525100352}.

\end{thebibliography}


\end{document}

End of manuscript · Back to top ↑