OctoInformBeta

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

Lemma 24: One-child interpretations use literal composite actual images, with a distinguished bit for single substitution

Compatible bits control substitution comparisons.

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

Substitution can change which variable controls a one-child candidate. The issue is how the old and new polarity choices constrain the direction of comparison between the resulting sets of terms.

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) with arbitrary axiom and product-rule relations. Its terms are variables, sort constants, applications, annotated abstractions λx:A.M\lambda x:A.M and dependent products Πx:A.B\Pi x:A.B.✦ Named variables are source notation; variables xix_i use de Bruijn indices, with zero referring to the nearest binder, and context lists are newest-first. Typing Γ⊢M:A\Gamma\vdash M:A is generated by the axiom, variable and weakening rules, dependent product formation permitted by ℛ\mathcal R, annotated abstraction, application and conversion of the expected type to a type admitting a sort.✦ A valid context Γ\Gamma is a list of declared types generated from the empty context by adjoining AA whenever Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦

Full β\beta reduction closes the contraction (λx:A.b)a→βb[x:=a](\lambda x:A.b)\,a\to_\beta b[x:=a] under every term constructor, including annotations and binder bodies.✦ Convertibility ≃β\simeq_\beta on terms is the smallest equivalence relation containing full β\beta reduction.✦ A normal term MM is a term admitting no reduction step✦; a weakly normalizing term MM is a term having a normal reduct, denoted M#M^\#.✦ A legal term TT in a context Γ\Gamma is a term occurring as either subject or expected type in a judgement Γ⊢M:A\Gamma\vdash M:A✦; system weak normalization is the property that every legal term in every valid context is weakly normalizing.✦

For a term MM and a family δ\delta of term images for variables, capture-avoiding simultaneous substitution M[δ]M[\delta] replaces free variables and acts beneath a binder using the lift that fixes index zero and shifts each inserted image.✦ For an index map ρ\rho, variable renaming MρM^\rho acts recursively with the lifted index map fixing zero and sending i+1i+1 to ρ(i)+1\rho(i)+1.✦ For a term NN, the single substitution ιN\iota_N sends zero to NN and i+1i+1 to xix_i✦; bound variable instantiation is b[ιN]b[\iota_N].✦

Profiles and Actual Substitutions

For a term TT in a context Γ\Gamma and sets I,JI,J of sorts, the normal form sort profile πΓ(T)\pi_\Gamma(T) and product output profile Out⁡(I,J)\operatorname{Out}(I,J) are the sets in (1). πΓ(T)={s∈S∣Γ⊢T#:s},Out⁡(I,J)={c∈S∣∃a∈I∃b∈J,(a,b,c)∈ℛ}.\begin{aligned} \pi_\Gamma(T)&=\{s\in S\mid\Gamma\vdash T^\#:s\},\\ \operatorname{Out}(I,J)&= \{c\in S\mid \exists a\in I\;\exists b\in J,\ (a,b,c)\in\mathcal R\}. \end{aligned}(1) A feasible profile II is a nonempty set of sorts realized as πΓ(T)\pi_\Gamma(T) by a normal term TT in a valid context.✦ A feasible product profile triple (I,J,K)(I,J,K) consists of three feasible profiles satisfying K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦

The signed primary profile graph has positive edges I→JI\to J for proper inclusions J⊊IJ\subsetneq I between feasible profiles; each feasible product triple gives a negative edge I→KI\to K and a positive edge J→KJ\to K.✦ A signed directed walk is a finite directed walk, allowing repetitions, whose parity counts negative edges modulo two; the empty walk has parity zero.✦ Write I⤳JI\leadsto J when such a walk exists, irrespective of parity.✦ A strongly connected component CC of the signed primary profile graph is the set of profiles mutually reachable with some fixed member of CC.✦

A saturated context tower Ω=(Ωn)\Omega=(\Omega_n) is a sequence of valid contexts with prefixes of length nn, each next prefix adjoining a type that admits a sort. Every fixed-level expression having a sort at stage nn occurs as a declared type at arbitrarily late stages m≥nm\geq n. Free tower variables use fixed levels. Index-to-level reversal rnr_n and tower typing are defined by (2); the renaming acts on both subject and expected type. rn(i)={n−1−i,i<n,i,i≥n,Ω⊢M:A⇔∃n,Ωn⊢Mrn:Arn.\begin{aligned} r_n(i)&=\begin{cases}n-1-i,&i<n,\\i,&i\geq n,\end{cases}\\ \Omega\vdash M:A &\quad\Longleftrightarrow\quad \exists n,\ \Omega_n\vdash M^{r_n}:A^{r_n}. \end{aligned}(2)

Context lookup Γ(i)=B\Gamma(i)=B assigns an index its declared type shifted into the full context.✦ A typed substitution δ:Γ→Δ\delta:\Gamma\to\Delta is a family of terms such that Δ⊢δ(i):B[δ]\Delta\vdash\delta(i):B[\delta] for every lookup Γ(i)=B\Gamma(i)=B.✦ A tower typed substitution δ\delta from a context Γ\Gamma into a tower Ω\Omega is a family of term images satisfying the typed substitution condition with target Ω\Omega.✦ An environment (σ,ψ)(\sigma,\psi) from Γ\Gamma into Ω\Omega is a tower typed substitution σ\sigma together with a bit assignment ψ:ℕ→{0,1}\psi:\mathbb N\to\{0,1\}.✦

Support and Candidate Interpretation

The support supp⁡Γ(A)\operatorname{supp}_\Gamma(A) of a term AA in a context Γ\Gamma is either absent or a pair (i,p)(i,p) of a variable index and a parity. It is absent when πΓ(A)∉C\pi_\Gamma(A)\notin C. For a product Πx:D.E\Pi x:D.E whose profile belongs to CC, support follows the domain and reverses parity when πΓ(D)∈C\pi_\Gamma(D)\in C; otherwise it follows the codomain in D::ΓD::\Gamma, discarding support on the bound variable and decreasing surviving indices. A nonproduct whose profile belongs to CC has support (i,0)(i,0) when its variable head is ii, and absent support when it has no variable head.

For a bit bb and a bit sequence θ\theta, the bit sequence extension b::θb::\theta has value bb at zero and θ(i)\theta(i) at i+1i+1.✦ The chosen support bit cΓ(A)c_\Gamma(A) of a term AA in a context Γ\Gamma is the bit equal to pp when supp⁡Γ(A)=(0,p)\operatorname{supp}_\Gamma(A)=(0,p), and equal to 11 otherwise.✦

The recursive one-child interpretation ℰΓ(A;σ,θ)\mathcal E_\Gamma(A;\sigma,\theta) of a term AA in a context Γ\Gamma under an environment (σ,θ)(\sigma,\theta) into Ω\Omega is a set of terms. Put U=(A[σ])#U=(A[\sigma])^\#. Unless both πΓ(A)\pi_\Gamma(A) and the substituted tower profile belong to CC, this set is the upper candidate TopU\mathrm{Top}_U of typed strongly normalizing terms. When both profiles belong to CC, a product Πx:D.E\Pi x:D.E receives the raw product candidate formed from ℰΓ(D;σ,θ)\mathcal E_\Gamma(D;\sigma,\theta) and the codomain interpretations ℰD::Γ(E;n::σ,b::θ)\mathcal E_{D::\Gamma}(E;n::\sigma,b::\theta) for each term nn and bit bb; here n::σn::\sigma sends zero to nn and i+1i+1 to σ(i)\sigma(i). A nonproduct receives TopU\mathrm{Top}_U if it has no variable head or its head has bit 11, and the lower candidate BottomU\mathrm{Bottom}_U if its head has bit 00. The normal form candidate interpretation RΓ(A;σ,θ)R_\Gamma(A;\sigma,\theta) of a term AA in a context Γ\Gamma under an environment (σ,θ)(\sigma,\theta) into Ω\Omega is the set of terms defined by (3). RΓ(A;σ,θ)=ℰΓ(A#;σ,θ).R_\Gamma(A;\sigma,\theta) =\mathcal E_\Gamma(A^\#;\sigma,\theta).(3)✦

For sets X,YX,Y and a direction bit dd, signed inclusion X≼dYX\preceq_dY means X⊆YX\subseteq Y for d=0d=0 and Y⊆XY\subseteq X for d=1d=1; these directions are called positive and negative.✦ The compatibility condition Comp⁡(r,d,δ,θ,ψ)\operatorname{Comp}(r,d,\delta,\theta,\psi) on an optional support rr, a direction dd, a substitution δ\delta and bit assignments θ,ψ\theta,\psi is defined by (4), where ⊕\oplus is addition modulo two. Comp⁡(r,d,δ,θ,ψ)⇔∀i,p,r=(i,p)⇒(∃j,δ(i)=xj∧θ(i)=ψ(j))∨θ(i)=d⊕p.\begin{aligned} &\operatorname{Comp}(r,d,\delta,\theta,\psi)\\ &\quad\Longleftrightarrow\quad \forall i,p,\ r=(i,p)\ \Longrightarrow\ \bigl(\exists j,\ \delta(i)=x_j\ \land\ \theta(i)=\psi(j)\bigr) \ \lor\ \theta(i)=d\oplus p. \end{aligned}(4)✦

The Claim

Theorem 1. Let Γ⊢A:s\Gamma\vdash A:s, let AA be normal, and suppose πΓ(A)⤳K\pi_\Gamma(A)\leadsto K for some K∈CK\in C. Let Δ\Delta be valid, let δ:Γ→Δ\delta:\Gamma\to\Delta be typed, and let (σ,ψ)(\sigma,\psi) be an environment from Δ\Delta into Ω\Omega. Take a bit assignment θ\theta and a direction dd satisfying Comp⁡(supp⁡Γ(A),d,δ,θ,ψ)\operatorname{Comp}(\operatorname{supp}_\Gamma(A),d,\delta,\theta,\psi). With the actual composite images κ(i)=δ(i)[σ]\kappa(i)=\delta(i)[\sigma], the substitution comparison is ℰΓ(A;κ,θ)≼dRΔ(A[δ];σ,ψ).\mathcal E_\Gamma(A;\kappa,\theta) \preceq_d R_\Delta(A[\delta];\sigma,\psi).(5)✦ For any context Γ\Gamma, terms A,NA,N and bit assignment θ\theta, Comp⁡(supp⁡Γ(A),0,ιN,cΓ(A)::θ,θ).\operatorname{Comp}\bigl(\operatorname{supp}_\Gamma(A),0,\iota_N, c_\Gamma(A)::\theta,\theta\bigr).(6)✦

In the paper, the result reads: let Λ=Γ,y:B,Δ\Lambda=\Gamma,y:B,\Delta be valid, let Γ⊢N:B\Gamma\vdash N:B, and let TT be normal with πΛ(T)∈C\pi_\Lambda(T)\in C, put Γ′=Γ,Δ[y:=N]\Gamma'=\Gamma,\Delta[y:=N] and T′=(T[y:=N])#T'=(T[y:=N])^\#, and take typed substitutions ξ:Λ→Ω\xi:\Lambda\to\Omega and ξ′:Γ′→Ω\xi':\Gamma'\to\Omega with bits θ,θ′\theta,\theta' whose images respect composition up to conversion, so that ξ(y)≃βN[ξ′]\xi(y)\simeq_\beta N[\xi'] and the other images agree up to conversion; if the bits agree on every variable supported by both TT and T′T' and, whenever yy supports TT with parity pp, its bit is 00 when d⊕p=0d\oplus p=0 and 11 when d⊕p=1d\oplus p=1, then RΛ(T;ξ,θ)≼dRΓ′(T′;ξ′,θ′)R_\Lambda(T;\xi,\theta)\preceq_d R_{\Gamma'}(T';\xi',\theta') at their common actual normal type.

What Is Checked

The comparison (5) is stated over typed substitutions into a saturated tower, normal types whose primary profiles reach CC, and compatible support bits, whereas (6) quantifies over arbitrary contexts, terms and bit assignments.