Paths as functions of the interval
In cubical type theory, a path p : x = y in A is a function from an abstract interval into A. Its value at 0 is definitionally x and its value at 1 is y. Many path proofs can therefore be written directly, as functions of an interval coordinate, instead of by path induction. The operations of chapter 7, such as sym and trans, are built this way.
fun (i : Interval) => … binds a coordinate inside the forms below. Interval is not a type: it belongs to no universe and cannot be the domain of an ordinary function. A coordinate can be 0, 1, a bound coordinate i, or ~i, the reversal 1 − i, also written flip(i). Two more operations, meets and joins, are described below.
| Form | Meaning |
|---|---|
path(fun (i : Interval) => A, fun (i : Interval) => body) | The path whose value at i is body, in the family A |
path i => body | The same path, with the family read from the expected = or PathP type |
at(p, i), or p @ i | The value of p at coordinate i. @ binds tighter than every infix operator except application. |
PathP(fun (i : Interval) => A(i), a, b) | The type of dependent paths from a : A(0) to b : A(1); see dependent paths. x = y is the case of a constant family. |
Reversing a path is reading it backwards: its value at i is p’s value at ~i. Written in full, and with the shorthand:
def reverse_path(A : U0, x, y : A, p : x = y) : y = x {
exact path(fun (i : Interval) => A, fun (i : Interval) => at(p, flip(i)));
}
def reverse_again(A : U0, x, y : A, p : x = y) : y = x {
exact path i => p @ ~i;
}
def constant_path(A : U0, x : A) : x = x {
exact path i => x;
}
def value_at_zero(A : U0, x, y : A, p : x = y) : p @ 0 = x {
exact refl(x);
}
def value_at_one(A : U0, x, y : A, p : x = y) : p @ 1 = y {
rfl;
}
reverse_again is the same term as reverse_path, with the family A read from the goal y = x. constant_path is refl(x). A path’s values at 0 and 1 are its endpoints by computation, which is how the kernel checks every endpoint:
def wrong_direction(A : U0, x, y : A, p : x = y) : x = y {
// Error: Type mismatch: found p @ 1 = p @ 0, expected x = y.
exact path i => p @ ~i;
}
The shorthand needs an expected path type to supply the family:
// Error: path i => ... needs an expected Path or PathP type.
def no_expected_type(A : U0, x : A) := path i => x;
A coordinate is not a term, and Interval is not a type:
import unat;
def coordinate_as_term(A : U0, x : A) : x = x {
// Error: Interval coordinates can only be used in interval arguments.
exact path i => typed(UNat, i);
}
def interval_as_type(i : Interval) := i; // Error: Untranslated name: Interval
Squares
A path between paths is a function of two coordinates: a square. Its four sides are the paths at j = 0 and j = 1, and the paths traced by its corners. path j => path i => … writes one directly. The outer path j reads its family from the goal, and each inner path i from the equality that the goal’s family gives at j.
Given a pointwise equality H between two functions, applying f and g along a path p gives two paths, and H at the two ends joins them. They form a square:
def naturality_square(A, B : U0, f, g : A -> B,
H : (forall a : A. f(a) = g(a)), x, y : A, p : x = y) :
PathP(fun (j : Interval) => H(x) @ j = H(y) @ j, cong(f, p), cong(g, p)) {
exact path j => path i => H(p @ i) @ j;
}
At j = 0, H(p @ i) @ 0 is f(p @ i), which traces cong(f, p); at j = 1, it traces cong(g, p). At i = 0 and i = 1 it traces H(x) and H(y). The goal is a PathP, a path over a family of equality types, because the type of the inner path changes with j; dependent paths describes them. The kernel checks all four sides.
Meets and joins
i & j is the smaller of two coordinates, their meet, and i | j the larger, their join; meet(i, j) and join(i, j) say the same. & binds tighter than |, and both tighter than @: p @ ~i & j | k is p @ (((~i) & j) | k). The kernel inspector prints them as ∧ and ∨. At the corners of the square they are the familiar “and” and “or”:
i | j | i & j | i | j |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
A path applied to a meet or a join is a square, a function of two coordinates, called a connection. Squares like these are needed wherever one side of a square must shrink to a point. Along an edge, i & 0 is 0 and i & 1 is i, so p @ i & j is constant at x where j = 0 and is p where j = 1; p @ i | j is p where j = 0 and constant at y where j = 1. Both facts hold by computation:
def meet_edges(A : U0, x, y : A, p : x = y) :
(refl(x) = (path i => p @ i & 0)) and (p = (path i => p @ i & 1)) {
exact (refl(refl(x)), refl(p));
}
def join_edges(A : U0, x, y : A, p : x = y) :
(p = (path i => p @ i | 0)) and (refl(y) = (path i => p @ i | 1)) {
exact (refl(p), refl(refl(y)));
}
Read along the other coordinate, the meet shrinks p towards its start and the join shrinks it towards its end. In to_start, the square p @ i & j is refl(x) at j = 0 and p at j = 1; in to_end, p @ i | j is p at j = 0 and refl(y) at j = 1:
def to_start(A : U0, x, y : A, p : x = y) :
PathP(fun (j : Interval) => x = p @ j, refl(x), p) {
exact path j => path i => p @ i & j;
}
def to_end(A : U0, x, y : A, p : x = y) :
PathP(fun (j : Interval) => p @ j = y, p, refl(y)) {
exact path j => path i => p @ i | j;
}
p : x = y, with i to the right and j upwards. Solid edges are p, dashed edges are constant. Read from bottom to top, to_start grows refl(x) into p, and to_end shrinks p into refl(y).The best-known use is the singleton of a point x: the type of pairs of an end y and a path x = y. It is contractible: it has a center, (x, refl(x)), and every element w is equal to it. The path from the center to w moves the end forward along w.2, and the meet grows the path along with it: at coordinate j the pair is the point w.2 @ j and the part of w.2 that reaches it, path i => w.2 @ i & j. At j = 0 that part is refl(x), and at j = 1 it is all of w.2. Read from j = 1 back to j = 0, the same path slides w back to the center, shrinking its path to refl(x).
def Singleton(A : U0, x : A) := exists y : A. x = y;
def singletons_contractible(A : U0, x : A) :
exists center : Singleton(A, x). forall w : Singleton(A, x). center = w {
exact (typed(Singleton(A, x), (x, refl(x))),
fun (w : Singleton(A, x)) =>
path j => (w.2 @ j, path i => w.2 @ i & j));
}
// Path induction, from paths: to prove C of every pair (y, p), prove it of
// the center and transport along the contraction.
def based_path_induction(A : U0, x : A, C : Singleton(A, x) -> U0,
base : C((x, refl(x))), w : Singleton(A, x)) : C(w) {
exact transport base along singletons_contractible(A, x).2(w) in C;
}
w = (y, p) in Singleton(A, x), at three values of j. At each j the pair is the point w.2 @ j, shown as a dot, and the part of p that reaches it, path i => w.2 @ i & j, highlighted: one row of to_start’s square.based_path_induction is the reason this matters: a statement about every path starting at x follows from the single case refl(x). In cubical type theory path induction is derived in this way, not assumed: the built-in path_induction elaborates to a transport over the segments path j => p @ i & j, the same meet. For the circle, contractibility has a consequence that surprises at first; see loops and based paths.
Picking the wrong one is caught at the edges. With a meet, the path at i runs from x to p @ i, not from p @ i to y:
def wrong_connection(A : U0, x, y : A, p : x = y) :
PathP(fun (i : Interval) => p @ i = y, p, refl(y)) {
// Error: Type mismatch: found p @ 0 = p @ i, expected p @ i = y.
exact path i => path j => p @ j & i;
}
Coordinates obey the laws of a De Morgan algebra: & and | are associative, commutative and distribute over each other, and ~(i & j) is ~i | ~j. They are not Boolean: i & ~i is not 0, since at i = 1/2 it is 1/2. The checker does not simplify it away:
def not_boolean(A : U0, x, y : A, p : x = y) : refl(x) = (path i => p @ i & ~i) {
// Error: Type mismatch: found refl(x) = refl(x), expected refl(x) = (path i => p @ i & ~i).
exact refl(refl(x));
}
The composition tubes of hand-built proofs use connections in the same way. A tube fun (k : Interval) => q @ k & i is constant where i = 0 and follows q where i = 1, and fun (k : Interval) => p @ k | ~i is constant where i = 0 and follows p where i = 1.
Dependent paths
A path p : x = y in A, together with a family of types C : A -> U0, gives a type at every point of the path: C(p @ i), running from C(x) at i = 0 to C(y) at i = 1. A dependent path over p runs through these types. Its value at each i lies in C(p @ i), and it goes from a : C(x) to b : C(y). Its type is PathP(fun (i : Interval) => C(p @ i), a, b), the PathP of the table above.
p stand the types C(p @ i). A dependent path, highlighted, crosses them from a : C(x) to b : C(y). Transporting a along p, dashed, gives an element of C(y), and an equality in C(y) joins it to b: the same fact, stated in one type.When the family is constant, every value lies in the one type, and a dependent path is an ordinary path. x = y is PathP(fun (i : Interval) => A, x, y), and the checker treats the two as the same type:
def constant_family(A : U0, x, y : A, p : x = y) : PathP(fun (i : Interval) => A, x, y) {
exact p;
}
Otherwise a and b have different types, so a = b does not type-check, and a dependent path is the way to relate them. The commonest comes from a dependent function f : forall a : A. C(a), which sends p to a path from f(x) to f(y); cong cannot give it, since f(x) = f(y) is not a type. There are three ways to build it:
def section_path(A : U0, C : A -> U0, f : (forall a : A. C(a)), x, y : A, p : x = y) :
PathP(fun (i : Interval) => C(p @ i), f(x), f(y)) {
exact apd_path(f, p);
}
def section_by_hand(A : U0, C : A -> U0, f : (forall a : A. C(a)), x, y : A, p : x = y) :
PathP(fun (i : Interval) => C(p @ i), f(x), f(y)) {
exact path i => f(p @ i);
}
def section_via_transport(A : U0, C : A -> U0, f : (forall a : A. C(a)),
x, y : A, p : x = y) :
PathP(fun (i : Interval) => C(p @ i), f(x), f(y)) :=
lift apd(f, x, y, p) along p in C;
apd_path(f, p)is the built-in form.path i => f(p @ i)is the same path written out: at eachi,fat the pointp @ ilies inC(p @ i), as the family requires, and the ends aref(x)andf(y).lift q along p in Cconstructs it from an equality after transport, below.
The other statement compares in one type. Transporting a along p gives an element of C(y), transport a along p in C, and comparing it with b there is an ordinary equality, (transport a along p in C) = b, in C(y). The two statements are equivalent. Given a proof q of that equality, lift q along p in C constructs the dependent path. For a dependent function, apd(f, x, y, p) supplies q. An element and its own transport are joined by a dependent path:
def to_its_transport(A : U0, C : A -> U0, x, y : A, p : x = y, a : C(x)) :
PathP(fun (i : Interval) => C(p @ i), a, transport a along p in C) :=
lift refl(transport a along p in C) along p in C;
All three operands of lift and transport are expressions. Give a longer equality proof a name first with let q : (transport a along p in C) = b { … }, then use lift q along p in C. Parenthesize nested keyword expressions. The family C and base path p are explicit; lift, like path i => …, reads its endpoints from an expected path type. Give a result type on a definition or local binding, or use typed(PathP(…), lift q along p in C). A non-path result type is refused:
import unat;
def not_a_path_goal(A : U0, C : A -> U0, x, y : A, p : x = y) : UNat {
exact lift 0 along p in C; // Error: lift needs an expected Path or PathP type; annotate the result type.
}
Squares are dependent paths too. The type of to_start in meets and joins, PathP(fun (j : Interval) => x = p @ j, refl(x), p), is a dependent path over the family of path types x = p @ j, whose ends change with j.
Function extensionality: ext
Two functions are equal when they agree at every input. For a goal f = g between functions, ext x; takes an input x and continues with the goal f(x) = g(x):
def pointwise_path(A, B : U0, f, g : A -> B, h : (forall x : A. f(x) = g(x))) : f = g {
ext x;
exact h(x);
}
def dependent_pointwise(A : U0, C : A -> U0, f, g : forall a : A. C(a),
h : forall a : A. f(a) = g(a)) : f = g {
ext a;
exact h(a);
}
Cubical paths make function extensionality provable: path i => fun x => h(x) @ i is a path from f to g. ext x; builds that term. It works for dependent functions too, provided the goal is f = g with f, g : forall x : A. C(x). It uses no assumption; FunExt builds the same term. Unlike rw, ext never closes the block: a statement proving f(x) = g(x) must follow, even when that holds by rfl.
import unat;
def not_functions(n : UNat) : n = n {
ext x; // Error: ext requires equality of functions.
rfl;
}
Composition
comp(family, base, walls…) fills from coordinate 0 to coordinate 1, starting at base. Picture a square with the base as its bottom edge and the walls as its sides: comp produces the top edge. A wall face(i, 0, fun (j : Interval) => …) gives the side where the outer coordinate i is 0, and likewise for 1. The kernel checks that each wall starts on the base and that walls agree where they meet. With no walls, comp is transport.
def join_(A : U0, x, y, z : A, p : x = y, q : y = z) : x = z {
exact path i => comp(fun (j : Interval) => A, p @ i,
face(i, 0, fun (j : Interval) => x),
face(i, 1, fun (j : Interval) => q @ j));
}
def move(A : U0, C : A -> U0, x, y : A, p : x = y, v : C(x)) : C(y) {
exact comp(fun (j : Interval) => C(p @ j), v);
}
join is how trans is built: the bottom edge is p, the left wall stays at x, and the right wall follows q. A wall that does not start on the base is rejected. Here the left wall starts at y, but the base starts at x:
def misplaced_wall(A : U0, x, y, z : A, p : x = y, q : y = z) : x = z {
exact path i => comp(fun (j : Interval) => A, p @ i,
face(i, 0, fun (j : Interval) => y), // Error: Composition tube disagrees with its base.
face(i, 1, fun (j : Interval) => q @ j));
}
fill(family, base, level, walls…) is the same filling stopped at the coordinate level, so it gives the whole square rather than its top edge. face_when(formula, wall) states a wall’s face as a formula built from on(i, 0), on(i, 1), and and or:
def filler(A : U0, x, y, z : A, p : x = y, q : y = z) :
PathP(fun (j : Interval) => x = q @ j, p, trans(p, q)) {
exact path j => path i => fill(fun (k : Interval) => A, p @ i, j,
face(i, 0, fun (k : Interval) => x),
face(i, 1, fun (k : Interval) => q @ k));
}
def join_by_formulas(A : U0, x, y, z : A, p : x = y, q : y = z) : x = z {
exact path i => comp(fun (j : Interval) => A, p @ i,
face_when(on(i, 0), fun (j : Interval) => x),
face_when(on(i, 1), fun (j : Interval) => q @ j));
}
Interval and face formulas are kept in a normal form of joins of meets. Some compact formulas have exponentially large normal forms. Rather than exhaust memory, the checker refuses any expansion beyond 4,096 clauses or a fixed work budget, with a lattice budget error. Split such a proof into smaller named steps.
Box notation: compose and fill
compose j in A from b { on i = 0 => x; on i = 1 => q @ j; } describes a composition by listing its walls. The direction j runs from 0 to 1. The base b lies at j = 0; the result lies at j = 1. In a square, the base is the bottom edge, the walls are the sides, and the result is the top edge.
| Part | Meaning |
|---|---|
compose j | Introduce the composition direction j. |
in A | The type along that direction. A may mention j, as in C(p @ j). |
from b | The base, checked in A with j = 0. |
on face => wall; | A wall on the stated face, with a value in A at each j. Every wall ends with a semicolon. |
fill j in A from b at k { … } | The same box filled as far as k, with its result in A with j = k. At 0 it gives the base; at 1 it gives the composition. |
The new direction j is in scope in the family A and the wall expressions. It is not in scope in the base b, the face conditions or the fill coordinate k. Those use names already in scope. In particular, a wall's equation refers to an outer coordinate, such as the i introduced by path i => below. The fill coordinate may be 0, 1, an outer coordinate or an interval expression.
Here the bottom follows p, the left wall stays at x, and the right wall follows q. The top therefore joins x to z. The filler gives the intermediate path from x to q @ k at each k:
def join_by_box(A : U0, x, y, z : A, p : x = y, q : y = z) : x = z := path i => compose j in A from p @ i {
on i = 0 => x;
on i = 1 => q @ j;
};
def filler_by_box(A : U0, x, y, z : A, p : x = y, q : y = z) :
PathP(fun (k : Interval) => x = q @ k, p, join_by_box(A, x, y, z, p, q)) := path k => path i => fill j in A from p @ i at k {
on i = 0 => x;
on i = 1 => q @ j;
};
// Output: fun (A : U0, x, y, z : A, p : x = y, q : y = z) => path i => compose j in A from p @ i { on i =
// 0 => x; on i = 1 => q @ j; }
print(evaluate(!!!fun (A : U0, x, y, z : A, p : x = y, q : y = z) => join_by_box(A, x, y, z, p, q)));
A face is an equation i = 0 or i = 1, or a formula made from these with and, or and parentheses. and binds more tightly than or: i = 0 and k = 1 or i = 1 means (i = 0 and k = 1) or i = 1. The constants 0 and 1 mean the empty face and the whole face. These are coordinate conditions; they have no equality carrier annotation =[T]. For a loop, one wall can cover both endpoint faces:
def loop_by_box(A : U0, x : A, p : x = x) : x = x :=
path i => compose j in A from p @ i {
on i = 0 or i = 1 => x;
};
The kernel checks that every wall agrees with the base at j = 0 and that walls agree wherever their faces overlap. No walls are inferred. Empty braces describe transport along the family:
def move_by_box(A : U0, C : A -> U0, x, y : A, p : x = y, v : C(x)) : C(y) :=
compose j in C(p @ j) from v {};
The box notation expands to the existing comp and fill forms. The first box above is comp(fun (j : Interval) => A, b, face(i, 0, fun (j : Interval) => x), face(i, 1, fun (j : Interval) => q @ j)). A compound face becomes face_when, with each equation i = 0 written as on(i, 0). A composition the kernel cannot reduce prints as a box, as the checked output above shows.
compose is reserved and cannot name a user definition or binder. The generated member T.Hom.compose remains callable. An invalid face formula reports E193; a box missing its closing brace reports E194.
Squares
import squares; names a square's edges. Square(a0_, a1_, a_0, a_1) is PathP(fun (i : Interval) => a_0 @ i = a_1 @ i, a0_, a1_): a path from the left edge a0_ to the right edge a1_, over the bottom edge a_0 and the top edge a_1, so that s @ i @ j is its point at i across and j up. The corners are a00, a01, a10 and a11, and an edge is named by its corners, _ standing for the coordinate that varies along it. The library builds squares by conversion: the reflexive square of a path, the naturality square of a homotopy along a path, transposition and both flips, double composition with its filler, of which trans is the case with a constant first edge, and horizontal and vertical composition. Two squares on the same three sides have equal tops, top_unique, so a square is an equation of composites, square_to_path : Square(a0_, a1_, a_0, a_1) -> trans(a0_, a_1) = trans(a_0, a1_), and path_to_square goes back, though not as its inverse by conversion. The naturality of a homotopy as an equation, naturality_path, and a map's action on a composite, cong_trans, follow. The inspector shows a square's edges and corners.
import squares;
def natural{{A, B : U0, x, y : A}}(f, g : A -> B, h : forall a : A. f(a) = g(a), p : x = y) :
Square(h(x), h(y), cong(f, p), cong(g, p)) := naturality(f, g, h, p);
def transpose_twice{{A : U0, a00, a01, a10, a11 : A, a0_ : a00 = a01, a1_ : a10 = a11, a_0 : a00 = a10,
a_1 : a01 = a11}}(s : Square(a0_, a1_, a_0, a_1)) : transpose(transpose(s)) = s {
rfl;
}
def filler_top{{A : U0, w, x, y, z : A}}(p : w = x, q : x = y, r : y = z) :
transpose(double_comp_filler(p, q, r)) @ 1 = double_comp(p, q, r) {
rfl;
}
Glue types
Glue(A, face(i, 0, T, e), …) is the type A, except that on each face it is T, glued to A along an equivalence e from T to A there. On a face that holds it is T, so a line of Glue types connects the types at its ends: this is how ua turns an equivalence into a path. Here e is an equivalence in the form the kernel checks, a function whose fibers are contractible: ContrEquiv(U, T, A) of the library’s import contractible_maps;, not the Equiv of import paths_;. The library’s univalence module builds univalence this way. face_when(formula, T, e) states a face as in composition.
glue(a, face(i, 0, t), …) is an element of a Glue type: a in A, and on each face, for each piece in order, a value t of that piece’s type whose image under its equivalence is a there. Its Glue type is the one it is checked at, given here by typed. unglue(g) is the base of g, so unglue of a glue term is its base. Composition through a line of Glue types transports along it:
import contractible_maps;
def glued(A : U0) : A = A :=
path i => Glue(A, face(i, 0, A, id_contr_equiv(U0, A)), face(i, 1, A, id_contr_equiv(U0, A)));
def moved(A : U0, a : A) : A := comp(fun (j : Interval) => glued(A) @ j, a);
def moved_computes : moved(Unit or Unit, left(tt)) = left(tt) := refl(typed(Unit or Unit, left(tt)));
def unglue_glue(A : U0, a : A) : a = a :=
path i => unglue(typed(Glue(A, face(i, 0, A, id_contr_equiv(U0, A))), glue(a, face(i, 0, a))));
A part on a face is checked there, where each of the face’s coordinates is its endpoint: in face(k, 0, …), k is 0, and a variable whose type mentions k has its type at 0. So a value may be an element g of the Glue type itself, which on its face is the glued type, and glue(unglue(g), face(k, 0, g)) is g:
import contractible_maps;
def glue_eta(A : U0) :=
path(
fun (k : Interval) => forall g : Glue(A, face(k, 0, A, id_contr_equiv(U0, A))). g = g,
fun (k : Interval) => fun (g : Glue(A, face(k, 0, A, id_contr_equiv(U0, A)))) =>
path i => glue(unglue(g), face(k, 0, g))
);
A glue term with no Glue type to be checked at is refused, and so is unglue of anything but an element of a Glue type:
def untyped_glue(A : U0, a : A) := glue(a); // Error: glue needs the Glue type it builds an element of: write typed(Glue(…), glue(…)).
def unglue_a_point(A : U0, a : A) := unglue(a); // Error: unglue takes an element of a Glue type.
Higher inductive types
An inductive declaration can also include path constructors, which build paths rather than points. Write a path constructor’s endpoint equality as its result type:
inductive Circle : U0 {
base;
loop : base = base;
}
// For each coordinate i, loop @ i is a point of Circle.
def start : loop @ 0 = base { rfl; }
def finish : loop @ 1 = base { rfl; }
base is a point, and loop is a path from base to itself. A path is a function of an interval coordinate: for each i, loop @ i is a point of Circle, and its ends loop @ 0 and loop @ 1 are base. So Circle has two kinds of points: base, and the points loop @ i along the loop.
A function out of Circle is defined by match, with a clause for each kind of point. A clause is written as the point it covers: loop @ i => e gives the result at loop @ i. The matched value is that point, not the path. This function goes around the loop backwards:
inductive Circle : U0 {
base;
loop : base = base;
}
def reverse(c : Circle) : Circle := match c {
base => base;
loop @ i => loop @ ~i;
};
def reverse_loop : cong(reverse, loop) = sym(loop) { rfl; }
At loop @ i, reverse returns loop @ ~i, where ~i is 1 − i. At i = 0 and i = 1 the point is base, so there the clause must agree with the base clause: loop @ ~0 is loop @ 1, which is base, and loop @ ~1 is loop @ 0, also base. Taken over all i, the clause traces a path between the results at base. Applying reverse along the whole loop, cong(reverse, loop), gives that path, sym(loop), and rfl checks this by computation.
A clause whose ends disagree with the point clause is rejected. Here the loop clause traces a path from 1 to 1, but the base clause requires one from 0 to 0:
import unat;
use unat;
inductive Circle : U0 {
base;
loop : base = base;
}
def broken(c : Circle) : UNat := match c { // Error: Type mismatch: found 1 = 1, expected 0 = 0.
base => 0;
loop @ i => 1;
};
A constant clause traces the constant path. flatten sends every point of the loop to 0, so along the loop it gives refl(0). A variable or _ after the base clause covers the points along the loop, as in flatten_rest. A path clause can also be omitted and its path proved instead: obligations by rfl proves the path the missing loop clause must give, 0 = 0.
import unat;
use unat;
inductive Circle : U0 {
base;
loop : base = base;
}
def flatten(c : Circle) : UNat := match c {
base => 0;
loop @ i => 0;
};
def flatten_loop : cong(flatten, loop) = refl(0) { rfl; }
def flatten_rest(c : Circle) : UNat := match c {
base => 0;
_ => 0;
};
def flatten_again(c : Circle) : UNat := match c {
base => 0;
} obligations by rfl;
Loops and based paths
Circle has a single point constructor, base, so every path the declaration gives, loop, refl(base) and their compositions, starts and ends at base. Consider the singleton of base, Singleton(Circle, base): the pairs of an end y and a path base = y, called based paths. Each loop q : base = base gives one, (base, q), and these are all the pairs whose end is base itself. It is tempting to conclude that the based paths are just the loops. They are not. The singleton is contractible, so all of its elements are equal, in particular (base, loop) and (base, refl(base)):
inductive Circle : U0 {
base;
loop : base = base;
}
def Singleton(A : U0, x : A) := exists y : A. x = y;
def around : typed(Singleton(Circle, base), (base, refl(base))) = typed(Singleton(Circle, base), (base, loop)) {
exact path j => (loop @ j, path i => loop @ i & j);
}
around in Singleton(Circle, base), at j = 0, 1/2 and 1. The end of the pair, the dot, travels once around the circle, through points loop @ j that are not base, and the path to it, highlighted, grows into the whole loop.around is the singleton’s contraction at (base, loop). It moves the end of the pair along the loop, through the points loop @ j, which for 0 < j < 1 are points of the circle other than base, and grows the path with it. As loops, refl(base) and loop are not equal. rfl does not prove it, and no proof can: the loops at base correspond to the integers, with loop as 1 and refl(base) as 0, as the circle’s fundamental group proves.
inductive Circle : U0 {
base;
loop : base = base;
}
def not_by_computation : loop = refl(base) {
rfl; // Error: Type mismatch: found loop = loop, expected loop = refl(base).
}
So a one-to-one match between the elements of two types, here between the loops at base and the based paths that end at base, is not an equivalence of types. An equivalence must also match the paths between elements, and the singleton has paths, like around, that move an element’s end through other points, where the loops at a fixed end have none.
A header can also specify a truncation level. It adds a canonical constructor named TypeName.squash enforcing that level:
| Header result | Meaning |
|---|---|
: U0 | A type in U0, with no truncation imposed |
: prop | A proposition: any two values are equal |
: set | A set: any two equality proofs with the same endpoints are equal |
: trunc(n) | A higher truncation level, for an integer n ≥ −1; prop is −1 and set is 0 |
: prop U1 | Both a truncation level and a universe |
import hlevels;
inductive Mere(A : U0) : prop {
point(value : A);
}
def same(A : U0, x, y : Mere(A)) : x = y := Mere.squash(x, y);
def discard(A : U0, x : Mere(A)) : Unit := match x {
point(value) => tt;
};
A match on a truncated type must also respect its squash constructor. Importing hlevels lets the checker generate that branch when it can establish the required level of the result; Unit is a proposition in discard. Otherwise, write the squash clause, as the point it covers: Mere.squash(x, y) @ i => …, or give level evidence in obligations.
The library’s truncation: Trunc
The library’s propositional truncation is such a declaration, in the module h1_truncation, for a type in any universe below UU0:
inductive Trunc(U < UU0, A : U) : prop U {
point(a : A);
}
Trunc(U, A) says that A has an element without providing one, and is a proposition in A’s own universe. Its point point(a), also merely(U, A, a), computes; its generated Trunc.squash(x, y) identifies any two of its elements; and mere_eliminate(U, V, A, P, proposition, map, t) maps it into a proposition P of any universe V below UU0, given proposition : IsProp(V, P) and map : A -> P. It is no assumption. The library’s excluded middle and choice conclude such truncations (truncation).
import h1_truncation;
def inhabited(A : U0, a : A) : Trunc(U0, A) := point(a);
def all_equal(A : U0, x, y : Trunc(U0, A)) : x = y := Trunc.squash(x, y);
def into_a_proposition(A, P : U0, proposition : IsProp(U0, P), map_ : A -> P, t : Trunc(U0, A)) : P :=
mere_eliminate(U0, U0, A, P, proposition, map_, t);
evaluate inhabited(Unit, tt) expecting merely(U0, Unit, tt);
Coherence obligations: obligations
In a match on a higher inductive type, point clauses define how the function computes on canonical values, while path and squash clauses are coherence obligations showing that the result respects the path constructors and truncation level. Point constructors must always appear in the main braces before obligations. Declared path clauses (and explicit TypeName.squash clauses) can be written either inside the match braces or in a trailing obligations section on a match expression, a match statement, or an induction statement:
| Form | Meaning |
|---|---|
obligations { c(xs) @ i => … } | Named path or squash clauses: expressions ending in ; in a match term, or proof blocks { … } in a match or induction statement (with optional with ih in an induction statement). |
obligations by rfl | Proves every omitted declared path clause by computation, when its goal is a homogeneous path (the motive does not vary along the constructor) whose endpoints compute to the same value. |
obligations by { … } | Proves the single omitted declared path clause with a proof block. Introduce the constructor's arguments, and the recursive results of its recursive arguments, with intro; put tactics such as rw, simp, simpa and calc inside the block. |
obligations by term | Supplies a term for the single omitted declared path clause: a function from the constructor's arguments, and the recursive results of its recursive arguments, to the path between the endpoint values. |
obligations by hlevel, obligations by hlevel with [h] | Synthesizes omitted declared path clauses (when the target fiber is a proposition) and the generated TypeName.squash clause using hlevel, with optional evidence hints. |
In obligations { … }, each clause binds the constructor's arguments and interval coordinates, and the kernel checks the faces of its cube, at 0 and 1 in each coordinate, against the images of the constructor's boundary: the point clauses, the clauses of earlier path constructors for a higher cell, and the recursive results of recursive arguments. When a single declared path constructor is omitted and proved with obligations by { … } or obligations by term, the goal quantifies over the constructor's arguments, then over the recursive result of each recursive argument, and asks for a path (or PathP, for a dependent motive) between the endpoint values; a proof block introduces all of them before proving the path:
import unat;
import hlevels;
import quotients;
use unat;
inductive Circle : U0 {
base;
loop : base = base;
}
def statement_clauses(x : Circle) : UNat {
match x {
base => { exact 0; }
}
obligations {
loop @ i => { exact 0; }
}
}
def by_proof_block(A : U0, R : A -> A -> U0, q : Quotient(U0, A, R)) : UNat := match q {
class(a) => 0;
} obligations by {
intro a, b, r;
rfl;
};
def by_clause_term(A : U0, R : A -> A -> U0, q : Quotient(U0, A, R)) : UNat := match q {
class(a) => 0;
} obligations by (fun (a, b : A, r : R(a, b)) => path i => 0);
// turn's argument x is recursive: the goal binds x, then its recursive
// result ih, and asks for the path ih = ih.
inductive Rec : U0 {
pt;
turn(x : Rec) : x = x;
}
def recursive_obligation(x : Rec) : Unit := match x {
pt => tt;
} obligations by {
intro y, ih;
rfl;
};
Automatic synthesis of squash and path obligations
A type declared with : prop, : set or : trunc(n) adds a canonical constructor TypeName.squash of dimension n + 2 (dimension 1 for prop, 2 for set, 3 for trunc(1)). Whenever TypeName.squash is omitted from a match or induction and hlevels is imported, directly or through a module that imports it such as quotients, the elaborator automatically synthesizes the TypeName.squash clause, whether the declared path constructors are written inside the match, placed in obligations { … }, or proved with obligations by ….
To build the missing clause, the elaborator binds the constructor's arguments, positions and recursive results, then runs the hlevel search to inhabit its top-dimensional path in the motive B(z). Because each path dimension reduces the required level by one, eliminating a : prop requires IsProp of the motive fiber, eliminating a : set requires IsSet (HasLevel(U, 1, …)), and eliminating : trunc(n) requires HasLevel(U, n + 1, …); for a dependent motive whose fiber varies along the path, the search lifts a transport equality into a PathP. It uses, in order:
- Evidence in scope and hints: hypotheses,
letbindings, and hints inobligations by hlevel with […], lifted by cumulativity when a lower level is given (a contractible type or proposition has every higher level). Quantified family evidence such asforall z : Q. IsSet(U, B(z))is automatically specialized to the fiberB(z). - H-level statements: a type that is itself an h-level statement (
IsContr,IsProp,IsSetorHasLevel) is a proposition, and so has every level. - Registered rules: lemmas registered with
hlevel_rule, such asprop_type_is_setfrompropositions. - Type structure:
Unit,Void,UNat, function types (->,forall), pair types (and,exists), path types (=,PathP), and any truncated inductive type's own.squashconstructor.
The synthesized clause is an ordinary kernel term built from the lemmas of hlevels and checked by the C kernel; in the workspace inspector, it appears as a coherence obligation for TypeName.squash. Whereas TypeName.squash is synthesized without writing obligations, a declared path constructor is never silently omitted: to discharge declared path constructors by h-level when eliminating into a proposition, write obligations by hlevel. When the h-level search needs an expression that is not a bare local variable or rule, pass it with obligations by hlevel with […]:
import unat;
import hlevels;
import quotients;
use unat;
inductive Circle : U0 {
base;
loop : base = base;
}
inductive Gpd(A : U0) : trunc(1) {
point(a : A);
}
// The motive z = z is a path type in a set (Quotient), hence a proposition and
// a set: Quotient.squash is synthesized automatically from the motive's shape.
def classes_have_loops(A : U0, R : A -> A -> U0, q : Quotient(U0, A, R)) : q = q :=
match q as z return z = z {
class(a) => refl(typed(Quotient(U0, A, R), class(a)));
} obligations {
relate(a, b, r) @ i => refl(class_path(U0, A, R, a, b, r) @ i);
};
// Quantified family evidence `h` is specialized to `B(z)` to synthesize the
// three-dimensional Gpd.squash clause of a 1-truncated type.
def gpd_elim(
A : U0, B : Gpd(A) -> U0, h : forall z : Gpd(A). HasLevel(U0, 2, B(z)),
f : forall a : A. B(point(a)), q : Gpd(A)
) : B(q) := match q as z return B(z) {
point(a) => f(a);
};
// Into a proposition (Unit), `obligations by hlevel` synthesizes the omitted
// declared `loop` clause.
def circle_to_unit(x : Circle) : Unit {
match x {
base => { exact tt; }
}
obligations by hlevel;
}
// `with [h(tt)]` supplies evidence that is not a bare variable in scope.
def with_level_hint(
A : U0, R : A -> A -> U0, B : U0, h : Unit -> IsSet(U0, B), b : B, q : Quotient(U0, A, R)
) : B := match q {
class(a) => b;
relate(a, a2, r) @ i => b;
} obligations by hlevel with [h(tt)];
A point constructor cannot be moved into obligations, and every declared path constructor must either have a clause or be discharged by obligations:
import unat;
use unat;
inductive Circle : U0 {
base;
loop : base = base;
}
// Error: base is a point constructor: give its computational clause in match, before obligations.
def point_in_obligations(x : Circle) : UNat := match x {} obligations {
base => 0;
loop @ i => 0;
};
import unat;
use unat;
inductive Circle : U0 {
base;
loop : base = base;
}
// Error: match on Circle needs a clause for loop. Give path clauses in obligations { … }, or obligations by { … }.
def missing_loop(x : Circle) : UNat := match x {
base => 0;
};
A single proof block or term after obligations by applies to one omitted declared path constructor; when a type has several, name each clause in obligations { … } (or use obligations by rfl when all are reflexive). And when the target's truncation level cannot be established for the generated .squash constructor, checking fails rather than admitting an unsound elimination:
import unat;
use unat;
inductive TwoLoops : U0 {
hub;
first : hub = hub;
second : hub = hub;
}
// Error: obligations by a term or proof block needs exactly one missing declared path clause; found 2. Use named obligations { … } for separate clauses.
def ambiguous_obligation(x : TwoLoops) : UNat := match x {
hub => 0;
} obligations by {
rfl;
};
import hlevels;
import quotients;
// Error: Cannot generate Quotient.squash: U0 must be of h-level 1; no local evidence, hint or rule gives that. Give checked h-level evidence, or an explicit obligation.
def into_not_a_set(A : U0, R : A -> A -> U0, q : Quotient(U0, A, R)) : U0 := match q {
class(a) => A;
relate(a, b, r) @ i => A;
};
Set quotients
The quotient of a type by a relation has a class for each element, with related elements' classes equal. import quotients; declares it as a higher inductive type that is a set, so a path constructor makes related classes equal and the set squash makes it a set:
inductive Quotient(U < UU0, A : U, R : A -> A -> U) : set U {
class(a : A);
relate(a, b : A, r : R(a, b)) : class(a) = class(b);
}
No class carries a chosen element, and nothing about quotients uses an assumption: a closed computation with them evaluates. A map into a set that sends related elements to equal values descends to the quotient, and computes on classes:
computable def descend(
U, V < UU0, A : U, R : A -> A -> U, B : V, set_ : IsSet(V, B), f : A -> B,
respects : Respects(U, V, A, R, B, f), q : Quotient(U, A, R)
) :
B := match q return B {
class(a) => f(a);
}
obligations {
relate(a, b, r) @ i => respects(a, b, r) @ i;
};
In descend, the point clause class(a) => f(a) gives the value on a class, the obligation relate(a, b, r) @ i => respects(a, b, r) @ i traces the path respects(a, b, r) : f(a) = f(b) along relate(a, b, r), and Quotient.squash is generated from set_ : IsSet(V, B). Here the naturals modulo parity, and parity read off a class:
import unat;
import hlevels;
import quotients;
use unat;
def parity(n : UNat) : UNat := match n {
zero => 0;
succ(k) => match parity(k) {
zero => 1;
succ(j) => 0;
};
};
def SameParity(m, n : UNat) : U0 := parity(m) = parity(n);
def Parities : U0 := Quotient(U0, UNat, SameParity);
def parity_of(x : Parities) : UNat :=
descend(U0, U0, UNat, SameParity, UNat, unat_is_set, parity, fun (m, n : UNat, r : SameParity(m, n)) => r, x);
evaluate parity_of(class(7)) expecting 1;
descend(U, V, A, R, B, set, f, respects, q) takes the map f : A -> B, evidence that B is a set, and respects : forall a, b : A. R(a, b) -> f(a) = f(b). The quotient's universe U and the result's V are independent. At a class it is f, by computation (descend_class), and it is the only map that is (descend_unique). The module also gives:
| Definition | What it gives |
|---|---|
class_path(U, A, R, a, b, r) | The path between the classes of related elements |
quotient_is_set(U, A, R) | The quotient is a set |
quotient_induction | A value in a family of sets at every element, from values at the classes that the relation's paths carry to each other |
quotient_induction_prop | The same into a family of propositions, where values at the classes are enough |
maps_agreeing_on_classes | Two maps into a set that agree on the classes are equal |
descend2 | A map of two arguments that respects the relation in each descends, one argument after the other |
quotient_effective, class_path_equiv | For an equivalence relation valued in propositions, elements with equal classes are related, and the paths between two classes are equivalent to the relation |
Effectiveness reads the relation back from a path of classes. It needs the relation to be an equivalence valued in propositions: quotient_effective takes that evidence, then the two elements and the path. The proof descends relatedness to an element into the set of propositions, which univalence makes a set (propositional extensionality), so it uses no assumption, and on closed classes it computes:
import unat;
import hlevels;
import quotients;
use unat;
def parity(n : UNat) : UNat := match n {
zero => 0;
succ(k) => match parity(k) {
zero => 1;
succ(j) => 0;
};
};
def SameParity(m, n : UNat) : U0 := parity(m) = parity(n);
def Parities : U0 := Quotient(U0, UNat, SameParity);
computable def one_three : typed(Parities, class(1)) = typed(Parities, class(3)) :=
class_path(U0, UNat, SameParity, 1, 3, refl(1));
computable def same_parity : SameParity(1, 3) := quotient_effective(
U0, UNat, SameParity, fun (m, n : UNat) => unat_is_set(parity(m), parity(n)), fun (n : UNat) => refl(parity(n)),
fun (m, n : UNat, r : SameParity(m, n)) => sym(r), fun (k, m, n : UNat, r : SameParity(k, m), t : SameParity(m, n)) => trans(r, t),
1, 3, one_three
);
evaluate same_parity expecting refl(1);
The library builds number systems this way. integers takes the quotient of pairs of binary naturals, (a, b) standing for a - b, by having the same difference, a + d = c + b: int(a, b) is that integer, and int_add, int_mul and int_neg descend from pairs. Effectiveness makes its equality decidable (int_decide), since pairs have the same difference or not. rationals takes the quotient of fractions, as the integers' field of fractions. Both are models of the algebraic theories, and their arithmetic computes:
import integers;
use nat;
def equal_or_not(x, y : Z) : Nat := match int_decide(x, y) return Nat {
left same => 1;
right different => 0;
};
// 2 - 5 and 0 - 3 are one integer, and (-2) * (-3) is 6.
evaluate equal_or_not(int(2, 5), int(0, 3)) expecting 1;
evaluate equal_or_not(int_mul(int(0, 2), int(0, 3)), int(6, 0)) expecting 1;
Pushouts
A pushout glues A and B along a span f : C -> A, g : C -> B. It is an ordinary declaration with a path constructor, in the pushout module:
inductive Pushout(U < UU0, V < UU0, W < UU0, C : U, A : V, B : W, f : C -> A, g : C -> B) : max(
U, max(V, W)
) {
inl(a : A);
inr(b : B);
push(c : C) : inl(f(c)) = inr(g(c));
}
After import pushout;, write its universe arguments explicitly, as for any declaration with universe parameters. The constructors take their instance from the expected type, and match eliminates a pushout: a clause for each side and a path clause push(c) @ i, which the kernel checks against the two side clauses at i = 0 and i = 1.
import unat;
import pushout;
def TwoPoints : U0 := Pushout(U0, U0, U0, UNat, Unit, Unit, fun (n : UNat) => tt, fun (n : UNat) => tt);
def west : TwoPoints := inl(tt);
def east : TwoPoints := inr(tt);
def bridge(n : UNat) : west = east {
exact push(n);
}
def collapse(value : TwoPoints) : Unit := match value {
inl(a) => tt;
inr(b) => tt;
push(n) @ i => tt;
};
pushout_induction in the same module packages this elimination into a family over the pushout, with a dependent path over each push(c). Pushouts are not built into the kernel: they compose, transport and compute by the same rules as every declared higher inductive type.
Suspensions
The suspension of A is the pushout of the two maps A -> Unit. Its operations are ordinary definitions in the suspension library, so they are written with the pushout constructors:
import pushout;
def Suspension(A : U0) : U0 := Pushout(U0, U0, U0, A, Unit, Unit,
fun (_ : A) => tt, fun (_ : A) => tt);
def north(A : U0) : Suspension(A) := inl(tt);
def south(A : U0) : Suspension(A) := inr(tt);
def meridian(A : U0, a : A) : north(A) = south(A) := push(a);
After import suspension_types;, Suspension(A) has the points north(A) and south(A) and, for every a : A, a path meridian(A, a) : north(A) = south(A). suspension_induction(A, C, atNorth, atSouth, coherence, point) eliminates into a family C over the suspension. The coherence case takes a : A and proves transport(C, north(A), south(A), meridian(A, a), atNorth) = atSouth.
import suspension_types;
def pole_path(A : U0, a : A) : north(A) = south(A) {
exact meridian(A, a);
}
def to_unit(A : U0, point : Suspension(A)) : Unit {
exact suspension_induction(A, fun (s : Suspension(A)) => Unit, tt, tt,
fun (a : A) => refl(tt), point);
}
suspension_meridian_beta(A, C, atNorth, atSouth, coherence, a) is the computation law on a meridian, stated as an equality: the constructed section maps meridian(A, a) to coherence(a). The circle and puncture models build on these operations; see the suspension examples and the circle proof.