OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Specification, expressions, typing, and normalization: Arbitrary sort specifications, annotated expressions, and normalization of subjects and expected types under full beta reduction

Typing and normalization in pure type systems.

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

For an annotated dependent lambda calculus, normalization asks whether a term and its expected type admit normal forms, or whether all their beta reductions terminate. The admissible typing judgements depend on sort axioms and dependent product rules.

The Definition

Definition 1. A pure type specification PP is a triple consisting of a set SS of sorts and arbitrary axiom and product-rule relations, as in (1). P=(S,𝒜,ℛ),𝒜⊆S×S,ℛ⊆S×S×S.P=(S,\mathcal A,\mathcal R), \qquad \mathcal A\subseteq S\times S, \qquad \mathcal R\subseteq S\times S\times S.(1)✦

An expression MM over the sort set SS is an annotated lambda term generated by (2), where xx ranges over variables and ss 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.(2)✦ A variable renaming ρ\rho on expressions over SS is a map from free variables to variables that respects binding.✦ A simultaneous substitution σ\sigma on expressions over SS is a map from free variables to expressions that acts on expressions without capture.✦ A single-variable substitution [a/x][a/x] on expressions over SS is a map from free variables to expressions that sends the variable xx to an expression aa and leaves the other free variables fixed; its action b[a/x]b[a/x] on a binder body bb is bound-variable instantiation.

Full beta reduction →β\to_\beta on expressions over SS is the least relation satisfying (3), where C[−]C[-] ranges over expression contexts with one hole, including annotations and binder bodies. (λx:A.b)a→βb[a/x],M→βNC[M]→βC[N].\begin{gathered} (\lambda x:A.\,b)\,a \to_\beta b[a/x], \\[4pt] \frac{M\to_\beta N}{C[M]\to_\beta C[N]}. \end{gathered}(3)✦ Beta convertibility =β=_\beta on expressions over SS is the least equivalence relation containing →β\to_\beta; the notation →β*\to_\beta^* denotes the reflexive transitive closure of →β\to_\beta.

In named variable notation, a context is a finite sequence Γ=x1:A1,…,xn:An\Gamma=x_1:A_1,\ldots,x_n:A_n; an extension Γ,x:A\Gamma,x:A uses a fresh xx. For a fixed specification PP, the typing judgement Γ⊢M:A\Gamma\vdash M:A is the least relation closed under the rules in (4), where t,s1,s2,s3t,s_1,s_2,s_3 range over sorts and ff over expressions. (s,t)∈𝒜⌀⊢s:tΓ⊢A:sΓ,x:A⊢x:A,Γ⊢M:BΓ⊢A:sΓ,x:A⊢M:B,Γ⊢A:s1Γ,x:A⊢B:s2(s1,s2,s3)∈ℛΓ⊢Πx:A.B:s3,Γ,x: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}{\varnothing\vdash s:t} \qquad \frac{\Gamma\vdash A:s}{\Gamma,x:A\vdash x:A}, \\[8pt] \frac{\Gamma\vdash M:B\qquad\Gamma\vdash A:s} {\Gamma,x:A\vdash M:B}, \\[8pt] \frac{\Gamma\vdash A:s_1\qquad \Gamma,x:A\vdash B:s_2\qquad (s_1,s_2,s_3)\in\mathcal R} {\Gamma\vdash\Pi x:A.\,B:s_3}, \\[8pt] \frac{\Gamma,x:A\vdash b:B\qquad \Gamma\vdash\Pi x:A.\,B:s} {\Gamma\vdash\lambda x:A.\,b:\Pi x:A.\,B}, \\[8pt] \frac{\Gamma\vdash f:\Pi x:A.\,B\qquad\Gamma\vdash a:A} {\Gamma\vdash f\,a:B[a/x]}, \\[8pt] \frac{\Gamma\vdash M:A\qquad\Gamma\vdash B:s\qquad A=_\beta B} {\Gamma\vdash M:B}. \end{gathered}(4)✦

A valid context Γ\Gamma for PP is a finite sequence of declarations generated by (5). Valid⁡P(⌀)Valid⁡P(Γ)Γ⊢A:sValid⁡P(Γ,x:A).\frac{}{\operatorname{Valid}_P(\varnothing)} \qquad \frac{\operatorname{Valid}_P(\Gamma)\qquad\Gamma\vdash A:s} {\operatorname{Valid}_P(\Gamma,x:A)}.(5)✦ An expression MM is legal in a context Γ\Gamma when it occurs as a subject or an expected type of a typing judgement in Γ\Gamma, as in (6). 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).(6)✦

A beta normal form is an expression MM with no outgoing beta step, as in (7). $$M\in\mathrm{NF}_\beta \quad\Longleftrightarrow\quad \not\exists N\; M\to_\beta N.$$(7)✦ An expression MM is weakly normalizing when it reaches a beta normal form M#M^\# by finitely many steps, as in (8). M∈WNβ⇔∃M#(M→β*M#∧M#∈NFβ).M\in\mathrm{WN}_\beta \quad\Longleftrightarrow\quad \exists M^\#\;\bigl(M\to_\beta^* M^\#\ \land\ M^\#\in\mathrm{NF}_\beta\bigr).(8)✦ An expression MM is strongly normalizing when no infinite beta reduction starts from MM, as in (9). $$M\in\mathrm{SN}_\beta \quad\Longleftrightarrow\quad \not\exists (M_i)_{i\in\mathbb N}\; \bigl(M_0=M\ \land\ \forall i\in\mathbb N,\ M_i\to_\beta M_{i+1}\bigr).$$(9)✦

A pure type system PP is weakly normalizing when every expression legal in a valid context is weakly normalizing, as in (10). WNsys(P)⇔∀Γ(Valid⁡P(Γ)⇒∀M(Legal⁡P(Γ,M)⇒M∈WNβ)).\mathrm{WN}_{\mathrm{sys}}(P) \quad\Longleftrightarrow\quad \forall\Gamma\;\Bigl(\operatorname{Valid}_P(\Gamma)\ \Longrightarrow\ \forall M\;\bigl(\operatorname{Legal}_P(\Gamma,M) \ \Longrightarrow\ M\in\mathrm{WN}_\beta\bigr)\Bigr).(10)✦ A pure type system PP is strongly normalizing when every expression legal in a valid context is strongly normalizing, as in (11). SNsys(P)⇔∀Γ(Valid⁡P(Γ)⇒∀M(Legal⁡P(Γ,M)⇒M∈SNβ)).\mathrm{SN}_{\mathrm{sys}}(P) \quad\Longleftrightarrow\quad \forall\Gamma\;\Bigl(\operatorname{Valid}_P(\Gamma)\ \Longrightarrow\ \forall M\;\bigl(\operatorname{Legal}_P(\Gamma,M) \ \Longrightarrow\ M\in\mathrm{SN}_\beta\bigr)\Bigr).(11)✦

What Is Checked

The system normalization properties are stated over arbitrary specifications P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) and all legal expressions in their valid contexts.