OctoInformBeta

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

Lemma 29: Normal syntax has good active values under typed raw substitutions, and relevant profiles give good readouts at sorts

Conversion and renaming preserve structural goodness.

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

Consider a typing tree for an annotated term together with a raw substitution into a saturated context tower. The questions are whether structural goodness depends on the chosen convertible images, and when normal syntax has good active values and readouts.

Let P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) be a pure type system with arbitrary axiom and product-rule relations. Terms have annotated abstractions λx:A.M\lambda x:A.M and dependent products Πx:A.B\Pi x:A.B. Write M≡βNM\equiv_\beta N for beta convertibility, and M#M^\# for a chosen beta normal form when MM is weakly normalizing. Normality and strong normalization refer to full beta reduction, including annotations and binder bodies. A context is valid when each declaration has a sort in the preceding context.✦ A legal term is a term that occurs as a subject or an expected type in a typing judgment✦; system weak normalization is the property that every legal term in every valid context has a beta normal form.✦

A saturated context tower Ω\Omega is a sequence of valid contexts of length nn at stage nn, extended by one sortable declaration at each stage, in which each type sortable in an earlier prefix, with fixed free levels, is declared again beyond every prescribed stage.✦ The judgment Ω⊢M:A\Omega\vdash M:A means that M:AM:A holds at some finite stage after translating free levels to that stage’s variable indices.✦ Ordinary contexts use newest declarations first and variables indexed by natural numbers. A typing tree t:Γ⊢M:Tt:\Gamma\vdash M:T retains the formation choices and conversions at every node, including each chosen product-rule triple.✦

Define the profiles and product outputs by (1); a feasible profile is a nonempty profile of a normal term in a valid context. πΓ(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\mathcal A(s,t)\},& \operatorname{Out}(I,J)&=\{c\in S\mid \exists a\in I\;\exists b\in J\;\mathcal R(a,b,c)\}. \end{aligned}(1) 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).✦ The primary signed graph has positive edges I→JI\to J for strict inclusions J⊊IJ\subsetneq I between feasible profiles, and, for each feasible triple, a negative edge I→KI\to K and a positive edge J→KJ\to K.✦ A signed walk has the parity of its number of negative edges✦; directed reachability allows either parity✦, whereas positive reachability uses only positive edges.✦ Empty walks are allowed. The axiom profile Ax⁡(s)\operatorname{Ax}(s) of a sort ss is the set of its axiom successors.

Fix a family CC of profiles. The observation layers of the family CC are the profiles positively reachable in the primary graph from a nonempty Ax⁡(s)\operatorname{Ax}(s) with {s}∈C\{s\}\in C.✦ The secondary graph has the positive primary edges between observation layers, and a negative edge I→KI\to K for each feasible triple whose three profiles are observation layers.✦ A direct layer II is an observation layer occurring in a triple (I,J,K)(I,J,K) with J,K∈CJ,K\in C.✦ An active layer II is an observation layer that reaches a direct layer in the secondary graph; write 𝖠𝖼𝗍(I)\mathsf{Act}(I) for this condition.✦ A plain layer is an observation layer with walks of both parities to direct layers.✦ A free layer of sign ε\varepsilon is a nonplain profile with a walk of parity ε\varepsilon to a direct layer.✦

A strongly connected component consists of all vertices mutually reachable with one of its vertices.✦ A forbidden configuration is a secondary strongly connected component DD of plain layers containing a negative edge, together with a feasible triple (I,J,K)(I,J,K) and a sort ss such that J,K,{s}∈DJ,K,\{s\}\in D, Ax⁡(s)\operatorname{Ax}(s) is nonempty, and Ax⁡(s)\operatorname{Ax}(s) positively reaches II in the primary graph.✦ Component relevance 𝖱𝖾𝗅C(Γ,M)\mathsf{Rel}_C(\Gamma,M) of a term MM in a context Γ\Gamma is the condition in (2), where ⤳prim\leadsto_{\mathrm{prim}} denotes primary directed reachability. 𝖱𝖾𝗅C(Γ,M)⇔∃K∈CπΓ(M)⤳primK.\mathsf{Rel}_C(\Gamma,M)\quad\Longleftrightarrow\quad \exists K\in C\;\;\pi_\Gamma(M)\leadsto_{\mathrm{prim}}K.(2)✦

Values, Readouts, and Goodness

A tower-typed raw substitution σ:Γ→Ω\sigma:\Gamma\to\Omega assigns an arbitrary term σ(n)\sigma(n) to each variable, with Ω⊢σ(n):A[σ]\Omega\vdash\sigma(n):A[\sigma] whenever the context lookup at nn is AA.✦ Two tower-typed raw substitutions σ,τ:Γ→Ω\sigma,\tau:\Gamma\to\Omega are compatible when σ(n)≡βτ(n)\sigma(n)\equiv_\beta\tau(n) for every n<|Γ|n<|\Gamma|.✦ A declaration-preserving renaming ρ:Γ→Δ\rho:\Gamma\to\Delta is a map of variables sending each lookup n:An:A to a lookup ρ(n):A[ρ]\rho(n):A[\rho]; tρt^\rho denotes the renamed typing tree in a valid Δ\Delta.

A normalization candidate at TT is a set AA satisfying the bounds in (3) and closed under typed head expansion.✦ For a type DD, write Top⁡D\operatorname{Top}_D for the strongly normalizing terms typed at DD in the tower.✦ A tested stack is an argument list that is empty at any type, or has first argument n∈Top⁡Dn\in\operatorname{Top}_D at a product Πx:D.E\Pi x:D.E and a remaining tested stack at (E[n/x])#(E[n/x])^\#.✦ Iterated application is written Mn→M\vec n. Top⁡T={M∣Ω⊢M:T and M is strongly normalizing},GT={M∣Ω⊢M:T and Mn→ is strongly normalizing for every tested stack n→ at T},GT⊆A⊆Top⁡T.\begin{aligned} \operatorname{Top}_T&=\{M\mid\Omega\vdash M:T\text{ and }M\text{ is strongly normalizing}\},\\ G_T&=\{M\mid\Omega\vdash M:T\text{ and }M\vec n\text{ is strongly normalizing} \text{ for every tested stack }\vec n\text{ at }T\},\\ G_T&\subseteq A\subseteq\operatorname{Top}_T. \end{aligned}(3) A candidate AA at TT is closed under typed head expansion when it contains (λx:D.b)nn→(\lambda x:D.b)\,n\,\vec n whenever this term has tower type TT, its annotation DD, body bb, argument nn and remaining argument list are strongly normalizing, and b[n/x]n→∈Ab[n/x]\vec n\in A. Argument list reduction is the relation on argument lists that changes one entry by a beta step.✦ An actual type is a normal sortable term or a literal sort. A candidate assignment is a function assigning a candidate to every actual type; denote the space of these assignments by ℬ\mathcal B.✦ The ground candidate GTG_T consists of the terms of tower type TT whose application to every tested stack at TT is strongly normalizing.✦

The observation constructions use system weak normalization and exclusion of a forbidden configuration. A normalized active type is a normal sortable type with active profile✦; a normalized plain type is a normal sortable type with plain profile. An application key at a normalized active or normalized plain type TT is a choice of T=Πx:D.ET=\Pi x:D.E and a normal argument aa with Ω⊢a:D\Omega\vdash a:D and active profile at E[a/x]E[a/x]. The target of an application key at T=Πx:D.ET=\Pi x:D.E with argument aa is (E[a/x])#(E[a/x])^\#.

The plain observation schema has these keys and targets, with a domain parameter precisely when the key’s domain is active.✦ A finite continuation path is a finite sequence of keys following their targets.✦ The payload occurrences of a finite continuation path are occurrences that select the domain parameters on that path.✦ A plain observation at TT is a function assigning a base result to each finite continuation path and every assignment of recursive plain observations to its payload occurrences. With base ℬ\mathcal B, write this space as XTX_T. Its prefix decomposition in (4) separates the empty path from the first key; PaP_a is the recursive plain space at the domain of aa when that domain is active, and is a one-element space otherwise. XT≃ℬ×∏a a key at T(Pa→Xtarget⁡(a)).X_T\simeq\mathcal B\times\prod_{a\text{ a key at }T} (P_a\to X_{\operatorname{target}(a)}).(4)✦ A tagged plain observation (T,p)(T,p) at a type TT is a pair with p∈XTp\in X_T.✦ The top candidate assignment sends each actual type AA to Top⁡A\operatorname{Top}_A.✦ The distinguished plain space element with base bb is the recursive plain observation whose table is constantly bb.✦ The default actual plain observation at TT takes this constant value to be the top candidate assignment.✦

A free observation frame consists of an expression key and an optional payload, either a tagged plain observation or an observation of the opposite sign.✦ A finite continuation stack is a finite list of continuing free frames✦, and a terminal exit stack is a finite list of continuing free frames followed by a terminal frame.✦ A free table is a function assigning a candidate assignment to each finite continuation stack and an optional tagged plain observation to each terminal exit stack.✦ If 𝒯(Y)\mathcal T(Y) is this table space with opposite observations in YY, its finite stages and signed spaces are as in (5). $$F_0=\varnothing,\qquad F_{n+1}=\mathcal T(\mathcal T(F_n)),\qquad F^-=\varinjlim_n F_n,\qquad F^+=\mathcal T(F^-).$$(5) A raw observation is an observation with a plain, positive, or negative tag.✦ A raw observation fits a type TT when its plain tag names exactly TT, or its signed tag agrees with a free layer of that sign at πΩ(T)\pi_\Omega(T).✦ A typed value at TT is a raw observation fitting TT.✦ The base assignment b(v)∈ℬb(v)\in\mathcal B of a raw observation is the first coordinate of (4) in the plain case, the empty continuing result in the positive case, and the empty continuing result of its represented behaviour in the negative case.✦

Table reindexing along a map f:X→Yf:X\to Y sends a free table over opposite observations in YY to a table over opposite observations in XX by applying ff to every opposite payload before evaluating either kind of stack.✦ The observation stage successor maps FnF_n into Fn+1F_{n+1}: its map out of the empty stage is unique, and its map at the next stage reindexes tables twice along the preceding successor map.✦ The observation stage inclusion from FnF_n to FmF_m, for n≤mn\leq m, is the composite of the intervening stage successor maps.✦ The finite stage embedding sends an observation in FnF_n to its class in the negative observation space F−F^-.✦ Finite stage restriction at nn sends a positive observation to the table obtained by reindexing it along the embedding of FnF_n into F−F^-.✦ Finite stage behaviour sends an observation in FnF_n to a table over positive opposite observations; at a successor stage it reindexes the table along restriction to the preceding stage.✦

A constant free table with base bb and exit value oo returns bb on every continuation stack and oo on every exit stack, and is the default positive observation with these values. The default negative observation with these values is the image of that constant table from the first finite stage.✦

A typed observation environment ee on Γ\Gamma consists of a typed raw substitution σ\sigma and optional observation parameters fitting each normalized substituted declaration type.✦ An absent parameter requires an inactive declaration. Extension by a term aa typed at A[σ]A[\sigma] and a matching optional parameter gives an environment on A::ΓA::\Gamma, keeping the raw term aa as the new image.✦ Write Me=(M[σ])#M_e=(M[\sigma])^\# and Te=(T[σ])#T_e=(T[\sigma])^\#. For a tree t:Γ⊢M:st:\Gamma\vdash M:s, its substituted actual expression under ee is MeM_e, a normal sortable term in the tower.✦ For a tree t:Γ⊢M:Tt:\Gamma\vdash M:T, its substituted actual type under ee is TeT_e, which is a normal sortable term or a literal sort.

Structural evaluation of t:Γ⊢M:Tt:\Gamma\vdash M:T in ee gives a preliminary result consisting of Val⁡(t,e)\operatorname{Val}(t,e), a typed observation at TeT_e when 𝖠𝖼𝗍(πΩ(Te))\mathsf{Act}(\pi_\Omega(T_e)), and Read⁡(t,e)\operatorname{Read}(t,e), a candidate at MeM_e. The base readout is b(Val⁡(t,e))(Me)b(\operatorname{Val}(t,e))(M_e) when πΩ(Me)∈C\pi_\Omega(M_e)\in C, T=sT=s with {s}∈C\{s\}\in C, and πΩ(Te)\pi_\Omega(T_e) is active; otherwise it is Top⁡Me\operatorname{Top}_{M_e}.✦ A distinguished observation is the canonical typed observation at a normalized active type.✦ Prescribing a base changes the empty observation and keeps the distinguished nonempty observations.✦ Projection of a fitting raw value keeps it; projection of any other raw value gives the distinguished value.✦

The candidate coordinate update of an assignment bb at an actual type TT by a candidate AA replaces b(T)b(T) by AA and retains every other coordinate.✦

The base evaluation result for a typing judgment and environment pairs the supplied active values with their base readout.✦ The optional evaluation parameter of a preliminary result is its raw value when the normalized substituted expected type has active profile, and is absent otherwise.✦

Variable evaluation uses the environment parameter, and sort evaluation has a distinguished active value and top readout.✦ A lambda observation action is a function sending each application key and compatible optional payload to a typed value at its target.✦ Abstraction evaluation uses the body’s result in the extended environment as this action.✦ Application evaluation supplies a typed value at the normalized instantiated target, using the function and argument results. Plain application uses the continuation coordinate in (4).✦ Free application continues by slicing a table, or exits to a plain observation. Its gate requires a matching application key and domain payload, with a plain target exactly in the exit case.✦ A checked exit projects a present plain observation and uses the distinguished value for an absent exit.✦

The slice of a free table at a frame is the table obtained by prefixing that frame to every continuation stack and to the continuing part of every exit stack.✦ The negative observation slice of v∈F−v\in F^- at a frame over positive opposite observations is a negative observation whose represented behaviour is the slice of the represented behaviour of vv.✦

A raw lambda table takes a base, a body action from frames over positive opposite observations to negative observations, and an exit action on those frames. Its empty continuing result is the base; after a first continuing frame it uses the represented behaviour of the selected body, and on a lone terminal frame it uses the exit action.✦

The lambda observation value of an action at a normalized active type TT is the typed observation at TT formed by the corresponding plain or signed free lambda construction.✦ For a normalized active type with plain profile, the plain lambda prefix of an action is the typed observation whose continuation at each key is the action on that key and its compatible optional payload, with the instantiated body as target.✦

The lambda exit operation for an action and a free frame decodes the frame payload and tests the exit gate. It returns the action’s target value as a tagged plain observation when that gate holds, and is absent otherwise.✦

At a positive free type, the positive lambda continuation of an action at a positive frame is the positive observation supplied by the action when the continuation gate holds after decoding the payload; otherwise it is the default positive observation with top candidate assignment and absent exit.✦ At a negative free type, the negative lambda continuation of an action at a negative frame is the negative observation supplied by the action when the continuation gate holds after decoding the payload; otherwise it is the default negative observation with top candidate assignment and absent exit.✦

The positive lambda table of an action at a positive free type has the top candidate assignment as its empty continuing result and follows the positive lambda continuation after a first continuing frame. Its exit at a lone terminal frame is the lambda exit operation, and after continuing frames it follows the same continuation on the residual exit stack. The negative lambda behaviour of an action at a negative free type is the raw lambda table with top candidate assignment as base, negative lambda continuation as body action, and the lambda exit operation with negative frame payloads as exit action.✦ Negative behaviour packing sends a free table over positive opposite observations to a negative observation having that represented behaviour when one exists; otherwise it returns the default negative observation with top candidate assignment and absent exit.✦

For a product, fix domain and body typings, chosen sorts satisfying ℛ\mathcal R, and an environment. Its normalized domain and body are DD and EE. Given a domain candidate dd and body candidates for every typed argument and compatible payload, its tester set is dd when πΩ(D)∈C\pi_\Omega(D)\in C, and Top⁡D\operatorname{Top}_D otherwise.✦ At a typed argument nn, its fiber family consists exactly of the payload-indexed body candidates when πΩ((E[n/x])#)∈C\pi_\Omega((E[n/x])^\#)\in C, and consists only of the top candidate otherwise; an untyped argument has no fibers.✦ The product candidate consists of the terms in Top⁡Πx:D.E\operatorname{Top}_{\Pi x:D.E} sending every tester into every corresponding fiber.✦ Product evaluation uses this candidate as its readout and updates its exact coordinate in the observation’s candidate assignment.✦ For a normalized active type T=Πx:D.ET=\Pi x:D.E supplied by a product instance, the normalized argument frame of nn with Ω⊢n:D\Omega\vdash n:D and active instantiated target is the application key with domain DD, body EE and argument n#n^\#.

The recursive goodness pair of a tree under a raw substitution is denoted by (6); its components are propositions, distinct from evaluation values and candidates. 𝖦𝗈𝗈𝖽(t,σ)=(ValGood⁡(t,σ),ReadGood⁡(t,σ)).\mathsf{Good}(t,\sigma)= \bigl(\operatorname{ValGood}(t,\sigma),\operatorname{ReadGood}(t,\sigma)\bigr).(6) At a variable, value goodness is automatic; at a sort, both components are automatic. For a product with result sort cc, let gg be the condition requiring domain readout goodness when the substituted domain profile lies in CC, and body readout goodness under every typed raw argument extension whose body profile lies in CC. Its value condition requires gg when both the substituted product profile and {c}\{c\} lie in CC, while its readout condition requires gg when the product profile lies in CC. An abstraction’s value condition requires body value goodness under every typed raw argument extension with active target. An application’s value condition requires function value goodness and, when the domain is active, argument value goodness, provided the substituted function type is active; otherwise it requires neutrality of the application. Variables, abstractions, and applications use the base readout condition with their respective value conditions.

The Claim

Theorem 1. Let t:Γ⊢M:Tt:\Gamma\vdash M:T be a typing tree in a saturated context tower setting Ω\Omega with profile family CC. For compatible typed raw substitutions σ,τ:Γ→Ω\sigma,\tau:\Gamma\to\Omega, the equivalences in (7) hold. (ValGood⁡(t,σ)⇔ValGood⁡(t,τ))∧(ReadGood⁡(t,σ)⇔ReadGood⁡(t,τ)).\bigl(\operatorname{ValGood}(t,\sigma)\Longleftrightarrow \operatorname{ValGood}(t,\tau)\bigr) \quad\land\quad \bigl(\operatorname{ReadGood}(t,\sigma)\Longleftrightarrow \operatorname{ReadGood}(t,\tau)\bigr).(7)✦ For a declaration-preserving renaming ρ:Γ→Δ\rho:\Gamma\to\Delta with valid Δ\Delta and any raw substitution σ\sigma, the goodness pair satisfies (8). 𝖦𝗈𝗈𝖽(tρ,σ)=𝖦𝗈𝗈𝖽(t,σ∘ρ).\mathsf{Good}(t^\rho,\sigma)=\mathsf{Good}(t,\sigma\circ\rho).(8)✦ Suppose MM is beta normal and σ:Γ→Ω\sigma:\Gamma\to\Omega is typed. Then (9) holds, with the second clause for every sort ss. 𝖠𝖼𝗍(πΩ(T[σ]))⇒ValGood⁡(t,σ),T=s and 𝖱𝖾𝗅C(Γ,M)⇒ReadGood⁡(t,σ).\begin{aligned} \mathsf{Act}(\pi_\Omega(T[\sigma])) &\ \Longrightarrow\ \operatorname{ValGood}(t,\sigma),\\ T=s\ \text{ and }\ \mathsf{Rel}_C(\Gamma,M) &\ \Longrightarrow\ \operatorname{ReadGood}(t,\sigma). \end{aligned}(9)✦ For structural evaluation, suppose system weak normalization holds and there is no forbidden configuration. Let t:Γ⊢M:st:\Gamma\vdash M:s and let ee be a typed observation environment. If πΩ(Me)∈C\pi_\Omega(M_e)\in C, {s}∈C\{s\}\in C, and 𝖠𝖼𝗍(πΩ(s))\mathsf{Act}(\pi_\Omega(s)), the readout is given by (10). Read⁡(t,e)=b(Val⁡(t,e))(Me).\operatorname{Read}(t,e)=b(\operatorname{Val}(t,e))(M_e).(10)✦ For t:Γ⊢M:st:\Gamma\vdash M:s and any raw substitution σ\sigma, suppose πΩ(M[σ])∈C\pi_\Omega(M[\sigma])\in C, {s}∈C\{s\}\in C, and 𝖠𝖼𝗍(πΩ(s))\mathsf{Act}(\pi_\Omega(s)). Then (11) holds. ReadGood⁡(t,σ)⇔ValGood⁡(t,σ).\operatorname{ReadGood}(t,\sigma)\Longleftrightarrow \operatorname{ValGood}(t,\sigma).(11)✦

In the paper, the result reads: goodness has the structural invariances of Lemma 28; when the actual expression profile and {s}\{s\} lie in the paper’s component 𝒮\mathcal S and Ax⁡(s)\operatorname{Ax}(s) is active, Read⁡(M:s)\operatorname{Read}(M:s) is the base projection at every syntactic shape and its goodness is equivalent to Val\operatorname{Val} goodness; every normal syntax tree has good active Val\operatorname{Val} under every typed raw substitution, and a normal tree M:sM:s has good Read\operatorname{Read} when its generic expression profile lies in the paper’s family 𝒰∪𝒮\mathcal U\cup\mathcal S.

What Is Checked

The claims concern typing trees and their declaration-preserving renamings, typed raw substitutions and their pointwise convertibility, the recursively defined goodness pair, and structural evaluation in typed observation environments. Renaming lifts across a binder✦, preserves beta convertibility✦, and transports a typing tree to the renamed judgment.✦ A function’s product type has a sort.✦ Normalizing a product instance preserves its product structure✦; a tester typed at its normalized domain is typed at the raw substituted domain✦, and substitution in a frame environment has exactly the frame’s normalized target type.✦

Excluding a forbidden configuration makes the plain schema’s domain dependencies well-founded, including dependencies reached after finite continuations.✦ The finite free stages form a directed system✦. A continuation with nonplain target preserves the source’s free sign.✦ The product test construction yields a normalization candidate with every matching body payload included. The optional plain payload determined by a plain key’s frame parameters fits that key’s domain. Every payload occurrence along a finite continuation path gives a recursive domain dependency on the path’s starting node.