OctoInformBeta

OpenAI preprint, September 2026 · §2. Structural properties

Lemma 6: Expected types are recovered up to β\beta convertibility, with sort and product-rule witnesses for arbitrary specifications

Typing generation recovers constructor premises.

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

Typing generation asks which premises a typing judgement imposes on the outer constructor of its subject. The expected type may have been changed by conversion.

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 variables, sort constants, applications faf\,a, annotated abstractions λx:A.b\lambda x:A.b, and dependent products Πx:A.B\Pi x:A.B.✦ The named binders are source notation; variables in the library use de Bruijn indices vnv_n, with v0v_0 referring to the nearest binder. Contexts are finite lists in newest-first order, written (A,Γ)(A,\Gamma) when extended by a type AA, or (x:A,Γ)(x:A,\Gamma) in named notation.

For a term MM over SS and a map ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N, the renamed term M[ρ]M[\rho] is the term obtained by replacing each free vnv_n by vρ(n)v_{\rho(n)}.✦ It fixes sorts and acts recursively on term constructors, using the lifted map ρ+(0)=0\rho^+(0)=0 and ρ+(n+1)=ρ(n)+1\rho^+(n+1)=\rho(n)+1 under a binder. Write ↑M\uparrow M for renaming by successor. For a term MM over SS and an assignment σ\sigma of terms to indices, the substituted term M[σ]M[\sigma] is the term obtained by replacing vnv_n by σ(n)\sigma(n) and fixing sorts.✦ It acts recursively, using σ+(0)=v0\sigma^+(0)=v_0 and σ+(n+1)=↑σ(n)\sigma^+(n+1)=\uparrow\sigma(n) under a binder.

The single-variable substitution σa\sigma_a determined by a term aa over SS is the assignment of terms to indices given by σa(0)=a\sigma_a(0)=a and σa(n+1)=vn\sigma_a(n+1)=v_n.✦ For terms aa and bb over SS, the bound-variable instance b[a]b[a] is the term given by b[a]=b[σa]b[a]=b[\sigma_a], written b[a/x]b[a/x] with named binders.✦ For a context Γ\Gamma, context lookup Γ(n)=C\Gamma(n)=C is the relation between an index nn and its declared type CC viewed in the full context, defined by (1).✦ (A,Γ)(0)=↑A,Γ(n)=C(A,Γ)(n+1)=↑C.(A,\Gamma)(0)=\uparrow A, \qquad \frac{\Gamma(n)=C}{(A,\Gamma)(n+1)=\uparrow C}.(1)

One-step β\beta reduction →β\to_\beta is the least relation containing (2) and closed under every term constructor, including reduction in abstraction annotations and bodies and in product domains and codomains.✦ (λx:A.b)a→βb[a/x].(\lambda x:A.b)\,a\to_\beta b[a/x].(2) The β\beta convertibility relation ≡β\equiv_\beta is the smallest equivalence relation containing →β\to_\beta.✦

The typing judgement Γ⊢M:T\Gamma\vdash M:T is the least relation closed under the axiom, variable, weakening, product, abstraction, application, and conversion rules.✦ An axiom (s,t)∈𝒜(s,t)\in\mathcal A gives ⌀⊢s:t\varnothing\vdash s:t. Whenever Γ⊢A:s\Gamma\vdash A:s, the variable rule gives (A,Γ)⊢v0:↑A(A,\Gamma)\vdash v_0:\uparrow A, and weakening takes Γ⊢M:T\Gamma\vdash M:T to (A,Γ)⊢↑M:↑T(A,\Gamma)\vdash\uparrow M:\uparrow T. When Γ⊢A:s1\Gamma\vdash A:s_1, (x:A,Γ)⊢B:s2(x:A,\Gamma)\vdash B:s_2, and (s1,s2,s3)∈ℛ(s_1,s_2,s_3)\in\mathcal R, the product Πx:A.B\Pi x:A.B has type s3s_3. When (x:A,Γ)⊢b:B(x:A,\Gamma)\vdash b:B and Γ⊢Πx:A.B:s\Gamma\vdash\Pi x:A.B:s for some sort ss, abstraction gives Γ⊢λx:A.b:Πx:A.B\Gamma\vdash\lambda x:A.b:\Pi x:A.B. When Γ⊢f:Πx:A.B\Gamma\vdash f:\Pi x:A.B and Γ⊢a:A\Gamma\vdash a:A, application gives Γ⊢fa:B[a/x]\Gamma\vdash f\,a:B[a/x]. Given Γ⊢M:A\Gamma\vdash M:A, A≡βBA\equiv_\beta B, and Γ⊢B:s\Gamma\vdash B:s for some sort ss, conversion gives Γ⊢M:B\Gamma\vdash M:B.

The generation condition 𝒢Γ(M,T)\mathcal G_\Gamma(M,T) for terms M,TM,T in a context Γ\Gamma is a condition determined by the outer constructor of MM. For M=vnM=v_n, it requires a type CC with Γ(n)=C\Gamma(n)=C and T≡βCT\equiv_\beta C; for M=sM=s, it requires a sort tt with (s,t)∈𝒜(s,t)\in\mathcal A and T≡βtT\equiv_\beta t. For M=Πx:A.BM=\Pi x:A.B, it requires sorts s1,s2,s3s_1,s_2,s_3 satisfying (4); for M=λx:A.bM=\lambda x:A.b, it requires a term BB and a sort ss satisfying (5); for M=faM=f\,a, it requires terms A,BA,B satisfying (6).

The Claim

Theorem 1 (Typing generation). Let P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) be a pure type specification and suppose Γ⊢M:T\Gamma\vdash M:T. The generation condition holds as in (3): 𝒢Γ(M,T).\mathcal G_\Gamma(M,T).(3)✦ Γ⊢A:s1,(x:A,Γ)⊢B:s2,(s1,s2,s3)∈ℛ,T≡βs3.\begin{gathered} \Gamma\vdash A:s_1,\qquad (x:A,\Gamma)\vdash B:s_2,\\ (s_1,s_2,s_3)\in\mathcal R,\qquad T\equiv_\beta s_3. \end{gathered}(4)✦ (x:A,Γ)⊢b:B,Γ⊢Πx:A.B:s,T≡βΠx:A.B.\begin{gathered} (x:A,\Gamma)\vdash b:B,\qquad \Gamma\vdash\Pi x:A.B:s,\\ T\equiv_\beta\Pi x:A.B. \end{gathered}(5)✦ Γ⊢f:Πx:A.B,Γ⊢a:A,T≡βB[a/x].\Gamma\vdash f:\Pi x:A.B,\qquad \Gamma\vdash a:A,\qquad T\equiv_\beta B[a/x].(6)✦

What Is Checked

The statements concern the typing relation on de Bruijn terms in newest-first contexts for arbitrary pure type specifications, with full β\beta convertibility between expected types. Equality of terms is decidable whenever equality of sorts is decidable.