OctoInformBeta

OpenAI preprint, September 2026 · §2. Structural properties

Lemma 12: Under system weak normalization, a typed witness persists with every original rule on a finite set of sorts

Localizing a failure of strong normalization.

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

The sort collection of a pure type system need not be finite. The question is whether a typed failure of strong normalization in a system with normal forms for every expression occurring as the subject or expected type of a derivable judgement needs the ambient system’s whole collection of sorts.

A pure type system specification 𝒫=(S,𝒜,ℛ)\mathcal P=(S,\mathcal A,\mathcal R) consists of a sort collection SS, an arbitrary axiom relation 𝒜⊆S2\mathcal A\subseteq S^2, and an arbitrary product-rule relation ℛ⊆S3\mathcal R\subseteq S^3.✦

Terms over SS form the collection Term⁡(S)\operatorname{Term}(S) generated by the grammar (1). M,N,A,B::=x∣s∣MN∣λx:A.M∣Πx:A.B,s∈S.M,N,A,B ::= x \mid s \mid M\,N \mid \lambda x:A.M \mid \Pi x:A.B, \qquad s\in S.(1)✦ Displayed variable names are source notation for de Bruijn indices, with index zero referring to the nearest enclosing binder; contexts are finite lists in newest-first order.

The variable renaming M[ρ]M[\rho] of a term MM over SS, for ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N, is the term obtained by replacing each free index nn by ρ(n)\rho(n).✦ The simultaneous substitution M[σ]M[\sigma] in a term MM over SS, for σ:ℕ→Term⁡(S)\sigma:\mathbb N\to\operatorname{Term}(S), is the term obtained by replacing each free index nn by σ(n)\sigma(n).✦ Both operations fix sorts and act recursively on applications and binder domains; under a binder, renaming fixes zero and sends n+1n+1 to ρ(n)+1\rho(n)+1, while substitution fixes zero and sends n+1n+1 to σ(n)\sigma(n) with free indices increased by one. For terms aa and bb over SS, bound variable instantiation b[a/x]b[a/x] is capture-avoiding substitution using the single variable substitution that sends zero to aa and each n+1n+1 to the variable of index nn.✦

Full one-step β\beta reduction →β\to_\beta on terms over SS is the least relation containing (2) and closed under application in either position, reduction in abstraction annotations and bodies, and reduction in product domains and codomains. (λx:A.b)a→βb[a/x].(\lambda x:A.b)\,a\to_\beta b[a/x].(2)✦ Write →β*\to_\beta^* for zero or more reduction steps, and ≡β\equiv_\beta for β\beta convertibility, the smallest equivalence relation containing →β\to_\beta.✦

For a context Γ\Gamma and terms M,AM,A over SS, the typing judgement Γ⊢𝒫M:A\Gamma\vdash_{\mathcal P}M:A is the least relation generated by the sort axioms ⌀⊢𝒫s:t\varnothing\vdash_{\mathcal P}s:t for (s,t)∈𝒜(s,t)\in\mathcal A, variable introduction, and weakening by a type AA with Γ⊢𝒫A:s\Gamma\vdash_{\mathcal P}A:s for some sort ss, together with the product, abstraction, application, and conversion rules.✦ A product Πx:A.B\Pi x:A.B has sort s3s_3 when Γ⊢𝒫A:s1\Gamma\vdash_{\mathcal P}A:s_1, x:A,Γ⊢𝒫B:s2x:A,\Gamma\vdash_{\mathcal P}B:s_2, and (s1,s2,s3)∈ℛ(s_1,s_2,s_3)\in\mathcal R. An abstraction λx:A.b\lambda x:A.b has type Πx:A.B\Pi x:A.B when x:A,Γ⊢𝒫b:Bx:A,\Gamma\vdash_{\mathcal P}b:B and that product has some sort in Γ\Gamma. Application of f:Πx:A.Bf:\Pi x:A.B to a:Aa:A has type B[a/x]B[a/x]. Conversion changes an expected type AA to BB when A≡βBA\equiv_\beta B and Γ⊢𝒫B:s\Gamma\vdash_{\mathcal P}B:s for some sort ss.

A valid context Γ\Gamma for 𝒫\mathcal P is a list generated from the empty context by extending a valid Γ\Gamma to x:A,Γx:A,\Gamma whenever Γ⊢𝒫A:s\Gamma\vdash_{\mathcal P}A:s for some sort ss.✦

A legal term MM for 𝒫\mathcal P in a context Γ\Gamma is a term occurring as the subject or expected type of a derivable typing judgement in that context, as in (3). Legal⁡𝒫(Γ,M)⇔∃A∈Term⁡(S),Γ⊢𝒫M:A∨Γ⊢𝒫A:M.\operatorname{Legal}_{\mathcal P}(\Gamma,M) \quad\Longleftrightarrow\quad \exists A\in\operatorname{Term}(S),\quad \Gamma\vdash_{\mathcal P}M:A\ \lor\ \Gamma\vdash_{\mathcal P}A:M.(3)✦

A β\beta normal form MM over SS is a term with no one-step β\beta reduct.✦ A term MM over SS is weakly normalizing if it has a reachable normal form M#M^\#, as specified in (4); the term MM is strongly normalizing, written SN⁡(M)\operatorname{SN}(M), if no infinite full β\beta reduction sequence begins at MM. WN⁡(M)⇔∃M#,M→β*M#∧∀N,M#↛βN.\operatorname{WN}(M) \quad\Longleftrightarrow\quad \exists M^\#,\quad M\to_\beta^*M^\# \ \land\ \forall N,\ M^\#\not\to_\beta N.(4)✦

System weak normalization of 𝒫\mathcal P is the condition (5) on every legal subject and expected type in every valid context. SWN⁡(𝒫)⇔∀Γ valid for 𝒫,∀M,Legal⁡𝒫(Γ,M)⇒WN⁡(M).\operatorname{SWN}(\mathcal P) \quad\Longleftrightarrow\quad \forall\Gamma\text{ valid for }\mathcal P,\ \forall M,\quad \operatorname{Legal}_{\mathcal P}(\Gamma,M)\Longrightarrow\operatorname{WN}(M).(5)✦

For D⊆SD\subseteq S, the induced restriction 𝒫|D\mathcal P|_D is the specification over DD retaining every original axiom and product rule on those sorts, given by (6). 𝒫|D=(D,𝒜∩D2,ℛ∩D3).\mathcal P|_D=(D,\mathcal A\cap D^2,\mathcal R\cap D^3).(6)✦

The Claim

Theorem 1. Suppose 𝒫\mathcal P is system weakly normalizing. Every nonempty subset D⊆SD\subseteq S satisfies (7). SWN⁡(𝒫|D).\operatorname{SWN}(\mathcal P|_D).(7)✦ Suppose also that Γ⊢𝒫M:T\Gamma\vdash_{\mathcal P}M:T and that MM is not strongly normalizing. There are a finite subset D⊆SD\subseteq S, a context Γ′\Gamma' over DD, and terms M′,T′∈Term⁡(D)M',T'\in\operatorname{Term}(D) satisfying (8). Γ′⊢𝒫|DM′:T′,¬SN⁡(M′),SWN⁡(𝒫|D).\Gamma'\vdash_{\mathcal P|_D}M':T', \qquad \neg\operatorname{SN}(M'), \qquad \operatorname{SWN}(\mathcal P|_D).(8)✦

In the paper, the result reads: if every legal expression of 𝒫\mathcal P is weakly normalizing for full β\beta reduction but some legal expression is not strongly normalizing, there are finite sets S0⊆SS_0\subseteq S, 𝒜0⊆𝒜∩S02\mathcal A_0\subseteq\mathcal A\cap S_0^2, and ℛ0⊆ℛ∩S03\mathcal R_0\subseteq\mathcal R\cap S_0^3 such that (S0,𝒜0,ℛ0)(S_0,\mathcal A_0,\mathcal R_0) has both properties.

What Is Checked

The finite counterexample statement (8) concerns a typed subject that fails strong normalization in a system satisfying (5); the restriction statement (7) concerns a nonempty subset of its sorts. Equality of terms is decidable whenever equality of sorts is decidable.