OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1: For every legal expression in every valid context, with full β\beta reduction

Weakly normalizing pure type systems normalize strongly.

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 pure type specification P=(S,A,R)P=(S,A,R) consists of a set SS of sorts, an axiom relation A⊆S×SA\subseteq S\times S and a product-rule relation R⊆S3R\subseteq S^3.✦ Both relations are arbitrary. The expressions of PP are generated by (1), where xx ranges over variables and ss over SS: M,N,U,V::=x∣s∣MN∣λx:U.M∣Πx:U.V.M,N,U,V ::= x \mid s \mid M\,N \mid \lambda x:U.\,M \mid \Pi x:U.\,V.(1)✦

A variable renaming ρ\rho is a map from variables to variables, acting on free occurrences without capture.✦ A simultaneous substitution σ\sigma is a map from variables to expressions; its action M[σ]M[\sigma] replaces free occurrences without capture.✦ The single-variable substitution [x:=N][x:=N] is a substitution that replaces the variable xx by the expression NN and leaves all other free variables unchanged.✦ The instantiation M[x:=N]M[x:=N] of a binder body MM with argument NN is the expression obtained by substituting NN for its bound variable xx.✦

Full one-step β\beta reduction →β\to_\beta is the relation on expressions obtained by contracting (2) at any occurrence, including either component of an application and the annotation and body of an abstraction or dependent product: (λx:U.M)N→βM[x:=N].(\lambda x:U.\,M)\,N \to_\beta M[x:=N].(2)✦ Write →β*\to_\beta^* for a finite sequence of zero or more reduction steps. The β\beta convertibility relation =β=_\beta is the smallest equivalence relation containing →β\to_\beta.✦

Typing and Legality

A context Γ\Gamma is a finite sequence of variable declarations x:Ux:U. The typing judgement Γ⊢M:U\Gamma\vdash M:U relates an expression MM to its expected type UU in Γ\Gamma and is generated by (3), where s,t,s1,s2,s3s,t,s_1,s_2,s_3 range over sorts and each newly declared variable xx is fresh for Γ\Gamma: (s,t)∈A⌀⊢s:tΓ⊢U:sΓ,x:U⊢x:UΓ⊢M:VΓ⊢U:sΓ,x:U⊢M:VΓ⊢U:s1Γ,x:U⊢V:s2(s1,s2,s3)∈RΓ⊢Πx:U.V:s3Γ,x:U⊢M:VΓ⊢Πx:U.V:sΓ⊢λx:U.M:Πx:U.VΓ⊢M:Πx:U.VΓ⊢N:UΓ⊢MN:V[x:=N]Γ⊢M:UΓ⊢V:sU=βVΓ⊢M:V.\begin{gathered} \frac{(s,t)\in A}{\varnothing\vdash s:t} \qquad \frac{\Gamma\vdash U:s}{\Gamma,x:U\vdash x:U} \\[6pt] \frac{\Gamma\vdash M:V\qquad\Gamma\vdash U:s} {\Gamma,x:U\vdash M:V} \\[6pt] \frac{\Gamma\vdash U:s_1\qquad \Gamma,x:U\vdash V:s_2\qquad(s_1,s_2,s_3)\in R} {\Gamma\vdash\Pi x:U.\,V:s_3} \\[6pt] \frac{\Gamma,x:U\vdash M:V\qquad \Gamma\vdash\Pi x:U.\,V:s} {\Gamma\vdash\lambda x:U.\,M:\Pi x:U.\,V} \\[6pt] \frac{\Gamma\vdash M:\Pi x:U.\,V\qquad\Gamma\vdash N:U} {\Gamma\vdash M\,N:V[x:=N]} \\[6pt] \frac{\Gamma\vdash M:U\qquad\Gamma\vdash V:s\qquad U=_\beta V} {\Gamma\vdash M:V}. \end{gathered}(3)✦

A valid context Γ\Gamma is a finite sequence of variable declarations built from the empty context by successive extensions x:Ux:U, where the part of Γ\Gamma preceding each declaration types UU at some sort ss.✦ A legal expression MM in Γ\Gamma is an expression occurring as either the subject or the expected type of a typing judgement, as in (4): Legal⁡P(Γ,M)⇔∃U,(Γ⊢M:U)∨(Γ⊢U:M).\operatorname{Legal}_P(\Gamma,M) \quad\Longleftrightarrow\quad \exists U,\; (\Gamma\vdash M:U)\ \lor\ (\Gamma\vdash U:M).(4)✦

Normalization

An expression MM is a β\beta normal form if it has no one-step β\beta reduct.✦ A weakly normalizing expression MM is an expression admitting a normal form M#M^\# with M→β*M#M\to_\beta^*M^\#.✦ A strongly normalizing expression MM is an expression from which every β\beta reduction sequence is finite.✦

The system properties WN⁡(P)\operatorname{WN}(P) and SN⁡(P)\operatorname{SN}(P) require, respectively, weak and strong normalization of every legal expression in every valid context.

The Claim

Theorem 1. Let P=(S,A,R)P=(S,A,R) be a pure type specification satisfying WN⁡(P)\operatorname{WN}(P). Then SN⁡(P).\operatorname{SN}(P).(5)✦

What Is Checked

The assertion (5) is stated for the typing and full β\beta reduction of an arbitrary pure type specification, with legality (4) quantified over valid contexts.

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