OctoInformBeta

OpenAI preprint, September 2026 · §5. Observation spaces and substitution-stable candidates

Lemma 26: Legal products admit compatible profiles, and component membership forces active application domains to be direct

Plainness propagates backwards and free signs compose.

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

Applying a term of type Πx:A.B\Pi x:A.B to an argument q:Aq:A gives the expected type B[q/x]B[q/x]. Observation layers concern the sort profiles of these types and the signs assigned to the domain and codomain positions of a product.

Let P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) be a pure type specification, with arbitrary axiom and product-rule relations. 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.✦ We use named notation for terms whose unnamed variables are de Bruijn indices, with zero referring to the nearest binder. Renaming acts on free variables and is lifted under binders; simultaneous substitution is capture-avoiding. Bound variable instantiation B[q/x]B[q/x] substitutes qq for the bound variable and removes that binder.✦

Full β\beta reduction contracts (λx:A.M)q(\lambda x:A.M)\,q to M[q/x]M[q/x] and is closed under every term position, including annotations and binder bodies.✦ Full β\beta convertibility is the smallest equivalence relation on terms containing full β\beta reduction.✦ A term TT is normal if it admits no full β\beta reduction step, and weakly normalizing if it reduces by full β\beta reduction in finitely many steps to a normal term. Write T#T^\# for the chosen full normal form when one exists, with a fixed fallback otherwise.✦

Typing Γ⊢M:A\Gamma\vdash M:A uses the axiom, variable, weakening, product, abstraction, application and conversion rules of PP. Contexts are newest-first finite lists. A valid context for PP is a newest-first finite list obtained from the empty context by successive extensions of a context Γ\Gamma with a type AA whenever Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦ A legal term MM in Γ\Gamma is a term occurring as either the subject or the expected type of a typing judgement in Γ\Gamma.✦ System weak normalization means that every legal term in every valid context is weakly normalizing, including both subjects and expected types.✦

Profiles and Observation Layers

The normal form sort profile πΓ(T)\pi_\Gamma(T) of a term TT in a context Γ\Gamma is the set of all sorts typing T#T^\# in Γ\Gamma.✦ The axiom profile Ax⁡(s)\operatorname{Ax}(s) of a sort ss is the set of its axiom successors, and the product output profile Out⁡(I,J)\operatorname{Out}(I,J) of profiles II and JJ is the set of every output allowed by a domain sort in II and a codomain sort in JJ: πΓ(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 profile is a nonempty set I=πΓ(T)I=\pi_\Gamma(T) from (1), for some valid context Γ\Gamma and normal term TT.✦ A feasible product profile triple (I,J,K)(I,J,K) is a triple of feasible domain, codomain and product profiles satisfying K=Out⁡(I,J)K=\operatorname{Out}(I,J); we write Triple⁡(I,J,K)\operatorname{Triple}(I,J,K) for this condition.✦

The primary graph has profiles as vertices and signs 00 and 11, denoting positive and negative edges. Its positive edges are strict inclusions I→JI\to J with J⊊IJ\subsetneq I and both profiles feasible, and codomain edges J→KJ\to K from feasible triples (I,J,K)(I,J,K). Its negative edges are the domain edges I→KI\to K from those triples. Write I→b1JI\xrightarrow{b}_1J for a primary edge of sign bb.

A signed directed walk is a finite walk, allowing repetitions, whose sign is the parity of its number of negative edges; the empty walk has sign 00.✦ Write I⤳ibJI\leadsto_i^bJ for such a walk in graph ii, and I⤳i+JI\leadsto_i^+J for a walk using only positive edges. Directed reachability ignores the sign.✦ A strongly connected component CC is a set containing a vertex rr such that its members are exactly the vertices reachable from rr and from which rr is reachable.✦

An observation layer II for a set CC of profiles is a profile positively reachable in the primary graph from a nonempty axiom profile whose singleton sort belongs to CC. The set of observation layers is 𝒪C={I∣∃s∈S{s}∈C,Ax⁡(s)≠⌀,Ax⁡(s)⤳1+I}.\mathcal O_C=\{I\mid\exists s\in S\; \{s\}\in C,\quad\operatorname{Ax}(s)\ne\varnothing,\quad \operatorname{Ax}(s)\leadsto_1^+I\}.(2)✦ On the layers in (2), the secondary graph retains every positive primary edge. It has a negative edge I→12KI\xrightarrow{1}_2K whenever Triple⁡(I,J,K)\operatorname{Triple}(I,J,K) holds and all three profiles belong to 𝒪C\mathcal O_C. These are exactly its edges.

A direct layer II for a set CC of profiles is an observation layer occurring as the domain profile of a feasible triple whose codomain and product profiles lie in CC: Direct⁡C(I)⇔I∈𝒪C∧∃J∈C∃K∈CTriple⁡(I,J,K).\operatorname{Direct}_C(I)\quad\Longleftrightarrow\quad I\in\mathcal O_C\ \land\ \exists J\in C\;\exists K\in C\;\operatorname{Triple}(I,J,K).(3) An active layer II for a set CC of profiles is a profile that reaches a direct layer for CC through secondary edges. A plain layer II for a set CC of profiles is a profile that reaches direct layers for CC by secondary walks of both parities, with possibly different endpoints. A free layer II of sign bb for a set CC of profiles is a nonplain profile with a secondary walk of sign bb to a direct layer for CC.✦ We write Active⁡C(I)\operatorname{Active}_C(I), Plain⁡C(I)\operatorname{Plain}_C(I) and Free⁡C(I,b)\operatorname{Free}_C(I,b) for these conditions, using the direct layers of (3).

Tower Types and Application Frames

A saturated context tower Ω\Omega is a family of valid contexts Γn\Gamma_n of length nn, each extending the preceding context by a type having a sort there. Every fixed-level type having a sort at stage nn is declared again at stages arbitrarily far beyond nn. Free names in the tower have fixed levels. Their translation to indices at stage nn is the renaming ρn(i)=n−1−i\rho_n(i)=n-1-i for i<ni<n, with ρn(i)=i\rho_n(i)=i otherwise.✦

Tower typing and the tower normal form profile are given by Ω⊢M:A⇔∃nΓn⊢M[ρn]:A[ρn],πΩ(T)={s∈S∣Ω⊢T#:s}.\begin{aligned} \Omega\vdash M:A &\quad\Longleftrightarrow\quad \exists n\;\Gamma_n\vdash M[\rho_n]:A[\rho_n],\\ \pi_\Omega(T)&=\{s\in S\mid\Omega\vdash T^\#:s\}. \end{aligned}(4) A normalized active type TT in Ω\Omega is a normal term having some sort in Ω\Omega and an active profile πΩ(T)\pi_\Omega(T).✦ An active application key a=(A,B,q)a=(A,B,q) for TT is a product presentation T=Πx:A.BT=\Pi x:A.B with a normal argument Ω⊢q:A\Omega\vdash q:A for which πΩ(B[q/x])\pi_\Omega(B[q/x]) is active.✦ Under system weak normalization its target term is Ta=(B[q/x])#.T_a=(B[q/x])^\#.(5)✦

The Claim

Theorem 1. Let PP be a pure type specification and CC a set of profiles. If JJ is plain and I→b2JI\xrightarrow{b}_2J is a secondary edge, then (6) holds: Plain⁡C(I).\operatorname{Plain}_C(I).(6)✦ If II and JJ are free with signs ss and tt, respectively, and I→b2JI\xrightarrow{b}_2J is a secondary edge, their signs satisfy (7), where ⊕\oplus is addition modulo two: s=b⊕t.s=b\oplus t.(7)✦ Let Ω\Omega be a saturated context tower. Suppose Ω⊢Πx:A.B:u\Omega\vdash\Pi x:A.B:u for some sort uu and Ω⊢q:A\Omega\vdash q:A. There is a profile JJ satisfying (8): Triple⁡(πΩ(A),J,πΩ(Πx:A.B))∧πΩ(B[q/x])⤳1+J.\operatorname{Triple}\bigl(\pi_\Omega(A),J, \pi_\Omega(\Pi x:A.B)\bigr) \quad\land\quad \pi_\Omega(B[q/x])\leadsto_1^+J.(8)✦ Suppose further that PP is system weakly normalizing, CC is a strongly connected component of the primary graph, and a=(A,B,q)a=(A,B,q) is an active application key for a normalized active type TT. If πΩ(T)\pi_\Omega(T) and πΩ(Ta)\pi_\Omega(T_a) lie in CC and πΩ(A)\pi_\Omega(A) is active, then (9) holds: Direct⁡C(πΩ(A)).\operatorname{Direct}_C\bigl(\pi_\Omega(A)\bigr).(9)✦

What Is Checked

The layer claims are stated over the secondary graph for an arbitrary specification and set CC; the frame claims concern tower typings of both the product and its argument, with the component and activity hypotheses required for (9). Under system weak normalization, the target construction in (5) yields a normal term having a sort in Ω\Omega and an active profile.