OctoInformBeta

OpenAI preprint, September 2026 · §2. Structural properties

Lemma 2: The subject and expected type are scoped at the length of the context

Typing enforces context validity and scoping.

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

The scoping question concerns free indices in the subject and expected type and the sorting requirements on the context’s declarations.

A pure type specification P=(S,A,R)P=(S,A,R) consists of a set SS of sorts, an axiom relation A⊆S×SA\subseteq S\times S, and a product-rule relation R⊆S×S×SR\subseteq S\times S\times S.✦ The set 𝒯(S)\mathcal T(S) of terms is generated by (1), with i∈ℕi\in\mathbb N and s∈Ss\in S: M,N,U,V::=i∣s∣MN∣λU.M∣ΠU.V.M,N,U,V ::= i\mid s\mid MN\mid\lambda U.M\mid\Pi U.V.(1)✦ The abstraction λU.M\lambda U.M has domain annotation UU, and ΠU.V\Pi U.V is a dependent product. These are de Bruijn terms: index 00 denotes the newest variable, and a context Γ\Gamma is a finite list of terms written newest first, with U::ΓU::\Gamma adjoining UU to Γ\Gamma. The corresponding named binder forms are λx:U.M\lambda x:U.M and Πx:U.V\Pi x:U.V.

For a natural number nn, a term M∈𝒯(S)M\in\mathcal T(S) is scoped at nn when every free index is less than nn, with the binder clauses specified in (2): Scoped⁡n(i)⇔i<n,Scoped⁡n(s)⇔True,Scoped⁡n(MN)⇔Scoped⁡n(M)∧Scoped⁡n(N),Scoped⁡n(λU.M)⇔Scoped⁡n(U)∧Scoped⁡n+1(M),Scoped⁡n(ΠU.V)⇔Scoped⁡n(U)∧Scoped⁡n+1(V).\begin{aligned} \operatorname{Scoped}_n(i)&\iff i<n, & \operatorname{Scoped}_n(s)&\iff\mathrm{True},\\ \operatorname{Scoped}_n(MN)&\iff \operatorname{Scoped}_n(M)\land\operatorname{Scoped}_n(N),\\ \operatorname{Scoped}_n(\lambda U.M)&\iff \operatorname{Scoped}_n(U)\land\operatorname{Scoped}_{n+1}(M),\\ \operatorname{Scoped}_n(\Pi U.V)&\iff \operatorname{Scoped}_n(U)\land\operatorname{Scoped}_{n+1}(V). \end{aligned}(2)✦

Substitution and Typing

A variable renaming ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N acts on terms by replacing indices. Its action M⟨ρ⟩M\langle\rho\rangle, its lift under a binder, and the shift ↑M\uparrow M are specified in (3): i⟨ρ⟩=ρ(i),ρ+(0)=0,ρ+(i+1)=ρ(i)+1,↑M=M⟨i↦i+1⟩.\begin{gathered} i\langle\rho\rangle=\rho(i),\qquad \rho^+(0)=0,\qquad \rho^+(i+1)=\rho(i)+1,\\ \uparrow M=M\langle i\mapsto i+1\rangle. \end{gathered}(3)✦ A simultaneous substitution σ:ℕ→𝒯(S)\sigma:\mathbb N\to\mathcal T(S) replaces each variable by its image, with action M[σ]M[\sigma] and binder lift given by (4): i[σ]=σ(i),σ+(0)=0,σ+(i+1)=↑(σ(i)).i[\sigma]=\sigma(i),\qquad \sigma^+(0)=0,\qquad \sigma^+(i+1)=\uparrow(\sigma(i)).(4)✦ Both operations fix sorts. They act componentwise on applications and binder annotations, using their lifted actions on binder bodies.

For terms M,N∈𝒯(S)M,N\in\mathcal T(S), the bound-variable instantiation M[N]M[N] is the term obtained by applying the single-variable substitution δN\delta_N of (5) to MM: δN(0)=N,δN(i+1)=i,M[N]=M[δN].\delta_N(0)=N,\qquad \delta_N(i+1)=i,\qquad M[N]=M[\delta_N].(5) One-step β\beta reduction is the compatible closure of the contraction (6), including reduction in every annotation and binder body: (λU.M)N→βM[N].(\lambda U.M)N\longrightarrow_\beta M[N].(6)✦ The relation M≡βNM\equiv_\beta N of β\beta convertibility is the equivalence relation generated by one-step β\beta reduction.✦

For terms M,T,f,a∈𝒯(S)M,T,f,a\in\mathcal T(S) and sorts s,t,s1,s2,s3∈Ss,t,s_1,s_2,s_3\in S, typing Γ⊢M:T\Gamma\vdash M:T is the least judgment generated by the rules in (7), where ⌀\varnothing is the empty context: (s,t)∈A⌀⊢s:tΓ⊢U:sU::Γ⊢0:↑UΓ⊢M:TΓ⊢U:sU::Γ⊢↑M:↑TΓ⊢U:s1U::Γ⊢V:s2(s1,s2,s3)∈RΓ⊢ΠU.V:s3U::Γ⊢M:VΓ⊢ΠU.V:sΓ⊢λU.M:ΠU.VΓ⊢f:ΠU.VΓ⊢a:UΓ⊢fa:V[a]Γ⊢M:UΓ⊢V:sU≡βVΓ⊢M:V.\begin{gathered} \frac{(s,t)\in A}{\varnothing\vdash s:t} \qquad \frac{\Gamma\vdash U:s}{U::\Gamma\vdash 0:\uparrow U} \\[6pt] \frac{\Gamma\vdash M:T\qquad\Gamma\vdash U:s} {U::\Gamma\vdash\uparrow M:\uparrow T} \\[6pt] \frac{\Gamma\vdash U:s_1\qquad U::\Gamma\vdash V:s_2 \qquad(s_1,s_2,s_3)\in R} {\Gamma\vdash\Pi U.V:s_3} \\[6pt] \frac{U::\Gamma\vdash M:V\qquad\Gamma\vdash\Pi U.V:s} {\Gamma\vdash\lambda U.M:\Pi U.V} \\[6pt] \frac{\Gamma\vdash f:\Pi U.V\qquad\Gamma\vdash a:U} {\Gamma\vdash fa:V[a]} \\[6pt] \frac{\Gamma\vdash M:U\qquad\Gamma\vdash V:s\qquad U\equiv_\beta V} {\Gamma\vdash M:V}. \end{gathered}(7)✦

A valid context Γ\Gamma for PP is a finite context obtained from the empty context by adjoining types that have a sort in the preceding context, as in (8): Valid⁡P(⌀)Valid⁡P(Γ)Γ⊢U:sValid⁡P(U::Γ).\operatorname{Valid}_P(\varnothing) \qquad \frac{\operatorname{Valid}_P(\Gamma)\qquad\Gamma\vdash U:s} {\operatorname{Valid}_P(U::\Gamma)}.(8)✦

The Claim

Theorem 1. Suppose Γ⊢M:T\Gamma\vdash M:T for the specification PP. Then (9) and (10) hold, where |Γ||\Gamma| is the length of the context: Valid⁡P(Γ).\operatorname{Valid}_P(\Gamma).(9)✦ Scoped⁡|Γ|(M)∧Scoped⁡|Γ|(T).\operatorname{Scoped}_{|\Gamma|}(M) \land\operatorname{Scoped}_{|\Gamma|}(T).(10)✦

In the paper, the result reads: if Γ⊢M:T\Gamma\vdash M:T in named notation, then Γ\Gamma is valid and FV(M)∪FV(T)⊆dom⁡(Γ)\mathrm{FV}(M)\cup\mathrm{FV}(T)\subseteq\operatorname{dom}(\Gamma), and the sorting judgment of each declaration of Γ\Gamma in its preceding prefix occurs as a subderivation of the given derivation, with FV\mathrm{FV} denoting free variables and dom⁡(Γ)\operatorname{dom}(\Gamma) the variables declared in Γ\Gamma.

What Is Checked

The assertions are stated over arbitrary pure type specifications P=(S,A,R)P=(S,A,R) and the typing judgments generated by (7) on de Bruijn terms in finite contexts. Equality of terms is decidable whenever equality of the sorts is decidable.