{'fraction_non_alphanumeric': 0.053539134457669176, 'fraction_numerical': 0.014720107667073223, 'mean_word_length': 3.790088638195004, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stable factorization from a fibred algebraic weak factorization system

We present a construction of stable diagonal factorizations, used to define categorical models of type theory with identity types, from a family of algebraic weak factorization systems on the slices of a category. Inspired by a computational interpretation of indexed inductive types in cubical type theory due to Cavallo and Harper, it can be read as a refactoring of a construction of van den Berg and Garner, and is a new alternative among a variety of approaches to modeling identity types in the literature.

The connection between weak factorization systems (wfs's) and identity types, observed notably by Awodey and Warren [AW09] and Gambino and Garner [GG08], lies at the heart of homotopical interpretations of type theory. However, as Awodey and Warren recognize, a weak factorization system alone is not sufficient to interpret Martin-Löf's intensional identity types in the standard sense [Mar75], because neither the factorization of maps nor the lifts of left against right maps are sufficiently structured to model coherence under substitution. Rather, one needs choices of factorizations and lifts in every context, coherently with respect to reindexing.
In order to deal with this problem, van den Berg and Garner [BG12] introduced the notion of a cloven wfs (cwfs) on a category, slightly weaker than but similar to the more widely-used algebraic wfs [GT06;Gar07]. A cloven wfs provides the choices of factorizations and lifts mentioned above in an empty context. However, additional work is required to obtain factorizations and lifts in an arbitrary context in a coherent way. Van den Berg and Garner thus require an even stronger assumption, that of a path object category [BG12, Axioms 1-3], which induces a cloven wfs but also satisfies the crucial property that its slices coherently inherit path object category structures. This is enough to derive a stable functorial choice of diagonal factorizations [BG12, Definition 3.3.3], which is more-or-less exactly what is needed to model identity types as part of a model of Martin-Löf's intensional type theory.
Unfortunately, the axioms that a path object category C must satisfy are somewhat onerous to check. Standard "objects of paths" in typical target categories-such as the exponential X [0,1] of a topological space X, or A ∆ 1 of a simplicial set A-are not path objects in this sense, because they satisfy only up to homotopy certain laws that are required to hold strictly in a path object category. (For example, path composition must be strictly associative.) Instead, van den Berg and Garner are forced to rely on more complex objects, such as Moore paths and their simplicial analogues. Showing that these objects satisfy the necessary axioms is non-trivial [BG12,§7].
In this note, we approach the problem from a different angle. Rather than looking for a structure on C that induces a cwfs and can be reindexed-thus induces a cwfs on every slice-we instead take such a family of factorization systems on the slices of C as input. Specifically, we use Swan's notion of fibred algebraic weak factorization system [Swa18b]. We will still need some assumptions to get from here to a stable functorial choice of diagonal factorizations, namely a functorial cocylinder satisfying some properties. However, these are fairly permissive; for one, we can use (−) ∆ 1 as our cocylinder in simplicial sets without issue.
We then rely on Swan's general techniques for constructing fibred factorization systems [Swa18d], which apply in such cases as simplicial and structural cubical sets. Intuitively, the "Moore-like" aspect of van den Berg and Garner's construction is encapsulated in this step, the factorizations in each slice typically being constructed by an inductive process (i.e., a small object argument). Our contribution, then, is to observe that we can leverage a technique already being used in the construction of awfs's, rather than introducing separately the machinery of Moore paths.
We introduce the basic notions in Section 1, give the main construction in Section 2, and instantiate it with cubical and simplicial sets in Section 3.

Related work
We have already discussed the connection with the work of van den Berg and Garner. Similar ideas were already employed by Warren [War08, Chapter 3], as briefly summarized in [AW09, §4.2]. Warren uses categories with a certain variety of interval (namely, a cocategory object satisfying further conditions) to interpret Martin-Löf identity types. Like the path objects of van den Berg and Garner, these must satisfy conditions such as (co)associativity on the nose. Any such interval induces a path object category structure; thus van den Berg and Garner's results generalize those of Warren [BG12,§5.4]. Warren's models invalidate the uniqueness of identity proofs but are 1-truncated-any pair of identities between identities are identified. (Warren separately constructs a model in strict ω-groupoids that is not n-truncated for any n ∈ N [War08, Chapter 4].) Swan has also presented two general constructions of a stable functorial choice of diagonal factorizations [Swa18a]. The first takes a algebraic model structure (ams) with structured weak equivalences as input [Swa18a,Theorem 4.13]; while the construction itself is appealingly direct, its hypotheses are difficult to verify. For this reason, Swan also presents a more specialized construction that requires fewer assumptions to apply [Swa18a,§5], taking a pre-ams satisfying axioms based on those used by Gambino and Sattler [GS17]. By imposing further conditions, further simplifications are possible [CCHM15, §9.1; Swa18a, §6; ABCFHL19, §2.16].
Swan's second construction bears a strong resemblance to our own. Indeed, in many ways the two seem to be "dual". Swan uses cofibration-trivial fibration factorization to construct the identity types, where we use trivial cofibration-fibration factorization; his proof of stability uses pullbackstability of the former factorization system, while we achieve stability by assuming that the latter is fibred. 1 Both constructions pass through a proof that the reflexivity map X → Id Γ (f ) is a deformation retract: Swan uses this to show that the map is a trivial cofibration, where we use it to show that the map Id Γ (f ) → Y × Γ Y is a fibration. (In [BG12], the trivial cofibrations are defined to be the strong deformation retracts.) We leave the teasing out of this apparent "duality" for future work. Because we rely on a fibred factorization system, however, we do exclude some interesting cases handled by Swan, in particular BCH cubical sets [BCH13]. (See [Swa18b, §9.3] for discussion of this case.) Other approaches to modeling identity types make use of regular fibrations (also called normal fibrations). The idea is to set up the factorization system so that identity types can be modeled simply by exponentiation by an interval object. Awodey defines an awfs on cartesian cubical sets such that the factorization of the diagonal ∆ : A → A×A is given by A → A I → A×A [Awo18]. Gambino and Larrea give a definition of normal fibration in any topos equipped with certain structure (such as simplicial sets or De Morgan cubical sets). Their definition is at least compatible with Σ, Π, and (of course) identity types; they leave univalent universes and inductive types for future work [GL19]. One weakness of normal fibrations is that they apparently interfere with the constructive modeling of univalent universes; Swan has demonstrated impossibility results to this effect for a certain class of models [Swa18c]. (On the other hand, Gambino and Henry have made recent progress towards a constructive simplicial model which interprets identity types by an interval exponential [GH19].) Finally, one may rely on general coherence results. Voevodsky's simplicial model of univalent type theory, for example, uses the exponential (−) ∆ 1 [KL12, Proposition 2.2.3] to obtain weakly stable identity types (among weakly stable versions of the other type formers) and then applies a coherence theorem, which constructs a new category from the category of simplicial sets in which the weakly stable structures become strictly stable. This is effective, but it is a big hammer; approaches such as our own are more targeted.
This construction was inspired by and adapted from the implementation of identity types (and indexed inductive types more generally) that the author developed with Robert Harper for a computational cartesian cubical type theory [CH19]. This note isolates the ideas needed to handle identity types; we expect that modeling higher inductive types with parameters, even simple ones, will require further assumptions.
Acknowledgments First and foremost I am grateful to Robert Harper, without whom this note could not exist. Andrew Swan provided feedback on multiple drafts and helped me to grasp both his own constructions and others in the literature. I thank Emily Riehl and Christian Sattler for their useful advice, and Mathieu Anel and Steve Awodey (among others) for teaching me the basics of model category theory over the years.
I gratefully acknowledge the support of the Air Force Office of Scientific Research through MURI grant FA9550-15-1-0053. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the AFOSR.

Fibred factorization systems
We briefly recall the concept of algebraic weak factorization system introduced by Grandis and Tholen [GT06] under the name natural weak factorization system. The distributive law requirement in Definition 1.2 was added later on by Garner [Gar07, Definition 1]; we will not use it explicitly here, so will neglect to explain what it means.
Definition 1.1. Write conc : C → × C C → → C → for the functor that takes a composable pair of arrows in a category C and performs the composition. A functorial factorization on a category C is a section L, R : C → → C → × C C → of conc. We will use the letter K to denote the functor Definition 1.2. An algebraic weak factorization system (awfs) on a category C consists of a comonad (L, Φ, Σ) and monad (R, Λ, Π) on C → such that 1. L, R is a functorial factorization, Definition 1.3. Given an awfs (L, R), we define L-map to be the category of pointed endofunctor coalgebras for (L, Φ) and R-map to be the category of pointed endofunctor algebras for (R, Λ).

Concretely, an object in
Intuitively, the maps s and p shown above provide universal solutions to filling problems against R-and L-maps respectively. We will use a few standard facts about algebraic weak factorization systems without proof: the maps returned by L and R are L-and R-maps respectively, L-maps lift functorially against R-maps, and R-maps are functorially closed under composition and pullback.
(We refer to, e.g., Riehl [Rie11] for a proper introduction to awfs's.) Our goal is to take a category C equipped with an awfs and construct a stable functorial choice of diagonal factorizations [BG12, Definition 3.3.3]. Under further conditions on C-notably, the Frobenius condition-these can be used to interpret type theory with identity types [BG12, Theorem 3.3.5]. As the further conditions and ultimate construction of a model of type theory are orthogonal to the construction of the diagonal factorizations, we will not discuss them further here.
Definition 1.4. A functorial choice of diagonal factorizations in an algebraic weak factorization system L, R on some C is a functor R-map → L-map× C R-map that, for every R-map f : X → Γ, assigns a factorization (P f , r f , p f ) of the diagonal ∆ f : X → X × Γ X as shown below.
Definition 1.5. A functorial choice of diagonal factorizations is stable when for every pullback square as shown on the left below, the square on the right is also a pullback.
Remark 1.6. Note that the stability condition above only concerns the underlying maps of the factorization, not their L-or R-map structures. As van den Berg and Garner note [BG12, Propositions 3.3.6 and 3.3.7], this condition is all that is needed.
To build a choice of diagonal factorizations, our construction will assume that the awfs is one of a family of awfs's defined on each slice of the input category. The following is the specialization of Swan's notion of fibred awfs over an arbitrary Grothendieck fibration [Swa18b,Definition 4.4.6] to the particular case of the codomain fibration over C [Swa18b, §7.3].
Definition 1.7. A fibred algebraic weak factorization system (fibred awfs) on a category C consists of a family of awfs's L Γ , R Γ on C/Γ for each Γ ∈ C that is stable under reindexing.

Cocylinders and homotopies
As part of our construction, we will also make use of a functorial cocylinder on the target category. Given an object X, the cocylinder I X is to be thought of as the object of paths in X. A functorial cocylinder is useful primarily because it allows us to say that fillers are unique up to homotopy. Definition 1.11. Given a functorial cocylinder on C and an object Γ ∈ C, there is an induced functorial cocylinder on C/Γ: given a : A → Γ, we define I Γ (A, a) as the following pullback.
It is straightforward to derive the transformations δ i Γ (−) and ε Γ (−). We will write I Γ A rather than I Γ (A, a) when the arrow can be inferred.
In the case that that the functorial cocylinder is given by exponentiation with an interval object, the following definitions specialize to instances of the Leibniz exponential.
Definition 1.12. Given a functorial cocylinder, we write ∂ A := δ 0 A, δ 1 A : For any map f : X → Y , we define maps δ 0 f and ∂ f as follows.
Definition 1.13. Given maps f 0 , f 1 : X → Y , a homotopy from f 0 to f 1 is a map ψ : X → I Y such that (δ i Y )ψ = f i for i ∈ {0, 1}. We write ψ : f 0 ∼ f 1 .
We will need to know that for any awfs L, R satisfying certain conditions, L-maps between fibrant objects (that is, A with an R-map structure on ! A : A → 1) give rise to deformation retracts. Definition 1.14. A map f : X → Y is a (left) deformation retract if there exists a map g : Y → X with gf = id X and a homotopy ψ : f g ∼ id Y . Given a category C with a functorial cocylinder, we write DefRet(C) for the category whose objects are deformation retracts (f, g, ψ) and morphisms (f , g , ψ ) → (f, g, ψ) are commutative squares (h, k) : f → f such that hg = gk and (I k)ψ = ψk.
Lemma 1.15. Fix a category C with a functorial cocylinder and an awfs L, R , together with a functor R-map → R-map assigning an R-map structure to ∂ f for every R-map f . Then we have a functor L-map × C×C (R-map × R-map) → DefRet(C) that, for each L-map m : A B with R-map structures on ! A : A → 1 and ! B : B → 1, produces a deformation retract structure on m.
Proof. We produce g : B → A and ψ : mg ∼ id B by solving the following lifting problems.
mg,id ψ 2 Constructing a stable factorization Axiom Set A. Fix a category C with finite limits and a fibred awfs L Γ , R Γ Γ∈C . We require the following.

A2. A functor
Remark 2.1. For the moment we choose a set of axioms that will take us most directly to our result; in Section 3, we present a second set formulated in terms of a (pre) algebraic model structure. In a situation where the L Γ , R Γ are the trivial cofibrations and fibrations of a fibred model structure, Axiom A2 can be read intuitively as a combination of more familiar conditions. First, that δ 0 Γ (−) takes fibrations to trivial fibrations. Second, that trivial fibration structure is fiberwise structure: a map f ∈ (C/Γ) → is globally a trivial fibration as soon as it is a trivial fibration as a map over Γ. And finally, that every trivial fibration is (of course) a fibration.
We aim to construct a stable functorial choice of diagonal factorizations for the awfs L 1 , R 1 . The central idea is to define the identity type in context Γ by factorizing the diagonal with respect to L Γ , R Γ . This is similar to the approach taken by van den Berg and Garner, the difference being that we use factorization relative to Γ rather than a path object.
This definition evidently satisfies the stability condition. However, note that the maps L Γ (∆ f ) and R Γ (∆ f ) are a priori only left and right maps with respect to L Γ , R Γ , whereas Definition 1.4 requires that they be so with respect to L 1 , R 1 . The remainder of this section is dedicated to establishing that this is indeed the case (and is functorially so). We will generally not check functoriality explicitly, as it is straightforward to verify.
The following two lemmas hold in a fibred awfs over any Grothendieck fibration (and with 1 replaced by any Γ in a suitable fashion), but we give concrete proofs for the sake of self-containedness. Lemma 2.3 is the easy half of the result we need: it shows that L Γ (∆ f ) above is an L 1 -map.
Lemma 2.2. We have a functor (C/Γ) → × C → R 1 -map → R Γ -map that, for each f : (X, x) → (Y, y) with an R 1 -map structure, provides an R Γ -map structure on f .
Proof. As the awfs is fibred, we have an R Γ -map structure on Γ × f : (Γ × X, π 1 ) → (Γ × Y, π 1 ). We now observe that f is a pullback of Γ × f along y, id : Y → Γ × Y , so we can apply the stability of R Γ -maps under pullback.
Lemma 2.3. We have a functor L Γ -map → L 1 -map that, for each m : (A, a) Γ (B, b), provides an L 1 -map structure on m.
Here we use the fact that the awfs is fibred to see that the top composite is indeed L 1 (m).
The next lemma allows us to transfer an R 1 -map structure forward along an L Γ -map when the target is at least an R Γ -map (as a map into the terminal object of C/Γ). We will use this to derive an R 1 -map structure on the map K Γ (∆ f ) → Γ from the R 1 -map structure on X → Γ.
Proof. Note that a : (A, a) → (Γ, id) is also an R Γ -map because the awfs is fibred. By Lemma 1.15 (for which we use Axiom A3), we see that m is a deformation retract in C/Γ, so we have r : (B, b) → (A, a) with rm = id A and a homotopy ψ : mr ∼ id B .
We need a lift for (id, R 1 (b)) : L 1 (b) → b. We first transform this into a lifting problem against a and produce a lift, using the L 1 -map structure on L 1 (b) and R 1 -map structure on a.
Note that mj a : K 1 (b) → B makes the lower triangle of the original problem commute, but not the upper triangle. We rectify this by solving the following lifting problem in C/Γ, using Axiom A2 to obtain an R 1 -map structure on δ 0 Γ b.
The map (δ 1 B)j b : K 1 (b) → B is our desired lift.
Finally, we show that any R Γ -map between R 1 -maps is itself an R 1 -map. Once we have derived an R 1 -map structure on the map K Γ (∆ f ) → Γ via the previous lemma, we can use this to derive an Lemma 2.5. We have a functor R Γ -map × C/Γ×C/Γ (R 1 -map × C R 1 -map) → R 1 -map that, given f : (X, x) Γ (Y, y) with R 1 -map structures on x and y, produces an R 1 -map structure on f . Proof. We must produce a diagonal lift for (id, R 1 (f )) : L 1 (f ) → f . First, we use the assumption that x is an R 1 -map to solve the following lifting problem.
Next, we use j x to define a second filling problem, which we solve using Axiom A3 and the assumption that y is an R 1 -map.
Finally, we have an R 1 -map structure on δ 0 Γ f by Axiom A2. Thus we can solve the following lifting problem. (Note that in the bottom map, we use the definition of I Γ Y as Γ × I Γ (I Y ).) Our final diagonal filler is then given by (δ 1 Γ X)j f : K 1 (f ) → X.
Although our ultimate goal is stable factorization of diagonal maps, we can more generally obtain stable factorization of all maps in C/Γ between R 1 -maps.
Theorem 2.6. We have a functor R Γ -map × C/Γ×C/Γ (R 1 -map × C R 1 -map) → L 1 -map × R 1 -map that, given f : (X, x) → (Y, y) in C/Γ with R 1 -map structures on x : X → Γ and y : Y → Γ, produces L 1 -and R 1 -map structures on L Γ (f ) : X → K Γ (f ) and R Γ : Proof. First, we have an L 1 -map structure on L Γ (f ) by Lemma 2.3. Write We have a R Γ -map structure on y : (Y, y) → (Γ, id) because the awfs is fibred. As R Γ -maps are closed under composition, we also have an R Γ -map structure on k : (K Γ (f ), k) → (Γ, id). We may therefore apply Lemma 2.4 to derive an R 1 -map structure on k. We now have an R Γ -map R Γ (f ) : (K Γ (f ), k) Γ (Y, y) between two R 1 -maps, so we can apply Lemma 2.5 to derive an R 1 -map structure on R Γ (f ).
Corollary 2.7. We have a stable functorial choice of diagonal factorizations in L 1 , R 1 .
Proof. Given an R 1 -map f : X 1 Γ, we define P f := K Γ (∆ f ), regarding the diagonal as a map ∆ f : (X, f ) → (X× Γ X, f •π 1 ) in C/Γ. Note that we have an R 1 -map structure on f •π 1 : X× Γ X → Γ: it is the composite of f : X 1 Y and π 1 : X × Γ X → X, the latter of which is the pullback of an R 1 -map and therefore an R 1 -map. Thus L Γ (f ) and R Γ (f ) are L 1 -and R 1 -maps by Theorem 2.6, so we may take r f := L Γ (f ) and p f := R Γ (f ). Functoriality of this choice follows from functoriality of Theorem 2.6, while stability is immediate from the fact that the awfs is fibred.

Examples
We now demonstrate the applicability of our construction. First, we bring our set of axioms closer to the common examples by considering the situation where the fibred awfs in question constitutes the trivial cofibrations and fibrations of a model structure. In this case we can recast Axiom Set A in a more natural way. Actually, we will not need a full model structure to do so; we can get by with a pre-ams à la Swan [Swa18a, Definition 2.8].
Definition 3.3 (Swa18a, Definition 2.8). A pre algebraic model structure (pre-ams) on a category C is a pair of awfs's C t , F and C, F t on C together with a morphism of awfs's ξ : C t , F → C, F t .
We refer to Riehl [Rie11, Definition 2.14] for a definition of morphism of awfs's; we will only need the following property.
Proposition 3.4. A pre-ams ξ : C t , F → C, F t induces a functor F t -map → F -map.
Axiom Set B. Fix a category C with finite limits and a fibred awfs C t Γ , F Γ Γ∈C . We require the following.

B4. A functor
Lemma 3.5. Any C and C t Γ , F Γ Γ∈C satisfying Axiom Set B also satisfies Axiom Set A.
Proof. Only Axiom A2 is not immediate. Suppose we are given an F Γ -map f : (X, x) Γ (Y, y); we need an F 1 -map structure on δ 0 Γ f . Thanks to Axiom B2 and Proposition 3.4, it suffices to obtain an F t 1 -map structure. We therefore show that δ 0 Γ f lifts against C 1 -maps; let some C 1 -map m : A → B be given with a lifting problem (h, k) : m → δ 0 Γ f in C. By composing the legs of δ 0 Γ f with h and k, we obtain a, b such that m is a map (A, a) → (B, b) over Γ. By reindexing m along ! Γ : Γ → 1, we obtain an C Γ -map structure on Γ × m : (Γ × A, π 1 ) → (Γ × B, π 1 ). By Axiom B1 and Proposition 3.2, we can pull back Γ × m back along b, id : (B, b) → (Γ × B, π 1 ) to obtain an C Γ -map structure on m : (A, a) → (B, b). Thus m lifts against δ 0 Γ f in C/Γ by Axiom B4, which in particular gives a filler for (h, k).
We now shift to a relatively concrete situation, applying the framework developed in [CMS19; CMS20] to obtain stable functorial diagonal factorizations in a variety of cubical models.
Axiom Set C. Fix a locally cartesian closed category C with finite colimits and disjoint coproducts. We require the following.
C2. An interval object δ 0 , δ 1 : 1 → I such that δ 0 and δ 1 are pullbacks of . C3. One of the following two conditions: (a) C is an (internal) category of presheaves and is a locally decidable monomorphism.
(b) C is a ΠW -pretopos and it satisfies the axiom weakly initial set of covers (WISC).
Remark 3.6. An interval I induces interval objects I Γ := π 2 : I × Γ → Γ in each slice category. For any map f : A → B, we define the mapping cylinder Cyl(f ) to be the pushout of B