OctoInformBeta

OpenAI preprint, September 2026 Β· Β§2. Structural properties

Lemma 4: Replacing one binder gives a typed assignment when the substituting term has the binder's type

Typed substitution preserves typing in valid contexts.

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 in a dependent typing judgement acts on the subject and its expected type. The assignment to each variable must respect the substitution into its own type.

A pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) consists of a collection of sorts 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.✦ Terms over SS are generated by variables n_\underline n for natural numbers nn, sort constants s∈Ss\in S, application MNM\,N, annotated abstraction Ξ»x:A.b\lambda x:A.b, and dependent product Ξ x:A.B\Pi x:A.B.✦ Variable names at binders are source notation; occurrences use de Bruijn indices, with zero denoting the nearest binder. Contexts are finite lists in newest-first order, with (A,Ξ“)(A,\Gamma) denoting extension of Ξ“\Gamma by AA.

The renaming M⟨ρ⟩M\langle\rho\rangle of a term MM by a map ρ:β„•β†’β„•\rho:\mathbb N\to\mathbb N is the term obtained by replacing n_\underline n by ρ(n)_\underline{\rho(n)}, fixing sorts, and acting recursively on applications and binder domains.✦ Under a binder its action uses the lifted renaming ρ+(0)=0\rho^+(0)=0 and ρ+(n+1)=ρ(n)+1\rho^+(n+1)=\rho(n)+1. Write ↑M\uparrow M for the renaming that increases every free index by one.

A simultaneous substitution Οƒ\sigma is an assignment of terms to natural-number indices; its action M[Οƒ]M[\sigma] is the capture-avoiding operation in (1), where the lifted assignment is given by Οƒ+(0)=0_\sigma^+(0)=\underline 0 and Οƒ+(n+1)=↑σ(n)\sigma^+(n+1)=\uparrow\sigma(n). n_[Οƒ]=Οƒ(n),s[Οƒ]=s,(MN)[Οƒ]=M[Οƒ]N[Οƒ],(Ξ»x:A.b)[Οƒ]=Ξ»x:A[Οƒ].b[Οƒ+],(Ξ x:A.B)[Οƒ]=Ξ x:A[Οƒ].B[Οƒ+].\begin{aligned} \underline n[\sigma]&=\sigma(n), & s[\sigma]&=s,\\ (M\,N)[\sigma]&=M[\sigma]\,N[\sigma],\\ (\lambda x:A.b)[\sigma]&=\lambda x:A[\sigma].b[\sigma^+],\\ (\Pi x:A.B)[\sigma]&=\Pi x:A[\sigma].B[\sigma^+]. \end{aligned}(1)✦

The single-variable substitution κN\kappa_N associated with a term NN is the assignment in (2); bound-variable instantiation is b[N/0]=b[κN]b[N/0]=b[\kappa_N].✦ κN(0)=N,κN(n+1)=n_.\kappa_N(0)=N,\qquad \kappa_N(n+1)=\underline n.(2)✦

One-step Ξ²\beta reduction β†’Ξ²\to_\beta is the least relation containing (Ξ»x:A.b)Nβ†’Ξ²b[N/0](\lambda x:A.b)\,N\to_\beta b[N/0] and closed under reduction in either application position, in abstraction annotations and bodies, and in product domains and codomains.✦ The relation =Ξ²=_\beta of Ξ²\beta convertibility is the smallest equivalence relation containing β†’Ξ²\to_\beta.✦

The typing judgement Ξ“βŠ’M:A\Gamma\vdash M:A is the least relation generated by the pure type system rules.✦ Axioms give []⊒s:t[]\vdash s:t for (s,t)βˆˆπ’œ(s,t)\in\mathcal A. From Ξ“βŠ’A:s\Gamma\vdash A:s, the variable rule gives (A,Ξ“)⊒0_:↑A(A,\Gamma)\vdash\underline 0:\uparrow A; weakening sends Ξ“βŠ’M:B\Gamma\vdash M:B to (A,Ξ“)βŠ’β†‘M:↑B(A,\Gamma)\vdash\uparrow M:\uparrow B under the same condition. Product formation uses Ξ“βŠ’A:s1\Gamma\vdash A:s_1 and (A,Ξ“)⊒B:s2(A,\Gamma)\vdash B:s_2 to give Ξ“βŠ’Ξ x:A.B:s3\Gamma\vdash\Pi x:A.B:s_3 when (s1,s2,s3)βˆˆβ„›(s_1,s_2,s_3)\in\mathcal R. Abstraction gives Ξ“βŠ’Ξ»x:A.b:Ξ x:A.B\Gamma\vdash\lambda x:A.b:\Pi x:A.B when (A,Ξ“)⊒b:B(A,\Gamma)\vdash b:B and the product has a sort in Ξ“\Gamma. Application gives Ξ“βŠ’fN:B[N/0]\Gamma\vdash f\,N:B[N/0] from Ξ“βŠ’f:Ξ x:A.B\Gamma\vdash f:\Pi x:A.B and Ξ“βŠ’N:A\Gamma\vdash N:A. Conversion gives Ξ“βŠ’M:B\Gamma\vdash M:B from Ξ“βŠ’M:A\Gamma\vdash M:A when A=Ξ²BA=_\beta B and Ξ“βŠ’B:s\Gamma\vdash B:s for some sort ss.

A valid context Ξ”\Delta is a newest-first list obtained from the empty context by adjoining AA to a valid Ξ“\Gamma whenever Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦ Context lookup Ξ“(n)=A\Gamma(n)=A is the relation between a context, an index, and its type generated by (3). (A,Ξ“)(0)=↑AΞ“(n)=A(B,Ξ“)(n+1)=↑A.\frac{}{(A,\Gamma)(0)=\uparrow A} \qquad \frac{\Gamma(n)=A}{(B,\Gamma)(n+1)=\uparrow A}.(3)✦

A typed simultaneous substitution Οƒ:Ξ“β‡’Ξ”\sigma:\Gamma\Rightarrow\Delta is an assignment of terms to indices satisfying the typing condition (4) for every context lookup. Ξ“(n)=Aβ‡’Ξ”βŠ’Οƒ(n):A[Οƒ].\Gamma(n)=A\quad\Longrightarrow\quad \Delta\vdash\sigma(n):A[\sigma].(4)✦

The Claim

Theorem 1. Let Ξ“βŠ’M:A\Gamma\vdash M:A, let Ξ”\Delta be a valid context, and let Οƒ:Ξ“β‡’Ξ”\sigma:\Gamma\Rightarrow\Delta be a typed simultaneous substitution. Then Ξ”βŠ’M[Οƒ]:A[Οƒ].\Delta\vdash M[\sigma]:A[\sigma].(5)✦ For a term NN with Ξ“βŠ’N:D\Gamma\vdash N:D, the single-variable substitution satisfies ΞΊN:(D,Ξ“)β‡’Ξ“.\kappa_N:(D,\Gamma)\Rightarrow\Gamma.(6)✦

In the paper, the result reads: in named-variable notation, let Ξ“=(x1:A1,…,xn:An)\Gamma=(x_1:A_1,\ldots,x_n:A_n) and let Ξ”\Delta be valid, and suppose that Ξ”βŠ’Οƒ(xi):Ai[Οƒ|{x1,…,xiβˆ’1}]\Delta\vdash\sigma(x_i):A_i[\sigma|_{\{x_1,\ldots,x_{i-1}\}}] for 1≀i≀n1\leq i\leq n; then Ξ“βŠ’M:A\Gamma\vdash M:A gives Ξ”βŠ’M[Οƒ]:A[Οƒ]\Delta\vdash M[\sigma]:A[\sigma]; in particular, for a context Θ\Theta, Ξ“,x:D,Θ⊒M:A\Gamma,x:D,\Theta\vdash M:A and Ξ“βŠ’N:D\Gamma\vdash N:D give Ξ“,Θ[x:=N]⊒M[x:=N]:A[x:=N]\Gamma,\Theta[x:=N]\vdash M[x:=N]:A[x:=N].

What Is Checked

The claims (5) and (6) are stated over arbitrary pure type specifications, indexed terms in newest-first contexts, and the typed assignments of (4), with validity of the target context required for (5).