greatitself.
Continue
research37 min studyLesson 995 in Mathematics

Identity types and path induction

Separate computation from equality evidence and derive transport coherence using the identity eliminator.

Before you begin
On this page

The question for today

What you’ll understand

  • Distinguish judgmental equality from inhabiting an identity type.
  • Use path induction to construct transport and its coherence laws.
  • Identify which equalities require an inductive proof rather than reduction alone.

Two expressions can be equal because the rules compute them to the same result, or because a term witnesses an identity between them. These are different judgments in intensional type theory. The identity eliminator explains how equality evidence can move data between indexed types and how paths compose. Its apparent simplicity is powerful, but it does not make every equality proof reflexivity or identify all parallel paths. We will check a transport law and contrast it with a familiar arithmetic equality that remains stuck under open computation.

Judgmental equality belongs to the checking rules

Judgmental equality compares expressions according to the chosen conversion rules, such as beta reduction and the computation equations of recursors. It is written here with a triple bar and is not itself an internal type whose evidence can be assumed as an ordinary variable. If two types are judgmentally equal, conversion lets a term checked at one be used at the other. The exact relation depends on which reduction and eta rules the theory declares.

An identity type instead expresses a proposition or higher type inside the theory. Reflexivity inhabits identity from an object to itself, including when the two displayed endpoints are judgmentally equal by conversion. Other identity proofs may be built with induction or additional assumptions. Intensional identity does not include unrestricted equality reflection: possessing a path does not automatically make the endpoints judgmentally interchangeable in every checker computation. Transport is the explicit bridge between their indexed fibers.

a≡b:A⟹refl⁡a:(a=Ab),p:(a=Ab) ⇏ a≡b as a conversion rule.a\equiv b:A\quad\Longrightarrow\quad \operatorname{refl}_a:(a=_A b),\qquad p:(a=_A b)\ \not\Rightarrow\ a\equiv b\text{ as a conversion rule}.
The second statement describes the absence of general equality reflection in the intensional theory used here.↔ Scroll wide equations horizontally.

Path induction reduces a dependent family to reflexivity

Fix an element a of A and a family C depending on an endpoint b and a path from a to b. To construct an element in every such C, provide the case with endpoint a and reflexivity path. The identity eliminator extends this base case to all endpoints and paths, with a judgmental computation rule at reflexivity. The endpoint must vary with the path in the motive; silently fixing both endpoints before applying induction can remove the generality that makes the rule valid.

Path induction does not state that every loop at a is equal to reflexivity. That conclusion would require an additional principle in general. Instead, it says that a suitably dependent construction over a moving endpoint is determined by its reflexive case. Applying the rule defines inverse paths, concatenation, action of a function on paths, and transport. Laws between those operations are then identity proofs, with some special reflexive cases computing directly.

C:∏b:A(a=b)→U,d:C(a,refl⁡a)⟹J(d,b,p):C(b,p).C:\prod_{b:A}(a=b)\to\mathcal U,\quad d:C(a,\operatorname{refl}_a)\quad\Longrightarrow\quad J(d,b,p):C(b,p).
The motive varies in b and p; the computation rule is J(d,a,refl)≡d.↔ Scroll wide equations horizontally.

Transport retains the dependency of the fiber

For a family B over A, a path from x to y induces a function from B of x to B of y. At reflexivity, that function computes to the identity. This makes transport useful for indexed vectors or finite sets: equality of indices supplies a principled way to move a value whose type mentions one index into the corresponding type mentioning the other. A syntactic rewrite tactic may construct this transport behind the scenes, but the underlying dependency remains.

Arithmetic illustrates why equality evidence can be necessary even when both expressions look obviously equivalent. Define addition by recursion on its first argument. Zero plus n computes to n immediately, while n plus zero remains blocked when n is an unknown variable. An induction proof constructs an identity from n plus zero to n; that proof does not retroactively add a new judgmental reduction rule for all open terms. Function extensionality and uniqueness of identity proofs are also separate questions, not consequences of this notation.

transport⁡B(p):B(x)→B(y),transport⁡B(refl⁡x,u)≡u.\operatorname{transport}_B(p):B(x)\to B(y),\qquad \operatorname{transport}_B(\operatorname{refl}_x,u)\equiv u.
Identity evidence moves a value between fibers, while the reflexive case has a specified computational reduction.↔ Scroll wide equations horizontally.

Work it through

Transport along two paths or along their concatenation

Let p:x=y, q:y=z, and u:B(x). Construct an identity between transporting u first along p and then q, and transporting it along p followed by q. Check a concrete reflexive instance in Fin(3).

  1. Both proposed results lie in B(z). State the desired equality with y, z, p, and q varying in the dependent motive, so that successive applications of path induction are legitimate.

  2. Apply path induction first to p and then to q. In the remaining reflexive case, each transport computes to the identity and the concatenation of the two reflexive paths computes to reflexivity under its chosen definition. Both sides reduce to u, and reflexivity finishes the proof.

  3. For the index three, take the family Fin over natural numbers, both paths reflexivity at three, and the element two of Fin(3). Each side computes to the same element two. The generic coherence proof extends this checked base case through path induction; it is not a claim that arbitrary p and q are judgmentally reflexive.

transport⁡B(q,transport⁡B(p,u))=transport⁡B(p⋅q,u).\operatorname{transport}_B(q,\operatorname{transport}_B(p,u))=\operatorname{transport}_B(p\mathbin{\cdot}q,u).
The concatenation convention p·q means first p, then q; the displayed generic equality is propositional.↔ Scroll wide equations horizontally.
The result

Transport respects concatenation up to a constructed identity, and its doubly reflexive Fin(3) instance computes to two.

The living notebook

Explore the model

Interactive lab

Interactive lab · modular

Keep an element inside its indexed finite fiber

Pause and Reset, then set modulus to 3 and additive step to 1. After two Steps predict residue 2, an element of Fin(3) used in the reflexive example. For a fresh comparison Reset and set modulus to 2 and step to 1: all residues are 0 or 1, so the old value 2 is not in that fiber. The instrument illustrates finite membership and does not manufacture a path between the different indices or perform transport. Parameter edits retain time; set both controls after each Reset.

Keep an element inside its indexed finite fiberAddition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Current readings: Residue r0: 0; Orbit period · m/gcd(m,a): 12; Distinct residues visited: 1 of 12. All parameters are adjustable with the labeled controls below.Repeated addition modulo 12: the current residue is 0, and the orbit period is 12.01234567891011+ 5mod 12An additive orbitn = 0rₙ = 0Period = 12Cycle starts at 0:0 → 5 → 10 → 3 →8 → 1 → 6 → 11 →4 → 9 → 2 → 7 → 0Exact residues · two additions per second
Additive orbitCurrent residue / next edge
Residue r0
0
Orbit period · m/gcd(m,a)
12
Distinct residues visited
1 of 12
t = 0 s

Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forChanging an index changes the allowed data; transport requires equality evidence rather than an arbitrary parameter edit.

Pause & reason

Check your understanding

For addition defined by recursion on its first argument, which statement about an unknown n is correct?

Your turn

Try it yourself

Describe a proof of n+0=n for the stated addition recursion. Give its base and successor cases, and explain why the open expression n+0 does not simply compute to n.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Use the motive asserting the identity at n, then apply successor to the induction hypothesis.

Compare with the solution

At zero, both sides compute to zero and reflexivity applies. At successor n, unfolding addition gives succ(n+0). The induction hypothesis is a path from n+0 to n; applying successor to that path gives a path from succ(n+0) to succ(n). This supplies the successor case. For an unknown n the first argument is neither visibly zero nor successor, so the recursor is blocked. The induction proof inhabits the identity type without changing that computational fact.

Keep the idea

Take it with you

  • Judgmental conversion and internal identity evidence are different notions.
  • Path induction uses a motive whose endpoint varies together with the path.
  • Transport coherence is proved by identity elimination rather than assumed as equality reflection.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.