OctoInformBeta

OpenAI preprint, September 2026 Β· Β§4. Two component constructions

Lemma 23: structural invariance: Declaration renaming with matching actual images and bits, and context equivalence

Structural invariance of one-child candidate evaluation.

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 context supplies the declarations of a type’s free variables. One-child candidate evaluation also takes an actual image and a polarity bit for each variable.

A pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) consists of a sort set 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.✦ Its terms are variables, sorts, applications MNM\,N, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B.✦ Variable names are source notation; indices count outwards from the nearest binder, starting at zero, and contexts list newest declarations first.

For an index map ρ\rho, the renamed term M⟨ρ⟩M\langle\rho\rangle is obtained from MM by replacing each free index ii by ρ(i)\rho(i).✦ Under a binder its lift fixes zero and sends i+1i+1 to ρ(i)+1\rho(i)+1. For a simultaneous substitution Οƒ\sigma, an assignment of terms to indices, the substituted term M[Οƒ]M[\sigma] is obtained from MM by replacing each free index ii by the term Οƒ(i)\sigma(i), acting on every annotation, and lifting under binders by fixing the bound variable and shifting the free indices of each substituted image.✦ Both operations preserve sorts and act on both parts of an application. The single-variable substitution determined by aa sends zero to aa and i+1i+1 to variable ii✦; bound-variable instantiation b[a/x]b[a/x] is substitution by this assignment.✦

Full one-step Ξ²\beta reduction β†’Ξ²\to_\beta is the closure of (Ξ»x:A.b)aβ†’Ξ²b[a/x](\lambda x:A.b)\,a\to_\beta b[a/x] under all term positions, including annotations and binder bodies.✦ Convertibility ≑β\equiv_\beta is the least equivalence relation containing β†’Ξ²\to_\beta.✦ A normal form MM is a term with no outgoing Ξ²\beta step.✦ A term MM is weakly normalizing when some normal form M#M^\# is reachable by finitely many such steps, including zero steps.✦

Typing Ξ“βŠ’M:A\Gamma\vdash M:A is the pure type system judgment with the axiom relation π’œ\mathcal A, product rules β„›\mathcal R, variable and weakening rules, abstraction and application rules, and conversion of an expected type to a sortable Ξ²\beta-convertible type.✦ A valid context of the pure type system is a context obtained from the empty context by extensions that adjoin AA to an already obtained context Ξ“\Gamma whenever Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦ A term MM is legal in Ξ“\Gamma when some judgment Ξ“βŠ’M:A\Gamma\vdash M:A or Ξ“βŠ’A:M\Gamma\vdash A:M holds.✦ System weak normalization means that every legal term in every valid context is weakly normalizing, including both subjects and expected types.✦

A saturated context tower Ξ©=(Ξ©n)nβˆˆβ„•\Omega=(\Omega_n)_{n\in\mathbb N} is a sequence of valid contexts of length nn, each extended at the next stage by a type admitting a sort. The index-to-level reversal rnr_n is the index map that sends i<ni<n to nβˆ’1βˆ’in-1-i and fixes iβ‰₯ni\geq n.✦ Saturation requires that, whenever Ξ©n⊒A⟨rn⟩:s\Omega_n\vdash A\langle r_n\rangle:s, every bound β„“\ell admits mβ‰₯n,β„“m\geq n,\ell with Ξ©m+1=A⟨rm⟩::Ξ©m\Omega_{m+1}=A\langle r_m\rangle::\Omega_m. Here the free names of AA are fixed levels, while bound variables remain indices.

Declarations and Assignments

Context lookup i:AβˆˆΞ“i:A\in\Gamma is the relation expressing that index ii has declared type AA viewed in the full context Ξ“\Gamma.✦ With ↑(i)=i+1\uparrow(i)=i+1, its generating rules are (1). 0:AβŸ¨β†‘βŸ©βˆˆA::Ξ“,i:AβˆˆΞ“i+1:AβŸ¨β†‘βŸ©βˆˆB::Ξ“.0:A\langle\uparrow\rangle\in A::\Gamma, \qquad \frac{i:A\in\Gamma} {i+1:A\langle\uparrow\rangle\in B::\Gamma}.(1)✦ A declaration-preserving renaming from Ξ“\Gamma to Ξ”\Delta is an index map ρ\rho satisfying (2). i:AβˆˆΞ“β‡’Ο(i):AβŸ¨ΟβŸ©βˆˆΞ”for every i,A.i:A\in\Gamma \quad\Longrightarrow\quad \rho(i):A\langle\rho\rangle\in\Delta \qquad\text{for every }i,A.(2)✦

Context equivalence Γ≃Δ\Gamma\simeq\Delta is the relation on valid contexts defined by agreement on subjects and expected types as in (3). Γ≃Δ⇔Γ,Ξ” are valid and (Ξ“βŠ’M:Bβ‡”Ξ”βŠ’M:B) for every M,B.\Gamma\simeq\Delta \quad\Longleftrightarrow\quad \Gamma,\Delta\text{ are valid and } \bigl(\Gamma\vdash M:B\ \Longleftrightarrow\ \Delta\vdash M:B\bigr) \text{ for every }M,B.(3)✦

A polarity assignment ΞΈ:β„•β†’{0,1}\theta:\mathbb N\to\{0,1\} assigns a Boolean bit to each index.✦ Fix the ambient tower Ξ©\Omega and the class CC of profiles used by the one-child interpretation. The sort profile πΓ(T)\pi_\Gamma(T) of a term TT in a context Ξ“\Gamma is the set of sorts typing the chosen normal form T#T^\# in Ξ“\Gamma when weak normalization supplies that form.

The recursive one-child interpretation β„°Ξ“(A;Οƒ,ΞΈ)\mathcal E_\Gamma(A;\sigma,\theta) is a set of terms selected by the sort profile of AA in its context and the sort profile of A[Οƒ]A[\sigma] in the ambient tower. When both profiles lie in CC, a product Ξ x:D.E\Pi x:D.E receives the raw product candidate, whose membership condition tests applications against the recursive interpretations of DD and EE, with Οƒ\sigma and ΞΈ\theta extended at the binder for each actual image and bit. A nonproduct receives the upper candidate of typed strongly normalizing terms at the normal-form selection of A[Οƒ]A[\sigma] if it has no variable head or its head’s bit is 11, and the lower ground tested-stack candidate if its head’s bit is 00. When either profile test fails, the interpretation receives the upper candidate at that same normal-form selection.

The Claim

Theorem 1. Suppose Ξ“βŠ’A:s\Gamma\vdash A:s for a sort ss. Let Ξ”\Delta be valid and let ρ\rho be a declaration-preserving renaming from Ξ“\Gamma to Ξ”\Delta. Let actual substitutions Οƒ,Ο„\sigma,\tau and polarity assignments ΞΈ,ψ\theta,\psi satisfy Ο„βˆ˜Ο=Οƒ\tau\circ\rho=\sigma and ψ∘ρ=ΞΈ\psi\circ\rho=\theta. The renaming law is (4). β„°Ξ“(A;Οƒ,ΞΈ)=β„°Ξ”(A⟨ρ⟩;Ο„,ψ).\mathcal E_\Gamma(A;\sigma,\theta) =\mathcal E_\Delta(A\langle\rho\rangle;\tau,\psi).(4)✦ For a context Ξ”\Delta equivalent to Ξ“\Gamma, arbitrary actual substitution Οƒ\sigma and polarity assignment ΞΈ\theta, the context law is (5). β„°Ξ“(A;Οƒ,ΞΈ)=β„°Ξ”(A;Οƒ,ΞΈ).\mathcal E_\Gamma(A;\sigma,\theta) =\mathcal E_\Delta(A;\sigma,\theta).(5)✦

In the paper, the result reads: valid thinning and context conversion preserve the support, its polarity and the candidates, and pointwise Ξ²\beta-convertible actual images preserve the candidates when the old polarity bits agree.

What Is Checked

The laws are stated over types admitting a sort, declaration-preserving renamings into valid contexts, context equivalence, and arbitrary actual substitutions and polarity assignments for the fixed recursive one-child interpretation.