OctoInformBeta

OpenAI preprint, September 2026 · §3. Sort profiles and normalization candidates

Lemma 17: A finite argument spine with strongly normalizing annotation, body, arguments and contractum

Sufficient conditions for strongly normalizing head expansions.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A head β\beta redex can stand at the front of a finite argument spine. Full β\beta reduction also acts inside the abstraction’s annotation and body, and inside each argument of the spine.

The terms over a sort collection SS form the smallest collection generated by (1), where xx ranges over variables and ss over SS. M,N,A,B::=x∣s∣MN∣λx:A.M∣Πx:A.B.M,N,A,B ::= x \mid s \mid M\,N \mid \lambda x:A.M \mid \Pi x:A.B.(1)✦ Names denote binders in this notation; de Bruijn indices count outwards from the nearest enclosing binder, starting at zero.

Simultaneous substitution for an assignment σ\sigma of terms to variable indices is the operation on terms that replaces the variable of index nn by σ(n)\sigma(n) and fixes sort constants. It acts recursively on both parts of an application and on the annotation of an abstraction or the domain of a dependent product. Under either binder it uses the lifted assignment: index zero maps to the variable of index zero, and index n+1n+1 maps to σ(n)\sigma(n) with every free index increased by one.

The single-variable substitution σa\sigma_a associated with a term aa is the assignment in (2), where vnv_n denotes the variable of index nn. σa(0)=a,σa(n+1)=vn.\sigma_a(0)=a,\qquad \sigma_a(n+1)=v_n.(2)✦ Bound variable instantiation b[a/x]b[a/x] is simultaneous substitution of σa\sigma_a into the body bb of a binder named xx.✦

One-step β\beta reduction →β\to_\beta on annotated terms is the least relation containing (3) and closed under application in either position, dependent products in the domain and codomain, and abstractions in the annotation and body. (λx:A.b)a→βb[a/x].(\lambda x:A.b)\,a \to_\beta b[a/x].(3)✦ A term MM is strongly normalizing, written SN⁡(M)\operatorname{SN}(M), when no infinite sequence of these full β\beta reductions begins at MM.✦

For a term ff and a finite argument list a→\vec a, iterated application fa→f\,\vec a is the left-associated application defined by (4), where [][] denotes the empty list and a::a→a::\vec a denotes the list with first entry aa and remaining entries a→\vec a. f[]=f,f(a::a→)=(fa)a→.f\,[] = f,\qquad f\,(a::\vec a)=(f\,a)\,\vec a.(4)✦ Argument list reduction a→→argsa→′\vec a\to_{\mathrm{args}}\vec a\,' is the relation on finite lists of terms in which exactly one entry is replaced by a one-step β\beta reduct and all other entries remain fixed.✦ A finite argument list a→\vec a of terms is strongly normalizing when no infinite sequence of argument list reductions begins at a→\vec a.✦

The Claim

Theorem 1. Let AA be an annotation, bb an abstraction body with bound variable xx, aa a term, and a→\vec a a finite argument list. Suppose that AA, bb and aa are strongly normalizing, that a→\vec a is a strongly normalizing argument list, and that b[a/x]a→b[a/x]\,\vec a is strongly normalizing. The head expansion satisfies (5). SN⁡(((λx:A.b)a)a→).\operatorname{SN}\bigl(((\lambda x:A.b)\,a)\,\vec a\bigr).(5)✦

What Is Checked

The claim (5) is stated over annotated terms with capture-avoiding bound variable instantiation and full β\beta reduction, using strong normalization of terms and of finite lists under argument list reduction.

When equality of sorts in SS is decidable, equality of terms over SS is decidable.