Cubist

LANGUAGE REFERENCE · CHAPTER 7

Equality and paths

Identity types and their operations, transport, path induction, and propositions and sets.

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 + n and n do. 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 for n + 0 = n. Using it to replace x by y takes an explicit operation: transport, cong, rw or simp.

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

OperationData and result
refl(x)x = x
sym(p), or ~pFor p : x =[T] y, the reversed path y =[T] x
trans(p, q), or p ++ qFor 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 with hlevel_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, Void and UNat have 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.
}