OctoInformBeta

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

Lemma 28: Compatible raw environments, declaration renaming, context conversion and convertible expected types in structural evaluation

Observation outputs under changes of typing data.

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 environment supplies raw terms for the variables of a typing derivation and observation parameters at its active declarations. Structural evaluation assigns an observation to the expected type and a normalization candidate to the substituted subject. The two outputs concern different terms, even when the subject is itself a type.

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations. 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.✦ Names in these expressions are source notation; variable positions in a context use de Bruijn indices, starting at zero, and contexts are newest-first. Write Γ(n)=A\Gamma(n)=A for declaration lookup with AA viewed in the full context, including its index shifts.✦ A valid context is obtained from the empty context by extensions A::ΓA::\Gamma with Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦

Write M≡βNM\equiv_\beta N for the equivalence relation generated by full beta reduction, including reduction in every annotation and binder body.✦ Assume system weak normalization: in each valid context, both the subjects and the expected types of typing judgements have beta normal forms.✦ Write M#M^\# for the chosen normal form of such a term, and M[σ]M[\sigma] for capture-avoiding simultaneous substitution. Under a binder its lift fixes zero and sends n+1n+1 to σ(n)\sigma(n) with its free indices increased by one.✦ Renaming M[ρ]M[\rho] uses the analogous lift of an index map, fixing zero and sending n+1n+1 to ρ(n)+1\rho(n)+1; B[a/x]B[a/x] denotes bound variable instantiation. A term MM is legal in Γ\Gamma when it occurs as either the subject or the expected type of a typing judgement in Γ\Gamma.

A saturated context tower Ω\Omega is a sequence of valid prefixes Ωn\Omega_n of length nn, each extended by one sortable declaration, in which every sortable type expressed with fixed free levels is declared again beyond every stage bound.✦ Tower typing Ω⊢M:A\Omega\vdash M:A means typing at some prefix after converting both MM and AA from levels to indices.✦ At length nn this conversion sends i<ni<n to n−1−in-1-i and fixes the other indices.✦ The normal form profiles and the axiom and product output profiles 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 is a nonempty profile in (1) realized by a normal term in a valid context.✦ 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).✦

Observation Layers

The primary signed graph has positive edges I→JI\to J for strict inclusions J⊊IJ\subsetneq I of feasible profiles. A feasible product profile triple (I,J,K)(I,J,K) gives 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; the empty walk has even parity. Write I⤳JI\leadsto J for reachability with either parity, and I⤳+JI\leadsto_+J for a walk using only positive edges. A strongly connected component consists of exactly the vertices mutually reachable with one of its vertices.✦

For a family CC of profiles, the observation layers 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 these layers as vertices. Its positive edges are the primary positive edges between them, and its negative edges I→KI\to K come from feasible product profile triples (I,J,K)(I,J,K) all of whose profiles are observation layers.✦ A direct layer II for a family CC of profiles is an observation layer admitting a feasible product profile triple (I,J,K)(I,J,K) with J,K∈CJ,K\in C.✦ Write 𝒟C\mathcal D_C for the direct layers and I⤳CεDI\leadsto_C^\varepsilon D for a secondary walk of parity ε∈{0,1}\varepsilon\in\{0,1\}. The active, plain and signed free layers are defined by 𝖠C(I)⇔∃D∈𝒟C∃ε∈{0,1}I⤳CεD,𝖯C(I)⇔(∃D∈𝒟CI⤳C0D)∧(∃D∈𝒟CI⤳C1D),𝖥Cε(I)⇔¬𝖯C(I)∧∃D∈𝒟CI⤳CεD.\begin{aligned} \mathsf A_C(I)&\ \Longleftrightarrow\ \exists D\in\mathcal D_C\ \exists\varepsilon\in\{0,1\}\ I\leadsto_C^\varepsilon D,\\ \mathsf P_C(I)&\ \Longleftrightarrow\ (\exists D\in\mathcal D_C\ I\leadsto_C^0D)\ \land\ (\exists D\in\mathcal D_C\ I\leadsto_C^1D),\\ \mathsf F_C^\varepsilon(I)&\ \Longleftrightarrow\ \neg\mathsf P_C(I)\ \land\ \exists D\in\mathcal D_C\ I\leadsto_C^\varepsilon D. \end{aligned}(2)

Assume there is no forbidden configuration for P,CP,C. Such a configuration is a secondary strongly connected component DD consisting of plain layers and containing a negative edge, together with a feasible product profile triple (I,J,K)(I,J,K) and a sort ss for which J,K,{s}∈DJ,K,\{s\}\in D, Ax⁡(s)\operatorname{Ax}(s) is nonempty, and Ax⁡(s)⤳+I\operatorname{Ax}(s)\leadsto_+I in the primary graph.✦

Candidates and Observation Values

A term is strongly normalizing when no infinite sequence of full beta reductions starts at it.✦ An argument list is strongly normalizing when the relation reducing one component at a time admits no infinite sequence.✦ Write Ma→M\,\vec a for left-associated iterated application.✦ The top and ground sets at TT in the tower are Top⁡T={M∣Ω⊢M:T and M is strongly normalizing},GT={M∣Ω⊢M:T and, for every tested stack a→ at T,Ma→ is strongly normalizing}.\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, for every tested stack }\vec a \text{ at }T,\ M\,\vec a\text{ is strongly normalizing}\}. \end{aligned}(3) The empty stack is tested at every type; a::a→a::\vec a is tested at Πx:A.B\Pi x:A.B when a∈Top⁡Aa\in\operatorname{Top}_A and a→\vec a is tested at (B[a/x])#(B[a/x])^\#.✦ A normalization candidate XX at TT is a set with GT⊆X⊆Top⁡TG_T\subseteq X\subseteq\operatorname{Top}_T in (3), closed under typed head expansion: membership of b[a/x]a→b[a/x]\,\vec a entails membership of (λx:A.b)aa→(\lambda x:A.b)\,a\,\vec a when the latter has tower type TT, the annotation AA, body bb and argument aa are strongly normalizing, and a→\vec a is a strongly normalizing argument list.✦

An actual type is a normal term sorted in Ω\Omega, or a literal sort.✦ A candidate assignment bb assigns a normalization candidate b(T)b(T) to every actual type TT.✦ The top assignment chooses Top⁡T\operatorname{Top}_T at each coordinate; a coordinate update b[T↦X]b[T\mapsto X] replaces just that candidate. A normalized active type TT is a normal, sorted term with 𝖠C(πΩ(T))\mathsf A_C(\pi_\Omega(T)); a normalized plain type TT is a normal, sorted term with 𝖯C(πΩ(T))\mathsf P_C(\pi_\Omega(T)).

A plain application key at a normalized plain type TT chooses a decomposition T=Πx:A.BT=\Pi x:A.B and a normal argument aa with Ω⊢a:A\Omega\vdash a:A and active target (B[a/x])#(B[a/x])^\#.✦ Its target node is that normal form✦, and its domain node is AA when the domain is active, with no domain otherwise. A plain schema is a system of nodes equipped with keys, targets and optional domains.✦ A finite continuation path successively follows targets✦; a payload occurrence selects a domain at one of its frames.✦ Path parameters assign a recursive observation at each such occurrence.✦ For a plain schema with well-founded recursive domain dependency, a base space BB and a node nn, the recursive plain space 𝒫B(n)\mathscr P_B(n) consists of tables valued in BB on continuation paths from nn and their recursive path parameters.✦ Its unfolding is its recursive table, with prefix decomposition 𝒫B(n)≃B×∏a a key at n(Par⁡𝒫B(a)→𝒫B(target(a))),\mathscr P_B(n)\simeq B\times \prod_{a\text{ a key at }n} \left(\operatorname{Par}_{\mathscr P_B}(a) \longrightarrow\mathscr P_B(\operatorname{target}(a))\right),(4)✦ where Par⁡𝒫B(a)\operatorname{Par}_{\mathscr P_B}(a) is the single frame parameter space. The distinguished element is the constant table.✦ A tagged plain observation consists of its normalized plain type and a plain observation with candidate assignments as base.✦ The actual plain schema has normalized plain types as nodes, with the plain application keys, target nodes and optional domain nodes just described.✦

Free observations have positive and negative signs. A free frame consists of a term key and a payload, which is absent or contains a plain observation or an observation of the sign opposite to that of the free observation containing the frame.✦ A continuing stack is a finite list of frames✦; an exit stack adds a terminal frame.✦ A free table assigns a candidate assignment to each continuing stack and an optional tagged plain observation to each exit stack.✦ The finite stages start with the empty space and at each successor take tables whose opposite values are tables over the preceding stage.✦ Negative observations form the direct limit of these stages✦; positive observations are tables over negative observations.✦ Represented negative behavior is a table over positive observations. Slicing a table prefixes one frame to either kind of stack.✦ The constant tables give the default signed observations, with the negative default represented at the first stage. A raw lambda table with base bb, body action kk assigning a negative observation to each frame over positive observations, and exit action oo is a table over positive observations. Its empty continuing result is bb; after a first frame aa it follows the represented behavior of k(a)k(a) on the remaining stack, while a lone terminal frame aa has exit result o(a)o(a).✦

A raw observation has a plain, positive or negative tag.✦ A typed observation value at TT is a raw observation compatible with TT: a plain tag has exactly type TT, while a positive tag has parity zero, a negative tag has parity one, and a signed tag of parity ε\varepsilon requires 𝖥Cε(πΩ(T))\mathsf F_C^\varepsilon(\pi_\Omega(T)).✦ An optional payload fits TT when it is absent at an inactive profile, or present with a compatible tag.✦ The base of a raw observation is its empty continuing observation, using (4) in the plain case and represented behavior in the negative case.✦ The distinguished typed observation uses the top assignment and default continuations.✦ Projection to an active type keeps a compatible raw observation and uses the distinguished observation otherwise.✦ For a normalized active type TT and candidate assignment bb, the prescribed base observation at TT has empty observation bb and retains every nonempty observation of the distinguished observation.✦

Environments and Structural Evaluation

A typed observation environment e=(σe,pe)e=(\sigma_e,p_e) from Γ\Gamma to Ω\Omega consists of a raw substitution σe\sigma_e and optional raw observations pe(n)p_e(n) satisfying Γ(n)=A⇒Ω⊢σe(n):A[σe],pe(n) fits (A[σe])#.\Gamma(n)=A\quad\Longrightarrow\quad \Omega\vdash\sigma_e(n):A[\sigma_e],\qquad p_e(n)\text{ fits }(A[\sigma_e])^\#.(5)✦ For a new declaration AA, an argument aa with tower type A[σe]A[\sigma_e] and a payload pp fitting (A[σe])#(A[\sigma_e])^\# extend ee to A::ΓA::\Gamma by sending zero to a,pa,p and each successor to the old image and payload. The substituted actual type of a judgement Γ⊢M:T\Gamma\vdash M:T is (T[σe])#(T[\sigma_e])^\#; when active it is also a normalized active type. For a sorted subject the substituted actual expression is (M[σe])#(M[\sigma_e])^\#.✦

Image compatibility means convertibility of images at every position of Γ\Gamma.✦ Compatibility of environments on Γ\Gamma, reindexing from Γ\Gamma to Δ\Delta, and identity of data across these contexts mean, respectively, e∼f⇔∀n<|Γ|,σe(n)≡βσf(n)∧pe(n)=pf(n),e∼ρf⇔∀n<|Γ|,σe(n)=σf(ρ(n))∧pe(n)=pf(ρ(n)),e≐f⇔σe=σf∧pe=pf.\begin{aligned} e\sim f\quad&\Longleftrightarrow\quad \forall n<|\Gamma|,\quad \sigma_e(n)\equiv_\beta\sigma_f(n)\ \land\ p_e(n)=p_f(n),\\ e\sim_\rho f\quad&\Longleftrightarrow\quad \forall n<|\Gamma|,\quad \sigma_e(n)=\sigma_f(\rho(n))\ \land\ p_e(n)=p_f(\rho(n)),\\ e\doteq f\quad&\Longleftrightarrow\quad \sigma_e=\sigma_f\ \land\ p_e=p_f. \end{aligned}(6) The last equality in (6) concerns the entire assignments, including positions beyond the contexts.

A declaration-preserving renaming ρ:Γ→Δ\rho:\Gamma\to\Delta is an index map satisfying Γ(n)=A⇒Δ(ρ(n))=A[ρ].\Gamma(n)=A\quad\Longrightarrow\quad \Delta(\rho(n))=A[\rho].(7) Context equivalence Γ≃Δ\Gamma\simeq\Delta means that both contexts are valid and Γ⊢M:A\Gamma\vdash M:A exactly when Δ⊢M:A\Delta\vdash M:A, for every subject MM and expected type AA.✦ A typing tree tt for Γ⊢M:T\Gamma\vdash M:T is a finite derivation retaining its declaration lookups, chosen axiom successors and product formation sorts, and conversions to the expected types.✦ Write tρt^\rho for its renaming along (7) into a valid Δ\Delta, tΔt^\Delta for its context conversion along Γ≃Δ\Gamma\simeq\Delta, and tUt^U for its root retargeting when Γ⊢M:U\Gamma\vdash M:U and U≡βTU\equiv_\beta T.

Structural evaluation ℰ(t,e)\mathcal E(t,e) follows the chosen formation roles of tt. Its preliminary result has an active observation value Val⁡(t,e)\operatorname{Val}(t,e) at (T[σe])#(T[\sigma_e])^\# whenever that type is active, and a candidate Read⁡(t,e)\operatorname{Read}(t,e) at (M[σe])#(M[\sigma_e])^\#.✦ Write |Val⁡(t,e)||\operatorname{Val}(t,e)| for the underlying raw observation and |Read⁡(t,e)||\operatorname{Read}(t,e)| for the underlying set of terms. Its optional parameter is Par⁡(t,e)={some⁡(|Val⁡(t,e)|),𝖠C(πΩ((T[σe])#)),none⁡,otherwise.\operatorname{Par}(t,e)= \begin{cases} \operatorname{some}(|\operatorname{Val}(t,e)|), &\mathsf A_C(\pi_\Omega((T[\sigma_e])^\#)),\\ \operatorname{none},&\text{otherwise}. \end{cases}(8)✦

Variable evaluation takes its value from the declaration’s environment parameter.✦ Sort evaluation uses the distinguished active observation and the top readout.✦

A product instance consists of a context Γ\Gamma, a typed observation environment on Γ\Gamma, a domain DD and body EE with Γ⊢D:a\Gamma\vdash D:a and D::Γ⊢E:bD::\Gamma\vdash E:b, and a chosen result sort cc with (a,b,c)∈ℛ(a,b,c)\in\mathcal R.✦ Its substituted body uses the lifted substitution.✦ Its domain, body and instantiated targets have chosen normal forms. Product evaluation uses the domain readout as testers when the domain profile belongs to CC, and otherwise uses the top set.✦ The candidate fiber family is empty at an argument without tower type at the normalized domain. At a typed argument it consists exactly of the body candidate sets arising from all fitting payloads when the normalized target profile belongs to CC, and otherwise consists of the top set at that target alone. The product test consists of top terms sending every tester into every corresponding fiber.✦ Its observation updates the product’s exact candidate coordinate.

An active application key at a normalized active type TT chooses a decomposition T=Πx:A.BT=\Pi x:A.B and a normal argument aa with Ω⊢a:A\Omega\vdash a:A, such that (B[a/x])#(B[a/x])^\# is active; this normalized instantiated body is its active target type.✦ A lambda action at a normalized active type TT is a function assigning a typed target observation to every active application key at TT and fitting payload.✦ Abstraction evaluation uses the body evaluations in extended environments to give this action. The plain lambda uses the continuation coordinates of (4). For a normalized active type TT, a free application gate at a term qq, optional raw observation pp and exit flag holds when there is an active application key at TT whose argument is qq and whose domain admits pp as a fitting payload, and its target is plain exactly when the exit flag is true.✦ Signed continuation uses the same free sign✦, and failed gates use the defaults. Application evaluation applies the function observation to the normalized argument key and its payload, through a plain continuation, a free slice or an exit projected to the target type.

Negative behavior packing chooses a negative observation representing a table over positive observations when one exists. Otherwise it returns the default negative observation with the top candidate assignment and an absent exit.

For a plain application key, plain payload encoding sends a fitting optional raw observation to its single frame parameters, retaining the matching plain observation when the domain is active.✦

At an active application key whose source type is positively free, positive frame payload encoding sends a fitting optional raw observation to an absent payload, a tagged plain observation or a negative observation, retaining its matching tag.✦ At an active application key whose source type is negatively free, negative frame payload encoding sends a fitting optional raw observation to an absent payload, a tagged plain observation or a positive observation, retaining its matching tag.✦

Positive frame payload decoding sends absence to an absent raw payload, a negative observation to a present negatively tagged raw payload, and a plain observation to a present plainly tagged raw payload.✦ Negative frame payload decoding sends absence to an absent raw payload, a positive observation to a present positively tagged raw payload, and a plain observation to a present plainly tagged raw payload.✦

For a lambda action at TT, the lambda exit operation decodes a frame payload and tests the exit gate. At a successful gate it returns the tagged plain observation supplied by the action at the witnessing key; otherwise it returns no exit observation.✦

For a positively free type TT and lambda action, the positive lambda table has top candidate assignment at the empty continuing stack and follows the positive lambda continuation after a first frame. Its exit at a lone terminal frame is the lambda exit operation with positive payload decoding, and its exits after a first continuing frame follow that continuation on the remaining exit stack.

For a negatively free type TT and lambda action, the negative lambda behavior is the raw lambda table with top candidate assignment as base, negative lambda continuation as body action, and the lambda exit operation with negative payload decoding as exit action.✦

The checked exit value at an active type TT is the distinguished observation when the exit is absent, and otherwise is the projection to TT of the returned tagged plain observation.✦

For a base evaluation result, the readout uses the observation’s base coordinate at the substituted actual expression precisely when the subject profile belongs to CC, the expected type is a literal sort ss with {s}∈C\{s\}\in C, and the expected type is active. Otherwise it is the top candidate.

The Claim

Theorem 1. Let Ω\Omega be a saturated context tower for the weakly normalizing specification PP, and let CC have no forbidden configuration. Let tt be a typing tree for Γ⊢M:T\Gamma\vdash M:T.

  1. Suppose CC is a strongly connected component of the primary graph, and e,fe,f are typed observation environments on Γ\Gamma with e∼fe\sim f. Their outputs satisfy (9): Par⁡(t,e)=Par⁡(t,f),|Read⁡(t,e)|=|Read⁡(t,f)|.\operatorname{Par}(t,e)=\operatorname{Par}(t,f),\qquad |\operatorname{Read}(t,e)|=|\operatorname{Read}(t,f)|.(9)✦

  2. Let Δ\Delta be valid, let ρ:Γ→Δ\rho:\Gamma\to\Delta preserve declarations, and let e,fe,f be environments on Γ,Δ\Gamma,\Delta with e∼ρfe\sim_\rho f. Renamed evaluation satisfies (10): Par⁡(t,e)=Par⁡(tρ,f),|Read⁡(t,e)|=|Read⁡(tρ,f)|.\operatorname{Par}(t,e)=\operatorname{Par}(t^\rho,f),\qquad |\operatorname{Read}(t,e)|=|\operatorname{Read}(t^\rho,f)|.(10)✦

  3. Suppose Γ≃Δ\Gamma\simeq\Delta, and let e,fe,f be environments on these contexts with e≐fe\doteq f. Evaluation in the converted context satisfies (11): Par⁡(t,e)=Par⁡(tΔ,f),|Read⁡(t,e)|=|Read⁡(tΔ,f)|.\operatorname{Par}(t,e)=\operatorname{Par}(t^\Delta,f),\qquad |\operatorname{Read}(t,e)|=|\operatorname{Read}(t^\Delta,f)|.(11)✦

  4. Suppose Γ⊢M:U\Gamma\vdash M:U and U≡βTU\equiv_\beta T. Let ee be an environment on Γ\Gamma for which both πΩ((T[σe])#)\pi_\Omega((T[\sigma_e])^\#) and πΩ((U[σe])#)\pi_\Omega((U[\sigma_e])^\#) are active. Retargeted evaluation satisfies (12): |Val⁡(t,e)|=|Val⁡(tU,e)|.|\operatorname{Val}(t,e)|=|\operatorname{Val}(t^U,e)|.(12)✦

What Is Checked

The statements concern finite typing trees with their chosen formation roles, tower-typed raw substitutions and fitting optional payloads, under system weak normalization and exclusion of a forbidden configuration; the compatibility statement additionally assumes that CC is a primary strongly connected component.

Declaration-preserving renamings lift through context extension✦, and renaming preserves beta convertibility.✦

Typing trees recover their typing judgements.✦

In a plain schema, a node depends on each domain node reached after a finite continuation path from it.✦ For the actual plain schema this relation is well-founded✦, and each path payload occurrence gives such a dependency.✦

Negative observation behavior remains representable after slicing.✦

For a product instance, normalizing its substituted product gives the product of its normalized domain and body.✦ An argument typed at the normalized domain remains typed at the raw substituted domain✦, and the body normal form under its frame environment is exactly the active key’s target type.✦ The corresponding indexed product tests are normalization candidates.

Whenever Γ⊢M:Πx:A.B\Gamma\vdash M:\Pi x:A.B, the product Πx:A.B\Pi x:A.B itself has a sort in Γ\Gamma.✦

For every plain application key, its frame parameters determine an optional plain observation payload that fits its domain.✦