Two kinds of equality
x = y is the identity type: its elements are paths from x to y, and a proof of x = y is such a path. It is a type like any other, so paths between paths are stated with another identity type.
Two notions of “equal” appear throughout the reference:
- Definitional equality (conversion): two terms compute to the same normal form, as
0 + nandndo. The checker uses it silently. It is never a proposition you state or prove. See conversion. - Propositional equality: a path
p : x = y, which must be constructed, as forn + 0 = n. Using it to replacexbyytakes an explicit operation:transport,cong,rworsimp.
refl(x) is the path from x to itself. It proves x = y exactly when x and y are definitionally equal, so it connects the two notions:
import unat;
use unat;
def zero_is_zero : 0 = 0 {
exact refl(0);
}
def numeral_is_successors : succ(succ(0)) = 2 {
exact refl(2);
}
def path_between_paths(A : U0, x : A) : refl(x) = refl(x) {
exact refl(refl(x));
}
import unat;
use unat;
def zero_is_one : 0 = 1 {
exact refl(0); // Error: Type mismatch: found 0 = 0, expected 0 = 1.
}
Carriers
The carrier of an equality is the type both sides belong to. x = y infers it. x =[T] y states it: both endpoints must have type T. This is the same identity type, not a cast or an assertion of definitional equality.
def explicit_carrier(A : U0, x : A) : x =[A] x {
exact refl(x);
}
def reverse_type_equality(A : U1, B : U1, p : A =[U1] B) : B =[U1] A {
exact sym(p);
}
In A =[U1] B, the endpoints are types and the carrier is a universe. Equalities between different types come from univalence; see extensionality and univalence. The carrier must be the type of both endpoints:
import unat;
def wrong_carrier(x : UNat) : x =[Unit] x {
exact refl(x); // Error: Type mismatch: found UNat, expected Unit.
}
Types that are definitionally equal need no univalence: refl proves them equal. When B does not mention a, exists a : A. B is a pair of an a : A and a value of B, whatever a is. That is the same type as A and B. In the same way, when B does not mention x, forall x : A. B is the type of functions from A to B, A -> B:
def exists_is_and(A : U0, B : U0) : (exists a : A. B) =[U0] (A and B) { // Warning: a is unused in the body: write A and … instead of exists a : A. ….
exact refl(A and B);
}
def forall_is_arrow(A : U0, B : U0) : (forall x : A. B) =[U0] (A -> B) { // Warning: x is unused in the body: write A -> … instead of forall x : A. ….
exact refl(A -> B);
}
Because the two forms are the same type, the checker warns about a quantified variable that its body does not mention and suggests the shorter form.
Operations on paths
| Operation | Data and result |
|---|---|
refl(x) | x = x |
sym(p), or ~p | For p : x =[T] y, the reversed path y =[T] x |
trans(p, q), or p ++ q | For p : x = y and q : y = z, the composite x = z |
cong(f, p) | For f : A -> B and p : x = y, the path f(x) = f(y) |
transport(C, x, y, p, value) | For p : x = y and value : C(x), an element of C(y). See transport. |
apd(f, x, y, p) | For f : forall a : A. C(a), a proof of transport(C, x, y, p, f(x)) = f(y) |
apd_path(f, p) | The same fact as a dependent path. See dependent paths. |
These are built into the language and need no import. They build cubical paths pointwise and use no assumption.
def reverse_path(A : U0, x, y : A, p : x = y) : y = x {
exact sym(p);
}
def join_paths(A : U0, x, y, z : A, p : x = y, q : y = z) : x = z {
exact trans(p, q);
}
def map_path(A, B : U0, f : A -> B, x, y : A, p : x = y) : f(x) = f(y) {
exact cong(f, p);
}
def apply_path(A, B : U0, f, g : A -> B, p : f = g, a : A) : f(a) = g(a) {
exact cong(fun (h : A -> B) => h(a), p);
}
~p and p ++ q are notation for sym(p) and trans(p, q), and check to the same paths. ~ binds tighter than @, so ~p @ i is (~p) @ i; ++ binds looser than + and tighter than =, and groups to the left, as a calc chain does: p ++ q ++ r is trans(trans(p, q), r).
def round_trip(A : U0, x, y, z : A, p : x = y, q : y = z) : x = x {
exact p ++ q ++ ~q ++ ~p;
}
def notation_is_trans(A : U0, x, y, z : A, p : x = y, q : y = z) : ~p ++ p ++ q = trans(trans(sym(p), p), q) {
exact refl(trans(trans(sym(p), p), q));
}
trans needs the first path to end where the second starts:
def gap_between(A : U0, x, y, z, w : A, p : x = y, q : z = w) : x = w {
exact trans(p, q); // Error: Path endpoints do not match.
}
import unat;
def not_a_path(f : UNat -> UNat, n : UNat) : f(n) = f(n) {
exact cong(f, n); // Error: cong requires a path.
}
cong needs a function with a fixed result type. For a dependent function, f(x) and f(y) have different types, so f(x) = f(y) does not type-check the way cong needs; use apd or apd_path:
def dependent_cong(A : U0, C : A -> U0, f : forall a : A. C(a), x, y : A, p : x = y) : f(x) = f(y) {
exact cong(f, p); // Error: Type mismatch: found C(y), expected C(x).
}
Some inferred pair projections do not keep enough equality information for sym, trans or cong. In that case, state the path first with let p : x = y := term;.
Transport
transport value along p in C moves value : C(x) along p : x = y to an element of C(y). It reads the endpoints from the type of p; the family C is written explicitly. The built-in call transport(C, x, y, p, value) remains available. along is a contextual separator, so it can also be used as an ordinary name.
A parenthesized value is allowed: transport (f(x)) along p in C. Parenthesize a whole compound value or nested transport, and parenthesize the whole transport before projecting from it or using it in an equality.
def move(A : U0, C : A -> U0, x, y : A, p : x = y, v : C(x)) : C(y) {
exact transport(C, x, y, p, v);
}
def move_along(A : U0, C : A -> U0, x, y : A, p : x = y, v : C(x)) : C(y) {
exact transport v along p in C;
}
def respects(A : U0, C : A -> U0, f : forall a : A. C(a), x, y : A, p : x = y) :
transport(C, x, y, p, f(x)) = f(y) {
exact apd(f, x, y, p);
}
The stated endpoints must be the path’s endpoints, in order:
def backwards(A : U0, C : A -> U0, x, y : A, p : x = y, v : C(y)) : C(x) {
exact transport(C, y, x, p, v); // Error: Transport endpoints do not match.
}
import unat;
use unat;
def not_a_path(C : UNat -> U0, v : C(0)) : C(0) {
exact transport(C, 0, 0, 0, v); // Error: transport requires a path.
}
To move backwards, transport along sym(p).
Path induction
path_induction(A, motive, base, x, y, p) is the eliminator of the identity type. The motive takes a, b : A and q : a = b and returns a type. The base case takes a : A and proves motive(a, a, refl(a)). The result proves motive(x, y, p). Informally: to prove something about every path, it is enough to prove it for reflexivity, provided both endpoints are free to vary. It uses no assumption.
def symmetric(A : U0, x, y : A, p : x = y) : y = x {
exact path_induction(A, fun (a, b : A, q : a = b) => b = a,
fun (a : A) => refl(a), x, y, p);
}
based_induction(U, V, A, x, motive, base, y, p) fixes the left endpoint x. The motive takes b : A and q : x = b. The base proves motive(x, refl(x)), and the result proves motive(y, p). U is the universe of A and V that of the motive, both written as concrete universes.
def based(A : U0, x, y : A, p : x = y,
C : forall b : A. (x = b) -> U0, c : C(x, refl(x))) : C(y, p) {
exact based_induction(U0, U0, A, x, C, c, y, p);
}
def swapped_endpoints(A : U0, x, y : A, p : x = y) : x = y {
// Error: Path induction endpoints/carrier do not match.
exact path_induction(A, fun (a, b : A, q : a = b) => a = b,
fun (a : A) => refl(a), y, x, p);
}
import unat;
def not_a_universe(A : U0, x, y : A, p : x = y,
C : forall b : A. (x = b) -> U0, c : C(x, refl(x))) : C(y, p) {
// Error: Based induction needs universes.
exact based_induction(UNat, U0, A, x, C, c, y, p);
}
The paths library
import paths_; provides named forms and laws: inverse_, concatenate and ap for sym, trans and cong, and laws such as inverse_left, right_unit and path_associative. Some take a universe argument first.
import paths_;
def reversed(A : U0, x, y : A, p : x = y) : y = x {
exact inverse_(U0, A, x, y, p);
}
def cancel(A : U0, x, y : A, p : x = y) : trans(sym(p), p) = refl(y) {
exact inverse_left(A, x, y, p);
}
The laws are propositional: trans(sym(p), p) is not definitionally refl(y), so refl does not prove it.
Propositions and sets
import hlevels; measures how much a type's paths carry, in every universe U below UU0. IsContr(U, A) says that A has a center with a path to every element, and IsProp(U, A) that any two elements are equal. HasLevel(U, n, A) is IsProp at n = 0, and at n + 1 it says that every path type of A has level n. IsSet(U, A) is level 1, so by conversion it says that any two parallel paths are equal.
import hlevels;
use unat;
def set_unfolds(A : U0) : IsSet(U0, A) = (forall x, y : A. forall p, q : x = y. p = q) {
rfl;
}
def props_are_sets(A : U0, h : IsProp(U0, A)) : IsSet(U0, A) {
exact prop_is_set(U0, A, h);
}
def pairs_of_sets(A : U0, B : A -> U0, hA : IsSet(U0, A), hB : forall a : A. IsSet(U0, B(a))) :
IsSet(U0, exists a : A. B(a)) {
exact sigma_has_level(U0, 1, A, B, hA, hB);
}
The module also proves that levels are cumulative and that having a level is a proposition. Retracts, function types, pairs, products and path types keep levels and contractibility, and subtypes keep levels. Hedberg's theorem says that a type with decidable equality is a set, as unat_is_set shows for UNat. The propositions of a universe form a set too, by univalence (propositional extensionality), and a set quotient is a set by its declaration.
Proving levels: hlevel
hlevel; closes a goal IsContr(U, A), IsProp(U, A), IsSet(U, A) or HasLevel(U, n, A). It also closes an equality x = y whose type is a proposition. It tries, in order:
- evidence in scope, or listed after
with, that states the level or a lower one, where a proposition or a contractible type has every level; - a level statement being itself a proposition;
- a rule whose statement matches the type: quantified evidence in scope or after
with, then a lemma registered withhlevel_rule; its parameters are read from the match, and its premises proved the same way; - the type's shape, at a numeral level: functions, pairs and paths reduce to their parts, and
Unit,VoidandUNathave their levels.
It needs import hlevels;. A quantified hint is a rule, so h below serves for B(a), and so would h in scope alone. The search spends counted fuel, and the kernel checks the proof it builds.
import hlevels;
def functions_into_nat(A : U0) : IsSet(U0, A -> UNat) {
hlevel;
}
def equal_in_a_proposition(A : U0, h : IsProp(U0, A), x, y : A) : x = y {
hlevel;
}
def from_a_hint(A : U0, B : A -> U0, h : forall x : A. IsSet(U0, B(x)), a : A) : IsSet(U0, B(a) and UNat) {
hlevel with [h];
}
hlevel_rule lemma; registers a checked lemma whose type states a level, for every hlevel after it and in the modules that import it. Each of the lemma's parameters must be read from the carrier of its statement, or be a premise, a level statement that the search proves in turn. A type that the shape rules cannot see into, such as a declared type, gets its level this way:
import hlevels;
use unat;
inductive Box(A : U0) : U0 {
box(a : A);
}
def unbox(A : U0, b : Box(A)) : A := match b {
box(a) => a;
};
def box_unbox(A : U0, b : Box(A)) : typed(Box(A), box(unbox(A, b))) = b := match b {
box(a) => refl(typed(Box(A), box(a)));
};
// A box is a retract of its contents.
def box_is_set(A : U0, setA : IsSet(U0, A)) : IsSet(U0, Box(A)) :=
retract_has_level(U0, 1)(A, Box(A), fun (b : Box(A)) => unbox(A, b), fun (a : A) => box(a),
fun (b : Box(A)) => box_unbox(A, b), setA);
hlevel_rule box_is_set;
def boxes_of_functions : IsSet(U0, Box(Box(Unit -> Unit))) {
hlevel;
}
A lemma whose parameter is neither read from its statement nor a premise is no rule, and is refused where it is registered. The library registers prop_type_is_set, so the propositions of a universe are a set. The same search fills a level statement that a call leaves out, such as a carrier's setness field in a model's T.make(…).
A set's evidence never equates two elements: UNat is a set, but not a proposition. A failure names the obligation nothing discharges:
import hlevels;
use unat;
def zero_is_one : 0 = 1 {
hlevel; // Error: hlevel could not prove 0 = 1; UNat is not a proposition: 0 and 1 differ.
}
import hlevels;
def unknown_codomain(A, B : U0) : IsSet(U0, A -> B) {
hlevel; // Error: hlevel could not prove IsSet(U0, A -> B): it needs B to be a set; no local evidence, hint or rule gives that.
}