OctoInformBeta

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

Lemma 5: Replacing the newest declaration type by a convertible type sorted in the common context gives equivalent contexts

Sorted head conversion preserves 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

A context declaration supplies a type for a variable that may occur in both the subject and the expected type of a judgement. Context conversion concerns changing the declared type while keeping those terms fixed.

A pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) consists of a collection SS of sorts, 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.✦ The terms over SS are generated by variables, sort constants, application MNM\,N, annotated abstraction Ξ»x:A.M\lambda x:A.M, and dependent product Ξ x:A.B\Pi x:A.B.✦ Variables have de Bruijn indices; v0v_0 refers to the nearest binder, and the names in abstractions and products are named source notation. A context is a finite list of declaration types in newest-first order; A::Ξ“A::\Gamma denotes extension of Ξ“\Gamma by the newest declaration type AA.

Substitution and Typing

For a map ρ:β„•β†’β„•\rho:\mathbb N\to\mathbb N, the renaming M[ρ]M[\rho] of a term MM is the term obtained by replacing vnv_n by vρ(n)v_{\rho(n)}.✦ It fixes sorts and acts recursively on applications and binder domains; binder bodies use the lifted map ρ+\rho^+ defined in (1). The shift M↑M^\uparrow of a term MM is the term obtained by increasing every free index by one. ρ+(0)=0,ρ+(n+1)=ρ(n)+1,M↑=M[n↦n+1].\rho^+(0)=0,\qquad \rho^+(n+1)=\rho(n)+1, \qquad M^\uparrow=M[n\mapsto n+1].(1)

For an assignment Οƒ:β„•β†’Term⁡(S)\sigma:\mathbb N\to \operatorname{Term}(S), where Term⁡(S)\operatorname{Term}(S) is the collection of terms over SS, the simultaneous substitution M[Οƒ]M[\sigma] in a term MM is the term obtained by replacing vnv_n by Οƒ(n)\sigma(n). It fixes sorts and acts recursively on applications and binder domains, using the lifted substitution Οƒ+\sigma^+ in binder bodies. For terms aa and bb, the single-variable substitution Οƒa\sigma_a and bound-variable instantiation b[a]b[a] are given with this lift in (2); instantiation replaces index zero by aa and decrements higher free indices. Οƒ+(0)=v0,Οƒ+(n+1)=Οƒ(n)↑,Οƒa(0)=a,Οƒa(n+1)=vn,b[a]=b[Οƒa].\begin{gathered} \sigma^+(0)=v_0,\qquad \sigma^+(n+1)=\sigma(n)^\uparrow,\\ \sigma_a(0)=a,\qquad \sigma_a(n+1)=v_n,\qquad b[a]=b[\sigma_a]. \end{gathered}(2)

One-step Ξ²\beta reduction β†’Ξ²\to_\beta on terms over SS is the least relation containing the contraction in (3) and closed under reduction in either part of an application, in an abstraction’s annotation and body, and in a dependent product’s domain and codomain.✦ The Ξ²\beta convertibility relation =Ξ²=_\beta on terms over SS is the smallest equivalence relation containing one-step Ξ²\beta reduction β†’Ξ²\to_\beta.✦ (Ξ»x:A.b)aβ†’Ξ²b[a].(\lambda x:A.b)\,a\to_\beta b[a].(3)

The typing relation Ξ“βŠ’M:C\Gamma\vdash M:C, between a context Ξ“\Gamma and terms M,CM,C over SS, is the least relation generated by the axiom, variable, weakening, product, abstraction, application and conversion rules in (4).✦ (s,t)βˆˆπ’œ[]⊒s:tΞ“βŠ’A:sA::Ξ“βŠ’v0:Aβ†‘Ξ“βŠ’M:CΞ“βŠ’A:sA::Ξ“βŠ’M↑:Cβ†‘Ξ“βŠ’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 v_0:A^\uparrow} \\[1.2ex] \frac{\Gamma\vdash M:C\qquad\Gamma\vdash A:s} {A::\Gamma\vdash M^\uparrow:C^\uparrow} \\[1.2ex] \frac{\Gamma\vdash A:s_1\qquad A::\Gamma\vdash B:s_2 \qquad(s_1,s_2,s_3)\in\mathcal R} {\Gamma\vdash\Pi x:A.B:s_3} \\[1.2ex] \frac{A::\Gamma\vdash b:B\qquad\Gamma\vdash\Pi x:A.B:s} {\Gamma\vdash\lambda x:A.b:\Pi x:A.B} \\[1.2ex] \frac{\Gamma\vdash f:\Pi x:A.B\qquad\Gamma\vdash a:A} {\Gamma\vdash f\,a:B[a]} \qquad \frac{\Gamma\vdash M:A\qquad\Gamma\vdash B:s\qquad A=_\beta B} {\Gamma\vdash M:B}. \end{gathered}(4)

A valid context Ξ”\Delta for PP is a context generated from the empty context by extending a valid context Ξ“\Gamma by a type AA whenever Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦ Context equivalence Γ≃PΞ”\Gamma\simeq_P\Delta is the relation on contexts defined by (5), requiring validity of both contexts and agreement of their typing judgements.✦ Γ≃PΔ⇔Γ and Ξ” are valid,for all terms M,C,(Ξ“βŠ’M:Cβ‡”Ξ”βŠ’M:C).\Gamma\simeq_P\Delta \quad\Longleftrightarrow\quad \begin{gathered} \Gamma\text{ and }\Delta\text{ are valid},\\ \text{for all terms }M,C,\quad (\Gamma\vdash M:C\ \Longleftrightarrow\ \Delta\vdash M:C). \end{gathered}(5)

The Claim

Theorem 1 (Head conversion). Let Ξ“βŠ’A:s\Gamma\vdash A:s and Ξ“βŠ’Aβ€²:t\Gamma\vdash A':t for sorts s,ts,t, and suppose that A=Ξ²Aβ€²A=_\beta A'. The context equivalence is (6): A::Γ≃PAβ€²::Ξ“.A::\Gamma\simeq_P A'::\Gamma.(6)✦ Aβ€²::Ξ“βŠ’M:C.A'::\Gamma\vdash M:C.(7)

What Is Checked

Head conversion is stated over the full typing relation of an arbitrary pure type specification, with both declaration types sorted in the common context and related by Ξ²\beta convertibility.

Equality of terms is decidable whenever equality of sorts is decidable.