OctoInformBeta

OpenAI preprint, September 2026 · §2. Structural properties

Lemma 13: Countably many sorts and a chosen axiom give common finite contexts and variable-valued substitutions

Saturated towers supply arbitrarily late variables.

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

The item concerns typing over an increasing sequence of finite contexts, with free variables numbered by the stages at which they enter. Let P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) be a pure type specification, where 𝒜\mathcal A is an axiom relation on SS and ℛ\mathcal R is a product-rule relation on SS.✦ Terms are variables viv_i, sorts s∈Ss\in S, applications MNM\,N, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ The displayed binder names are notation; variables use de Bruijn indices, with zero referring to the nearest enclosing binder, and finite contexts are ordered newest first.

A renaming ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N acts on a term MM by MρM\rho, replacing free indices according to ρ\rho and fixing sorts.✦ Below a binder its lift fixes zero and sends i+1i+1 to ρ(i)+1\rho(i)+1. Write Term(S)\mathrm{Term}(S) for the set of terms over SS. A simultaneous substitution σ:ℕ→Term(S)\sigma:\mathbb N\to\mathrm{Term}(S) acts by M[σ]M[\sigma]; its lift fixes the bound variable and sends i+1i+1 to σ(i)\sigma(i) with all free indices increased by one.✦ Both operations act recursively on applications, annotations, and binder bodies. For terms aa and bb over SS, the single substitution σa\sigma_a sends zero to aa and i+1i+1 to viv_i✦; instantiation is b[a/0]=b[σa]b[a/0]=b[\sigma_a].✦

Full one-step beta reduction →β\to_\beta contracts (λx:A.b)a(\lambda x:A.b)\,a to b[a/0]b[a/0] and is closed under every term constructor, including annotations and binder bodies.✦ Beta convertibility ≡β\equiv_\beta on terms over SS is the least equivalence relation containing full one-step beta reduction.✦ A beta normal form MM over SS is a term with no one-step reduct.✦ A term MM over SS is weakly normalizing, written WN(M)\mathrm{WN}(M), when MM reaches a normal form M#M^\# in finitely many steps, possibly zero✦; it is strongly normalizing, written SN(M)\mathrm{SN}(M), when no infinite beta reduction begins at MM.✦

Typing Γ⊢M:A\Gamma\vdash M:A is the pure type system judgement generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules of PP.✦ Product formation uses the triples in ℛ\mathcal R, abstraction requires a sorted product type, and conversion requires a sorted target type. A valid context Δ\Delta for PP is a finite context obtained from the empty context by extensions A::ΓA::\Gamma with Γ⊢A:s\Gamma\vdash A:s for some s∈Ss\in S.✦ Context lookup Γ(i)=A\Gamma(i)=A gives the declared type as viewed in the full context; writing ↑\uparrow for the renaming i↦i+1i\mapsto i+1, its defining clauses are (1). (A::Γ)(0)=A↑,Γ(i)=B⇒(A::Γ)(i+1)=B↑.(A::\Gamma)(0)=A\uparrow, \qquad \Gamma(i)=B\ \Longrightarrow\ (A::\Gamma)(i+1)=B\uparrow.(1)✦

Towers and Their Judgements

A saturated context tower Ω=(Ωn)n∈ℕ\Omega=(\Omega_n)_{n\in\mathbb N} for PP is a sequence of valid contexts with |Ωn|=n|\Omega_n|=n, each extending its predecessor by one type having a sort there, such that every type sorted at a stage occurs as a new declaration at arbitrarily late stages.✦ The reversal rnr_n in (2) translates their free levels into the indices of a context of length nn. rn(i)={n−1−i,i<n,i,i≥n.r_n(i)= \begin{cases} n-1-i,&i<n,\\ i,&i\geq n. \end{cases}(2)✦

Tower typing Ω⊢M:A\Omega\vdash M:A is typing of both MM and AA at some finite stage after reversal, as in (3).✦ A tower-typed substitution σ\sigma for Γ\Gamma in Ω\Omega is an assignment satisfying the declared types of all variables of Γ\Gamma; this is written Ω⊨σ:Γ\Omega\models\sigma:\Gamma, as in (4).✦ Ω⊢M:A⇔∃n∈ℕ,Ωn⊢Mrn:Arn.\Omega\vdash M:A \quad\Longleftrightarrow\quad \exists n\in\mathbb N,\quad \Omega_n\vdash Mr_n:Ar_n.(3)✦ Ω⊨σ:Γ⇔∀i,A,Γ(i)=A⇒Ω⊢σ(i):A[σ].\Omega\models\sigma:\Gamma \quad\Longleftrightarrow\quad \forall i,A,\quad \Gamma(i)=A\ \Longrightarrow\ \Omega\vdash\sigma(i):A[\sigma].(4)✦

The Claim

Theorem 1. Suppose that SS is at most countable and fix an axiom (s0,t0)∈𝒜(s_0,t_0)\in\mathcal A. There is a sequence of contexts CnC_n, with one context at each stage nn. The constructed saturated tower is given by (5). Ωn=Cn(n∈ℕ).\Omega_n=C_n\qquad(n\in\mathbb N).(5)✦ For a term AA and a sort ss with Cn⊢Arn:sC_n\vdash Ar_n:s, and any lower bound ℓ∈ℕ\ell\in\mathbb N, the construction satisfies (6). ∃m≥max⁡{n,ℓ},Cm+1=(Arm)::Cm.\exists m\geq\max\{n,\ell\},\qquad C_{m+1}=(Ar_m)::C_m.(6)✦

Let Ω\Omega now be any saturated context tower for PP. For a type AA with Ω⊢A:s\Omega\vdash A:s and a lower bound ℓ∈ℕ\ell\in\mathbb N, there is a variable as in (7). ∃i≥ℓ,Ω⊢vi:A.\exists i\geq\ell,\qquad \Omega\vdash v_i:A.(7)✦ Given judgements Ω⊢M:A\Omega\vdash M:A and Ω⊢N:B\Omega\vdash N:B, a common stage exists as in (8). ∃n∈ℕ,Ωn⊢Mrn:ArnandΩn⊢Nrn:Brn.\exists n\in\mathbb N,\qquad \Omega_n\vdash Mr_n:Ar_n \quad\text{and}\quad \Omega_n\vdash Nr_n:Br_n.(8)✦ For a finite valid context Γ\Gamma, there is a variable-valued typed substitution as in (9). ∃ρ:ℕ→ℕ,Ω⊨(i↦vρ(i)):Γ.\exists\rho:\mathbb N\to\mathbb N,\qquad \Omega\models(i\mapsto v_{\rho(i)}):\Gamma.(9)✦

For every term MM over SS and every n∈ℕn\in\mathbb N, reversal satisfies (10). WN(Mrn)⇔WN(M).\mathrm{WN}(Mr_n)\quad\Longleftrightarrow\quad\mathrm{WN}(M).(10)✦ Every renaming ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N preserves strong normalization of a term MM, as in (11). SN(Mρ).\mathrm{SN}(M\rho).(11)✦ For any renaming ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N such that MρM\rho is strongly normalizing, (12) holds. SN(M).\mathrm{SN}(M).(12)✦

In the paper, the result reads: if SS is at most countable and the variable names form a countably infinite set, there is a possibly empty countable sequence Ω\Omega of named declarations, with a judgement over Ω\Omega meaning one over some finite initial segment, such that every finite initial segment is valid and an infinite set of names is disjoint from all declared names; whenever a finite initial segment P0P_0 satisfies P0⊢D:sP_0\vdash D:s, infinitely many later declarations have the form y:Dy:D with distinct names yy; every finite valid context Γ\Gamma embeds by an injective renaming ρ\rho of its declared variables as a subsequence of a finite initial segment, and such an embedding sends Γ⊢M:A\Gamma\vdash M:A to P1⊢Mρ:AρP_1\vdash M\rho:A\rho over a finite initial segment P1P_1 containing the embedded context; for every finite initial segment P0P_0 with P0⊢D:sP_0\vdash D:s and every finite set FF of names, a larger finite initial segment QQ ends in a declaration y:Dy:D with y∉F∪dom⁡(P0)y\notin F\cup\operatorname{dom}(P_0) and Q⊢y:DQ\vdash y:D; finitely many judgements over Ω\Omega hold over a common finite initial segment; and the injective renamings of the embedding clause preserve and reflect weak and strong normalization.

What Is Checked

The axiom and product-rule relations of PP are arbitrary, without functionality or uniqueness of sort witnesses. The tower judgements in (3) and (4) concern terms and their expected types under the finite-context typing relation.

Cn is valid,|Cn|=n,∃D,s,Cn⊢D:sandCn+1=D::Cn.\begin{gathered} C_n\text{ is valid},\qquad |C_n|=n,\\ \exists D,s,\qquad C_n\vdash D:s \quad\text{and}\quad C_{n+1}=D::C_n. \end{gathered}(13)