Equality by computation
Chapter 1 accepted refl(4) as evidence of 2 + 2 = 4 because 2 + 2 computes to 4. This chapter says what computing means, and where the checker relies on it.
The checker accepts a term when its type is definitionally equal to the type required. Two terms are definitionally equal when they compute to the same normal form, a term in which no reduction step applies anywhere. Bound names do not matter: fun (x : A) => x and fun (y : A) => y are the same function. refl and rfl prove an equality exactly when its sides are definitionally equal. The reduction steps are:
- beta: a function applied to an argument computes, so
(fun (n : UNat) => succ(n))(0)is1; - delta: a named definition unfolds to its checked body;
- eliminator rules:
induction,match,unpackand the other eliminators compute on constructors, so2 + 2is4butn + 0is stuck on the variablen; - eta: a function equals
fun x => f(x), and a pair equals the pair of its components; - cubical rules: a path at
0or1is its endpoint, and interval formulas are compared in normal form; see cubical paths.
The checker compares two types this way wherever one must match another: when exact gives a value for the goal, when an argument meets its parameter’s type, when intro looks for a function type in the goal, and when let name : T := term; checks term. In the REPL, evaluate shows a term’s normal form.
import unat;
use unat;
def beta : (fun (n : UNat) => succ(n))(0) = 1 {
rfl;
}
def add_two(n : UNat) := succ(succ(n));
def delta : add_two(1) = 3 {
rfl;
}
def eliminators : match typed(Unit or UNat, right(4)) return UNat { left u => 0; right n => n; } = 2 + 2 {
rfl;
}
import unat;
use unat;
def function_eta(A, B : U0, f : A -> B) : f = fun (x : A) => f(x) {
rfl;
}
def pair_eta(p : UNat and UNat) :
p = unpack p as (a, b) return UNat and UNat { typed(UNat and UNat, (a, b)); } {
rfl;
}
def pair_projection : typed(UNat and UNat, (2, 5)).2 = 5 {
rfl;
}
An eliminator applied to a variable does not compute, so an equality that needs a case analysis or induction on the variable is not definitional. It is a theorem, proved with a lemma, rw or simp:
import unat;
use unat;
def plus_zero(n : UNat) : n + 0 = n {
rfl; // Error: Type mismatch: found n + 0 = n + 0, expected n + 0 = n.
}
Such an equality is propositional: it holds, but only by a proof, a path that the chapter on equality and paths describes. The checker never uses a theorem automatically. A proved equality such as commutativity is a path, not a reduction rule; rw and simp use it only when it is named in the proof or registered with simp_rule.
Definitions unfold
A definition unfolds wherever conversion needs its value: conversion opens boxed_successor(1) to succ(1), which is the numeral 2. There is no separate operation that unfolds a term on request, and no way to keep a definition folded; conversion unfolds definitions as it needs them.
import unat;
use unat;
def boxed_successor(n : UNat) := succ(n);
def opened_is_two : boxed_successor(1) = 2 {
exact refl(2);
}
def opened_in_a_type(v : boxed_successor(0) = 1) : 1 = 1 {
exact v;
}
Unfolding hints
Earlier versions of the checker needed to be told which definitions to unfold. The syntax remains, so older proofs still check, but new proofs do not need it. with unfolding [name₁, name₂] { expression } checks one expression as a definition of its own. The list names already checked definitions; the braces hold one expression, without a trailing semicolon. Empty lists and nested scopes are allowed. The names once steered the kernel’s conversion search, which was retired on 2026-10-02; the checker now unfolds whatever a comparison needs, so the list has no further effect.
import unat;
use unat;
def identity(n : UNat) := n;
def identity_zero : identity(0) = 0 {
exact with unfolding [identity] { refl(0) };
}
def twice(n : UNat) := identity(identity(n));
def nested : twice(0) = 0 {
exact with unfolding [twice] { with unfolding [identity] { refl(0) } };
}
def no_hints : 0 = 0 {
exact with unfolding [] { refl(0) };
}
The compiler keeps the result as a checked helper definition, so the enclosing proof can reuse it without expanding it again. The names change nothing else: never the type, the assumptions or the proof obligations, and they are no evidence of an equality. evaluate ignores them.
import unat;
use unat;
def unknown_hint : 0 = 0 {
// Error: No checked definition to unfold: missing_name
exact with unfolding [missing_name] { refl(0) };
}
Only top-level definitions can be listed; a parameter or local name is not one:
import unat;
def local_hint(n : UNat) : n = n {
exact with unfolding [n] { refl(n) }; // Error: No checked definition to unfold: n
}
def identity(n : UNat) := n;
def statement_in_braces : identity(0) = 0 {
exact with unfolding [identity] { refl(0); }; // Error: Expected '}', found ';'.
}