Basic definitions of homotopy type theory

This file defines some of the most basic types and type formers, such as sums, products, Sigma types and path types. It defines the action of functions on paths ap, transport, equivalences, and function extensionality. It also defines truncatedness, and a number of other fundamental definitions used throughout the library. Import the file of reserved notations so we maintain consistent level notations throughout the library.

This command prevents Coq from automatically defining the eliminator functions for inductive types. We will define them ourselves to match the naming scheme of the HoTT Book. In principle we ought to make this Global, but unfortunately the tactics induction and elim assume that the eliminators are named in Coq's way, e.g. thing_rect, so making it global could cause unpleasant surprises for people defining new inductive types. However, when you do define your own inductive types you are encouraged to also do Local Unset Elimination Schemes and then use Scheme to define thing_ind, thing_rec, and (for compatibility with induction and elim) thing_rect, as we have done below for paths, Empty, Unit, etc. We are hoping that this will be fixed eventually; see https://github.com/coq/coq/issues/3745.

Datatypes

Functions

Notation for non-dependent function types

Option type

option A is the extension of A with an extra element None

Sum type

sum A B, written A + B, is the disjoint sum of A and B

Product type

prod A B, written A × B, is the product of A and B; the pair pair A B a b of a and b is abbreviated (a,b)

Type classes

This command prevents Coq from trying to guess the values of existential variables while doing typeclass resolution. If you don't know what that means, ignore it.

A PreOrder is both Reflexive and Transitive.

Above, we have made reflexivity, symmetry, and transitivity reduce under cbn/simpl to their underlying instances. This allows the tactics to build proof terms referencing, e.g., concat. We use change after the fact to make sure that we didn't cbn away the original form of the relation. If we want to remove the use of cbn, we can play tricks with Module Types and Modules to declare inverse directly as an instance of Symmetric without changing its type. Then we can simply unfold symmetry. See the comments around the definition of inverse. Overwrite reflexivity so that we use our version of Reflexive rather than having the tactic look for it in the standard library. We make use of the built-in reflexivity to handle, e.g., single-constructor inductives.

Even if we weren't using cbn, we would have to redefine symmetry, since the built-in Coq version is sometimes too smart for its own good, and will occasionally fail when it should not.

We redefine transitivity to work without needing to include Setoid or be using Leibniz equality, and to give proofs that unfold to concat.

Basic definitions

Define an alias for Set, which is really Type₀.

We make the identity map a notation so we do not have to unfold it, or complicate matters with its type.

Constant functions

Sigma types

(sig A P), or more suggestively {x:A & (P x)} is a Sigma-type.

We make the parameters maximally inserted so that we can pass around pr1 as a function and have it actually mean "first projection" in, e.g., ap.

This lets us pattern match sigma types in let expressions

We define notation for dependent pairs because it is too annoying to write and see exist P x y all the time. However, we put it in its own scope, because sometimes it is necessary to give the particular dependent type, so we'd like to be able to turn off this notation selectively.

We bind fibration_scope with sig so that we are automatically in fibration_scope when we are passing an argument of type sig.

The following notation is very convenient, although it unfortunately clashes with Proof General's "electric period". We have added format specifiers in Notations.v so that it will display without an extra space, as x.1 rather than as x .1.

Composition of functions.

We put the following notation in a scope because leaving it unscoped causes it to override identical notations in other scopes. It's convenient to use the same notation for, e.g., function composition, morphism composition in a category, and functor composition, and let Coq automatically infer which one we mean by scopes. We can't do this if this notation isn't scoped. Unfortunately, Coq doesn't have a built-in function_scope like type_scope; type_scope is automatically opened wherever Coq is expecting a Sort, and it would be nice if function_scope were automatically opened whenever Coq expects a thing of type ∀ _, _ or _ → _. To work around this, we open function_scope globally. We allow writing (f o g)%function to force function_scope over, e.g., morphism_scope.

This definition helps guide typeclass inference.

Dependent composition of functions.

The groupoid structure of identity types.

The results in this file are used everywhere else, so we need to be extra careful about how we define and prove things. We prefer hand-written terms, or at least tactics that allow us to retain clear control over the proof-term produced. We define our own identity type, rather than using the one in the Coq standard library, so as to have more control over transitivity, symmetry and inverse. It seems impossible to change these for the standard eq/identity type (or its Type-valued version) because it breaks various other standard things. Merely changing notations also doesn't seem to quite work.

Our identity type is the Paulin-Mohring style. We derive the Martin-Lof eliminator.

And here's the "right-sided" Paulin-Mohring eliminator.

We declare a scope in which we shall place path notations. This way they can be turned on and off by the user. We bind path_scope to paths so that when we are constructing arguments to things like concat, we automatically are in path_scope.

The inverse of a path.

Declaring this as simpl nomatch prevents the tactic simpl from expanding it out into match statements. We only want inverse to simplify when applied to an identity path.

If we wanted to not have the constant symmetric_paths floating around, and wanted to resolve inverse directly, instead, we could play this trick, discovered by Georges Gonthier to fool Coq's restriction on Identity Coercions:

Module Export inverse.
  Definition inverse {A : Type} {x y : A} (p : x = y) : y = x
    := match p with idpath => idpath end.
End inverse.

Module Type inverseT.
  Parameter inverse : forall {A}, Symmetric (@paths A).
End inverseT.

Module inverseSymmetric (inverse : inverseT).
  Global Existing Instance inverse.inverse.
End inverseSymmetric.

Module Export symmetric_paths := inverseSymmetric inverse.

We define equality concatenation by destructing on both its arguments, so that it only computes when both arguments are idpath. This makes proofs more robust and symmetrical. Compare with the definition of identity_trans.

See above for the meaning of simpl nomatch.

Note that you can use the Coq tactics reflexivity, transitivity, etransitivity, and symmetry when working with paths; we've redefined them above to use typeclasses and to unfold the instances so you get proof terms with concat and inverse. The identity path.

The composition of two paths. We put p and q in path_scope explicitly. This is a partial work-around for https://coq.inria.fr/bugs/show_bug.cgi?id=3990, which is that implicitly bound scopes don't nest well.

The inverse of a path. See above about explicitly placing p in path_scope.

An alternative notation which puts each path on its own line, via the format specification in Notations.v. Useful as a temporary device during proofs of equalities between very long composites; to turn it on inside a section, say Open Scope long_path_scope.

An important instance of paths_ind is that given any dependent type, one can transport elements of instances of the type along equalities in the base: transport P p u transports u : P x to P y along p : x = y.

See above for the meaning of simpl nomatch.

Transport is very common so it is worth introducing a parsing notation for it. However, we do not use the notation for output because it hides the fibration, and so makes it very hard to read involved transport expression.

The first time rewrite is used in each direction, it creates transport lemmas called internal_paths_rew and internal_paths_rew_r. See ../Tactics.v for how these compare to transport. We use rewrite here to trigger the creation of these lemmas. This ensures that they are defined outside of sections, so they are not unnecessarily polymorphic. The lemmas below are not used in the library. TODO: If Coq PR18299 is merged (possibly in Coq 8.20), then we can instead register wrappers for [transport] to be used for rewriting. See the comment by Dan Christensen in that PR for how to do this. Then the tactics [internal_paths_rew_to_transport] and [rewrite_to_transport] can be removed from ../Tactics.v.

Having defined transport, we can use it to talk about what a homotopy theorist might see as "paths in a fibration over paths in the base"; and what a type theorist might see as "heterogeneous equality in a dependent type". We will first see this appearing in the type of apD. Functions act on paths: if f : A → B and p : x = y is a path in A, then ap f p : f x = f y. We typically pronounce ap as a single syllable, short for "application"; but it may also be considered as an acronym, "action on paths".

We introduce the convention that apKN denotes the application of a K-path between functions to an N-path between elements, where a 0-path is simply a function or an element. Thus, ap is a shorthand for ap01.

Similarly, dependent functions act on paths; but the type is a bit more subtle. If f : ∀ a:A, B a and p : x = y is a path in A, then apD f p should somehow be a path between f x : B x and f y : B y. Since these live in different types, we use transport along p to make them comparable: apD f p : p # f x = f y. The type p # f x = f y can profitably be considered as a heterogeneous or dependent equality type, of "paths from f x to f y over p".

See above for the meaning of simpl nomatch.

Homotopies between functions

For the benefit of readers of the HoTT Book:

Equivalences

Homotopy equivalences are a central concept in homotopy type theory. Before we define equivalences, let us consider when two types A and B should be considered "the same". The first option is to require existence of f : A → B and g : B → A which are inverses of each other, up to homotopy. Homotopically speaking, we should also require a certain condition on these homotopies, which is one of the triangle identities for adjunctions in category theory. Thus, we call this notion an *adjoint equivalence*. The other triangle identity is provable from the first one, along with all the higher coherences, so it is reasonable to only assume one of them. Moreover, as we will see, if we have maps which are inverses up to homotopy, it is always possible to make the triangle identity hold by modifying one of the homotopies. The second option is to use Vladimir Voevodsky's definition of an equivalence as a map whose homotopy fibers are contractible. We call this notion a *homotopy bijection*. An interesting third option was suggested by André Joyal: a map f which has separate left and right homotopy inverses. We call this notion a *homotopy isomorphism*. While the second option was the one used originally, and it is the most concise one, it makes more sense to use the first one in a formalized development, since it exposes most directly equivalence as a structure. In particular, it is easier to extract directly from it the data of a homotopy inverse to f, which is what we care about having most in practice. Thus, adjoint equivalences are what we will refer to merely as *equivalences*. Naming convention: we use equiv and Equiv systematically to denote types of equivalences, and isequiv and IsEquiv systematically to denote the assertion that a given map is an equivalence. A typeclass that includes the data making f into an adjoint equivalence.

We mark eisadj as Opaque to deter Coq from unfolding it when simplifying. Since proofs of eisadj typically have larger proofs than the rest of the equivalence data, we gain some speed up as a result.

A record that includes all the data of an adjoint equivalence.

A notation for the inverse of an equivalence. We can apply this to a function as long as there is a typeclass instance asserting it to be an equivalence. We can also apply it to an element of A <~> B, since there is an implicit coercion to A → B and also an existing instance of IsEquiv.

A shorthand for applying paths between equivalences like functions.

Function extensionality

The function extensionality axiom is formulated as a class. To use it in a theorem, just assume it with `{Funext}, and then you can use path_forall, defined below. If you need function extensionality for a whole development, you can assume it for an entire Section with Context `{Funext}. We use a dummy class and an axiom to get universe polymorphism of Funext while still tracking its uses. Coq's universe polymorphism is parametric; in all definitions, all universes are quantified over before any other variables. It's impossible to state a theorem like (∀ i : Level, P i) → Q (e.g., "if C has all limits of all sizes, then C is a preorder" isn't statable)*. By making isequiv_apD10 an Axiom rather than a per-theorem hypothesis, we can use it at multiple incompatible universe levels. By only allowing use of the axiom when we have a Funext in the context, we can still track what theorems depend on it (because their type will mention Funext). By giving Funext a field whose type is an axiom, we guarantee that we cannot construct a fresh instance of Funext without admit; there's no term of type dummy_funext_type floating around. If we did not give Funext any fields, then we could accidentally manifest a Funext using, e.g., constructor, and then we wouldn't have a tag on the theorem that did this. As Funext is never actually used productively, we toss it in Type0 and make it Monomorphic so it doesn't add more universes.

That's not technically true; it might be possible to get non-parametric universe polymorphism using Modules and (Module) Functors; we can use functors to quantify over a Module Type which requires a polymorphic proof of a given hypothesis, and then use that hypothesis polymorphically in any theorem we prove in our new Module Functor. But that is far beyond the scope of this file.

Contractibility and truncation levels

Truncation measures how complicated a type is in terms of higher path types. The (-2)-truncated types are the contractible ones, whose homotopy is completely trivial. More precisely, a type A is contractible if there is a point x : A and a (pointwise) homotopy connecting the identity on A to the constant map at x. The (n+1)-truncated types are those whose path types are n-truncated. Thus, (-1)-truncated means "the type of paths between any two points is contractible". Such a type is necessarily a sub-singleton: any two points are connected by a path which is unique up to homotopy. In other words, (-1)-truncated types are truth values. We call such types "propositions" or "h-propositions". Next, 0-truncated means "the type of paths between any two points is a sub-singleton". Thus, two points might not have any paths between them, or they have a unique path. Such a type may have many points but it is discrete in the sense that all paths are trivial. We call such types "sets" or "h-sets". In this library, a witness that a type is n-truncated is formalized by the IsTrunc n typeclass. In many cases, the typeclass machinery of Coq can automatically infer a witness for a type being n-truncated. Because IsTrunc n A itself has no computational content (that is, all witnesses of n-truncation of a type are provably equal), it does not matter much which witness Coq infers. Therefore, the primary concerns in making use of the typeclass machinery are coverage (how many goals can be automatically solved) and speed (how long does it take to solve a goal, and how long does it take to error on a goal we cannot automatically solve). Careful use of typeclass instances and priorities, which determine the order of typeclass resolution, can be used to effectively increase both the coverage and the speed in cases where the goal is solvable. Unfortunately, typeclass resolution tends to spin for a while before failing unless you're very, very, very careful. We currently aim to achieve moderate coverage and fast speed in solvable cases. How long it takes to fail typeclass resolution is not currently considered, though it would be nice someday to be even more careful about things. In order to achieve moderate coverage and speedy resolution, we currently follow the following principles. They set up a kind of directed flow of information, intended to prevent cycles and potentially infinite chains, which are often the ways that typeclass resolution gets stuck.

• We prefer to reason about IsTrunc (S n) A rather than IsTrunc n (@paths A a b). Whenever we see a statement (or goal) about truncation of paths, we try to turn it into a statement (or goal) about truncation of a (non-paths) type. We do not allow typeclass resolution to go in the reverse direction from IsTrunc (S n) A to ∀ a b : A, IsTrunc n (a = b).
• We prefer to reason about syntactically smaller types. That is, typeclass instances should turn goals of type IsTrunc n (∀ a : A, P a) into goals of type ∀ a : A, IsTrunc n (P a); and goals of type IsTrunc n (A × B) into the pair of goals of type IsTrunc n A and IsTrunc n B; rather than the other way around. Ideally, we would add similar rules to transform hypotheses in the cases where we can do so. This rule is not always the one we want, but it seems to heuristically capture the shape of most cases that we want the typeclass machinery to automatically infer. That is, we often want to infer IsTrunc n (A × B) from IsTrunc n A and IsTrunc n B, but we (probably) don't often need to do other simple things with IsTrunc n (A × B) which are broken by that reduction.
  We begin by defining the type that indexes the truncation levels.

We will use Notation for trunc_indexes, so define a scope for them here. Numeral notation for trunc_indexes is set up in Basics/Trunc.v.

We define truncatedness using an inductive type IsTrunc_internal A n. We use a notation IsTrunc n A simply to swap the orders of arguments, and notations Contr, IsHProp and IsHSet which specialize to n being -2, -1 and 0, respectively. An alternative is to use a Fixpoint, and that was done in the past. The advantages of the inductive approach are: IsTrunc_internal is cumulative; typeclass inherence works smoothly; the library builds faster. Some disadvantages are that we need to manually apply the constructors when proving that something is truncated, and that the induction principle is awkward to work with.

A version of istrunc_unfold for successors.

We define a slight variation of istrunc_unfold, which differs only it what it does for n = -2. It will produce a section of the following type family.

The variant of istrunc_unfold lets us treat any proof of truncation as a function. For n = -2, it produces the contracting homotopy.

We add this as a coercion.

Truncated relations

Hprop-valued relations. Making this a Notation rather than a Definition enables typeclass resolution to pick it up easily. We include the base type A in the notation since otherwise e.g. ∀ (x y : A) (z : B x y), IsHProp (C x y z) will get displayed as ∀ (x : A), is_mere_relation (C x).

Natural numbers

Misc

We put Empty here, instead of in Empty.v, because Ltac done uses it.

Likewise, we put Unit here, instead of in Unit.v, because Trunc uses it.

A Unit goal should be resolved by auto and trivial.

Pointed types

A space is pointed if that space has a point.

Homotopy fibers

Homotopy fibers are homotopical inverse images of points.

Smallness

We say that X : Type@{j} is small (relative to Type@{i}) if it is equivalent to a type in Type@{i}. We use a record to avoid an extra universe variable. This version has no constraints on i and j. It lands in max(i+1,j), as expected. We mark the i variable as being invariant, so that Coq is better at guessing universe variables when this is used.

Propositional resizing

See the note by Funext above regarding classes for axioms.

Propositional resizing says that every (-1)-truncated type is small.