OctoInformBeta

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

Terminal targets and the proof context: Positive telescopes and the permitted types of proof variables

Normal targets and converter proof 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

The distinction between data and proof applies to variables in a context and to arguments of dependent products. A converter declaration assigns a type to a proof variable, with a target as its input type.

Fix a sort collection SS. Pure type system terms over SS are generated by variables, sort constants, application, annotated abstraction and dependent product, as in (1), where s∈Ss\in S. M,N,A,B::=x∣s∣MN∣λx:A.M∣Πx:A.B.M,N,A,B ::= x \mid s \mid M\,N \mid \lambda x:A.M \mid \Pi x:A.B.(1)✦ Named binders in (1) stand for de Bruijn notation: variables have natural number indices, and index zero refers to the nearest enclosing binder.

The modes are data 𝖽\mathsf d and proof 𝗉\mathsf p.✦ An argument and result label ℓ\ell is one of dddd, dpdp and pppp, denoting data/data, data/proof and proof/proof, respectively.✦ A labelled term TT over SS is a term with the syntax of (1) and a label from dddd, dpdp and pppp on every application, abstraction and dependent product.✦ Write Πℓx:A.B\Pi^\ell x:A.B for a product with label ℓ\ell. The label erasure |T||T| of a labelled term TT is the unlabelled term obtained by deleting every label and preserving the remaining syntax.✦

For a term MM over SS and a substitution σ\sigma assigning a term over SS to each variable index, the simultaneous substitution M[σ]M[\sigma] is the term obtained by replacing each variable of index nn by σ(n)\sigma(n) and fixing sort constants.✦ It acts recursively on applications and on binder domains; in a binder body it uses the lifted substitution, which fixes the new variable and increases every free index in each older image by one. For terms aa and bb over SS, the single-variable substitution σa\sigma_a is the map from variable indices to terms over SS, and the bound-variable instantiation b[a]b[a] is the term over SS, specified by (2). σa(0)=a,σa(n+1)=n,b[a]=b[σa],\sigma_a(0)=a,\qquad \sigma_a(n+1)=n,\qquad b[a]=b[\sigma_a],(2) where the nn on the right denotes the variable of index nn.

Full one-step β\beta reduction →β\to_\beta on terms over SS is the least relation containing the head contraction in (3) and closed under reduction in either subterm of an application, annotated abstraction or dependent product. (λx:A.b)a→βb[a].(\lambda x:A.b)\,a\to_\beta b[a].(3)✦ A β\beta normal form MM is a term with no one-step β\beta reduct.✦

A data-only term UU over SS is a labelled term whose every application, abstraction and dependent product has label dddd.✦ Write Data⁡(U)\operatorname{Data}(U) for this condition. A positive telescope EE over SS is a labelled term in the least class specified by (4), where the domain DD is arbitrary. Data⁡(U)Pos⁡(U)Pos⁡(E)Pos⁡(Πdpx:D.E).\frac{\operatorname{Data}(U)}{\operatorname{Pos}(U)} \qquad \frac{\operatorname{Pos}(E)}{\operatorname{Pos}(\Pi^{dp}x:D.E)}.(4)✦

For a labelled term TT over SS and a map ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N, the labelled variable renaming T[ρ]T[\rho] is the labelled term over SS obtained by replacing each variable index nn by ρ(n)\rho(n) and preserving sorts and labels.✦ It acts recursively on subterms, using under each binder the lifted renaming that fixes the newly bound variable and shifts the renamed indices of older variables. Write ↑T\uparrow T for renaming by n↦n+1n\mapsto n+1.

A labelled context Γ\Gamma over SS is a newest-first list of labelled terms over SS; A::ΓA::\Gamma adjoins the newest declaration AA. Labelled context lookup Γ[n]=A\Gamma[n]=A is the least relation specified by (5). (A::Γ)[0]=↑A,Γ[n]=A(B::Γ)[n+1]=↑A.(A::\Gamma)[0]=\uparrow A, \qquad \frac{\Gamma[n]=A}{(B::\Gamma)[n+1]=\uparrow A}.(5)✦

The Definition

Definition 1. A normal positive target TT over SS is a labelled term satisfying (6). Target⁡(T)⇔Pos⁡(T)∧|T| is a full β normal form.\operatorname{Target}(T) \quad\Longleftrightarrow\quad \operatorname{Pos}(T)\ \land\ |T|\text{ is a full $\beta$ normal form}.(6)✦

A converter proof context (Γ,γ)(\Gamma,\gamma) over SS is a labelled context with a mode assignment γ:ℕ→{𝖽,𝗉}\gamma:\mathbb N\to\{\mathsf d,\mathsf p\} satisfying (7); the codomain FF is arbitrary. ProofContext⁡(Γ,γ)⇔every lookup Γ[n]=A with γ(n)=𝗉 satisfiesA=Πppx:R.Ffor some labelled R,F with Target⁡(R).\begin{gathered} \operatorname{ProofContext}(\Gamma,\gamma)\quad\Longleftrightarrow\\ \text{every lookup $\Gamma[n]=A$ with $\gamma(n)=\mathsf p$ satisfies}\\ A=\Pi^{pp}x:R.F \quad\text{for some labelled $R,F$ with $\operatorname{Target}(R)$.} \end{gathered}(7)✦

What Is Checked

The definitions concern labelled terms over an arbitrary sort collection SS and newest-first contexts equipped with assignments of data and proof modes. Equality of modes and labels is decidable; equality of labelled and unlabelled terms is decidable whenever equality of sorts is decidable.