OctoInformBeta

OpenAI preprint, September 2026 · §2. Structural properties

Lemma 11: With a shape classification for sorted normal expressions and equality of normal forms under conversion

Normal forms retain typing under weak 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

A typing judgement relates an expression to an expected type, and both may contain β\beta redexes. Normalizing a subject and normalizing its expected type are distinct operations. The outer shape of an expression also matters when that expression is normal and has a sort as its type.

A pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) consists of a collection SS of sorts, an axiom relation 𝒜⊆S×S\mathcal A\subseteq S\times S, and a product-rule relation ℛ⊆S×S×S\mathcal R\subseteq S\times S\times S.✦ Both relations are arbitrary. The terms over SS are generated by the grammar in (1), where xx denotes a variable and s∈Ss\in S a sort: 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)✦ The variables in (1) are written with names; in de Bruijn notation, index zero denotes the nearest enclosing binder. Contexts are finite lists in newest-first order, with x:A,Γx:A,\Gamma denoting extension of Γ\Gamma.

A variable renaming ρ\rho is a map on variable indices, acting recursively on terms.✦ Under a binder its lift fixes zero and sends n+1n+1 to ρ(n)+1\rho(n)+1. A simultaneous substitution σ\sigma is a map from variable indices to terms, extended recursively to terms.✦ Its lift under a binder fixes index zero and replaces index n+1n+1 by σ(n)\sigma(n) with its free indices increased by one. Both operations act on the annotations as well as the bodies of abstractions and products. The single-variable substitution determined by a term aa sends zero to aa and each n+1n+1 to the variable of index nn.✦ Bound-variable instantiation b[a/x]b[a/x] of a body bb by a term aa is the capture-avoiding action on bb of the single-variable substitution determined by aa, written in named notation.✦

One-step β\beta reduction →β\to_\beta is the least relation containing the contraction in (2) and closed under every term constructor, including abstraction annotations and the domains and bodies of dependent products: (λ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 such steps. β\beta convertibility ≡β\equiv_\beta is the smallest equivalence relation containing →β\to_\beta.✦

The typing judgement Γ⊢M:A\Gamma\vdash M:A is the least relation generated by the rules in (3), where ⋅\cdot denotes the empty context and context extension uses a fresh variable xx: (s,t)∈𝒜⋅⊢s:tΓ⊢A:sx:A,Γ⊢x:AΓ⊢M:BΓ⊢A:sx:A,Γ⊢M:BΓ⊢A:s1x:A,Γ⊢B:s2(s1,s2,s3)∈ℛΓ⊢Πx:A.B:s3x:A,Γ⊢b:BΓ⊢Πx:A.B:sΓ⊢λx:A.b:Πx:A.BΓ⊢f:Πx:A.BΓ⊢a:AΓ⊢fa:B[a/x]Γ⊢M:AΓ⊢B:sA≡βBΓ⊢M:B.\begin{gathered} \frac{(s,t)\in\mathcal A}{\cdot\vdash s:t} \qquad \frac{\Gamma\vdash A:s}{x:A,\Gamma\vdash x:A} \qquad \frac{\Gamma\vdash M:B\quad\Gamma\vdash A:s} {x:A,\Gamma\vdash M:B} \\[1ex] \frac{\Gamma\vdash A:s_1\quad x:A,\Gamma\vdash B:s_2 \quad(s_1,s_2,s_3)\in\mathcal R} {\Gamma\vdash\Pi x:A.B:s_3} \\[1ex] \frac{x:A,\Gamma\vdash b:B\quad\Gamma\vdash\Pi x:A.B:s} {\Gamma\vdash\lambda x:A.b:\Pi x:A.B} \qquad \frac{\Gamma\vdash f:\Pi x:A.B\quad\Gamma\vdash a:A} {\Gamma\vdash f\,a:B[a/x]} \\[1ex] \frac{\Gamma\vdash M:A\quad\Gamma\vdash B:s\quad A\equiv_\beta B} {\Gamma\vdash M:B}. \end{gathered}(3)✦ A valid context Γ\Gamma is a finite list generated from the empty context by adjoining x:Ax:A to a valid context Δ\Delta whenever Δ⊢A:s\Delta\vdash A:s for some sort ss.✦ A legal term MM in Γ\Gamma is a term occurring as a subject or an expected type of a typing judgement, as specified in (4): Legal⁡P(Γ,M)⇔∃A(Γ⊢M:A∨Γ⊢A:M).\operatorname{Legal}_P(\Gamma,M) \quad\Longleftrightarrow\quad \exists A\,\bigl(\Gamma\vdash M:A\ \lor\ \Gamma\vdash A:M\bigr).(4)✦

A term MM is β\beta normal if it has no one-step β\beta reduct.✦ A term MM is weakly normalizing if some β\beta normal term is reachable from MM by →β*\to_\beta^*.✦ For a weakly normalizing term MM, a chosen normal form M#M^\# is a β\beta normal term reachable from MM by →β*\to_\beta^*, as specified in (5): M→β*M#,Normal⁡(M#).M\to_\beta^*M^\#, \qquad \operatorname{Normal}(M^\#).(5)✦ A system PP is weakly normalizing if every legal term in every valid context is weakly normalizing, including subjects and expected types.✦

A neutral term MM is a variable applied to zero or more arguments, each argument being an arbitrary term.✦

The Claim

Theorem 1. Let PP be a weakly normalizing pure type system and suppose Γ⊢M:A\Gamma\vdash M:A. The subject and expected type conclusions are (6) and (7), respectively: Γ⊢M#:A.\Gamma\vdash M^\#:A.(6)✦ Γ⊢M:A#.\Gamma\vdash M:A^\#.(7)✦ For any pure type system, suppose Γ⊢M:s\Gamma\vdash M:s for a sort ss and MM is β\beta normal. Its shape satisfies (8): (∃t∈S,M=t)∨Neutral⁡(M)∨(∃A,B,M=Πx:A.B).\bigl(\exists t\in S,\ M=t\bigr) \ \lor\ \operatorname{Neutral}(M) \ \lor\ \bigl(\exists A,B,\ M=\Pi x:A.B\bigr).(8)✦ For weakly normalizing terms MM and NN with M≡βNM\equiv_\beta N, their chosen normal forms satisfy (9): M#=N#.M^\#=N^\#.(9)✦

What Is Checked

The typing conclusions concern the judgement in (3) under system weak normalization; the shape conclusion assumes sorted typing and normality, while the conversion conclusion concerns weakly normalizing terms independently of typing. Equality of the terms in (1) is decidable whenever equality of sorts in SS is decidable.