Univalent polymorphism
Benno van den Berg




We show that Martin Hyland's effective topos can be exhibited as the homotopy category of a path category 𝔼𝔽𝔽. Path categories are categories of fibrant objects in the sense of Brown satisfying two additional properties and as such provide a context in which one can interpret many notions from homotopy theory and Homotopy Type Theory. Within the path category 𝔼𝔽𝔽 one can identify a class of discrete fibrations which is closed under push forward along arbitrary fibrations (in other words, this class is polymorphic or closed under impredicative quantification) and satisfies propositional resizing. This class does not have a univalent representation, but if one restricts to those discrete fibrations whose fibres are propositions in the sense of Homotopy Type Theory, then it does. This means that, modulo the usual coherence problems, it can be seen as a model of the Calculus of Constructions with a univalent type of propositions. We will also build a more complicated path category in which the class of discrete fibrations whose fibres are sets in the sense of Homotopy Type Theory has a univalent representation, which means that this will be a model of the Calculus of Constructions with a univalent type of sets.


Pitfalls of statistics-limited X-ray polarization analysis
    [
    Accepted 23/03/2018
==========================================================






§ INTRODUCTION


There has been a continuing interest in obtaining models of impredicative type theories, like the Calculus of Constructions (CoC). One reason is the use of CoC as the basis of proof assistants such as Coq and Lean; on a more theoretical level, these models shed light on issues surrounding impredicativity. Recently, the quest for models has received a new impetus due to the influence of Homotopy Type Theory (HoTT). Some natural questions which have arisen are whether it is possible to have universes which are both impredicative and univalent, how the type Prop of propositions in CoC relates to the notion of proposition in HoTT and whether one can obtain models of Voevodsky's resizing axioms.

So what is needed to model CoC? Roughly, what one needs is a category equipped with two classes of maps, one (“the small fibrations”) contained in the other (“the fibrations”), and where both classes are pullback stable, closed under composition and contain all isomorphisms. One needs a particular small fibration (a “representation”) such that any other small fibration can be obtained as a pullback of that one; in addition, one needs to be able to push forward fibrations along other fibrations (where push forward is the right adjoint to pullback), and, crucially, one needs that small fibrations are closed under being pushed forward along arbitrary fibrations (this is what is meant by impredicativity in this context).

There is an old idea (see <cit.>) that models of CoC can be obtained by looking at Hyland's effective topos  <cit.>: the idea is that in this case every map is fibration and the small fibrations are the discrete maps, with a map in the effective topos being discrete if all its fibres are subcountable. It turns out that this does not quite work, due to a certain ambiguity in the notion of a discrete map, as explained in <cit.>. There is a global notion of a discrete map, where one says that a map f: Y → X in  is discrete if f can be covered by a subobject of the natural numbers object π_X: ℕ× X → X in /X (this is how discrete maps are defined in <cit.>). In this case the discrete maps have a representation, but are not stable under push forward along arbitrary maps (see <cit.>). Alternatively, there is the local notion of a discrete map, where one says that a map f: Y → X is discrete if there is an epi q: X' → X such that q^*f is covered by a subobject of the natural numbers object π_X': ℕ× X' → X' in /X' (this is equivalent to saying that, internally, f has the right lifting property with respect to Ω→ 1 or ∇(2) → 1). In this case the discrete maps are stable under push forward along arbitrary maps, but it is still an open question whether the discrete maps defined in this local manner have a representation in . 

The standard way of solving this problem is to restrict to the ¬¬-separated objects in the effective topos (the assemblies; see also <cit.>). Within these assemblies the distinction between the two notions of a discrete map disappears (see <cit.>) and the discrete maps have a representation and are closed under push forward along arbitrary maps. This means that within the assemblies one can obtain a model of CoC, and to this day this remains the “standard” model for CoC.

This paper suggests an alternative solution. The first step in this direction is the observation that the the effective topos arises as the homotopy category of a certain path category, which we will denote 𝔼𝔽𝔽. 

The notion of a path category, short for a category with path objects, was first introduced in <cit.> and provides an abstract categorical setting for doing homotopy theory, in a manner similar to Quillen's model categories. Path categories are categories equipped with two classes of maps, fibrations and equivalences, satisfying a number of axioms which strengthen Ken Brown's axioms for a category of fibrant objects <cit.> (in that sense the notion of a path category is similar to Joyal's notion of a tribe <cit.>, with the notion of a tribe being the stronger of the two). From a type-theoretic perspective, path categories provide models of “propositional identity types” (models of Martin-Löf's identity types but with the computation rule formulated as a propositional equality; see <cit.>). The key notions from Homotopy Type Theory such as transport, univalence and hlevel, make sense in any path category, and therefore these notions make sense in 𝔼𝔽𝔽 as well. 

It turns out that in 𝔼𝔽𝔽 one can define a notion of discrete fibration which is stable under push forward along arbitrary fibrations. It is still unclear if the class of discrete fibrations has a representation in 𝔼𝔽𝔽; however, if we restrict the hlevel of its fibres to propositions in the sense of HoTT, the discrete fibrations will have a representation and will still be be closed under push forward along arbitrary fibrations. In fact, its representation is essentially the subobject classifier in the effective topos and this representation will be univalent in 𝔼𝔽𝔽. That means that with the class of propositional discrete fibrations as the small fibrations, 𝔼𝔽𝔽 is a model of CoC with a univalent Prop. Given that the homotopy category of 𝔼𝔽𝔽 is the effective topos, this may not be so surprising. However, the author of this paper thinks it is quite satisfying to see the notion of proposition from CoC, HoTT and the effective topos match up nicely like this. In addition, it is interesting to note that 𝔼𝔽𝔽 is a model of propositional resizing. (This should be compared with the negative result due to Taichi Uemura <cit.>, showing that it fails in cubical assemblies.)

One way in which the model in 𝔼𝔽𝔽 is somewhat poor is that its universe only contains propositions (in the sense of HoTT) and therefore excludes many data types like ℕ or ℕ→ℕ (in that it differs from the standard model in assemblies). The difficulty is that these objects are not propositions, but actually live one hlevel higher: that is, they are sets in the sense of HoTT. For that reason I will also construct a more complicated path category  𝔼𝔽𝔽_1 in which the class of fibrations of discrete sets is an impredicative class of small fibrations with a univalent representation. This univalent universe will also contain such objects as ℕ or ℕ→ℕ.

There is a clear sense in which the construction of 𝔼𝔽𝔽_1 is the natural next step after the construction of 𝔼𝔽𝔽. The natural next step after that would be the construction of a path category 𝔼𝔽𝔽_2 in which the class of discrete fibrations of groupoids would be closed under push forward along arbitrary fibrations and would have a univalent representation. In the limit one would expect to be able to construct a path category 𝔼𝔽𝔽_∞ in which the class of discrete fibrations (without any restriction on its hlevel) would be closed under push forward along arbitrary fibrations and have a univalent representation. This would provide an alternative way of salvaging the original idea of obtaining models of CoC using discrete fibrations.

At this point I should make two important disclaimers. Firstly, when I say that 𝔼𝔽𝔽 and 𝔼𝔽𝔽_1 are models of CoC, I am ignoring the usual coherence problems related to substitution. I suspect it would be relatively straightforward to solve this by some careful rephrasing in terms of categories with families <cit.>, but I am leaving this to future work. Secondly, and this may be the more essential point, 𝔼𝔽𝔽 and 𝔼𝔽𝔽_1 will be models of a version of CoC in which many definitional equalities have been replaced by propositional ones: this applies not just to the computation rule for the identity type, but to many computation rules. In fact, I am imagining a version of CoC in which the notion of definitional equality has been completely eliminated in favour of the notion of propositional equality. I am currently working on writing down a precise syntax for such a system, but this is still work in progress.  I suspect that a reader familiar with the categorical semantics of type theory can guess what it would look like on the basis of the categorical definitions in Section 2 below.

Throughout this paper we will rely on categorical language: familiarity with the language of type theory will not be assumed.

Finally, unless explicitly noted otherwise, the results obtained here are all constructive. However, since we will be interested in building models of impredicative type theories, our metatheory will be impredicative as well, which means that our metatheory will be something like intuitionistic Zermelo-Fraenkel set theory (IZF) or the internal logic of an elementary topos with a natural numbers object (both can be seen as subsystems of ZF). Results which rely on the axiom of choice will be marked with the label (ZFC).



§ PATH CATEGORIES


We will start this paper by discussing the notion of a path category, as introduced in <cit.>, and by showing how many of the concepts in Homotopy Type Theory make sense in the context of a path category. The reader who wishes to see more details should consult Section 2 of <cit.>.



 §.§ Definition
 Let me first give the definition.

pathcat
A path category (short for a category with path objects) is a category C equipped with two classes of maps, called fibrations and equivalences, respectively. A fibration which is also an equivalence will be called trivial. If X → PX → X × X is a factorisation of the diagonal on X as an equivalence followed by a fibration, then PX is a path object for X. In this case, we will often denote the equivalence X → PX by r and the fibration PX → X × X by (s, t). In a path category the following axioms should be satisfied:


  * Isomorphisms are fibrations and fibrations are closed under composition.

  * C has a terminal object 1 and X → 1 is always a fibration.

  * The pullback of a fibration along any other map exists and is again a fibration.

  * Isomorphisms are equivalences and equivalences satisfy 6-for-2: that is, if f, g, h are maps for which the composition hgf is defined and for which hg and gf are equivalences, then f,g,h and hgf are equivalences as well.

  * Every object X has at least one path object.

  * Trivial fibrations are stable under pullback along arbitrary maps.

  * Trivial fibrations have sections.



onequivalences In <cit.> the equivalences were called weak equivalences. Since every object in a path category is both fibrant and cofibrant (to use the language of model categories) and we have eqishomeq below, there does not really seem to be much need for the adjective “weak”, so we have decided to drop it. Indeed, the HoTT book <cit.> simply calls this class of maps equivalences, without the adjective.


A basic fact about path categories is that they are stable under slicing.

Slicing for path categories
Let C be a path category and X be an object in C. Write C(X) for the full subcategory of C/X whose objects are fibrations. With the equivalences and fibrations as in C, this is again a path category.


pullingback
If f: Y → X is a morphism in a path category, then the functor 
    f^*: C(X) →C(Y),
 obtained by pulling back fibrations along f, preserves all the structure of a path category: that is, it preserves fibrations, equivalences, the terminal object and pullbacks of fibrations along arbitrary maps.

 See <cit.>.




 §.§ Homotopy in path categories
 On parallel morphisms in a path category one can define a homotopy relation, as follows.

homotopy
If f, g: Y → X are two parallel maps in a path category, then we say that f and g are homotopic if there is a map H: Y → PX to a path object on X making



         PX [d, "(s,t)"] 

Y [r, "(f,g)"'] [ur, dotted, "H"]     X ×X



commute. (One can show that this is independent of the choice of path object PX.) In this case we write f ≃ g, or H: f ≃ g if we wish to stress the homotopy H. More generally, suppose p: X → I is a fibration and P_I(X) is the path object of X in the slice category 𝒞(I). If f, g: Y → X are two parallel maps with pf = pg, then we say that f and g are fibrewise homotopic if there is a map H: Y → P_I(X) making



     P_IX [d,"(s, t)"] 

Y [r, "(f, g)"'] [ur, dotted, "H"]     X ×_I X



commute. (This is again independent of the choice of path object P_I(X).) In this case we write f ≃_I g, or H: f ≃_I g if we wish to stress the fibrewise homotopy H.


homcongr
The homotopy relation ≃ is a congruence on C.


This is Theorem 2.14 in <cit.>.


The quotient is the homotopy category of C. A map which becomes an isomorphism in the homotopy category is called a homotopy equivalence.

eqishomeq
The equivalences and homotopy equivalences coincide in a path category.


This is Theorem 2.16 in <cit.>.


Using the notion of homotopy we can strengthen homcongr.

everyobjgroupoiduptohom
 Every object in a path category carries a groupoid structure up to homotopy. More precisely, if A is an object in a path category and PA is a path object for A with equivalence r: A → PA and fibration (s,t): PA → A × A, while PA ×_A PA is the pullback



 PA ×_A PA [d, "p_1"'] [r,"p_2"]     PA [d,"t"] 

PA [r, "s"']     A,



then there are maps μ: PA ×_A PA → PA and σ: PA → PA with (s,t)μ = (sp_2,tp_1) and (s,t)σ = (t,s) such that:


  * μ(p_1,μ(p_2,p_3)) ≃_A × Aμ(μ(p_1,p_2),p_3): PA ×_A PA ×_A PA → PA.

  * μ(1, rs) ≃_A × A 1: PA → PA.

  * μ(rt,1) ≃_A × A 1: PA → PA.

  * μ(1,σ) ≃_A × A rt: PA → PA.

  * μ(σ, 1) ≃_A × A rs: PA → PA.



See <cit.>.


inftygroupoid
 In fact, the arguments in <cit.> can be modified to show that every object in a path category carries the structure of a Grothendieck ∞-groupoid.





 §.§ Transport and univalence
 A crucial concept in homotopy type theory is transport.

transport
Let f: Y → X be a fibration, and Y ×_X PX be the following pullback



Y ×_X PX [d, "p_1"'] [r, "p_2"]     PX [d, "s"] 

Y [r, "f"']     X



A transport structure Γ on f is a map 

    Γ: Y ×_X PX → Y
 such that f Γ = tp_2 and Γ(1_Y, rf) ≃_X 1_Y.


The intuition behind transport is the following: given a fibration f: Y → X, an element y_0 ∈ Y and a path α: x_0 → x_1 in X with f(y_0) = x_0, transport finds an element y_1 in Y with f(y_1) = x_1. In addition, we require that if α would the reflexivity path at x_0, then y_1 should be connected to y_0 by a path lying in the fibre over x_0.

existenceanduniquenessoftransport
Every fibration f: Y → X carries a transport structure and transport structures are unique up to fibrewise homotopy over X.


This is Theorem 2.26 in <cit.>.


In the sequel we will frequently rely on the following properties of transport.

basicpropoftransport
 Let f: Y → X be a fibration with transport structure 
    Γ: Y ×_X PX → Y.
 Then:

 
  * Γ preserves fibrewise homotopy. More precisely, the maps 
    Γ(sp_1,p_2),Γ(tp_1,p_2):P_X(Y) ×_X PX → Y
 are fibrewise homotopic.
 
  * If you have two paths in X which have the same end points and which are homotopic relative those end points, then the transports of y ∈ Y along both paths are fibrewise homotopic. More precisely, the maps

    Γ(p_1,sp_2), Γ(p_1,tp_2):Y ×_X P_X × X(PX) → Y

are fibrewise homotopic.

  * The transport of an element in Y along the composition of two paths and the result of first transporting it along one path and then along the other are fibrewise homotopic. More precisely, the maps

    Γ(p_1,μ(p_3,p_2)), Γ(Γ(p_1,p_2),p_3): Y ×_X PX ×_X PX → Y

are fibrewise homotopic.



See <cit.>.


transportisanequivalence
Suppose p: Y → X is a fibration and f, g: Z → X are two parallel maps which are homotopic via a homotopy H: Z → PX. The morphism f^* p → g^* p over Z induced by H and the transport structure on p is an equivalence. 

 To be clear, if H: Z → PX is the homotopy and Γ: Y ×_X PX → Y is a transport structure, the induced map f^*p → g^* p is:


 
  Z fp Y [rr, "1 ×_X Hπ_Z"]         Z ×_X Y ×_X PX [rr, "Z ×_X Γ"]         Z gp Y.
 


Since every path in PX has an inverse up to homotopy, there is also an operation g^* p → f^*p induced by the inverse of the homotopy H. Using the properties of transport from the previous proposition one can show that this operation is homotopy inverse to the one induced by H.


A fibration is univalent if we can also go in the other direction, as follows.

univalence The fibration p: Y → X is univalent if the following holds: whenever f, g: Z → X are two morphisms and w: f^* p → g^* p is an equivalence in the slice over Z, then there is a homotopy H: Z → PX between f and g such that w is, up to fibrewise homotopy over Z, the equivalence induced by H, as in the previous proposition.


onunivalence In other words, if p: Y → X is a fibration, then any path π: x → x' in X induces an equivalence between the fibres Y_x ≃ Y_x'; a fibration is univalent if, up to fibrewise homotopy, every equivalence between the fibres is obtained in this way. This may look a bit different from  the way univalence is usually stated, but it is equivalent to the standard formulation, as discussed on the HoTT mailing list. See also <cit.> for more details.




 §.§ Function spaces
 No type theory is complete without function types. We will work with function types in the following form, that is, they will be exponentials in the homotopy category.

hexpo
If X and Y are objects in a path category, then we will call an object X^Y the homotopy exponential of X and Y if it comes equipped with a map ev: X^Y × Y → X such that for any map h: A × Y → X there is a map H: A → X^Y such that ev(H × 1_Y) ≃ h, with H being unique up to homotopy with this property.


ondefihomexp Perhaps two remarks are in order about this definition of a homotopy exponential from a type-theoretic perspective. First of all, we only demand that ev(H × 1_Y) and h are homotopic, rather than equal. This basically states β-equality in a propositional, rather than a definitional form: this reflects the fact that we are thinking of a version of type theory in which all the computational rules have been stated propositionally. Secondly, the fact that H is unique up to homotopy amounts to the validity of function extensionality. (See also <cit.>.) Similar remarks apply to the following definition of homotopy Π-types.


hPitypes If g: Z → Y and f: Y → X are fibration, then the homotopy Π-type of f along g is a fibration Π_f(g): E → X equipped with a map ε: f^*Π_f(g) → g over Y such that for any h: A → X and m: f^*h → g over Y there exists a map M: h →Π_f(g) such that ε∘ f^*M ≃_Y m, with M being unique up to fibrewise homotopy over X with this property. We will say that a path category C has homotopy Π-types if all such homotopy Π-types exist for fibrations f and g.


One can phrase this in terms of right adjoints but one has to be a bit careful. If C is a path category with homotopy Π-types and f: Y → X is a fibration in C, then the pullback functor f^*: C(X) →C(Y) has a right adjoint if we pass to the homotopy category. That is, there is an operation Π_f: C(Y) →C(X) which goes in the other direction, but it is only a functor up to fibrewise homotopy over X. 

Also, we cannot really say that the operation Π_f: C(Y) →C(X) preserves fibrations. We do have the following statement, however, which is a good substitute.

goodchoiceofpie
 Let C be a path category with homotopy Π-types. Assume f: Y → X is a fibration in C, while p: B → A is a fibration in C(Y) and Π_f(A) is a homotopy Π-type in C(X). Then there exists a homotopy Π-type Π_f(B) in C(X) together with a fibration Π_f(p): Π_f(B) →Π_f(A) in C(X) such that:

 
  * The diagram
  

 
  f^*Π_f(B) [d,"f^*Π_f(p)"'] [r, "ε"]     B [d, "p"] 

  f^*Π_f(A) [r, "ε"']     A 

 


  in C(Y) commutes.
 
  * For each object C in C(X) the diagram
 

 
  Ho(C(X))(C, Π_f(B)) [d] [r]     Ho(C(Y))(f^*C, B) [d] 

  Ho(C(X))(C, Π_f(A)) [r]     Ho(C(Y))(f^*C, A) 

 


  is a pullback in .


 (Compare <cit.>.) We construct Π_f(p) as follows. First, we take the pullback


 
  P [d, "q"'] [r]     B [d, "p"] 

  f^*Π_f(A) [r, "ε"']     A 

 


and then we define Π_f(p) to be Π_π(q), where π: f^*Π_f(A) →Π_f(A) is the projection.




 §.§ Homotopy n-types
 One can also makes sense of Voevodsky's homotopy levels in the context of path categories.

hlevels
The fibrations of n-types (n ≥ -2) are defined inductively as follows:


  * A fibration f: Y → X is a fibration of (-2)-types if f is trivial. 

  * A fibration f: Y → X is a fibration of (n+1)-types if P_X(Y) → Y ×_X Y is a fibration of n-types for some path object P_X(Y) for f in C(X).

An object X in a path category is called an n-type if the map X → 1 is a fibration of n-types.


namesforhlevels For small n we will often use the following terminology for n-types, as is customary in the context of HoTT.


 (-2)-types     contractible types 

(-1)-types      propositions 

0-types     sets 

1-types     groupoids 
 




In the definition of a fibration of (n+1)-types the dependence on the choice of path object P_X(Y) is only apparent. The reason for this is that path objects are unique up to equivalence (see <cit.>) and we have the following proposition.

hlevelsstableunderpbk Let f be a fibration of n-types.


  * If g is a fibration which can be obtained by pulling back f along some map, then g is also a fibration of n-types.

  * If w is an equivalence and g is a fibration such that f ≃ gw or fw ≃ g, then g is also a fibration of n-types.

  * If w is an equivalence and g is a fibration such that f ≃ wg or wf ≃ g, then g is also a fibration of n-types.



(1) is easily proved by induction on n ≥ -2 using pullingback.

(2) It suffices to prove that if g = fw and w is an equivalence, then g is a fibration of n-types. To see this, note, first of all, that if g ≃ fw, then there is a map w' homotopic to w such that g = fw' (see <cit.>); such a map w' is an equivalence as well, because it is homotopic to w. Furthermore, if gw ≃ f, then g ≃ fw^-1 for a homotopy inverse w^-1 of w; and such a homotopy inverse is an equivalence as well.

So we prove that if g = fw and w: Z → Y is an equivalence and f: Y → X and g: Z → X are fibrations, with f being a fibration of n-types, then g is a fibration of n-types as well. This statement is proved by induction on n, with the case n = 0 following from 6-for-2 for equivalences.

So assume the statement is true for n and f is a fibration of (n+1)-types. We have a commuting diagram of the form


 
  Z [r] [d, "w"']     P_X(Z) [r] [d, dotted]     Z ×_X Z [d, "w ×_X w"] 

Y [r]     P_X(Y) [r]     Y ×_X Y.
 


In this diagram we have a dotted arrow down the middle which make the diagram on the left commute up to homotopy, while the diagram of the right commutes on the nose (see <cit.>). The dotted arrow is an equivalence because all the other arrows in the left hand square are. In addition, because equivalences are stable under pullback along fibrations (see <cit.>), we have that w ×_X w and the inscribed map P_X(Z) → (w ×_X w)^* P_X(Y) are equivalences as well. By assumption, the map P_X(Y) → Y ×_X Y is a fibration of n-types, so by (1) the same is true for its pullback along w ×_X w, and hence the same is true for P_X(Z) → Z ×_X Z by induction hypothesis. Hence g is a fibration of (n+1)-types.

(3) Again, it suffices to prove only one of the two statements and we will show that f ≃ wg implies that g is a fibration of n-types. So assume f ≃ wg and construct the following pullback



 D [r, "v"] [d, "h"']     B [d, "f"] 

C [r, "w"']     A.



We have wgv ≃ fv = wh and since w is an equivalence, it follows that h ≃ gv. Since v is an equivalence by <cit.> and h is a fibration of n-types by (1), this implies that g is a fibration of n-types by (2).


hlevelsandPi
If C is a path category with homotopy Π-types, then Π_f:C(Y) →C(X) preserves fibrations of n-types for any fibration f: Y → X.


This is Theorem 7.1.9 in the HoTT book <cit.>. The proof is by induction on n ≥ -2. 

We have seen that Π_f is not really a functor, but it is one up to homotopy. For that reason it preserves equivalences and therefore the statement is true for n = -2.

For the induction step, suppose that p: Z → Y is a fibration on (n+1)-types in C(Y); so P_Y(Z) → Z ×_Y Z is a fibration of n-types. Since Π_f(Z) ×_X Π_f(Z) is a homotopy Π-type of Z ×_Y Z along f, we can compute Π_f(P_Y(Z)) as in the proof of goodchoiceofpie, which, by induction hypothesis and the previous proposition, ensures that 

    Π_f(P_Y(Z))) →Π_f(Z) ×_X Π_f(Z)

will be a fibration of n-types. Since Π_f preserves equivalences, Π_f(P_Y(Z)) is a path object for Π_f(Z) in C(X) and therefore Π_f(Z) → X is a fibration of (n+1)-types, as desired.


ntruncation
The n-truncation of a fibration f: B → A is a factorisation of f as a map g: B → C followed by a fibration on n-types h: C → A, in such a way that if g': B → C' and h': C' → A is another such factorisation, then there exists a map d: C → C' over A with dh ≃_A g'; if, moreover, d': C → C' would be another such map then d ≃_A d'. 





 §.§ Small fibrations
 Let us suppose S is a subclass of the class of fibrations which is closed under composition, contains all isomorphisms and is stable under homotopy pullback. (Recall that a commutative square



D [r] [d, "g"']     B [d, "f"] 

C [r]     A 



in which both f and g are fibrations is a homotopy pullback if the induced map D → C ×_A B is an equivalence. By saying that S is stable under homotopy pullback, we mean that whenever there is such a square and f belongs to S, then g belongs to S as well.) Let us refer to the elements of S as the “small fibrations”.

representation Let S be a class of small fibrations, as above. A representation for such a class S is a small fibration π: E → U such that any other small fibration f: B → A can be obtained as a homotopy pullback of that one via some map A → U.

 
We will be especially interested in classes of small fibrations with a univalent representation. Note that for a univalent representation π: E → U the classifying map A → U is unique up to homotopy.

For obtaining models of CoC, we need to assume in addition that the class of small fibrations is impredicative.

impredicative
Let S be a class of small fibrations in a path category with homotopy Π-types. Then S is called impredicative (or polymorphic) if it is closed under Π_f for any fibration f.


Finally, we can also formulate Voevodsky's resizing axiom.

resizing A class of small fibrations S satisfies (propositional) resizing if every propositional fibration belongs to S.




§ THE PATH CATEGORY 𝔼𝔽𝔽


In this section we will see that Martin Hyland's effective topos <cit.> is the homotopy category of an interesting path category. This path category will be called 𝔼𝔽𝔽 and is constructed as follows.

Objects of the category 𝔼𝔽𝔽 consist of:


  * A set A.

  * A function α: A →ℕ (sending an element a ∈ A to its realizer).

  * For each pair of elements a,a' ∈ A a subset 𝒜(a,a') of ℕ.

  * A function which computes for a realizer of a ∈ A an element in 1_a ∈𝒜(a,a).

  * A function which given realizers for a,a' and π∈𝒜(a,a') computes an element π^-1∈𝒜(a', a).

  * A function which given realizers for a,a',a” and π∈𝒜(a,a'), π' ∈𝒜(a',a”) computes an element π' ∘π∈𝒜(a,a”).


Objects in this category will typically be denoted by (A, α, 𝒜), suppressing the data in  (4-6).

onobjinEFF1
Just to be clear, condition (4) has to be read in the following way: there is a partial computable function, which given any element a ∈ A computes an element in 𝒜(a,a) from the realizer of a.  Conditions (5) and (6) have to be read in the same way. In fact, from a certain point onwards we will simply state a condition like (4) as: an element in 𝒜(a,a) can be computed from a ∈ A, where it has to be understood that the partial computable function gets the realizer of a as input.


A morphism f: (B, β, ℬ) → (A, α, 𝒜) in 𝔼𝔽𝔽 consists of:


  * A function f: B → A such that the realizer of f(b) can be computed from a realizer of b.

  * For each b, b' ∈ B a function f_(b, b'): ℬ(b,b') →𝒜(fb, fb') such that f_(b,b')(π) can be computed from realizers for b,b' and π.

If f: (B, β, ℬ) → (A, α, 𝒜) is such a morphism, we will refer to Gödel numbers for the partial computable functions whose existence is demanded in (1) and (2) as trackings for the 0- and 1-cells, respectively. 

thinkingofEFF The right way to think about the objects and morphisms in 𝔼𝔽𝔽 is as locally codiscrete bigroupoids and (non-strict) homomorphisms between them, with elements in A as the 0-cells and the elements in 𝒜(a,a') as the 1-cells. The definitions do not mention 2-cells, but one should really think of any two elements in 𝒜(a,a') as being connected by a unique 2-cell. So one could add certain (weak) groupoid laws and demand that the morphisms preserve them, but with this intuition in mind it becomes clear that such conditions would be superfluous.


homotopyinEFF
Two parallel maps f, g: (B, β, ℬ) → (A, α, 𝒜) are homotopic if there is a function computing for every realizer for b ∈ B an element in 𝒜(fb,gb) (such a function is called a homotopy). A Gödel number for such a function will be called a coded homotopy. A map f: (B, β, ℬ) → (A, α, 𝒜) is a (homotopy) equivalence if there is a morphism g in the other direction (the homotopy inverse) such that both composites fg and gf are homotopic to the identity.


Note that the homotopy relation does not take into account the action of morphisms on 1-cells.

fibrinEFF
A map f:  (B, β, ℬ) → (A, α, 𝒜) in 𝔼𝔽𝔽 is a fibration if:


  * for any b, a and π: f(b) → a one can effectively find b', ρ: b → b' such that f(b') = a and f(ρ) = π (meaning: there are partial computable functions φ and ψ such that for any b, a and π: f(b) → a there are b', ρ: b → b' with f(b') = a and f(ρ) = π and with φ computing the realizer of b' from π and realizers for a and b and with ψ computing ρ from π and realizers for a and b).

  * for any b, b' ∈ B, ρ∈ℬ(b,b') and π∈𝒜(fb,fb') one can compute ρ' ∈ℬ(b,b') with f(ρ') = π.



secondcondition The second (somewhat remarkable) condition here is easy to miss, but with a bigroupoidal intuition it is clear that it should be there: it states a lifting condition for the invisible 2-cells.


EFFisapathcat
With the equivalences and fibrations as defined above, 𝔼𝔽𝔽 is a path category.

 We verify the axioms. It is easy to see that axioms 1 and 2 for a path category are satisfied, and because the  homotopy relation is a congruence,  axiom 4 follows as well.

Let us first construct pullbacks of fibrations. If f: (B, β, ℬ) → (A, α, 𝒜) is a fibration and g: (C, γ, 𝒞) → (A, α, 𝒜) is any map, then its pullback is:

    D     =    {  (c,b)   :   g(c) = f(b)  }
    δ(c,b)     =     (γ(c), β(b)) 
    𝒟((c,b),(c',b'))     =    { (π∈𝒞(c,c'), ρ∈ℬ(b,b'))   :   g(π) = f(ρ)  }

Note that one has to use the second condition in the definition of a fibration to define the bigroupoid structure on (D, δ, 𝒟): for instance, if d = (c,b) ∈ D, then there are 1-cells 1_b ∈ℬ(b,b) and 1_c ∈𝒞(c,c). We have g(1_c) ∈𝒜(fb,fb), so by the second condition there is a 1-cell π∈ℬ(b,b) with f(π) = g(1_c) and hence 1_d := (1_c,π) ∈𝒟(d,d). For the inverses and composition there are similar arguments. In addition, the obvious projection (D, δ, 𝒟) → (C, γ, 𝒞) is again a fibration (this takes care of axiom 3).

Let us now construct path objects (axiom 5). If (A, α, 𝒜) is any object, then its path object (P, π, 𝒫) is:

    P     =    {  (a,a', ρ)   :   a,a' ∈ A, ρ∈𝒜(a,a')  }
    π(a,a',ρ)     =     ( α(a), α(a'), ρ ) 
    𝒫((a,a',ρ),(b,b',σ))     =    {⟨ m, n ⟩  :   m ∈𝒜(a,a'), n ∈𝒜(b,b') }

Note that the notion of homotopy determined by these path objects is precisely the homotopy relation we defined earlier.

Finally, we make the following claim: a fibration f: (B, β, ℬ) → (A, α, 𝒜) is trivial precisely when it has a section s such that sf is homotopic to the identity. Then it is easy to see that trivial fibrations have sections and are stable under pullback (axioms 6 and 7). So suppose that g: A → B is a morphism such that H: fg ≃ 1. Then for every a ∈ A there is a morphism H_a: fga → a, and the first property of a fibration allows us to find an element sa ∈ B and a morphism K_a: ga → sa such that f(K_a) = H_a. If π: a → a' is a 1-cell in A, then we can use the fact that g is a morphism to find a 1-cell sa → sa'. Using the second condition for a fibration we can choose s(π): sa → sa' such that fs(π) = π. This constructs a section s of f, which is homotopic to g. This shows that the claim about trivial fibrations is correct.


hoisEff  The homotopy category of 𝔼𝔽𝔽 is equivalent to the effective topos.


We will assume familiarity with the effective topos  (see, for instance, <cit.>). Consider the functor 
    P: 𝔼𝔽𝔽→

sending (A, α, 𝒜) to (A, =_A) with

    a =_A a' = { <n,π,n'>   :   n = α(a), n' = α(a'), π∈𝒜(a,a') }

and f: (B, β, ℬ) → (A, α, 𝒜) to F: A × B → Pow(ℕ) with

    F(b,a) = { <m, π, n>   :   m = β(b), n = α(a), π∈𝒜(fb,a). }

This functor P is full and for two parallel arrows f, g in 𝔼𝔽𝔽 we have Pf = Pg precisely when f and g are homotopic. So it remains to verify that P is essentially surjective.

So let (X, =_X) be an object in the effective topos. If (A, α, 𝒜) is the object in 𝔼𝔽𝔽 with

    A     =    { <x,n>   :   x ∈ X, n ∈ x =_X x }
    α(<x,n>)     =     n 
    𝒜(<x,n>,<x',n'>)     =     x =_X x'

then P(A, α, 𝒜) ≅ (X, =_X) in .


onchoiceandEFF In a metatheory without the axiom of choice, the effective topos can be defined in different ways. To prove that the functor P from the previous proof is full, we need a version where functionality of a morphism F: (B, =_B) → (A, =_A) in  means that we have a function f picking for every b ∈ B and n ∈ b=_B b an element a = f(b, n) ∈ A such that from n one can compute an element in F(b,a).


onrosolini The contents from this section are very close to an earlier argument by Rosolini in <cit.>, where he also constructs the effective topos as a homotopy quotient. The main difference is that here we obtain the effective topos as the homotopy category of a path category, which also involves finding a suitable class of fibrations; in addition, we think of the objects in the path category as degenerate bigroupoids, rather than as 2-groupoids.


alsofromearlierpaper
It also follows from <cit.> that the effective topos arises as a homotopy category: since the effective topos is the exact completion of the category of partitioned assemblies (see <cit.>), the effective topos is the homotopy category of Ex( PAsm), where Ex is the homotopy exact completion from <cit.> and PAsm is the category of partitioned assemblies regarded as a path category by declaring every map to be a fibration and the isomorphisms to be the equivalences. The construction in this section is similar, but different: indeed, in Ex( PAsm) not every fibration would be a fibration of sets, as happens for 𝔼𝔽𝔽 (see inEFFeverythingset below).




§ FUNCTION SPACES IN 𝔼𝔽𝔽


The purpose of this section is to show that 𝔼𝔽𝔽 has homotopy Π-types. We will only give the constructions here, as the verifications are both straightforward and tedious.

EFFhasexp
The path category 𝔼𝔽𝔽 has homotopy exponentials.


If B = (B, β, ℬ) and A = (A, α, 𝒜) are two objects in 𝔼𝔽𝔽, then the homotopy exponential A^B can be constructed as follows:


  * The elements of the underlying set are triples consisting of a morphism f: B → A and trackings for both its 0- and 1-cells.

  * Realized by a code for the pair consisting of the tracking for the 0- and 1-cells.

  * And the 1-cells between f and g are coded homotopies between f and g.

This completes the construction.


onhexpinEFF The construction in the previous proposition does not yield a genuine exponential in 𝔼𝔽𝔽, for more than one reason. First of all, there is some arbitrariness in how the evaluation morphism A^B × B → A is defined on 1-cells. In addition, since trackings are not unique, there is no canonical choice for the exponential transpose.


EFFhasPi
The path category 𝔼𝔽𝔽 has homotopy Π-types.


If (A, α, 𝒜) is an object in 𝔼𝔽𝔽 and a ∈ A, then this induces an arrow a: 1 → A sending the unique 0-cell in 1 to a and the unique 1-cell in 1 to 1_a. In addition, if π∈𝒜(a,a'), then this induces a homotopy between the parallel arrows a, a': 1 → A, which we will also denote by π. So it follows from transportisanequivalence that if f: (B, β, ℬ) → (A, α, 𝒜) is a fibration and π∈𝒜(a,a'), then π induces an equivalence Γ^B_π: B_a → B_a', where B_a and B_a' are the pullbacks of f along a: 1 → A and a': 1 → A, respectively.

If g: (C, γ, 𝒞) → (B, β, ℬ) is another fibration, then the fibration

    Π_f(g): (D, δ, 𝒟) → (A, α, 𝒜)

is constructed as follows. We define (D, δ, 𝒟) by:


  * Elements of D consist of an element a ∈ A, a section s: B_a → C of g and trackings for the 0- and 1-cells of s.

  * A realizer of such an element is a coded triple consisting of the realizer of a ∈ A and the trackings for the 0- and 1-cells of s.

  * A 1-cell between (a, s) and (a', s') consists of a code for a pair containing an element π: a → a' and a coded homotopy between s' ∘Γ^B_π and Γ^C_π∘ s.

In addition, the map Π_f(g) is obtained by projecting on a and π. Lengthy verifications are now in order.




§ DISCRETE FIBRATIONS IN 𝔼𝔽𝔽


Within the path category 𝔼𝔽𝔽 one can define an impredicative class of small fibrations given by the discrete fibrations.

discretefibrationsinEFF A fibration f: (B, β, ℬ) → (A, α, 𝒜) is a standard discrete fibration if for elements b, b' ∈ B we have:

if f(b) = f(b') and β(b) = β(b'), then b = b'.

A fibration f is discrete if f can be written as gw with w being an equivalence and g a standard discrete fibration.


onalternativedeffordiscrfibr
We could also have said that a fibration f is discrete if there a standard discrete fibration g and an equivalence w such that f ≃ gw, or fw ≃ g, or fw = g. By arguments as in hlevelsstableunderpbk one can show that all these definitions are equivalent.



discrfibrimprclassofsmallmaps The discrete fibrations form an impredicative class of small fibrations in that:


  * every isomorphism is a discrete fibration, 

  * discrete fibrations are stable under homotopy pullback,

  * discrete fibrations are closed under composition, and

  * discrete fibrations are closed under Π_f with f a (not necessarily discrete) fibration.



It is easy to see that every isomorphism is a standard discrete fibration, that standard discrete fibrations are stable under pullback, closed under composition and that Π_f(g) as constructed in EFFhasPi is a standard discrete fibration whenever f and g are fibrations and g is standard discrete. From this the statement follows.


otherdiscretethings


  * It also follows from the construction of path objects in 𝔼𝔽𝔽 as in EFFisapathcat that (s, t): PX → X × X is discrete for any object X. (In fact, we have that P_I(X) → X ×_I X is discrete for any fibration X → I.)

  * One also easily verifies that 𝔼𝔽𝔽 has homotopy sums (as in <cit.>) and that for any two discrete fibrations f: B → A and g: D → C, the map f + g: B + D → A + C is again discrete, and that for any two discrete fibrations f: B → A and g: C → A the map [f,g]: B + C → A is again discrete.

  * We can call an object A discrete if the map A → 1 is a discrete fibration. So, basically, an object (A, α, 𝒜) is discrete if α is injective, or if it is homotopic to such an object (see also the definition of the category 𝔻𝕀𝕊ℂ in Section 11 below). Examples of such discrete objects are the terminal object, its finite coproducts (0,1,2), as well as the homotopy natural numbers object (N, ν, 𝒩) with:

    N     =    ℕ
    ν(n)     =    { n }
    𝒩(n,n)     =    { 0 }
    𝒩(n, m)     =    ∅ n ≠ m.




According to <cit.>, Peter Freyd suggested defining discrete maps in  by an internal orthogonality condition. It turns out that the same is possible in 𝔼𝔽𝔽. First of all, let 𝕁 = (J, j, 𝒥) be the object in 𝔼𝔽𝔽 with

    J     =    { 0, 1 }
    
    j(i)     =     0 
    𝒥(i,i)     =    { 0 }
    𝒥(i, k)     =    ∅ i ≠ k.

If (A, α, 𝒜) is any object in 𝔼𝔽𝔽, then the homotopy exponential A^𝕁 can be computed as follows:

 
  * The underlying set of A^𝕁 consists of pairs of elements (a_0,a_1) in A with α(a_0) = α(a_1).
 
  * The realizer of such a pair (a_0,a_1) is α(a_0) = α(a_1).
 
  * The set 𝒜((a_0,a_1),(b_0,b_1)) is the intersection of 𝒜(a_0,b_0) and 𝒜(a_1,b_1).

Moreover, there is an obvious diagonal map A →𝒜^𝕁 which copies the 0- and 1-cells. If f: B → A is any map, then this induces a (strictly) commuting square



B [r] [d, "f"']     B^𝕁 [d, "f^𝕁"] 

A [r]     A^𝕁, 



and if f is a fibration, then so is f^𝕁.

discretealafreydinEFF (ZFC) The following are equivalent for a fibration f: B → A:

 
  * f is discrete.
 
  * The square above is a homotopy pullback.
 
  * There is a computable function which given two elements b_0,b_1 ∈ B with f(b_0) = f(b_1) and n = β(b_0) = β(b_1) computes an element in ℬ(b_0,b_1) from n.



(1) ⇒ (2): If f is a standard discrete fibration, then the square above is actually a genuine pullback. Since the statement in (2) is homotopy invariant, the implication follows.

(2) ⇒ (3): The statement in (2) means that the diagonal map

    d: B →{ (b_0,b_1)   :   f(b_0) = f(b_1), β(b_0) = β(b_1) }

is an equivalence. Since we have π d = 1 where π is the projection on the first coordinate, d is an equivalence precisely when d π≃ 1. Unwinding this gives the statement in (3).

(3) ⇒ (1): Consider the equivalence relation ∼ on B defined by

    b_0 ∼ b_1  f(b_0) = f(b_1) β(b_0) = β(b_1),

and choose B' to be a subset of B which contains precisely one element from each equivalence class. The inclusion of B' in B determines a map (B',β,ℬ) → (B, β, ℬ) with β and ℬ on B' just being the restrictions to B'. The statement in (3) implies that this map is an equivalence, while its composition with f is a standard discrete fibration by construction.


notinterval Superficially, 𝕁 may look a bit like an interval, but it is really rather different from the object which should be considered as the interval object in 𝔼𝔽𝔽, which is 𝕀 = (I, ι, ℐ) with

    I     =    { 0, 1 }
    ι(i)     =     i 
    ℐ(i,j)     =    { 0 }.

Indeed, for this object we have that 𝕀→ 1 is a trivial fibration and that PX ≃ X^𝕀, while 𝕁→ 1 is far from a trivial fibration and we have X ≃ PX ≃ X^𝕁 only if X is discrete. Since 𝕁 is a version of ∇(2), this also shows that our work here is rather different in spirit from that in <cit.> and <cit.>. Another difference is that these papers seek to define homotopy-theoretic structures on the effective topos and do not regard it as a homotopy-theoretic quotient of some other category.




§ PROPOSITIONS IN 𝔼𝔽𝔽


It is not clear to me if the class of discrete fibrations has a representation: indeed, this is the same problem as the one whether the class of discrete maps (defined locally) has a representation in , which is still open. It will be possible to show, using a standard argument, that no representation of the class of discrete fibrations in 𝔼𝔽𝔽 can be univalent  (see nounivreprfordiscrfibr below). 

But first we will show that one can obtain a univalent representation if we restrict to the discrete propositional fibrations. As a first step in this direction, we will explicitly construct propositional truncations in 𝔼𝔽𝔽.

existofproptrinEFF
(Existence of propositional truncation) Every fibration f: B → A factors as a map g: B → C followed by a fibration of propositions h: C → A, in a “universal” way: if g': B → C' and h': C' → A is another such factorisation, there is a map d: C → C' over A with dg ≃_A g', with the map d itself being unique up to fibrewise homotopy over A with this property.


Let me just give the construction: if f: (B, β, ℬ) → (A, α, 𝒜) is a fibration, then we define C := (B, β, 𝒞) with 𝒞(b,b') = 𝒜(fb,fb'). It is now easy to see that C → C ×_A C is an equivalence, turning C → A into a propositional fibration; the remaining verifications are also easy and left to the reader. 


Note that this means that, up to equivalence, any propositional fibration 
    f: (B, β, ℬ) → (A, α, 𝒜)
 can be assumed to satisfy ℬ(b,b') = 𝒜(fb,fb'); if f is also discrete, we may even assume that B ⊆ A ×ℕ with f being the projection on the first and β the projection on the second coordinate (the reason for this is that propositional truncation as in the proof of the previous proposition preserves standard discrete fibrations). This is quite helpful when trying to prove:

discrpropsclassified
The class of discrete propositional fibrations in 𝔼𝔽𝔽 is an impredicative class of small fibrations with a univalent representation.


It follows from hlevelsandPi and discrfibrimprclassofsmallmaps that the discrete propositional fibrations form an impredicative class of small fibrations, so it remains to construct a univalent representation π: E → U. We do this as follows:


  * U consists of subsets X of ℕ

  * any such X is realized by 0, 

  * a 1-cell between X and Y in U consists of realizers r: X → Y and s: Y → X (that is, r is a Gödel number of a partial recursive function which is defined on every element in X and which on these elements in X outputs an element in Y; similarly for s),

while:


  * E consists of pairs (X,x) with X a subset of ℕ and x ∈ X,

  * the pair (X,x) is realized by x,

  * a 1-cell between (X,x) and (Y,y) is the same as a 1-cell between X and Y.

This is clearly a discrete propositional fibration, and to see that it is a univalent representation, consider a map f: (B, β, ℬ) → (A, α, 𝒜) and assume that ℬ(b,b') = 𝒜(fb,fb') and B ⊆ A ×ℕ with f being the projection on the first and β the projection on the second coordinate. This gives rise to map k: A → U which is obtained by sending a ∈ A to B_a = { n ∈ℕ  :   (a,n) ∈ B } and by sending π∈𝒜(a,a') to a tracking of the equivalence Γ^B_π: B_a → B_a'. The remaining verifications are left to the reader.



inEFFeverythingset
In 𝔼𝔽𝔽 every fibration is a fibration of sets.


If f: (B, β, ℬ) → (A, α, 𝒜) is a fibration, then we can factor B → B ×_A B as an equivalence B → P followed by a fibration P → B ×_A B with P = (P, π, 𝒫) given by:

    P     =    { (b ∈ B, b' ∈ B, π∈ℬ(b,b')   :   f(b) = f(b') }
    π(b,b',π)     =    ⟨β(b),β(b'),π⟩
    𝒫((b_0,b'_0,π_0), (b_1,b'_1,π_1))     =    {⟨ n, n' ⟩  :   n ∈ℬ(b_0,b_1), n' ∈ℬ(b_0',b_1') }

Since P → B ×_A B is a propositional fibration, f is a fibration of sets.


nounivreprfordiscrfibr
The class of discrete fibrations in 𝔼𝔽𝔽 does not have a univalent representation.

 If a class of small fibrations has a univalent representation π: E → U with U a set, then every small object A has, up to homotopy, precisely one self-equivalence. Indeed, an object with more than one self-equivalence would give rise to a map 1 → U which is homotopic to itself in more than one way, which is impossible if U is a set. 

So because 2 is a discrete object which is equivalent to itself in two different ways, the class of discrete fibrations cannot have a univalent representation in 𝔼𝔽𝔽. (This is, in fact, a well-known argument: see <cit.>.)


Finally, let us point out that, assuming the axiom of choice in the metatheory, we can prove that the discrete (propositional) fibrations satisfy resizing.

resizinginEFF
(ZFC) In 𝔼𝔽𝔽 propositional fibrations are discrete. Therefore the the discrete (propositional) fibrations in 𝔼𝔽𝔽 are a class of small fibrations satisfying resizing.


Suppose f: (B, β, ℬ) → (A, α, 𝒜) is propositional, and let 
    C = { (a, n) : (∃ b)   f(b) = a, β(b) = n },
 with γ(a, n) = n and 𝒞((a,n),(a', n')) = 𝒜(a, a'). Clearly, the projection π: C → A is a discrete propositional fibration. There is an obvious morphism B → C over A, and, using AC, there is also a morphism C → B over A. Since f and π are propositional, the maps going back and forth between B and C are each other's homotopy inverses, so f is discrete as well.




§ A REMARK ON CHURCH'S THESIS IN 𝔼𝔽𝔽


A classical result in the metamathematics of constructivism says that extensional Heyting arithmetic in finite types with the axiom of choice for finite types proves the negation of Church's Thesis (saying that any function f: ℕ→ℕ is computable) (see, for instance, <cit.>). This means in particular that if we work in Martin-Löf Type Theory with function extensionality, then this theory will refute Church's Thesis in the following form:

    Π f: ℕ→ℕ. Σ n ∈ℕ. .

However, if we use propositional truncation ‖…‖ to turn the Σ into ∃ (to use the terminology from Homotopy Type Theory) and we read Church's Thesis as:

    Π f: ℕ→ℕ. ‖Σ n ∈ℕ. ‖,

then this statement holds in 𝔼𝔽𝔽. One way of seeing this starts by observing that if P is the functor from the proof of hoisEff and f: B → A is a fibration in 𝔼𝔽𝔽, then Pf is a monomorphism precisely when f is propositional (this should be clear from the description of the functor P, the discussion on page 67 of <cit.> and existofproptrinEFF). Therefore for any object A in 𝔼𝔽𝔽, the functor P sets up an order isomorphism between the subobject lattice on PA in  and the poset reflection of the full subcategory of the slice category 𝔼𝔽𝔽/A on the propositional fibrations. This means that what holds in the logic of 𝔼𝔽𝔽, when we interpret statements using propositions in the sense of Homotopy Type Theory (as explained in Sections 3.6 and 3.7 in <cit.>), is precisely what holds in the internal logic of . Since Church's Thesis holds there, the same is true for 𝔼𝔽𝔽. (See also <cit.>, especially Section 1.3.)



§ THE PATH CATEGORY 𝔼𝔽𝔽_1


A univalent universe containing sets like 2, ℕ and ℕ→ℕ must have an hlevel at least one: that is, it must at least be a groupoid. This means that if we want a category like 𝔼𝔽𝔽 in which there is a univalent representation classifying discrete sets, we have to consider objects with an additional level of complexity. Indeed, for the next step we need to consider tricategories which are locally codiscrete in the sense that any two parallel 2-cells are connected by a unique 3-cell. This sounds quite complicated, but it is not too bad: we have seen that locally codiscrete bigroupoids are in a sense easier than groupoids, and in the same way locally codiscrete tricategories are simpler objects than bicategories.

We define the following category 𝔼𝔽𝔽_1:


  * Objects consist of:


  * A set A.

  * A function α: A →ℕ.

  * For each pair of elements a, a' ∈ A a set of natural numbers (1-cells) 𝒜(a,a').  Instead of π∈𝒜(a,a') we will often write π: a → a'.

  * For each pair of elements π, π' ∈𝒜(a,a') a set of natural numbers (2-cells) 𝒜(π,π'). Instead of n ∈𝒜(π,π') we will often write n: π⇒π'. 

  * An effective function picking for each a ∈ A an element 1_a ∈𝒜(a,a).

  * An effective function picking for each a, a' ∈ A and π∈𝒜(a,a') an element π^-1∈𝒜(a',a).

  * An effective function picking for each a,a',a”∈ A and π∈𝒜(a,a') and ρ∈𝒜(a',a”) an element ρ∘π∈𝒜(a,a”).

  * Together with 2-cells 1_b ∘π⇒π and  π∘ 1_a ⇒π (which can be computed from a,b,π).

  * Together with 2-cells  π^-1∘π⇒ 1 and π∘π^-1⇒ 1 (which can be computed from the same data).

  * Together with 2-cells (σ∘ρ) ∘π⇒σ∘ (ρ∘π) (which can be computed from π,ρ,σ and realizers for the domains and codomains).

  * For each π∈𝒜(a,a') a 2-cell 1_π∈𝒜(π,π) (which can be computed from π and realizers for a and a').

  * For each pair of 2-cells n ∈𝒜(π,ρ) and m ∈𝒜(ρ,σ) a 2-cell m ∘_1 n ∈𝒜(π,σ) (which can be computed from n, m, π, ρ, σ and their domains and codomains).

  * For each 2-cell n ∈𝒜(π,ρ) a 2-cell n^-1∈𝒜(ρ,π) (which can again be computed from the relevant data).

  * For each pair of 2-cells n ∈𝒜(π,ρ) and m ∈𝒜(π',ρ') a 2-cell m ∘_0 n ∈𝒜(π' ∘π,ρ' ∘ρ) (which can also be computed from the relevant data).


  * Morphisms f: B → A consist of: 


  * A function f: B → A.

  * For each b_1,b_2 ∈ B a function f_b_1,b_2: ℬ(b_1,b_2) →𝒜(fb_1,fb_2), as well as

  * For each b_1,b_2 ∈ B and π,ρ∈ℬ(b_1,b_2) a function f_π,ρ:ℬ(π,ρ) →𝒜(fπ,fρ),

such that:


  * A realizer for f(b) can be computed from a realizer for b.

  * f_b_1,b_2(π) can be computed from realizers for b_1,b_2 and π.

  * f_π,ρ(n) can be computed from n, π and ρ and realizers for the domain and codomain of both π and ρ.

  * An element in 𝒜(f(1_b),1_fb) can be computed from a realizer for b.

  * An element in 𝒜(f(ρ∘π),fρ∘ fπ) can be computed from realizers for ρ,π and domains and codomains for ρ and π.



lasttwoconditons
It may look odd to not make the last two items (the “proof terms for functoriality”) part of the identity of a morphism. However, since we lack unit and associativity laws for 2-cells in the definition of an object in 𝔼𝔽𝔽_1 adding such would no longer result in a category.


I will continue to denote objects by (A, α, 𝒜).

fibrationinEFF1
A morphism f: (B, β, ℬ) → (A, α, 𝒜) in 𝔼𝔽𝔽_1 is called a fibration if


  * for every b ∈ B, a ∈ A and π∈𝒜(fb, a) one can effectively find elements b' ∈ B with f(b') = a and π' ∈ℬ(b, b') with f(π') = π.

  * for any π, π' ∈𝒜(fb,fb'), n ∈𝒜(π,π') and ρ∈ℬ(b,b') such that f(ρ) = π, one can compute ρ' ∈ℬ(b,b') and m ∈ℬ(ρ,ρ') with f(ρ') = π' and f(m) = n.

  * given a 2-cell m ∈ℬ(π,π') and a 2-cell n ∈𝒜(fπ,fπ') one can compute a 2-cell m' ∈ℬ(π,π') with f(m') = n.   



easyfibr
Isomorphisms are fibrations, fibrations are closed under composition and the unique map to the terminal object is always a fibration.


onpbks
Fibrations are stable under pullback.


Let f: B → A be a fibration and g: C → A be arbitrary. The pullback is computed as follows:


  * The underlying set is D := C ×_A B.

  * A realizer of (c, b) is the pair consisting of γ(c) and β(b).

  * 1-cells (c,b) → (c',b') are pairs of 1-cells π: c → c' and ρ: b → b' with g(π) = f(ρ).

  * 2-cells (π,ρ) ⇒ (π',ρ') are pairs of 2-cells n: π⇒π' and m: ρ⇒ρ' with g(n) = f(m).

The main difficulty here is not to show the universal property, but to prove that it is an object of 𝔼𝔽𝔽_1. As in EFFisapathcat, one defines identities or composition on the C-component of D just as in C, whereas for the B-component of D one uses the fact that f is a fibration to choose something in B which is both homotopic to the identity or composition of B and which has the same A-image as the object chosen in the C-component.


homotopyinEFF1
A homotopy between two morphisms f, g: (B, β, ℬ) → (A, α, 𝒜) in 𝔼𝔽𝔽_1 consists of:


  * a function H_1 picking for every b ∈ B an element in H_1(b) ∈𝒜(fb, gb).

  * a function H_2 picking for each π∈ℬ(b,b') a filler H_2(π) for the square



 fb [r, "f(π)"] [d, "H_1(b)"']     fb' [d, "H_1(b')"] 

gb [r, "g(π)"']     gb' 




such that:


  – H_1(b) can be computed from b.

  – H_2(π) can be computed from b,b' and π.

If H is such a homotopy, I will write H: f ≃ g. If such a homotopy H exists, I will call f and g homotopic and write f ≃ g. A coded homotopy is a pair consisting of Gödel numbers for the trackings of H_1 and H_2. If a map has a homotopy inverse, it will be called a (homotopy) equivalence.


Note that the homotopy relation does not take into account the action of morphisms on 2-cells.

2outof6
The homotopy relation is a congruence and hence isomorphisms are equivalences and equivalences satisfy 6-for-2.


pathobjects Every diagonal A → A × A factors as an equivalence followed by a fibration.


The path object on A = (A, α, 𝒜) is the object PA = (P, π, 𝒫), where:


  * P consists of triples (a, b, ρ) with a, b ∈ A and ρ∈𝒜(a,b),

  * π(a, b, ρ) is a triple consisting of the realizers of a and b, as well as the natural number ρ, and

  * 𝒫((a,b, ρ), (a',b',ρ')) consists of pairs of maps μ: a → a' and ν: b → b', together with a natural number n: νρ⇒ρ'μ. 

  * 2-cells between parallel (μ,ν,n) and (μ',ν',n') consist of pairs of 2-cells μ⇒μ' and ν⇒ν'.

In addition, there is an obvious factorisation of the diagonal 



A [r, "r"]     PA [r,"(s,t)"]     A ×A,



in which the first map is an equivalence and the second a fibration.


If H, K: f ≃ g are homotopies between f, g: B → A, let us write M: H ∼ K for a function M which computes for each b ∈ B a 2-cell in A between H_b: fb → gb and K_b: fb → gb.

The following proposition is a variation on a standard result from homotopy theory and higher category theory (see <cit.>).

adjequiv
Suppose f: A → B and g: B → A are morphisms with homotopies η: 1 ≃ gf and ε: fg ≃ 1. Then we can modify η to a homotopy η': 1 ≃ gf for which there are

    M: ε_f ∘ fη' ∼ 1_f  N: gε∘η'_g ∼ 1_g.

(A similar statement holds for ε.)


Let us first observe that if k: A → A is an endomorphism and H: 1 ≃ k is a homotopy, then there are two homotopies k ≃ kk, to wit H_k and kH. There is however a homotopy M: H_k ∼ kH between those. The reason is that
 a [r]^H_a [d]_H_a     ka [d]^H_ka 

ka [r]_k(H_a)     kka 
is a naturality square and H_a is an isomorphism.

So let us define

    η'_a := η^-1_gfa∘ g(ε_fa^-1) ∘η_a.

Since ε_f: fgf ≃ f is a natural transformation and η_a: a → gfa is a morphism, we have that
 fgfa [d]_ε_fa [r]^fgf(η_a)     fgfgfa [d]^ε_fgfa 

fa [r]_fη_a     fgfa 
commutes up to some 2-cell. Since we also have 2-cells fgfη_a ⇒ f(η_gfa) and ε_fgfa⇒ fg(ε_fa) by the previous observation, we find M: ε_f ∘ f(η') ∼ 1_f.

Dually, we have the natural transformation η_g: g ≃ gfg and the 1-cell ε_b: fgb → b leading to a 2-cell filling:
 gfgb [r]^η_gfgb [d]_gε_b     gfgfgb [d]^gfgε_b 

gb [r]_η_gb     gfgb. 
Since there is a 2-cell gfgε_b ⇒ g(ε_fgb), we also obtain N_b: gε_b ∘η'_gb∼ 1_gb.


ontrivfibr
A fibration f: B → A is trivial if and only if f has a section s: A → B for which there are H: 1_B ≃ sf and M: fH ∼ 1_f.


If such s, H, M exist, f is an equivalence, so it suffices to prove the other direction.

So assume f: B → A is a fibration which is also an equivalence. This means there are maps g: A → B and homotopies ε: fg ≃ 1 and η: 1 ≃ gf. By adjequiv we may assume that there is some N: ε_f ∘ f(η) ∼ 1_f.

Let  a ∈ A be arbitrary. Since ε_a: fga ≃ a and f is a fibration, we can effectively find an element sa ∈ B and a 1-cell τ_a: ga → sa such that f(τ_a) = ε_a. In addition, if π: a → a', then for ρ' := τ_a'∘ g(π) ∘τ_a^-1: sa → sa', we can compute a 2-cell n: f(ρ') ≃π, so we can determine an element s(π): sa → sa' such that fs(π) = π and a 2-cell:

    τ_π: s(π) ∘τ_a ⇒τ_a'∘ g(π).

Finally, if n: π⇒π' in A, then g yields a 2-cell m': s(π) ⇒ s(π') whose f-image is parallel to n. So we find an element s(n): s(π) ⇒ s(π') with f(s(n)) = n.

From this it follows that s is a morphism and τ is a homotopy between g and s. By construction, s is a section of f. Finally, if H = τ_f ∘η, then fH ∼ f(τ_f) ∘ f(η) = ε_f ∘ f(η) ∼ 1_f, as desired.


trivstableunderpbk
Trivial fibrations have sections and are stable under pullback along arbitrary maps.


We have shown:

EFF1pathcategory
With the equivalences and fibrations as defined above, the category 𝔼𝔽𝔽_1 carries the structure of a path category.


rosoliniagain The category 𝔼𝔽𝔽_1 is similar to one considered by Pino Rosolini in a talk at the Wessex Theory Seminar in 2010; however, his category is actually a 2-category, not a path category, and also his goals were different.




§ FUNCTION SPACES AND FUNCTION EXTENSIONALITY IN 𝔼𝔽𝔽_1


We now show that 𝔼𝔽𝔽_1 is a path category with homotopy Π-types. We will just outline the constructions and omit the lengthy verifications.

hexpinEFF1
The path category 𝔼𝔽𝔽_1 has homotopy exponentials.


If B = (B, β, ℬ) and A = (A, α, 𝒜) are two objects, then we define the homotopy exponential A^B to be the following:


  * At the set level it consists of all homomorphism f: B → A including all the trackings for 0,1 and 2-cells.

  * A realizer for f consists of trackings for its 0,1 and 2-cells (but there is no reason to include the proof terms for functoriality).

  * 1-cells between f and g are coded homotopies H: f ≃ g.

  * 2-cells between H and K are coded homotopies M: H ∼ K.

Checking that this works is a lengthy but routine exercise.


functionspacesinEFF1
The path category 𝔼𝔽𝔽_1 has homotopy Π-types.

 If (A, α, 𝒜) is an object in 𝔼𝔽𝔽_1 and a ∈ A, then there is a morphism 1 → (A, α, 𝒜), which we also call a, sending the unique 0-cell in 1 to a and the higher cells in 1 to the identity arrows on a and 1_a. If f: (B, β, ℬ) → (A, α, 𝒜) is a fibration, then we will write B_a for the object in 𝔼𝔽𝔽_1 obtained by pulling back f along a: 1 → A. Moreover, if π: a → a' is any 1-cell in A, then this induces a homotopy between a,a': 1 → A, which we will also call π. By transportisanequivalence this induces a homotopy equivalence Γ^B_π: B_a → B_a'. In addition, if n: π⇒π' is any 2-cell in A, this induces a fibrewise homotopy Γ_n between Γ_π and Γ_π' (see basicpropoftransport.(2)).

If g: (C, γ, 𝒞) → (B, β, ℬ) is another fibration, we define Π_f(g) to be the obvious projection to A from the following object:


  * The set consists of elements a ∈ A together with sections s: B_a → C of g with the required tracking data for 0,1,2-cells.

  * A realizer for such an element consists of a realizer for a ∈ A together with the tracking data for the 0,1,2-cells.

  * 1-cells between (a, s) and (a',s') consist of a 1-cell π: a → a' as well as a coded fibrewise homotopy H: Γ_π^C ∘ s ≃ s' ∘Γ^B_π: B_a → C.

  * 2-cells between those consist of a 2-cell n: π→π' in A together with a coded homotopy M: (s' ∘Γ_n^B) ∘ H ∼ H' ∘ (Γ^C_n ∘ s) between the homotopies Γ_π^C ∘ s ≃ s' ∘Γ_π'^B.

Some very lengthy verifications are now in order.





§ DISCRETE FIBRATIONS IN 𝔼𝔽𝔽_1


Within the path category 𝔼𝔽𝔽_1 we can again isolate an impredicative class of small fibrations given by the discrete fibrations.

discretefibrationsinEFF1 A fibration f: (B, β, ℬ) → (A, α, 𝒜) is a standard discrete fibration if for elements b, b' ∈ B we have:

if f(b) = f(b') and β(b) = β(b'), then b = b'.

A fibration f is discrete if f can be written as gw with w being an equivalence and g a standard discrete fibration.


By the same argument as before, we obtain:

discrfibrimprclassofsmallmapsagain The discrete fibrations form an impredicative class of small fibrations in that:


  * every isomorphism is a discrete fibration, 

  * discrete fibrations are stable under homotopy pullback,

  * discrete fibrations are closed under composition, and

  * discrete fibrations are closed under Π_f with f a (not necessarily discrete) fibration.



Also, it is possible to again characterise discrete fibrations by an orthogonality condition, in the following sense. Let 𝕁 be the object in 𝔼𝔽𝔽_1 with two 0-cells both having realizer 0 and only identity 1- and 2-cells, also given by the natural number 0. If f: B → A is a fibration, then the natural way of computing the homotopy exponential A^𝕁 gives rise to a (strictly) commuting square



B [r] [d, "f"']     B^𝕁 [d, "f^𝕁"] 

A [r]     A^𝕁, 



in which the horizontal arrows are the diagonals map and f^𝕁 is also a fibration.

discretealafreydinEFF1 (ZFC) The following are equivalent for a fibration f: B → A:

 
  * f is discrete.
 
  * The square above is a homotopy pullback.
 
  * There are computable functions φ and ψ such that for any two elements b_0,b_1 ∈ B with a = f(b_0) = f(b_1) and n = β(b_0) = β(b_1) the element φ(n) belongs to ℬ(b_0,b_1) and f(φ(n)) = 1_a, and such that for elements b_0,b_1,c_0,c_1 ∈ B with f(b_0) = f(b_1), f(c_0)=f(c_1), n = β(b_0) = β(b_1), m = β(c_0) = β(c_1) and π∈ℬ(b_0,c_0) ∩ℬ(b_1,c_1) we have that ψ(n,m,π) is a 2-cell filling



b_0 [r, "π"] [d, "φ(n)"']     c_0 [d, "φ(m)"] 

b_1 [r, "π"']     c_1. 









§ PROPOSITIONS IN 𝔼𝔽𝔽_1


existofproptrinEFF1
(Existence of propositional truncation) Every fibration f: B → A factors as a map g: B → C followed by a fibration of propositions h: C → A, in a “universal” way: if g': B → C' and h': C' → A is another such factorisation, there is a map d: C → C' over A with dg ≃_A g', with the map d itself being unique up to fibrewise homotopy over A with this property.


Let me just give the construction: if f: (B, β, ℬ) → (A, α, 𝒜) is a fibration, then we define C := (B, β, 𝒞) with 𝒞(b,b') = 𝒜(fb,fb') and 𝒞(π,π')=𝒜(fπ,fπ'). 


Note that this means that, up to equivalence, any propositional fibration 
    f: (B, β, ℬ) → (A, α, 𝒜)
 can be assumed to satisfy ℬ(b,b') = 𝒜(fb,fb') and ℬ(π,π') = 𝒜(fπ, fπ'); if f is also discrete, we may also assume that B ⊆ A ×ℕ with f being the projection on the first and β the projection on the second coordinate. 

discrpropsclassified
In 𝔼𝔽𝔽_1 the class of discrete propositional fibrations is an impredicative class of small fibrations with a univalent representation.


Discrete propositional fibrations are classified by the following π: E → U: 


  * U consists of subsets A of ℕ, with every such realized by 0.

  * 𝒰(A,B) consists of a pair a realizers (r: A → B, s: B → A).

  * Between any two such parallel 1-cells there exists a unique 2-cell.

  * E consists of pairs (A, a) with A ⊆ℕ and a ∈ A, realized by a.

  * ℰ((A,a),(B,b)) is just 𝒰(A,B).

  * And, again, any two parallel 1-cells are connected by a unique 2-cell.

The projection π: E → U is clearly a fibration of discrete propositions. We omit the verification that it is a univalent representation.


inZFC
(ZFC) In 𝔼𝔽𝔽_1 every propositional fibration is discrete. Hence the class of discrete fibrations satisfies propositional resizing.


Suppose f: (B, β, ℬ) → (A, α, 𝒜) is propositional, and let 
    C = { (a, n) : (∃ b)   f(b) = a, β(b) = n },
 with γ(a, n) = n and 𝒞((a,n),(a', n')) = 𝒜(a, a'), and also the 2-cells in C being those in A. Clearly, the projection π: C → A is a discrete fibration of propositions. There is an obvious morphism B → C over A, and, using the axiom of choice, there is also a morphism C → B over A. Since f and π are propositional, the maps going back and forth between B and C are equivalences, so f is discrete as well.




§ SETS IN 𝔼𝔽𝔽_1


So far we have only seen properties of 𝔼𝔽𝔽_1 which are also properties of 𝔼𝔽𝔽. The main difference, however, is that the fibrations of discrete sets also form an impredicative class of small fibrations in 𝔼𝔽𝔽_1 with a univalent representation. Before we show this, let us first show that 𝔼𝔽𝔽_1 allows a form of 0-truncation.

existof0trinEFF2
(Existence of 0-truncation) Every fibration f: B → A factors as a map g: B → C followed by a fibration of sets h: C → A, in a “universal” way: if g': B → C' and h': C' → A is another such factorisation, there is a map d: C → C' over A with dg ≃_A g', with the map d itself being unique up to fibrewise homotopy over A with this property.


Let me again just give the construction: if f: (B, β, ℬ) → (A, α, 𝒜) is a fibration, then we define C := (B, β, 𝒞) with 𝒞(b,b') = ℬ(b,b') and 𝒞(π,π')=𝒜(fπ,fπ'). 


Note that this means that any fibration of sets f: (B, β, ℬ) → (A, α, 𝒜) can be assumed to satisfy ℬ(π,π') = 𝒜(fπ,fπ'); if f is also discrete, we may even assume that B ⊆ A ×ℕ with f being the first and β being the second projection. This means that the category of discrete sets in 𝔼𝔽𝔽_1 looks essentially as follows.

Its objects are:


  * A subset A of ℕ.

  * For each pair of elements a,a' ∈ A a subset 𝒜(a,a') of ℕ.

  * A function which computes for any a ∈ A an element in 𝒜(a,a).

  * A function which given a,a' and π∈𝒜(a,a') computes an element π^-1∈𝒜(a'a).

  * A function which given a,a',a”∈ A and π∈𝒜(a,a'), π' ∈𝒜(a',a”) computes an element π' ∘π∈𝒜(a,a”).

We will often just write (A, 𝒜) for these objects. A morphism f: (B, ℬ) → (A, 𝒜) between such objects consists of:


  * A computable function f: B → A.

  * For each b, b' ∈ B a function f_(b, b'): ℬ(b,b') →𝒜(fb, fb') such that f_(b,b')(π) can be computed from b,b' and π.


We will denote this category by 𝔻𝕀𝕊ℂ. Note that 𝔻𝕀𝕊ℂ is a small category and it is also, essentially, the subcategory of discrete objects in 𝔼𝔽𝔽. In fact, because the map PA → A × A is always discrete in 𝔼𝔽𝔽, the category 𝔻𝕀𝕊ℂ inherits a path category structure from 𝔼𝔽𝔽. 

discrsetsclassifiedinEFF2
In 𝔼𝔽𝔽_1 the fibrations of discrete sets form an impredicative class of small fibrations with a univalent representation.


It follows from discrfibrimprclassofsmallmapsagain and hlevelsandPi that the fibrations of discrete sets form an impredicative class of small fibrations in 𝔼𝔽𝔽_1. That means that it remains to construct a univalent representation π: E → U.


  * The elements of U are the objects (A, 𝒜) of 𝔻𝕀𝕊ℂ.

  * A realizer for any such object (A, 𝒜) is 0.

  * The 1-cells are coded homotopy equivalences (f,g,H, K) (in the sense of 𝔻𝕀𝕊ℂ and 𝔼𝔽𝔽). 

  * The 2-cells between (f,g,H,K) and (f',g',H',K') consist of homotopies U: f ≃ f'.

In addition:


  * The elements of E are (A, 𝒜, a), where (A, 𝒜) is an object of 𝔻𝕀𝕊ℂ and a ∈ A.

  * A realizer for such a thing is just a.

  * The 1-cells between (A, 𝒜, a) and (B, ℬ, b) consist of a coded homotopy equivalence (f,g,H,K): (A, 𝒜) → (B, ℬ) and a 1-cell in ℬ(fa,b).

  * The 2-cells in E are as in U.

One can easily check that the projection π: E → U is a fibration of discrete sets, so it remains to verify that it is a univalent representation. So let f: (B, β, ℬ) → (A, α, 𝒜) be a fibration of discrete sets with ℬ(π,π') = 𝒜(fπ,fπ'), B ⊆ A ×ℕ, and f the first and β the second projection. Then for each a ∈ A the fibre B_a can be regarded as an object of 𝔻𝕀𝕊ℂ as between every two parallel 1-cells in B there is a unique 2-cell. This means that the classifying map A → U can be defined on 0-cells by sending a ∈ A to B_a. In addition, every π: a → a' induces an equivalence Γ^B_π: B_a → B_a' by transportisanequivalence, while every n: π⇒π' induces a homotopy Γ^B_π≃Γ^B_π' by basicpropoftransport.(2); this completes the definition of A → U. The properties of transport imply that this map is a morphism in 𝔼𝔽𝔽_1.

Finally, if f, g: A → U are two maps and w: f^*π→ g^*π is an equivalence, then for each a ∈ A the objects f^-1(a) and g^-1(a) are equivalent in 𝔻𝕀𝕊ℂ by w_a: using the definition of the path objects in 𝔼𝔽𝔽_1 in pathobjects, one can show that this induces a morphism H: A → PU which in turn induces an equivalence f^-1(a) → g^-1(a) which is fibrewise homotopic to w. In other words, π is univalent.


It is impossible to show that the class of discrete fibrations in 𝔼𝔽𝔽_1 has a univalent representation in view of the following facts.

everythinggrpinEFF2
In 𝔼𝔽𝔽_1 every fibration is a fibration of groupoids.


It is clear from the description of path objects in pathobjects that PA → A × A is always a fibration of (discrete) sets. Since the description of fibrewise path objects P_I(A) → A ×_I A for fibrations A → I is similar, we see that every fibration is a fibration of groupoids.


nounivreprfordiscrfibrinEFF1
The class of discrete fibrations in 𝔼𝔽𝔽_1 does not have a univalent representation.


If a class of small fibrations has a univalent representation π: E → U with U a groupoid, then for every small object A, self-equivalence w: A ≃ A and homotopies H, K: 1 ≃ w, we must have that H ∼ K. For otherwise there would be a loop in the universe which is homotopic to the constant loop in two different ways, which is impossible if the universe is a groupoid. 

So consider the following discrete object (A, α, 𝒜) in 𝔼𝔽𝔽_1: 

 
  * The set A of 0-cells is { 0, 1 }.
 
  * The map α is the identity.
 
  * The set 𝒜(i,j) = { 0, 1 } for all 0-cells i, j.
 
  * The set 𝒜(π,π') for parallel 1-cells π,π' is { 0 } if π = π' and empty otherwise.
 
  * The identity 1- and 2-cells are 0.
 
  * Composition of 1-cells is addition modulo 2.

This object has an endomorphism w: A → A which is obtained by sending 0-cells to themselves and 1-cells π∈𝒜(i,j) to themselves if i = j and to 1-π if i ≠ j; because w^2 = 1, the map w is an isomorphism and hence a self-equivalence.

There are two homotopies H,K: 1 ≃ w obtained by putting H_i = i: i → i and K_i = 1-i: i → i. These homotopies H and K are not homotopic to each other because A only has identity 2-cells and the homotopies H and K are distinct.


reprinEFF1
 It is unclear to me if the class of discrete fibrations in 𝔼𝔽𝔽_1 has a non-univalent representation.




§ CONCLUSION AND DIRECTIONS FOR FUTURE RESEARCH


The contents of this paper can be summarised by the following two theorems:

summth0
There exists a path category with homotopy Π-types 𝔼𝔽𝔽 whose homotopy category is equivalent to the effective topos. Within this path category one can identify a class of small fibrations (viz., the ones which are discrete and propositional) which is impredicative and has a univalent representation. In addition, propositional resizing holds.


summth1
There exists a path category with homotopy Π-types 𝔼𝔽𝔽_1 in which there is a class of small fibrations (viz., the fibrations of discrete sets) which is impredicative and has a univalent representation. In addition, propositional resizing holds.


It is not entirely clear when two path categories should be considered equivalent, but one would expect that if one had such a notion, the path category of sets in 𝔼𝔽𝔽_1 would be equivalent as a path category to 𝔼𝔽𝔽 = 𝔼𝔽𝔽_0. Indeed, as I already suggested in the introduction, one would expect that there would be path categories 𝔼𝔽𝔽_n such that the n-types in 𝔼𝔽𝔽_n+1 would be equivalent as a path category to 𝔼𝔽𝔽_n. Ultimately, there should be a path category 𝔼𝔽𝔽_∞ such that each 𝔼𝔽𝔽_n is equivalent to the path category of n-types in 𝔼𝔽𝔽_∞. For this path category 𝔼𝔽𝔽_∞ one should have the following:

effinfty
There exists a path category with homotopy Π-types 𝔼𝔽𝔽_∞ in which there is a class of small fibrations, the discrete ones, which is impredicative and has a univalent representation. These discrete fibrations can be defined using an internal orthogonality condition and for these discrete fibrations propositional resizing holds.


In addition, the following problems remain.


  Models of CoC and coherence issues The categories 𝔼𝔽𝔽 and 𝔼𝔽𝔽_1 come close to being models of some version of CoC, but fall short in two ways. First of all, the version of CoC we have in mind is one in which all definitional equalities have been replaced by propositional ones. It remains to make this more precise and in particular write down a syntax for this version of CoC. Secondly, we should address coherence issues and formulate these categories as categories with families <cit.> or some other standard notion of model of type theory.

  Choice issues We have used the axiom of choice in the proof of propositional resizing and in the proof of the fact that the discrete fibrations can be characterised by an internal orthogonality condition (see discretealafreydinEFF and resizinginEFF for the case of 𝔼𝔽𝔽). It seems likely that both applications of the axiom of choice can be eliminated by changing the definition of 𝔼𝔽𝔽 slightly. The idea would be to say that every object (A, α, 𝒜) in 𝔼𝔽𝔽 should also come equipped with a section of the surjection α: A → Im(α), but that morphisms are as before (so they do not have to preserve this additional structure). For the fibres of fibrations one should do something similar, so it might be that this would work best in the setting of categories with families. We leave the question whether this would give us a choice-free model of CoC to future work.


plain 

