OctoInformBeta

OpenAI preprint, September 2026 · §2. Structural properties

Lemma 9: The context and expected type stay fixed through reductions in annotations and binder bodies

Full beta reduction preserves typing.

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

Subject reduction concerns computation in a typing judgement whose context and expected type have already been chosen. Fix a pure type system specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), where SS is a collection of sorts, 𝒜⊆S2\mathcal A\subseteq S^2 is an arbitrary axiom relation, and ℛ⊆S3\mathcal R\subseteq S^3 is an arbitrary product-rule relation.✦

Terms over SS are the expressions generated by (1), where nn is a natural number and s∈Ss\in S: M,N,A,B::=n_∣s∣MN∣λx:A.M∣Πx:A.B.M,N,A,B ::= \underline n \mid s \mid M\,N \mid \lambda x:A.M \mid \Pi x:A.B.(1)✦ Binder names are source notation; the library’s variables are de Bruijn indices, with zero referring to the nearest binder. A context Γ\Gamma is a finite list of terms in newest-first order.

Substitution and Typing

The renaming M[ρ]M[\rho] of a term MM by a map ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N is the term obtained by replacing n_\underline n by ρ(n)_\underline{\rho(n)}.✦ It fixes sorts and acts recursively on applications and binder domains, using the lifted renaming ρ+\rho^+ in binder bodies. The simultaneous substitution M[σ]M[\sigma] in a term MM, for an assignment σ\sigma of terms to indices, is the term obtained by replacing n_\underline n by σ(n)\sigma(n), fixing sorts, and acting recursively with the lifted substitution σ+\sigma^+ in binder bodies.✦ These lifts and the shift ↑\uparrow are given by (2): ρ+(0)=0,ρ+(n+1)=ρ(n)+1,σ+(0)=0_,σ+(n+1)=σ(n)[↑],↑(n)=n+1.\begin{aligned} \rho^+(0)&=0,& \rho^+(n+1)&=\rho(n)+1,\\ \sigma^+(0)&=\underline 0,& \sigma^+(n+1)&=\sigma(n)[\uparrow],\\ \uparrow(n)&=n+1. \end{aligned}(2) For terms aa and bb, bound variable instantiation b[a/x]b[a/x] is the capture-avoiding substitution of aa for index zero in bb, using the single-variable substitution δa\delta_a of (3): δa(0)=a,δa(n+1)=n_,b[a/x]=b[δa].\delta_a(0)=a,\qquad \delta_a(n+1)=\underline n, \qquad b[a/x]=b[\delta_a].(3)

One-step beta reduction M→βNM\to_\beta N is the least relation containing (4) and closed under either position of an application, the annotation and body of an abstraction, and the domain and codomain of a dependent product: (λx:A.b)a→βb[a/x].(\lambda x:A.b)\,a\to_\beta b[a/x].(4)✦ Multi-step beta reduction M→β*NM\to_\beta^*N is the reflexive transitive closure of →β\to_\beta.✦ Beta convertibility M≡βNM\equiv_\beta N is the smallest equivalence relation containing →β\to_\beta.✦

For a context Γ\Gamma, a subject term MM and an expected type TT, the typing judgement Γ⊢M:T\Gamma\vdash M:T is the least relation generated by the axiom, variable and weakening rules in (5), together with product formation, abstraction, application and conversion in (6).✦ Here A,ΓA,\Gamma denotes extension by the newest entry AA, the letter ff ranges over terms, and the letters s,t,sis,t,s_i range over sorts. (s,t)∈𝒜[]⊢s:tΓ⊢A:sA,Γ⊢0_:A[↑]Γ⊢M:TΓ⊢A:sA,Γ⊢M[↑]:T[↑].\begin{gathered} \frac{(s,t)\in\mathcal A}{[]\vdash s:t} \qquad \frac{\Gamma\vdash A:s} {A,\Gamma\vdash\underline 0:A[\uparrow]} \\ \frac{\Gamma\vdash M:T\qquad\Gamma\vdash A:s} {A,\Gamma\vdash M[\uparrow]:T[\uparrow]}. \end{gathered}(5) Γ⊢A:s1A,Γ⊢B:s2(s1,s2,s3)∈ℛΓ⊢Πx:A.B:s3A,Γ⊢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{\Gamma\vdash A:s_1\qquad A,\Gamma\vdash B:s_2 \qquad(s_1,s_2,s_3)\in\mathcal R} {\Gamma\vdash\Pi x:A.B:s_3} \\ \frac{A,\Gamma\vdash b:B\qquad\Gamma\vdash\Pi x:A.B:s} {\Gamma\vdash\lambda x:A.b:\Pi x:A.B} \\ \frac{\Gamma\vdash f:\Pi x:A.B\qquad\Gamma\vdash a:A} {\Gamma\vdash f\,a:B[a/x]} \qquad \frac{\Gamma\vdash M:A\qquad\Gamma\vdash B:s\qquad A\equiv_\beta B} {\Gamma\vdash M:B}. \end{gathered}(6)

The Claim

Theorem 1 (Subject reduction). Suppose Γ⊢M:T\Gamma\vdash M:T. Every term NN with M→β*NM\to_\beta^*N has the typing judgement (7): Γ⊢N:T.\Gamma\vdash N:T.(7)✦ Every term NN with M→βNM\to_\beta N has the typing judgement (8): Γ⊢N:T.\Gamma\vdash N:T.(8)✦

What Is Checked

The statements range over typing judgements for arbitrary pure type system specifications and over full beta reduction.

If equality of sorts is decidable, then equality of terms is decidable.