OctoInformBeta

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

Lemma 31: Stored typing trees retain their original expected types

Full reduction transports good observations.

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

Let P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) be a pure type specification, with arbitrary axiom relation 𝒜⊆S×S\mathcal A\subseteq S\times S and product-rule relation ℛ⊆S×S×S\mathcal R\subseteq S\times S\times S.✦ Terms are variables, sorts, applications, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ Full one-step reduction →β\to_\beta contracts (λx:A.M)N(\lambda x:A.M)\,N to M[N/x]M[N/x] and permits reduction in every subterm, including annotations and binder bodies.✦ Convertibility is the equivalence relation generated by these steps.✦

A valid context Δ\Delta is a finite context obtained from the empty context by repeatedly extending a context Γ\Gamma with a declaration x:Ax:A whenever Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦ The judgement Γ⊢M:T\Gamma\vdash M:T uses the axiom, variable, weakening, product, abstraction, application and conversion rules of PP. A stored typing tree t∈𝖳𝗋𝖾𝖾P(Γ;M,T)t\in\mathsf{Tree}_P(\Gamma;M,T) is a finite derivation retaining the declaration lookup or axiom at a leaf, the chosen domain and body sorts and product-rule output at a product, and the conversions to the expected types. An abstraction retains its annotation and body trees and its product formation judgement; an application retains its function and argument trees and its instantiated target.

The variable names here are source notation. Contexts in the library are newest-first, and variables use de Bruijn indices. Declaration lookup shifts a stored declaration type into the full context.✦ Simultaneous substitution MσM\sigma is capture-avoiding: beneath a binder its lift fixes index zero and shifts the images of the old indices.✦ Single-variable substitution sends zero to the argument and decrements the remaining indices; bound-variable instantiation is the resulting substitution into a body. Variable renaming uses the corresponding lift under binders.

A term is normal when it has no full β\beta step✦, weakly normalizing when it reaches a normal term✦, and strongly normalizing, written 𝖲𝖭(M)\mathsf{SN}(M), when no infinite full reduction begins at it.✦ Assume system weak normalization: in every valid context both the subject and the expected type of every typing judgement are weakly normalizing.✦ These are the legal terms. Write M#M^\# for the chosen normal form whenever this assumption supplies its specification.

A saturated context tower Ω\Omega is an increasing sequence of valid contexts of length nn at stage nn, each extended by a sortable declaration, in which every type sortable at a stage is declared again arbitrarily far along the tower.✦ Tower terms use fixed levels for free variables. Tower typing Ω⊢M:T\Omega\vdash M:T means that some finite stage types both expressions after index to level reversal, which sends i<ni<n to n−1−in-1-i and fixes the other indices.✦

Profiles and Observation Layers

The normal-form sort profiles and the axiom and product output profiles are the sets in (1). A feasible profile II is a nonempty set of sorts of the form πΓ(T)\pi_\Gamma(T) for a normal term TT in a valid context Γ\Gamma.✦ πΓ(T)={s∣Γ⊢T#:s},πΩ(T)={s∣Ω⊢T#:s},Ax⁡(s)={t∣(s,t)∈𝒜},Out⁡(I,J)={c∣∃a∈I∃b∈J,(a,b,c)∈ℛ}.\begin{aligned} \pi_\Gamma(T)&=\{s\mid\Gamma\vdash T^\#:s\},& \pi_\Omega(T)&=\{s\mid\Omega\vdash T^\#:s\},\\ \operatorname{Ax}(s)&=\{t\mid(s,t)\in\mathcal A\},& \operatorname{Out}(I,J)&=\{c\mid\exists a\in I\;\exists b\in J, (a,b,c)\in\mathcal R\}. \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 of feasible profiles, and, for each feasible product profile triple, a negative edge I→KI\to K and a positive edge J→KJ\to K.✦

A signed directed walk has parity equal to the number of its negative edges modulo two; the empty walk is positive.✦ Directed reachability permits either parity✦, whereas positive reachability uses only positive edges.✦ A strongly connected component is the set of vertices mutually reachable with one of its vertices.✦ The observation layers of a family CC of profiles 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 signed graph has the positive primary edges between observation layers and the negative domain edges of product profile triples whose three profiles are observation layers.✦

A direct observation layer is an observation layer II occurring in a product profile triple (I,J,K)(I,J,K) with J,K∈CJ,K\in C.✦ An observation layer is active if it reaches a direct layer in the secondary graph.✦ A plain layer is an observation layer with walks of both parities to direct layers, which may be different.✦ A nonplain profile is a free layer of sign ε\varepsilon if it has a walk of parity ε\varepsilon to a direct layer.✦

A forbidden configuration is a secondary strongly connected component DD of plain layers containing a negative edge, together with a feasible product profile triple (I,J,K)(I,J,K) and a sort ss such that J,K,{s}∈DJ,K,\{s\}\in D and the nonempty Ax⁡(s)\operatorname{Ax}(s) has positive primary reachability to II.✦ Assume that no such configuration exists for PP and CC.

Candidates and Observation Spaces

Write Mn→M\vec n for left-associated iterated application.✦ An argument list reduces when one of its components takes a full β\beta step✦, and is strongly normalizing when no infinite sequence of such list reductions starts from it.✦ The top and ground candidates at TT are defined in (2). A tested stack is empty at any type, or has first argument n∈Top⁡Dn\in\operatorname{Top}_D at Πx:D.E\Pi x:D.E, where Top⁡D\operatorname{Top}_D is the set of strongly normalizing terms of tower type DD, and a tail tested at (E[n/x])#(E[n/x])^\#.✦ Top⁡T={M∣Ω⊢M:T∧𝖲𝖭(M)},GT={M∣Ω⊢M:T∧∀n→ tested at T,𝖲𝖭(Mn→)}.\begin{aligned} \operatorname{Top}_T &=\{M\mid\Omega\vdash M:T\ \land\ \mathsf{SN}(M)\},\\ G_T &=\{M\mid\Omega\vdash M:T\ \land\ \forall\vec n\text{ tested at }T,\ \mathsf{SN}(M\vec n)\}. \end{aligned}(2) A normalization candidate AA at TT is a set with GT⊆A⊆Top⁡TG_T\subseteq A\subseteq\operatorname{Top}_T closed under head expansion: if ((λx:D.b)n)n→((\lambda x:D.b)\,n)\vec n has tower type TT, its annotation, body, argument and further argument list are strongly normalizing, and b[n/x]n→∈Ab[n/x]\vec n\in A, then ((λx:D.b)n)n→∈A((\lambda x:D.b)\,n)\vec n\in A.✦ An actual type is a normal sortable expression or a literal sort.✦ A candidate assignment bb chooses a candidate b(T)b(T) at each actual type TT✦; the top assignment chooses Top⁡T\operatorname{Top}_T.✦ Updating a coordinate replaces just the candidate at that actual type.✦

A normalized active type TT is a normal sortable expression whose profile is active✦; a normalized plain type TT is a normal sortable expression whose profile is plain.✦ An application key at an active type TT is a choice of a decomposition T=Πx:D.ET=\Pi x:D.E and a normal argument Ω⊢a:D\Omega\vdash a:D with active instantiated target.✦ Its target type is (E[a/x])#(E[a/x])^\#.✦ A plain application key at a normalized plain type TT is an application key at TT.✦ The actual plain schema uses these keys and targets, with a domain node DD present precisely when its profile is active.✦

A plain observation schema FF is an assignment of keys, targets and optional domains to nodes.✦ A finite continuation path follows finitely many targets✦; its payload occurrences select the frames with a present domain.✦ Path parameters assign a value at the appropriate domain to every occurrence.✦ For a family of parameter spaces KK and a key with domain dd, single-frame parameters are values in K(d)K(d); a key without a domain has the unique empty assignment.✦ Path-parameter extension joins these to the remaining path parameters✦, and the empty path has its unique empty assignment.✦ The recursive dependency d≺nd\prec n means that dd occurs as a domain after finitely many continuing frames from nn.✦

For a schema FF with well-founded dependency and base BB, its recursive plain space 𝒫B(n)\mathcal P_B(n) consists of plain observation tables as in (3).✦ Here Par⁡𝒫B(p)\operatorname{Par}_{\mathcal P_B}(p) denotes path parameters with values in the recursive spaces, and Par⁡𝒫B(a)\operatorname{Par}_{\mathcal P_B}(a) denotes the single-frame parameters for a key aa. Unfolding identifies a space with this table, and its prefix decomposition separates the empty observation from the continuation coordinates. 𝒫B(n)≃∏p:path from n(Par⁡𝒫B(p)→B),𝒫B(n)≃B×∏a:key at n(Par⁡𝒫B(a)→𝒫B(target⁡(a))).\begin{aligned} \mathcal P_B(n) &\simeq \prod_{p:\,\text{path from }n} \bigl(\operatorname{Par}_{\mathcal P_B}(p)\to B\bigr),\\ \mathcal P_B(n) &\simeq B\times\prod_{a:\,\text{key at }n} \bigl(\operatorname{Par}_{\mathcal P_B}(a) \to\mathcal P_B(\operatorname{target}(a))\bigr). \end{aligned}(3) The actual plain observation spaces use the actual plain schema and candidate assignments as bases.✦ A distinguished element of an actual plain observation space is an observation with a constant table✦; the default actual plain observation is the distinguished element whose table has the top assignment as its constant value.✦ A tagged plain observation is a pair consisting of a normalized plain type and an observation in the actual plain observation space at that type.✦

A free observation frame is a key with a payload that is absent, plain, or an opposite value.✦ A continuation stack is a finite list of frames✦, and an exit stack is a continuation stack together with a terminal frame.✦ For keys QQ, plain payloads VV, bases BB, and exit results OO, let ℱ(Y)\mathcal F(Y) be the space of tables assigning a result in BB to each continuation stack with opposite values in YY, and a result in OO to each exit stack.✦ The signed free spaces are given by (4). V0=⌀,Vn+1=ℱ(ℱ(Vn)),ℱ−=colim⁡nVn,ℱ+=ℱ(ℱ−).V_0=\varnothing,\qquad V_{n+1}=\mathcal F(\mathcal F(V_n)),\qquad \mathcal F^- =\mathop{\mathrm{colim}}_n V_n,\qquad \mathcal F^+ =\mathcal F(\mathcal F^-).(4) Payload mapping changes opposite values and preserves plain values and absence✦; frame and stack mapping retain the keys. Table reindexing precomposes with these maps.✦ The observation stage successor uses reindexing twice, and its iterates are the stage inclusions. Finite-stage embedding gives the classes in ℱ−\mathcal F^-; restriction reindexes a positive table along an embedding. Finite-stage behavior uses restriction, and represented negative behavior assigns to each negative observation its table over positive opposite values.✦ A table slice prefixes a frame to its stacks.✦ Negative slicing selects a negative observation with the sliced represented behavior.✦ Default positive observations are constant tables✦; default negative observations embed constant tables at stage one.✦

Actual positive and negative observations take expressions as keys, tagged plain observations as plain payloads, candidate assignments as bases, and optional tagged plain observations as exits. A raw observation has a plain, positive, or negative tag.✦ Compatibility at TT requires the exact type TT on a plain tag, a positive free profile on a positive tag, and a negative free profile on a negative tag.✦ A typed observation value at TT is a compatible raw observation.✦ Optional payload compatibility requires absence at inactive domains and a compatible present value otherwise.✦ Active payload extraction retrieves that value; plain payload conversion relates compatible optional payloads to single frame parameters. Signed frame payload conversion preserves plain tags and treats a value of the opposite sign as the opposite payload. A positive application frame consists of an expression key and a payload that is absent, a tagged plain observation, or an actual negative observation.✦ A negative application frame consists of an expression key and a payload that is absent, a tagged plain observation, or an actual positive observation.✦ Positive frame payload decoding sends absence to absence, a tagged plain payload to a present plain raw observation, and an actual negative payload to a present negative raw observation.✦ Negative frame payload decoding sends absence to absence, a tagged plain payload to a present plain raw observation, and an actual positive payload to a present positive raw observation.✦

The base assignment of an observation is its empty observation, obtained through the plain prefix decomposition or the appropriate free table.✦ Plain value injection and extraction relate plain spaces to typed values; signed extraction retrieves the positive or negative observation. A distinguished typed value is a typed observation value constructed from the default observation.✦ Typed projection keeps a compatible raw value and otherwise selects the distinguished value.✦ The prescribed base observation at a normalized active type TT with candidate assignment bb is a typed value whose empty observation is bb and whose nonempty observations agree with the distinguished value at TT.✦ Plain observation tagging at a normalized active type with plain profile sends a typed value to the tagged plain observation consisting of that same normalized plain type and its extracted plain observation.✦

A lambda observation action is an assignment of a typed target value to every active application key and compatible payload.✦ A free application gate is a condition on an expression key, a payload and an exit flag: the key and payload must match an active application key with a compatible payload, and the flag must be true exactly when its target is plain.✦ Signed lambda continuations use the action at a continuation gate and otherwise the signed default. The lambda exit operation returns the tagged plain action value at an exit gate and otherwise no exit.✦ A raw lambda table has its prescribed base on the empty stack and follows its body action after a first frame.✦ The positive lambda table uses the top base and these continuations and exits.✦ At a normalized active type with negative free profile, 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 using negative frame payload decoding as exit action.✦ Negative behavior packing chooses a negative observation representing this table when one exists and otherwise the negative default.✦ The plain lambda prefix takes its continuation coordinates from the action.✦ The lambda observation value selects the appropriate plain or signed construction.✦

Observation value application follows the plain continuation coordinate, a signed continuation slice, or a checked exit according to the source and target profiles.✦ A checked exit is an operation that projects a present plain result to the target and otherwise uses the distinguished value.✦

Evaluation and Goodness

A typed observation environment ee from Γ\Gamma to Ω\Omega consists of a raw substitution σ\sigma and optional observation parameters pip_i. For each declaration lookup of ii at type AA, it requires Ω⊢σ(i):Aσ\Omega\vdash\sigma(i):A\sigma and payload compatibility of pip_i with (Aσ)#(A\sigma)^\#.✦ The images need not be strongly normalizing. Environment extension adjoins a raw typed argument and its compatible parameter.✦ If Γ⊢M:s\Gamma\vdash M:s, the substituted actual expression under ee is the actual type (Mσ)#(M\sigma)^\#.✦ If Γ⊢M:T\Gamma\vdash M:T, the substituted actual expected type is (Tσ)#(T\sigma)^\#✦, which gives a normalized active type when its profile is active.✦

A product instance is a choice of a domain DD, a body EE, formation sorts with their product rule, and an environment.✦ Its substituted domain is DσD\sigma✦, its substituted body uses the lifted substitution, and its raw instantiated target at nn is E(n⋅σ)E(n\cdot\sigma), where n⋅σn\cdot\sigma extends σ\sigma by the raw argument.✦ Their normal forms are denoted D0D_0, E0E_0, and EnE_n. Product instances arise from stored formation data or from a function typing at a product. Product instance extension adjoins an argument and compatible payload✦; an application frame environment uses the argument of its key.✦ The normalized argument frame instead uses the chosen normal form of a typed argument.✦

Given a domain candidate dd and payload-indexed body candidates b(n,p)b(n,p) at EnE_n, the tester set is dd when πΩ(D0)∈C\pi_\Omega(D_0)\in C and Top⁡D0\operatorname{Top}_{D_0} otherwise.✦ The fiber family 𝒞(n)\mathcal C(n) is empty unless Ω⊢n:D0\Omega\vdash n:D_0; for such an argument it comprises the candidates b(n,p)b(n,p) for all optional payloads pp compatible with D0D_0 when πΩ(En)∈C\pi_\Omega(E_n)\in C, and is {Top⁡En}\{\operatorname{Top}_{E_n}\} otherwise.✦ The indexed product test defining the product candidate is (5), with AA the tester set. {M∈Top⁡Πx:D0.E0∣∀n∈A∀U∈𝒞(n),Mn∈U}.\{M\in\operatorname{Top}_{\Pi x:D_0.E_0}\mid \forall n\in A\;\forall U\in\mathcal C(n),\ M\,n\in U\}.(5)✦

Structural preevaluation follows a stored typing tree and its chosen formation roles. Preevaluation gives an active observation value at (Tσ)#(T\sigma)^\# and a candidate readout at (Mσ)#(M\sigma)^\#; write the raw observation value and candidate set as 𝖵𝖺𝗅(t,e;ha)\mathsf{Val}(t,e;h_a) and 𝖱𝖾𝖺𝖽(t,e)\mathsf{Read}(t,e), with hah_a the assumption that the normalized expected type is active. Its optional evaluation parameter is present exactly in this active case.✦ A preliminary evaluation result for Γ⊢M:T\Gamma\vdash M:T under ee consists of a typed observation value at (Tσ)#(T\sigma)^\# whenever this type is active, together with a candidate readout at (Mσ)#(M\sigma)^\#.✦

The variable result takes its value from the environment parameter.✦ For a sort, the active value is distinguished and the readout is top.✦ The domain read and all compatible payload-indexed body reads determine the product candidate, which is then used to update the corresponding candidate coordinate of the product observation.✦ For an abstraction, the result uses the lambda observation action obtained by evaluating its body in the frame environments.✦ The application result applies the function’s observation using the argument’s optional evaluation parameter.✦

A base evaluation result combines its active values with the base candidate readout.✦ That readout uses the value’s base assignment at (Mσ)#(M\sigma)^\# when πΩ((Mσ)#)∈C\pi_\Omega((M\sigma)^\#)\in C, the original expected type is a literal sort ss with {s}∈C\{s\}\in C, and (Tσ)#(T\sigma)^\# is active; otherwise it is the top candidate.✦

Recursive evaluation goodness assigns a value condition 𝖵𝖺𝗅𝖦𝗈𝗈𝖽(t,σ)\mathsf{ValGood}(t,\sigma) and a readout condition 𝖱𝖾𝖺𝖽𝖦𝗈𝗈𝖽(t,σ)\mathsf{ReadGood}(t,\sigma) to a stored tree under a raw substitution. At a variable the value condition is automatic and the readout condition is the base readout condition; at a sort both are automatic. For a product with result sort cc, let gg require domain readout goodness when its substituted profile is in CC, and body readout goodness at every raw typed argument whose substituted body profile is in CC. Product value goodness requires gg when both {c}∈C\{c\}\in C and the substituted product profile is in CC; product readout goodness requires gg when that product profile is in CC.

For an abstraction, value goodness requires body value goodness under every raw typed argument with active target. For an application with active substituted function type, it requires function value goodness and, when the domain is active, argument value goodness; with inactive function type it requires the application to be neutral. The readout condition for an abstraction or application is its base readout condition with the indicated value requirement.

For trees t∈𝖳𝗋𝖾𝖾P(Γ;M,T)t\in\mathsf{Tree}_P(\Gamma;M,T) and t′∈𝖳𝗋𝖾𝖾P(Γ;N,T)t'\in\mathsf{Tree}_P(\Gamma;N,T), good observation transport 𝖦𝖳(t,t′)\mathsf{GT}(t,t') is the forward preservation property (6). The conditions range over every typed observation environment ee, with its raw substitution σ\sigma; in the value clause, hah_a denotes the assumption that πΩ((Tσ)#)\pi_\Omega((T\sigma)^\#) is active. 𝖵𝖺𝗅𝖦𝗈𝗈𝖽(t,σ)⇒{𝖵𝖺𝗅𝖦𝗈𝗈𝖽(t′,σ),𝖵𝖺𝗅(t,e;ha)=𝖵𝖺𝗅(t′,e;ha),𝖱𝖾𝖺𝖽𝖦𝗈𝗈𝖽(t,σ)⇒{𝖱𝖾𝖺𝖽𝖦𝗈𝗈𝖽(t′,σ),𝖱𝖾𝖺𝖽(t,e)=𝖱𝖾𝖺𝖽(t′,e).\begin{aligned} \mathsf{ValGood}(t,\sigma)&\ \Longrightarrow\ \begin{cases} \mathsf{ValGood}(t',\sigma),\\ \mathsf{Val}(t,e;h_a)=\mathsf{Val}(t',e;h_a), \end{cases}\\[4pt] \mathsf{ReadGood}(t,\sigma)&\ \Longrightarrow\ \begin{cases} \mathsf{ReadGood}(t',\sigma),\\ \mathsf{Read}(t,e)=\mathsf{Read}(t',e). \end{cases} \end{aligned}(6)✦

The Claim

Theorem 1 (Lemma 31). Assume system weak normalization for PP, let Ω\Omega be a saturated context tower, and let CC be a strongly connected component of the primary signed graph with no forbidden configuration. For a stored tree t∈𝖳𝗋𝖾𝖾P(Γ;M,T)t\in\mathsf{Tree}_P(\Gamma;M,T) and a full step M→βNM\to_\beta N, the reduction transport assertion is (7). ∃t′∈𝖳𝗋𝖾𝖾P(Γ;N,T),𝖦𝖳(t,t′).\exists\,t'\in\mathsf{Tree}_P(\Gamma;N,T),\qquad\mathsf{GT}(t,t').(7)✦

What Is Checked

The assertion is stated over stored typing trees, raw typed substitutions into a saturated tower, and compatible observation environments, under system weak normalization and the specified component and configuration hypotheses.

Stored trees recover their typing judgements, including a final expected sort that need not itself have a sort.✦ A function’s product type has a formation sort.✦

The actual plain dependencies are well-founded under the configuration exclusion.✦

The finite observation stage inclusions form a directed system.✦

Decoded plain payloads satisfy domain compatibility.✦ Typed values at plain types admit plain representations✦, and values at signed free types have the corresponding signed tags. A nonplain continuation target retains its source free sign.✦

For product instances, normalization preserves the product structure✦, a normalized-domain tester remains typed at the raw domain✦, and frame substitution has exactly the normalized target of the application key.✦

The indexed product tests used in evaluation are normalization candidates.