OctoInformBeta

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

Lemma 3: In valid target contexts, with weakening beneath the newest declaration

Typed renaming preserves dependent typing.

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

Thinning in a dependent context concerns the variables in a term and in its expected type. Fix a pure type specification (S,π’œ,β„›)(S,\mathcal A,\mathcal R), where SS is a collection of sorts, π’œβŠ†SΓ—S\mathcal A\subseteq S\times S is an arbitrary axiom relation, and β„›βŠ†SΓ—SΓ—S\mathcal R\subseteq S\times S\times S is an arbitrary product-rule relation.✦ The collection Term(S)\mathrm{Term}(S) of terms over SS is generated by (1). M,N::=n_∣s∣MN∣λx:A.M∣Πx:A.B,nβˆˆβ„•,s∈S.M,N ::= \underline n \mid s \mid M\,N \mid \lambda x:A.M \mid \Pi x:A.B, \qquad n\in\mathbb N,\quad s\in S.(1)✦ The binder names in (1) are notation for reading terms; variables are de Bruijn indices, with zero referring to the nearest binder. Contexts are finite lists in newest-first order, and A,Ξ“A,\Gamma denotes extension of Ξ“\Gamma by AA.

A variable renaming ρ:β„•β†’β„•\rho:\mathbb N\to\mathbb N acts on a term MM by replacing its free indices according to ρ\rho; write the result as MρM^\rho.✦ For a variable renaming ρ:β„•β†’β„•\rho:\mathbb N\to\mathbb N, the lifted renaming ρ+\rho^+ is the map in (2) used beneath a binder, and ↑\uparrow denotes the successor map. ↑(n)=n+1,ρ+(0)=0,ρ+(n+1)=ρ(n)+1.\uparrow(n)=n+1,\qquad \rho^+(0)=0,\qquad \rho^+(n+1)=\rho(n)+1.(2)✦ Renaming fixes sorts, distributes over application, and acts on annotated abstractions and dependent products by (3). (Ξ»x:A.b)ρ=Ξ»x:Aρ.bρ+,(Ξ x:A.B)ρ=Ξ x:Aρ.Bρ+.\begin{aligned} (\lambda x:A.b)^\rho&=\lambda x:A^\rho.b^{\rho^+},\\ (\Pi x:A.B)^\rho&=\Pi x:A^\rho.B^{\rho^+}. \end{aligned}(3)

A simultaneous substitution Οƒ:β„•β†’Term(S)\sigma:\mathbb N\to\mathrm{Term}(S) is an assignment of terms to indices. The action M[Οƒ]M[\sigma] of a simultaneous substitution Οƒ\sigma on a term MM is the term obtained by replacing n_\underline n by Οƒ(n)\sigma(n), fixing sorts, and distributing over application. The lifted substitution Οƒ+\sigma^+ of a simultaneous substitution Οƒ\sigma is an assignment of terms to indices satisfying Οƒ+(0)=0_\sigma^+(0)=\underline0 and Οƒ+(n+1)=Οƒ(n)↑\sigma^+(n+1)=\sigma(n)^\uparrow. Under either binder, substitution by Οƒ\sigma acts on the domain with Οƒ\sigma and on the body with Οƒ+\sigma^+. For terms aa and bb, bound variable instantiation b[a]b[a] is the term obtained by the substitution in (4), using the single-variable substitution Οƒa\sigma_a. Οƒa(0)=a,Οƒa(n+1)=n_,b[a]=b[Οƒa].\sigma_a(0)=a,\qquad \sigma_a(n+1)=\underline n, \qquad b[a]=b[\sigma_a].(4)

One-step Ξ²\beta reduction β†’Ξ²\to_\beta on Term(S)\mathrm{Term}(S) is the least relation containing (5) and closed under reduction in either part of an application, in every abstraction annotation and body, and in every product domain and codomain. (Ξ»x:A.b)aβ†’Ξ²b[a].(\lambda x:A.b)\,a\to_\beta b[a].(5)✦ Beta convertibility ≑β\equiv_\beta on Term(S)\mathrm{Term}(S) is the smallest equivalence relation containing β†’Ξ²\to_\beta.✦

The typing judgement Ξ“βŠ’M:A\Gamma\vdash M:A is the least relation satisfying the rules in (6); all displayed sort letters range over SS. (s,t)βˆˆπ’œ[]⊒s:tΞ“βŠ’A:sA,Ξ“βŠ’0_:Aβ†‘Ξ“βŠ’M:BΞ“βŠ’A:sA,Ξ“βŠ’M↑:Bβ†‘Ξ“βŠ’A:s1A,Ξ“βŠ’B:s2(s1,s2,s3)βˆˆβ„›Ξ“βŠ’Ξ x:A.B:s3A,Ξ“βŠ’b:BΞ“βŠ’Ξ x:A.B:sΞ“βŠ’Ξ»x:A.b:Ξ x:A.BΞ“βŠ’f:Ξ x:A.BΞ“βŠ’a:AΞ“βŠ’fa:B[a]Ξ“βŠ’M:AΞ“βŠ’B:sA≑βBΞ“βŠ’M:B.\begin{gathered} \frac{(s,t)\in\mathcal A}{[]\vdash s:t} \qquad \frac{\Gamma\vdash A:s}{A,\Gamma\vdash\underline0:A^\uparrow} \qquad \frac{\Gamma\vdash M:B\quad\Gamma\vdash A:s} {A,\Gamma\vdash M^\uparrow:B^\uparrow} \\[6pt] \frac{\Gamma\vdash A:s_1\quad A,\Gamma\vdash B:s_2 \quad(s_1,s_2,s_3)\in\mathcal R} {\Gamma\vdash\Pi x:A.B:s_3} \\[6pt] \frac{A,\Gamma\vdash b:B\quad\Gamma\vdash\Pi x:A.B:s} {\Gamma\vdash\lambda x:A.b:\Pi x:A.B} \qquad \frac{\Gamma\vdash f:\Pi x:A.B\quad\Gamma\vdash a:A} {\Gamma\vdash f\,a:B[a]} \\[6pt] \frac{\Gamma\vdash M:A\quad\Gamma\vdash B:s\quad A\equiv_\beta B} {\Gamma\vdash M:B}. \end{gathered}(6)✦

A valid context Ξ”\Delta is a finite newest-first list obtained from the empty context by extending a valid context Ξ“\Gamma with a type AA for which Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦

Context variable lookup Ξ“(n)=B\Gamma(n)=B is the relation generated by (7), expressing a declaration’s type at its position in the full context. (A,Ξ“)(0)=A↑,Ξ“(n)=B(D,Ξ“)(n+1)=B↑.(A,\Gamma)(0)=A^\uparrow, \qquad \frac{\Gamma(n)=B}{(D,\Gamma)(n+1)=B^\uparrow}.(7)✦

The Claim

Theorem 1. Let Ξ“βŠ’M:A\Gamma\vdash M:A, let Ξ”\Delta be a valid context, and let ρ:β„•β†’β„•\rho:\mathbb N\to\mathbb N be a renaming such that Ξ”βŠ’Ο(n)_:Bρ\Delta\vdash\underline{\rho(n)}:B^\rho whenever Ξ“(n)=B\Gamma(n)=B. Then Ξ”βŠ’Mρ:Aρ.\Delta\vdash M^\rho:A^\rho.(8)✦

Let A,Ξ“βŠ’b:BA,\Gamma\vdash b:B, and suppose that Ξ“βŠ’A:s\Gamma\vdash A:s and Ξ“βŠ’D:t\Gamma\vdash D:t for sorts s,ts,t. Then A↑,D,Ξ“βŠ’b↑+:B↑+.A^\uparrow,D,\Gamma\vdash b^{\uparrow^+}:B^{\uparrow^+}.(9)✦

In the paper, the result reads: if Ξ“βŠ’M:A\Gamma\vdash M:A and Ξ”\Delta is a valid context containing the named declarations of Ξ“\Gamma unchanged and in their original order, then Ξ”βŠ’M:A\Delta\vdash M:A.

What Is Checked

The renaming statement (8) ranges over arbitrary pure type specifications, a valid target context, and typed images of every source context lookup in (7). The insertion statement (9) concerns two types sortable over the same older context and a judgement under one of them. Both assertions use the typing relation (6), including dependent products and conversion for the full Ξ²\beta reduction in (5).