OctoInformBeta

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

Lemma 27: For weakly normalizing systems, with prefix decomposition and a distinguished table at each chosen base value

Graph exclusion permits recursive plain spaces.

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

An observation of a normalized plain type follows a finite sequence of typed applications. Values supplied at its active domains are the arguments of an observation table with values in a fixed base set.

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations, and a family C⊆𝒫(S)C\subseteq\mathcal P(S). Terms are variables, sort constants, applications MNM\,N, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ Write Γ⊢M:A\Gamma\vdash M:A for typing by the axiom, variable, weakening, product, abstraction, application, and conversion rules of PP. Conversion uses the equivalence relation generated by full β\beta reduction, including reduction in annotations and binder bodies.✦ Substitution B[a/x]B[a/x] is capture-avoiding instantiation of the bound variable✦; simultaneous substitution and variable renaming act under binders by their lifts.

A valid context is obtained from the empty context by adjoining AA when Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦ A legal term in Γ\Gamma occurs as either the subject or the expected type of a typing judgement.✦ Assume PP is weakly normalizing: every legal term in every valid context reaches a β\beta normal form.✦ A normal term has no one-step reduct✦, and M#M^\# denotes a chosen normal form when weak normalization supplies one.✦

Let Ω\Omega be a saturated context tower, with a valid context Γn\Gamma_n of length nn at each stage and Γn+1=An::Γn\Gamma_{n+1}=A_n::\Gamma_n, where Γn⊢An:sn\Gamma_n\vdash A_n:s_n for some sns_n. Contexts are newest-first. Tower terms use fixed levels for free variables; at stage nn, a level i<ni<n is read as the de Bruijn index n−1−in-1-i, while indices i≥ni\geq n are unchanged, and renaming is lifted under binders. Displayed binders use named notation. Tower typing Ω⊢M:A\Omega\vdash M:A means that some stage types both expressions after this translation.✦ A saturated context tower Ω\Omega is a context tower in which every type sortable at a stage, expressed with fixed free levels, is declared again at arbitrarily late stages.

The normal form sort profiles, axiom successors, and product-rule outputs are πΓ(T)={s∈S∣Γ⊢T#:s},πΩ(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\},& \pi_\Omega(T)&=\{s\in S\mid\Omega\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 I=πΓ(T)I=\pi_\Gamma(T) from (1) is a nonempty set of sorts obtained from a normal term TT in a valid context Γ\Gamma. A feasible product profile triple (I,J,K)(I,J,K) consists of feasible profiles with K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦

Signed Profiles and Observation Layers

The primary graph has profiles as vertices. Its positive edges are strict inclusions I→JI\longrightarrow J with feasible endpoints and J⊊IJ\subsetneq I, and codomain edges J→KJ\longrightarrow K for feasible product profile triples (I,J,K)(I,J,K). Its negative edges are the domain edges I→KI\longrightarrow K of those triples. Write I⤳+JI\leadsto_+J for a finite path consisting of positive primary edges, including the empty path.✦

The observation layers associated with CC form the set 𝒪C={I∣∃s∈S[{s}∈C∧Ax⁡(s)≠⌀∧Ax⁡(s)⤳+I]}.\mathcal O_C= \{I\mid\exists s\in S\;[\{s\}\in C\ \land\ \operatorname{Ax}(s)\ne\varnothing\ \land\ \operatorname{Ax}(s)\leadsto_+I]\}.(2)✦ The secondary graph on (2) retains a positive primary edge when both endpoints belong to 𝒪C\mathcal O_C. It has a negative edge I→KI\longrightarrow K for a feasible product profile triple (I,J,K)(I,J,K) when all three profiles belong to 𝒪C\mathcal O_C.

A signed walk is a finite directed walk whose sign is the parity of its number of negative edges; the empty walk is positive.✦ Directed reachability allows either parity.✦ A strongly connected component is the set of vertices mutually reachable with a fixed vertex in the set.✦

A direct layer is an I∈𝒪CI\in\mathcal O_C for which a feasible product profile triple (I,J,K)(I,J,K) has J,K∈CJ,K\in C.✦ An active layer I∈𝒪CI\in\mathcal O_C is an observation layer that reaches a direct layer in the secondary graph.✦ A plain layer I∈𝒪CI\in\mathcal O_C is an observation layer with both a positive walk and a negative walk in the secondary graph to direct layers, whose endpoints may differ.✦

A forbidden configuration DD is a strongly connected component of the secondary graph, all of whose vertices are plain, containing a negative edge and admitting a feasible product profile triple (I,J,K)(I,J,K) and a sort ss with J,K,{s}∈D,Ax⁡(s)≠⌀,Ax⁡(s)⤳+I.J,K,\{s\}\in D,\qquad \operatorname{Ax}(s)\ne\varnothing,\qquad \operatorname{Ax}(s)\leadsto_+ I.(3)✦ Write 𝔉C\mathfrak F_C for the existence of such a component satisfying (3).

Plain Types and Observation Tables

A normalized plain type TT is a normal term sortable in Ω\Omega whose profile πΩ(T)\pi_\Omega(T) is plain.✦ Let 𝒩\mathcal N be the collection of these types. An application key (A,B,a)(A,B,a) at T∈𝒩T\in\mathcal N is a decomposition T=Πx:A.BT=\Pi x:A.B together with a normal argument aa such that Ω⊢a:A\Omega\vdash a:A and πΩ(B[a/x])\pi_\Omega(B[a/x]) is active.✦ The target node of an application key (A,B,a)(A,B,a) is (B[a/x])#(B[a/x])^\#; when πΩ(A)\pi_\Omega(A) is active, the domain node of that key is AA.

A plain observation schema FF on a set XX assigns to each n∈Xn\in X a set KF(n)K_F(n) of keys, a target τF(n,a)∈X\tau_F(n,a)\in X for each key, and an optional domain δF(n,a)∈X∪{⊥}\delta_F(n,a)\in X\cup\{\bot\}, where ⊥\bot means no domain.✦ The actual schema FΩ,CF_{\Omega,C} has node set 𝒩\mathcal N, the application keys just defined, and τFΩ,C(T,(A,B,a))=(B[a/x])#,δFΩ,C(T,(A,B,a))={A,πΩ(A) is active,⊥,otherwise.\tau_{F_{\Omega,C}}(T,(A,B,a))=(B[a/x])^\#, \qquad \delta_{F_{\Omega,C}}(T,(A,B,a))= \begin{cases} A,&\pi_\Omega(A)\text{ is active},\\ \bot,&\text{otherwise}. \end{cases}(4)✦

For a schema FF, a finite continuation path from nn is either the empty path εn\varepsilon_n or a::pa::p, where a∈KF(n)a\in K_F(n) and pp starts at τF(n,a)\tau_F(n,a).✦ Write 𝒫F(n)\mathcal P_F(n) for these paths. A payload occurrence at dd on pp is a frame of pp whose designated domain is dd; its set is Slot⁡F(p,d)\operatorname{Slot}_F(p,d), with occurrences at different frames kept distinct.✦ The recursive domain dependency ≺F\prec_F is the least relation satisfying δF(n,a)=d⇒d≺Fn,d≺FτF(n,a)⇒d≺Fn.\delta_F(n,a)=d\ \Longrightarrow\ d\prec_F n, \qquad d\prec_F\tau_F(n,a)\ \Longrightarrow\ d\prec_F n.(5)✦ Here d,n∈Xd,n\in X and a∈KF(n)a\in K_F(n) in (5).

Let FF be a schema on XX and K(d)K(d) a family of sets indexed by d∈Xd\in X. A frame parameter is an assignment of a value in K(d)K(d) to the designated domain dd of one frame.✦ A path parameter for FF and KK is an assignment of a value in K(d)K(d) to each payload occurrence at dd on a continuation path.✦ Their spaces, and the observation tables with base BB, are Fr⁡F,K(a)=∏d∈X∏δF(n,a)=dK(d),Par⁡F,K(p)=∏d∈X∏u∈Slot⁡F(p,d)K(d),Tab⁡F(K,B,n)=∏p∈𝒫F(n)(Par⁡F,K(p)→B).\begin{aligned} \operatorname{Fr}_{F,K}(a) &=\prod_{d\in X}\prod_{\delta_F(n,a)=d}K(d),\\ \operatorname{Par}_{F,K}(p) &=\prod_{d\in X}\prod_{u\in\operatorname{Slot}_F(p,d)}K(d),\\ \operatorname{Tab}_F(K,B,n) &=\prod_{p\in\mathcal P_F(n)} \bigl(\operatorname{Par}_{F,K}(p)\to B\bigr). \end{aligned}(6) Empty-path parameters in (6) are the empty assignment.✦ Parameter extension combines a first-frame assignment with a tail assignment✦; head and tail restriction recover these two assignments.

Let FF have well-founded recursive domain dependency ≺F\prec_F. For a base set BB and a node nn, the recursive plain space WF(B,n)W_F(B,n) is a set of observation tables defined by recursion along ≺F\prec_F, with table equation and unfolding equivalence WF(B,n)=Tab⁡F(WF(B,−),B,n),UF,B,n:WF(B,n)≃Tab⁡F(WF(B,−),B,n).\begin{aligned} W_F(B,n)&=\operatorname{Tab}_F(W_F(B,-),B,n),\\ U_{F,B,n}&:W_F(B,n)\simeq \operatorname{Tab}_F(W_F(B,-),B,n). \end{aligned}(7) The equivalence UF,B,nU_{F,B,n} in (7) is induced by the displayed equality of spaces.✦

The Claim

Theorem 1 (Plain spaces). Assume no forbidden configuration occurs. For the actual schema F=FΩ,CF=F_{\Omega,C}, the recursive domain dependency satisfies ≺F is well founded.\prec_F\text{ is well founded}.(8)✦ For any base set BB and n∈𝒩n\in\mathcal N, define the actual plain observation space by 𝒮B(n):=WF(B,n).\mathcal S_B(n):=W_F(B,n).(9)✦ The prefix decomposition for a well-founded schema specializes to the equivalence pref⁡n:𝒮B(n)≃B×∏a∈KF(n)(Fr⁡F,𝒮B(a)→𝒮B(τF(n,a))).\operatorname{pref}_n:\mathcal S_B(n)\simeq B\times\prod_{a\in K_F(n)} \Bigl(\operatorname{Fr}_{F,\mathcal S_B}(a)\to \mathcal S_B(\tau_F(n,a))\Bigr).(10)✦ For any schema HH with well-founded recursive domain dependency, any set BB, and any b∈Bb\in B, its distinguished value at a node nn is 𝒅bH(n):=UH,B,n−1((p,ξ)↦b)∈WH(B,n).\mathbf d^{H}_b(n):= U_{H,B,n}^{-1}\bigl((p,\xi)\mapsto b\bigr)\in W_H(B,n).(11)✦

In the paper, the result reads: under the graph exclusion, the plain spaces admit prefix decomposition and distinguished values with base the constant 𝒕\mathbf t whose next values are distinguished values.

What Is Checked

The actual spaces (9) and prefix maps (10) concern normalized plain types in a saturated tower of a weakly normalizing pure type system, with the graph exclusion as the hypothesis of (8). The distinguished values (11) are stated for any well-founded schema and any chosen base value.

For every schema, a payload occurrence at dd on a continuation path from nn gives the recursive domain dependency d≺Fnd\prec_F n.✦