OctoInformBeta

OpenAI preprint, September 2026 Β· Β§10. Exclusion and completion of the proof

Lemma 57: For targets with a positive telescope shape and normal full erasure, including arbitrary data extensions

Normal proof exclusion in converter 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

Typing and mode assignment are separate judgments on annotated terms. The question is when a proof-mode inhabitant can have normal full erasure, given restrictions on its expected type and on the types of proof-mode variables.

A pure type specification (S,π’œ,β„›)(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.✦ Pure terms are variables, sorts, applications MNMN, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B.✦ A labelled term MM is a term built from variables, sorts, applications, annotated abstractions and dependent products, with a label β„“\ell on each application, abstraction and product, written M@β„“NM@_\ell N, Ξ»β„“x:A.M\lambda^\ell x:A.M and Ξ β„“x:A.B\Pi^\ell x:A.B.✦ The modes are data 𝖽\mathsf d and proof 𝗉\mathsf p✦; the labels 𝖽𝖽\mathsf{dd}, 𝖽𝗉\mathsf{dp} and 𝗉𝗉\mathsf{pp} specify their argument and result modes in that order.✦ Write a(β„“)a(\ell) and r(β„“)r(\ell) for those two modes.

Named binders are source notation. Variable indices are de Bruijn indices, with zero at the nearest binder, and contexts are newest-first. Renaming applies a map of indices to the variables of a term, fixing the newly bound variable and shifting older renamed indices under a binder.✦ Simultaneous substitution replaces variables by assigned terms, lifting the assignment under binders to avoid capture. These operations preserve sorts and constructor labels. In either syntax, bound variable instantiation b[a/x]b[a/x] uses the single-variable substitution sending index zero to aa and index n+1n+1 to the variable of index nn.

Label erasure |M||M| is the pure term obtained by deleting every constructor label, recursively through annotations and bodies.✦ Full Ξ²\beta reduction is the least relation containing the pure head contraction in (1) and closed under reduction in every term component.✦ Labelled Ξ²\beta reduction is the least relation on labelled terms containing the labelled head contraction in (1) and closed under reduction in every term component; the head contraction requires the application and abstraction labels to agree.✦ (Ξ»x:A.b)aβ†’Ξ²b[a/x],(Ξ»β„“x:A.b)@β„“aβ†’Ξ²Lb[a/x].\begin{aligned} (\lambda x:A.b)\,a &\longrightarrow_\beta b[a/x],\\ (\lambda^\ell x:A.b)@_\ell a &\longrightarrow_\beta^{\mathrm L} b[a/x]. \end{aligned}(1) Labelled Ξ²\beta convertibility is the smallest equivalence relation containing labelled reduction.✦ A pure term tt is in full Ξ²\beta normal form, written NF⁡(t)\operatorname{NF}(t), when it has no outgoing Ξ²\beta step.✦

Targets and Contexts

A data-only term UU is a labelled term every constructor label of which is 𝖽𝖽\mathsf{dd}.✦ Write π’Ÿ\mathcal D for these terms. A positive telescope EE is a labelled term in the class 𝒫\mathcal P generated by (2): its terminal is data-only, and each telescope binder has data argument mode and proof result mode, with an arbitrary domain DD. Uβˆˆπ’Ÿβ‡’Uβˆˆπ’«,Eβˆˆπ’«β‡’Ξ π–½π—‰x:D.Eβˆˆπ’«.U\in\mathcal D\ \Longrightarrow\ U\in\mathcal P, \qquad E\in\mathcal P\ \Longrightarrow\ \Pi^{\mathsf{dp}}x:D.E\in\mathcal P.(2)✦ A normal positive target TT is a labelled term in the class 𝒯\mathcal T defined by (3). 𝒯={Tβˆˆπ’«βˆ£NF⁡(|T|)}.\mathcal T=\{T\in\mathcal P\mid\operatorname{NF}(|T|)\}.(3)✦

For a labelled context Ξ“\Gamma, the labelled typing judgment Ξ“βŠ’M:A\Gamma\vdash M:A assigns expected type AA to subject MM for the specification (S,π’œ,β„›)(S,\mathcal A,\mathcal R). Its axiom rule gives βŒ€βŠ’s:t\varnothing\vdash s:t when (s,t)βˆˆπ’œ(s,t)\in\mathcal A. Variables and weakening require a sort-typed declaration; adjoining it shifts older variables and their expected types. Product formation assigns sort s3s_3 to a product with any label when its domain has sort s1s_1, its codomain has sort s2s_2 in the extended context, and (s1,s2,s3)βˆˆβ„›(s_1,s_2,s_3)\in\mathcal R. Abstraction assigns the dependent product type Ξ β„“x:A.B\Pi^\ell x:A.B to Ξ»β„“x:A.b\lambda^\ell x:A.b when the body has expected type BB in the context extended by AA and that product has a sort. Application requires a function of product type and an argument of its domain type; its label agrees with the product label, and its expected type is the codomain instantiated by the argument. Conversion changes the expected type to a labelled Ξ²\beta convertible type that itself has a sort.

A mode environment Ξ³\gamma is a function assigning a mode to each variable index. The extension m::Ξ³m::\gamma of a mode environment Ξ³\gamma by a mode mm is the mode environment assigning mm to zero and Ξ³(n)\gamma(n) to n+1n+1.✦ The mode judgment γ⊒M:m\gamma\vdash M:m gives variables their assigned modes and sorts data mode. An application with label β„“\ell requires function mode r(β„“)r(\ell) and argument mode a(β„“)a(\ell), and has mode r(β„“)r(\ell). An abstraction requires a data-mode annotation and a body of mode r(β„“)r(\ell) under a(β„“)::Ξ³a(\ell)::\gamma, and has mode r(β„“)r(\ell). A product has data mode and requires data mode for its domain and for its codomain under a(β„“)::Ξ³a(\ell)::\gamma.

Context lookup Ξ“(n)=A\Gamma(n)=A assigns the shifted head declaration to index zero.✦ A converter proof context (Ξ“,Ξ³)(\Gamma,\gamma) is a labelled context with a mode environment satisfying the restriction 𝖒(Ξ“,Ξ³)\mathsf C(\Gamma,\gamma) in (4); the codomain FF is arbitrary. 𝖒(Ξ“,Ξ³)⇔for every lookup Ξ“(n)=A with Ξ³(n)=𝗉,A=Π𝗉𝗉x:R.F for some Rβˆˆπ’― and F.\begin{split} \mathsf C(\Gamma,\gamma)\quad\Longleftrightarrow\quad &\text{for every lookup }\Gamma(n)=A\text{ with }\gamma(n)=\mathsf p,\\ &A=\Pi^{\mathsf{pp}}x:R.F \text{ for some }R\in\mathcal T\text{ and }F. \end{split}(4)✦

The Claim

Theorem 1. Let (Ξ“,Ξ³)(\Gamma,\gamma) be a converter proof context and TT a normal positive target. The exclusion is {Mβˆ£Ξ“βŠ’M:T,γ⊒M:𝗉,NF⁡(|M|)}=βŒ€.\{M\mid\Gamma\vdash M:T,\quad \gamma\vdash M:\mathsf p,\quad \operatorname{NF}(|M|)\}=\varnothing.(5)✦

In the paper, the result reads: if Ξ”\Delta is the ambient context or any legal extension of it by data declarations, there is no proof-mode term PP with NF⁡(|P|)\operatorname{NF}(|P|) and Ξ”βŠ’P:T\Delta\vdash P:T for any Tβˆˆπ’―T\in\mathcal T.

What Is Checked

The exclusion (5) is stated over arbitrary pure type specifications, labelled typing and mode judgments, with the context and target restrictions (4) and (3).

The data extension law is (6).

Theorem 2. Let (Ξ“,Ξ³)(\Gamma,\gamma) be a converter proof context, and let DD be any labelled term. Write D::Ξ“D::\Gamma for the context obtained by adjoining the declaration DD to Ξ“\Gamma. Then 𝖒(D::Ξ“,𝖽::Ξ³).\mathsf C(D::\Gamma,\mathsf d::\gamma).(6)✦