OctoInformBeta

OpenAI preprint, September 2026 ยท ยง10. Exclusion and completion of the proof

Proposition 58: Normal positive targets also exclude proof-mode inhabitants in converter proof contexts

Finite weakly normalizing systems satisfy relational exclusion.

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 sorts that classify a normal type determine a profile of that type. Product formation relates these profiles through a signed graph. The setting also includes labelled terms, whose labels distinguish data arguments from proof arguments.

A pure type system specification P=(S,๐’œ,โ„›)P=(S,\mathcal A,\mathcal R) consists of a set 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.โœฆ Its terms are variables, sorts, applications MNM\,N, annotated abstractions ฮปx:A.M\lambda x:A.M, and dependent products ฮ x:A.B\Pi x:A.B.โœฆ Displayed binders use names; variables have de Bruijn indices, with zero referring to the nearest binder, and contexts list the newest declaration first.

A renaming ฯ\rho is a map from variable indices to variable indices whose action on terms replaces each variable index nn by ฯ(n)\rho(n) and fixes sorts. A simultaneous substitution ฯƒ\sigma is a map from variable indices to terms whose action on terms replaces index nn by the term ฯƒ(n)\sigma(n). Both operations act recursively on every term component. Write Mโ†‘M\!\uparrow for renaming by nโ†ฆn+1n\mapsto n+1. Under a binder, the lifted renaming fixes the new index zero and shifts renamed older indices; the lifted substitution fixes the new variable and shifts the images of older variables. The single substitution determined by aa sends zero to aa and n+1n+1 to variable nn.โœฆ The bound variable instantiation b[a]b[a] of a term bb by a term aa is the result of applying to bb the substitution that sends zero to aa and n+1n+1 to variable nn.โœฆ

The typing judgement ฮ“โŠขM:A\Gamma\vdash M:A is generated by the pure type system rules. An axiom (s,t)โˆˆ๐’œ(s,t)\in\mathcal A gives []โŠขs:t[]\vdash s:t. A domain AA with ฮ“โŠขA:s\Gamma\vdash A:s permits the variable judgement A::ฮ“โŠข0:Aโ†‘A::\Gamma\vdash 0:A\!\uparrow and weakening into A::ฮ“A::\Gamma, shifting both subject and expected type by nโ†ฆn+1n\mapsto n+1. Product formation uses ฮ“โŠขA:s1\Gamma\vdash A:s_1, x:A,ฮ“โŠขB:s2x:A,\Gamma\vdash B:s_2, and (s1,s2,s3)โˆˆโ„›(s_1,s_2,s_3)\in\mathcal R to assign s3s_3 to ฮ x:A.B\Pi x:A.B. An abstraction has type ฮ x:A.B\Pi x:A.B when its body has type BB in the extended context and the product has a sort. Application of a function of this product type to a:Aa:A has type B[a]B[a]. Conversion changes an expected type to a ฮฒ\beta-convertible type that itself has a sort. A valid context ฮ“\Gamma of PP is a finite list obtained from the empty context by adjoining domains having a sort in the preceding context.โœฆ

Full one-step ฮฒ\beta reduction contracts (ฮปx:A.b)a(\lambda x:A.b)\,a to b[a]b[a] and is closed under every term component, including annotations and binder bodies.โœฆ ฮฒ\beta convertibility of terms of PP is the smallest equivalence relation containing full one-step ฮฒ\beta reduction.โœฆ A normal term MM of PP is a term that admits no full ฮฒ\beta reduction step.โœฆ A weakly normalizing term MM of PP is a term that reaches a normal term by full ฮฒ\beta reduction in finitely many steps, possibly zero; its chosen normal form is denoted by M#M^\#. A legal term LL in a context ฮ“\Gamma of PP is a term occurring as either the subject or the expected type of a judgement ฮ“โŠขM:A\Gamma\vdash M:A.โœฆ System weak normalization means that every legal term in every valid context is weakly normalizing.โœฆ

Profiles and Signed Graphs

The normal form sort profile ฯ€ฮ“(T)\pi_\Gamma(T) is the set of all sorts typing T#T^\#.โœฆ The axiom profile Ax⁡(s)\operatorname{Ax}(s) and the product output profile Out⁡(I,J)\operatorname{Out}(I,J) are the sets in (1): ฯ€ฮ“(T)={sโˆˆSโˆฃฮ“โŠขT#:s},Ax⁡(s)={tโˆˆSโˆฃ(s,t)โˆˆ๐’œ},Out⁡(I,J)={cโˆˆSโˆฃโˆƒaโˆˆIโˆƒbโˆˆJ,(a,b,c)โˆˆโ„›}.\begin{aligned} \pi_\Gamma(T)&=\{s\in S\mid\Gamma\vdash T^\#:s\},\\ \operatorname{Ax}(s)&=\{t\in S\mid(s,t)\in\mathcal A\},\\ \operatorname{Out}(I,J)&= \{c\in S\mid\exists a\in I\;\exists b\in J,\ (a,b,c)\in\mathcal R\}. \end{aligned}(1) A feasible sort profile IโІSI\subseteq S is a nonempty set equal to ฯ€ฮ“(T)\pi_\Gamma(T) for some valid context ฮ“\Gamma and normal term TT.โœฆ A feasible product profile triple (I,J,K)(I,J,K) consists of feasible profiles satisfying K=Out⁡(I,J)K=\operatorname{Out}(I,J); write ๐’ฏP\mathcal T_P for the set of these triples.โœฆ

The primary signed graph EPE_P has sets of sorts as vertices and exactly the positive and negative edges in (2): EP+={(I,J)โˆฃI,J are feasible,JโŠŠI}โˆช{(J,K)โˆฃโˆƒI,(I,J,K)โˆˆ๐’ฏP},EPโˆ’={(I,K)โˆฃโˆƒJ,(I,J,K)โˆˆ๐’ฏP}.\begin{aligned} E_P^+&=\{(I,J)\mid I,J\text{ are feasible},\ J\subsetneq I\} \cup\{(J,K)\mid\exists I,\ (I,J,K)\in\mathcal T_P\},\\ E_P^-&=\{(I,K)\mid\exists J,\ (I,J,K)\in\mathcal T_P\}. \end{aligned}(2)โœฆ A signed directed walk ww in a signed directed graph EE is a finite directed walk whose parity is the number of negative edges modulo two; repetitions are permitted, and the empty walk has even parity. Write IโคณEฮตJI\leadsto_E^\varepsilon J for such a walk of parity ฮตโˆˆ{0,1}\varepsilon\in\{0,1\} and IโคณEJI\leadsto_E J for directed reachability with either parity. Positive reachability, written Iโ†’+*EJI\xrightarrow{+*}_E J, uses only positive edges and permits the empty walk.โœฆ A strongly connected component CC of EE is a set containing a vertex rr such that IโˆˆCI\in C precisely when rโคณEIr\leadsto_E I and IโคณErI\leadsto_E r.โœฆ

For a family CC of profiles, the observation layers ๐’ชC\mathcal O_C are the profiles positively reachable from a nonempty axiom profile of a sort whose singleton belongs to CC, as in (3): ๐’ชC={IโˆฃโˆƒsโˆˆS,{s}โˆˆC,Ax⁡(s)โ‰ โŒ€,Ax⁡(s)โ†’+*EPI}.\mathcal O_C=\{I\mid\exists s\in S,\ \{s\}\in C,\ \operatorname{Ax}(s)\ne\varnothing,\ \operatorname{Ax}(s)\xrightarrow{+*}_{E_P}I\}.(3)โœฆ A direct observation layer II for CC is a profile in ๐’ชC\mathcal O_C for which some J,KโˆˆCJ,K\in C satisfy (I,J,K)โˆˆ๐’ฏP(I,J,K)\in\mathcal T_P. The secondary signed graph ECE_C has exactly the edges in (4): EC+={(I,J)โˆˆEP+โˆฃI,Jโˆˆ๐’ชC},ECโˆ’={(I,K)โˆฃโˆƒJ,I,J,Kโˆˆ๐’ชC,(I,J,K)โˆˆ๐’ฏP}.\begin{aligned} E_C^+&=\{(I,J)\in E_P^+\mid I,J\in\mathcal O_C\},\\ E_C^-&=\{(I,K)\mid\exists J,\ I,J,K\in\mathcal O_C, \ (I,J,K)\in\mathcal T_P\}. \end{aligned}(4)โœฆ A plain observation layer II is a profile with an even walk in ECE_C to a direct observation layer and an odd walk in ECE_C to a possibly different direct observation layer.โœฆ

A forbidden configuration ๐–ฅ(P,C)\mathsf F(P,C) consists of a strongly connected component DD of ECE_C all of whose vertices are plain observation layers, with a negative secondary edge having both endpoints in DD, and a triple (I,J,K)โˆˆ๐’ฏP(I,J,K)\in\mathcal T_P and sort ss such that J,K,{s}โˆˆDJ,K,\{s\}\in D, Ax⁡(s)โ‰ โŒ€\operatorname{Ax}(s)\ne\varnothing, and Ax⁡(s)โ†’+*EPI\operatorname{Ax}(s)\xrightarrow{+*}_{E_P}I.โœฆ Relational exclusion ๐–ฑ๐–ค(P)\mathsf{RE}(P) is the condition that every strongly connected component CC of EPE_P containing an odd closed walk and a triple of ๐’ฏP\mathcal T_P with all three profiles in CC has no forbidden configuration.โœฆ

Labelled Targets

The modes are data ๐–ฝ\mathsf d and proof ๐—‰\mathsf p.โœฆ A label โ„“\ell specifies its argument mode dโ„“d_\ell and result mode rโ„“r_\ell by (5): (d๐–ฝ๐–ฝ,r๐–ฝ๐–ฝ)=(๐–ฝ,๐–ฝ),(d๐–ฝ๐—‰,r๐–ฝ๐—‰)=(๐–ฝ,๐—‰),(d๐—‰๐—‰,r๐—‰๐—‰)=(๐—‰,๐—‰).(d_{\mathsf{dd}},r_{\mathsf{dd}})=(\mathsf d,\mathsf d),\qquad (d_{\mathsf{dp}},r_{\mathsf{dp}})=(\mathsf d,\mathsf p),\qquad (d_{\mathsf{pp}},r_{\mathsf{pp}})=(\mathsf p,\mathsf p).(5) Labelled terms attach one of these labels to each application, annotated abstraction, and dependent product, written fโ„“af\,{}_{\ell}a, ฮปโ„“x:A.b\lambda_\ell x:A.b, and ฮ โ„“x:A.B\Pi_\ell x:A.B.โœฆ Label erasure |M||M| deletes all labels and preserves every other term component.โœฆ Labelled renaming, simultaneous substitution, single substitution, and bound variable instantiation act as above and preserve constructor labels.

Labelled ฮฒ\beta reduction has full contextual closure and contracts (ฮปโ„“x:A.b)โ„“a(\lambda_\ell x:A.b)\,{}_{\ell}a to b[a]b[a] only when the two labels agree.โœฆ Labelled convertibility of labelled terms is the smallest equivalence relation containing labelled ฮฒ\beta reduction.โœฆ Labelled typing ฮ“โŠขLM:A\Gamma\vdash_{\mathrm L}M:A uses the same typing rules, with any label in product formation, matching labels on an abstraction and its product type, matching labels on an application and its functionโ€™s product type, and labelled convertibility in conversion.โœฆ

A mode environment ฮณ\gamma is a function from variable indices to modes. Its extension m::ฮณm::\gamma gives zero mode mm and index n+1n+1 mode ฮณ(n)\gamma(n).โœฆ The mode discipline ฮณโŠขmM:m\gamma\vdash_{\mathrm m}M:m is the least judgement assigning variable nn mode ฮณ(n)\gamma(n) and each sort data mode, with the remaining rules in (6): ฮณโŠขmf:rโ„“ฮณโŠขma:dโ„“ฮณโŠขmfโ„“a:rโ„“,ฮณโŠขmA:๐–ฝdโ„“::ฮณโŠขmb:rโ„“ฮณโŠขmฮปโ„“x:A.b:rโ„“,ฮณโŠขmA:๐–ฝdโ„“::ฮณโŠขmB:๐–ฝฮณโŠขmฮ โ„“x:A.B:๐–ฝ.\begin{gathered} \frac{\gamma\vdash_{\mathrm m}f:r_\ell\quad \gamma\vdash_{\mathrm m}a:d_\ell} {\gamma\vdash_{\mathrm m}f\,{}_{\ell}a:r_\ell},\\[6pt] \frac{\gamma\vdash_{\mathrm m}A:\mathsf d\quad d_\ell::\gamma\vdash_{\mathrm m}b:r_\ell} {\gamma\vdash_{\mathrm m}\lambda_\ell x:A.b:r_\ell},\qquad \frac{\gamma\vdash_{\mathrm m}A:\mathsf d\quad d_\ell::\gamma\vdash_{\mathrm m}B:\mathsf d} {\gamma\vdash_{\mathrm m}\Pi_\ell x:A.B:\mathsf d}. \end{gathered}(6)โœฆ

A data-only labelled term MM is a labelled term in which every constructor label is ๐–ฝ๐–ฝ\mathsf{dd}.โœฆ A positive telescope TT is a labelled term formed from a data-only labelled term by prefixing zero or more ๐–ฝ๐—‰\mathsf{dp} dependent products with arbitrary domains.โœฆ A normal positive target TT is a positive telescope whose erasure |T||T| is in full ฮฒ\beta normal form.โœฆ

Context lookup assigns index zero the successor shift of the newest declared type; on adjoining a declaration it shifts every older variableโ€™s type once more.โœฆ A converter proof context (ฮ“,ฮณ)(\Gamma,\gamma) is a labelled context with a mode environment such that each declared variable assigned proof mode has, under context lookup, type ฮ ๐—‰๐—‰x:R.F\Pi_{\mathsf{pp}}x:R.F for a normal positive target RR and an arbitrary codomain FF.โœฆ

The Claim

Theorem 1. Suppose PP is system-wide weakly normalizing. Let (ฮ“,ฮณ)(\Gamma,\gamma) be a converter proof context and TT a normal positive target. The exclusion of proof-mode inhabitants is (7): {Mโˆฃฮ“โŠขLM:T,ฮณโŠขmM:๐—‰}=โŒ€.\{M\mid\Gamma\vdash_{\mathrm L}M:T,\ \gamma\vdash_{\mathrm m}M:\mathsf p\}=\varnothing.(7)โœฆ If the sort set SS is finite, PP also satisfies (8): ๐–ฑ๐–ค(P).\mathsf{RE}(P).(8)โœฆ

In the paper, the result reads: if every legal expression of PP is weakly ฮฒ\beta-normalizing, then every primary component CC containing an odd closed walk and a feasible product profile triple entirely within CC satisfies the graph exclusion condition of $\S5$.

What Is Checked

Both statements assume system weak normalization: the relational statement concerns finite sort sets and the primary and secondary profile graphs, while the target statement concerns labelled typing and mode discipline in converter proof contexts with normal positive targets.