OctoInformBeta

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

Lemma 23: dependence on support: Comparison under typed substitution with compatible polarities in a one-child interpretation

Signed support controls candidate comparison.

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 one-child interpretation assigns a set of terms to a type using actual variable images and a separate assignment of polarity bits. The comparison concerns a normal type before and after a typed substitution into another context.

A pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) consists of a set of sorts, an arbitrary axiom relation, and an arbitrary product-rule relation.✦ Its terms are variables, sorts, applications MNM\,N, annotated abstractions λx:D.M\lambda x:D.M, and dependent products Πx:D.B\Pi x:D.B.✦ Named variables are used here; variable indices are de Bruijn indices, and contexts list the newest declaration first. The judgement Γ⊢M:T\Gamma\vdash M:T uses the axiom, variable, weakening, product, abstraction, application, and conversion rules determined by PP.✦ A valid context Γ\Gamma for PP is a context obtained from the empty context by successive extensions by types having some sort in the preceding context.✦

Simultaneous substitution M[σ]M[\sigma] replaces each free variable ii by σ(i)\sigma(i), lifting the substitution under binders to avoid capture.✦ Variable renaming replaces free indices by their images and also lifts under binders.✦ Bound-variable instantiation B[a/x]B[a/x] is the single substitution sending index zero to aa and index i+1i+1 to variable ii.✦ Full β\beta reduction contracts (λx:D.M)a(\lambda x:D.M)\,a to M[a/x]M[a/x] and is closed under every term constructor, including annotations and binder bodies✦; β\beta convertibility is its equivalence closure.✦ A normal term MM is a term that admits no reduction step.✦ A weakly normalizing term MM is a term that reaches a normal term in finitely many steps; its chosen normal form is M#M^\#.

Assume system weak normalization: every term occurring as a subject or as an expected type in a typing judgement in a valid context is weakly normalizing.✦ The normal-form sort profile in (1) records all possible sort witnesses. A feasible profile II is a nonempty sort profile of a normal term in a valid context.✦ A feasible product profile triple consists of feasible profiles I,J,KI,J,K with K=Out⁡(I,J)K=\operatorname{Out}(I,J), where πΓ(T)={s∈S∣Γ⊢T#:s},Out⁡(I,J)={c∈S∣∃a∈I∃b∈J,(a,b,c)∈ℛ}.\pi_\Gamma(T)=\{s\in S\mid\Gamma\vdash T^\#:s\}, \qquad \operatorname{Out}(I,J) =\{c\in S\mid \exists a\in I\ \exists b\in J,\ (a,b,c)\in\mathcal R\}.(1) The product output profile Out⁡(I,J)\operatorname{Out}(I,J) of sets of sorts II and JJ consists of all sorts obtainable by a product rule with a domain sort in II and a codomain sort in JJ.

The primary signed graph has a positive edge I→JI\to J for each strict inclusion J⊊IJ\subsetneq I of feasible profiles. Each feasible product profile triple gives a negative edge I→KI\to K and a positive edge J→KJ\to K. A signed directed walk is a finite walk whose parity counts its negative edges modulo two; the empty walk has parity zero.✦ Write I⇝JI\rightsquigarrow J for the existence of such a walk, without specifying its parity.✦ A strongly connected component CC of the primary signed graph is a set consisting of exactly the profiles mutually reachable with one chosen member.✦ Fix such a CC; a CC type is a type whose profile belongs to CC.

A saturated context tower Ω\Omega is a sequence of valid contexts Ωn\Omega_n of length nn, each obtained from the preceding context by one typed extension. Every type typable at a stage, expressed with fixed free variable levels, is declared again beyond every prescribed stage. Translation between levels and indices at stage nn reverses indices below nn by i↦n−1−ii\mapsto n-1-i and leaves larger indices fixed.✦ Tower typing Ω⊢M:T\Omega\vdash M:T means typing both translated terms in some Ωn\Omega_n.✦

A typed substitution δ:Γ→Δ\delta:\Gamma\to\Delta is an assignment satisfying (2); here Γ(i)=T\Gamma(i)=T denotes the declared type of variable ii viewed in the full context, with the required index shifts.✦ A tower-typed substitution from a context Γ\Gamma to Ω\Omega is an assignment of variable images satisfying (2) with Ω\Omega as the target judgement.✦ Γ(i)=T⇒Δ⊢δ(i):T[δ].\Gamma(i)=T \quad\Longrightarrow\quad \Delta\vdash\delta(i):T[\delta].(2)✦

Interpretation and Support

A polarity assignment is a map θ:ℕ→{0,1}\theta:\mathbb N\to\{0,1\}.✦ An environment e=(σ,ψ)e=(\sigma,\psi) for Δ\Delta consists of a tower-typed substitution σ\sigma from Δ\Delta and a polarity assignment ψ\psi.✦

Write EΓ(A;σ,θ)E_\Gamma(A;\sigma,\theta) for the recursive one-child interpretation. The tower profile of A[σ]A[\sigma] is the set of sorts typing its chosen normal form in the tower. When either πΓ(A)\pi_\Gamma(A) or this tower profile lies outside CC, the interpretation is the upper tower candidate at (A[σ])#(A[\sigma])^\#. When both profiles belong to CC, a product Πx:D.B\Pi x:D.B is interpreted by the raw dependent product of the recursively interpreted domain and codomain: the terms whose application to each term of the domain candidate belongs to the corresponding codomain candidate, with the actual images and bits extended at the binder. For a nonproduct with variable head ii, the candidate is the upper tower candidate when θ(i)=1\theta(i)=1 and the lower tower candidate when θ(i)=0\theta(i)=0; a nonproduct without a variable head uses the upper candidate. The normal-form interpretation RΔR_\Delta is defined by (3). RΔ(T;e)=EΔ(T#;σ,ψ),e=(σ,ψ).R_\Delta(T;e)=E_\Delta(T^\#;\sigma,\psi), \qquad e=(\sigma,\psi).(3)✦

The optional signed support rΓ(A)r_\Gamma(A) of a type AA in a context Γ\Gamma is either absent, denoted ⊥\bot, or a pair (i,p)(i,p) of a variable index and a parity bit. It is absent outside CC. Inside CC, a nonproduct has support (i,0)(i,0) when its head is variable ii, and absent support otherwise. For a product Πx:D.B\Pi x:D.B, if the domain profile belongs to CC, support follows the domain and reverses its parity; otherwise it follows the codomain, removing the bound variable from its support.

For a direction d∈{0,1}d\in\{0,1\}, signed inclusion X≼dYX\preceq_dY is the relation between sets XX and YY specified in (4). Polarity assignments θ,ψ\theta,\psi are compatible with a substitution δ\delta at support rr in direction dd when the condition in (5) holds whenever r=(i,p)r=(i,p); absent support imposes no condition. The operation ⊕\oplus is addition modulo two. X≼dY⇔{X⊆Y,d=0,Y⊆X,d=1.X\preceq_dY \quad\Longleftrightarrow\quad \begin{cases} X\subseteq Y,&d=0,\\ Y\subseteq X,&d=1. \end{cases}(4)✦ (∃j,δ(i)=jas a variable and θ(i)=ψ(j))orθ(i)=d⊕p.\bigl(\exists j,\ \delta(i)=j\ \text{as a variable and }\theta(i)=\psi(j)\bigr) \quad\text{or}\quad \theta(i)=d\oplus p.(5)✦

The Claim

Theorem 1. Let Γ⊢A:s\Gamma\vdash A:s, with AA normal, and suppose that πΓ(A)⇝K\pi_\Gamma(A)\rightsquigarrow K for some K∈CK\in C. Let Δ\Delta be a valid context and δ:Γ→Δ\delta:\Gamma\to\Delta a typed substitution. Take an environment e=(σ,ψ)e=(\sigma,\psi) for Δ\Delta, a polarity assignment θ\theta, and a direction dd. Suppose that θ,ψ\theta,\psi are compatible with δ\delta at rΓ(A)r_\Gamma(A) in direction dd. With τ(i)=δ(i)[σ]\tau(i)=\delta(i)[\sigma], the substitution comparison is EΓ(A;τ,θ)≼dRΔ(A[δ];e).E_\Gamma(A;\tau,\theta)\preceq_d R_\Delta(A[\delta];e).(6)✦

In the paper, the result reads: for fixed typed actual images, the candidate of a CC type depends on the bits of its starting context only through its support, if any.

What Is Checked

The comparison (6) is stated over full β\beta reduction and typing for PP, a saturated context tower, the primary profile component CC, typed substitutions, and environments whose polarities satisfy the signed support condition.