OctoInformBeta

OpenAI preprint, September 2026 · §3. Sort profiles and normalization candidates · §3

Profiles and the signed dependency graph: Feasible sort sets, inhabited normal witnesses, and the primary graph determined by product rules

Sort profiles and their signed dependencies.

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

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), where SS is a set of sorts, 𝒜⊆S×S\mathcal A\subseteq S\times S is an axiom relation, and ℛ⊆S×S×S\mathcal R\subseteq S\times S\times S is a product-rule relation.✦ Domain and codomain positions in a dependent product have different signs in the primary dependency graph on sort profiles.

Terms are variables, sort constants s∈Ss\in S, applications MNM\,N, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ The displayed names are source notation; de Bruijn indices count from the nearest binder, starting at zero. Contexts list the newest declaration first. A valid context is a finite context obtained from the empty context by adjoining x:Ax:A whenever Γ⊢A:s\Gamma\vdash A:s for some s∈Ss\in S, where this judgement means that AA has sort ss in Γ\Gamma.✦

Variable renaming by a map ρ\rho on indices is the operation that replaces free variables according to ρ\rho, lifting the map under each binder by fixing zero and sending n+1n+1 to ρ(n)+1\rho(n)+1.✦ Simultaneous substitution by an assignment σ\sigma of terms is the operation that replaces free variables according to σ\sigma; under a binder, zero remains a variable and the image of n+1n+1 is σ(n)\sigma(n) with its free indices increased by one.✦ The single-variable substitution for a term aa is the assignment that sends zero to aa and n+1n+1 to the variable nn.✦ Bound-variable instantiation b[a/x]b[a/x] of a term bb by a term aa is the term obtained by simultaneous substitution in bb, sending zero to aa and n+1n+1 to the variable nn.✦

One-step β\beta reduction is the least relation containing the contraction in (1) and closed under every term constructor, including annotations and binder bodies. (λx:A.b)a→βb[a/x].(\lambda x:A.b)\,a\longrightarrow_\beta b[a/x].(1)✦ β\beta convertibility is the least equivalence relation on terms containing one-step β\beta reduction. A term TT is normal if it admits no one-step β\beta reduction, and weakly normalizing if it reaches a normal term by finitely many steps.✦ Write T#T^\# for the unique full β\beta normal form when one exists, with a fixed arbitrary fallback otherwise.✦

The typing judgement Γ⊢M:A\Gamma\vdash M:A is generated by the axiom, variable and weakening rules, dependent product formation, abstraction, application, and conversion.✦ An axiom (s,t)∈𝒜(s,t)\in\mathcal A types s:ts:t in the empty context. Variable introduction and weakening extend a context by a type having some sort. Product formation uses (s1,s2,s3)∈ℛ(s_1,s_2,s_3)\in\mathcal R for a domain of sort s1s_1 and a codomain of sort s2s_2 in the extended context, giving the product sort s3s_3. Abstraction requires its dependent product type to have a sort; application instantiates the codomain. Conversion replaces an expected type by a β\beta-convertible type that itself has a sort in the same context.

Normal Witnesses

An inhabited normal witness (T,e)(T,e) for a set I⊆SI\subseteq S in a context Γ\Gamma is a pair of terms such that TT is a normal type assigned every sort in II and ee has type TT. Write Wit⁡Γ(I)\operatorname{Wit}_\Gamma(I) for the existence condition in (2). Wit⁡Γ(I)⇔∃T,e,T is normal,(∀s∈I,Γ⊢T:s),Γ⊢e:T.\operatorname{Wit}_\Gamma(I) \quad\Longleftrightarrow\quad \exists T,e,\quad T\text{ is normal},\quad (\forall s\in I,\ \Gamma\vdash T:s),\quad \Gamma\vdash e:T.(2)✦

The Claim

Definition 1 (Sort profiles and the primary graph). The normal-form sort profile πΓ(T)⊆S\pi_\Gamma(T)\subseteq S of a term TT in a context Γ\Gamma is the set in (3). πΓ(T)={s∈S∣Γ⊢T#:s}.\pi_\Gamma(T)=\{s\in S\mid\Gamma\vdash T^\#:s\}.(3)✦ A feasible sort profile is a nonempty set I⊆SI\subseteq S realized by a normal term in a valid context, as specified in (4). Feas⁡(I)⇔I≠⌀∧∃Γ,N,Γ is valid,N is normal,πΓ(N)=I.\operatorname{Feas}(I) \quad\Longleftrightarrow\quad I\ne\varnothing\ \land\ \exists\Gamma,N,\quad \Gamma\text{ is valid},\quad N\text{ is normal},\quad\pi_\Gamma(N)=I.(4)✦ The axiom profile Ax⁡(s)\operatorname{Ax}(s) of a sort s∈Ss\in S is its set of axiom successors, given by (5). Ax⁡(s)={t∈S∣(s,t)∈𝒜}.\operatorname{Ax}(s)=\{t\in S\mid(s,t)\in\mathcal A\}.(5)✦ For sets I,J⊆SI,J\subseteq S, the product output profile Out⁡(I,J)\operatorname{Out}(I,J) is the set of outputs allowed by their domain and codomain sorts in (6). Out⁡(I,J)={c∈S∣∃a∈I,∃b∈J,(a,b,c)∈ℛ}.\operatorname{Out}(I,J) =\{c\in S\mid\exists a\in I,\ \exists b\in J,\ (a,b,c)\in\mathcal R\}.(6)✦ A profile triple (I,J,K)(I,J,K) is a triple of feasible sort profiles whose product profile is the output profile, as in (7). Triple⁡(I,J,K)⇔Feas⁡(I)∧Feas⁡(J)∧Feas⁡(K)∧K=Out⁡(I,J).\operatorname{Triple}(I,J,K) \quad\Longleftrightarrow\quad \operatorname{Feas}(I)\land\operatorname{Feas}(J)\land \operatorname{Feas}(K)\land K=\operatorname{Out}(I,J).(7)✦ The signed primary dependency graph has feasible sort profiles as vertices and the least signed edge relation specified by (8), where ++ denotes a positive edge and −- a negative edge. I→+Jif I,J are feasible and J⊊I,I→−K,J→+Kif (I,J,K) is a profile triple.\begin{aligned} I\xrightarrow{+}J &\quad\text{if $I,J$ are feasible and $J\subsetneq I$},\\ I\xrightarrow{-}K,\qquad J\xrightarrow{+}K &\quad\text{if $(I,J,K)$ is a profile triple}. \end{aligned}(8)✦

Theorem 1 (Feasibility and witnesses). Let TT be weakly normalizing, and suppose its normal-form sort profile in Γ\Gamma is nonempty. Then (9) holds. Feas⁡(πΓ(T)).\operatorname{Feas}\bigl(\pi_\Gamma(T)\bigr).(9)✦ For a feasible sort profile I⊆SI\subseteq S, (10) holds. ∃Γ,Γ is valid∧Wit⁡Γ(I).\exists\Gamma,\quad \Gamma\text{ is valid}\quad\land\quad\operatorname{Wit}_\Gamma(I).(10)✦

What Is Checked

These definitions and assertions are stated over arbitrary axiom and product-rule relations, full β\beta reduction, the typing judgement Γ⊢M:A\Gamma\vdash M:A, and valid contexts.