OctoInformBeta

OpenAI preprint, September 2026 Β· Β§2. Structural properties

Lemma 10: Their expected types admit sorts, and typed normal forms have four syntactic shapes

Neutral terms have unique types up to conversion.

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

Typing a variable applied to arguments raises a uniqueness question when axiom and product relations admit several outputs.

A pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) is a triple consisting of a collection of sorts SS, an arbitrary axiom relation π’œβŠ†SΓ—S\mathcal A\subseteq S\times S, and an arbitrary product-rule relation β„›βŠ†SΓ—SΓ—S\mathcal R\subseteq S\times S\times S.✦ A term MM over SS is an expression generated by (1), where xx ranges over variables and ss ranges 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)✦ Variables use de Bruijn indices, with zero referring to the nearest enclosing binder; the binder names in (1) are named notation for these terms. A context Ξ“\Gamma is a finite list of declarations in newest-first order.

Renaming by a map ρ:β„•β†’β„•\rho:\mathbb N\to\mathbb N is the operation on terms that replaces variable index nn by ρ(n)\rho(n); under a binder its lift fixes zero and sends n+1n+1 to ρ(n)+1\rho(n)+1.✦ A simultaneous substitution Οƒ\sigma is an assignment of a term to each variable index that acts on terms by replacing index nn by Οƒ(n)\sigma(n); under a binder its lift sends zero to variable zero and sends n+1n+1 to Οƒ(n)\sigma(n) with its free indices increased by one.✦ Both operations leave sorts fixed and act recursively on applications, binder annotations and binder bodies. The single-variable substitution determined by a term aa is the simultaneous substitution that sends zero to aa and n+1n+1 to variable nn.✦ Bound-variable instantiation b[a/x]b[a/x] of a body bb by a term aa is the term obtained by applying the single-variable substitution determined by aa to bb, avoiding capture under binders.✦

One-step Ξ²\beta reduction β†’Ξ²\to_\beta is the least relation containing the contraction in (2) and closed under reduction in either part of an application and in every annotation and body of an abstraction or dependent product: (Ξ»x:A.b)aβ†’Ξ²b[a/x].(\lambda x:A.b)\,a \to_\beta b[a/x].(2)✦ The relation ≃β\simeq_\beta of Ξ²\beta convertibility is the smallest equivalence relation containing β†’Ξ²\to_\beta.✦

Typing Ξ“βŠ’M:A\Gamma\vdash M:A is the least relation generated by the rules in (3), written with fresh binder names; extending a context shifts free indices in the variable rule’s expected type and in weakening’s subject and expected type.✦ (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}{[]\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} \\[1.2ex] \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} \\[1.2ex] \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]} \\[1.2ex] \frac{\Gamma\vdash M:A\quad\Gamma\vdash B:s\quad A\simeq_\beta B} {\Gamma\vdash M:B}. \end{gathered}(3)✦

A neutral term EE is a term that is a variable or an application with a neutral function, as in (4); the argument MM ranges over arbitrary terms: E::=x∣EM.E ::= x \mid E\,M.(4)✦ A Ξ²\beta normal form MM is a term with no outgoing one-step Ξ²\beta reduction, as specified by (5): βˆ„NMβ†’Ξ²N.\nexists N\; M\to_\beta N.(5)✦

The Claim

Theorem 1. Let P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) be a pure type specification and Ξ“\Gamma a context. Let MM be neutral, and suppose Ξ“βŠ’M:A\Gamma\vdash M:A and Ξ“βŠ’M:B\Gamma\vdash M:B. Then A≃βB.A\simeq_\beta B.(6)✦ For a neutral term MM with Ξ“βŠ’M:A\Gamma\vdash M:A, there is a sort s∈Ss\in S such that Ξ“βŠ’A:s.\Gamma\vdash A:s.(7)✦ Let NN be a Ξ²\beta normal form with Ξ“βŠ’N:T\Gamma\vdash N:T. Then, for suitable sorts and terms, one of the following holds: N=s(s∈S)orN is neutralorN=Ξ x:C.DorN=Ξ»x:C.b.\begin{gathered} N=s\ (s\in S)\quad\text{or}\quad N\text{ is neutral}\quad\text{or}\\ N=\Pi x:C.D\quad\text{or}\quad N=\lambda x:C.b. \end{gathered}(8)✦

What Is Checked

The statements (6) and (7) concern neutral terms and their expected types in a common context over an arbitrary pure type specification, while (8) concerns a term in Ξ²\beta normal form together with a typing judgement for that term and its expected type. Equality of terms over SS is decidable whenever equality of sorts in SS is decidable.