OctoInformBeta

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

Proposition 33: Under weak normalization and graph exclusion, with product tests and specialization

Component laws for observation interpretations.

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

Substitution into a dependent type may change its sort profile and the observation parameters available for testing its terms. The component interpretation assigns normalization candidates to the resulting actual types.

Let P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) be a pure type specification, with arbitrary axiom and product-rule relations, and let SS be finite.✦ Terms are variables, sorts, applications, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B.✦ The variable names in these formulas are source notation; ordinary contexts use de Bruijn indices and newest-first lists. A valid context is the empty context or an extension x:A,Ξ“x:A,\Gamma of a valid context with Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦ The judgement Ξ“βŠ’M:A\Gamma\vdash M:A is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules of PP.✦

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 ≑β\equiv_\beta is its equivalence closure.✦ A normal term has no immediate reduct; a weakly normalizing term reaches a normal term, and a strongly normalizing term admits no infinite reduction sequence. The choice M#M^\# is the full normal form when one exists and a fixed fallback otherwise.✦ A term is legal in Ξ“\Gamma when it occurs as either subject or expected type in a judgement there.✦ Assume system weak normalization: every legal term in every valid context is weakly normalizing.✦ An expected type AA in Ξ“\Gamma is an expression that is either a literal sort or satisfies Ξ“βŠ’A:s\Gamma\vdash A:s for some ss.✦

A substitution ΞΎ\xi assigns raw terms to variables; MΞΎM\xi denotes capture-avoiding simultaneous substitution.✦ Under a binder its lift fixes the bound variable and shifts the free indices in every image.✦ The single-variable substitution giving B[N/x]B[N/x] sends zero to NN and decrements higher indices.✦ An extension ΞΎ[n/x]\xi[n/x] sends the new zero index to nn and each successor index to its old image.✦ Renaming acts on free variables and uses the corresponding lift under binders; write A↑A^\uparrow for renaming by successor.✦ Iterated application Mnβ†’M\vec n is left-associated.✦

Fix a saturated context tower Ξ©\Omega. Its stage kk is a valid context of length kk, and each stage extends its predecessor by a sortable declaration. Every sortable expression with fixed free levels is declared again beyond every stage bound at which it is available. Tower typing Ω⊒M:A\Omega\vdash M:A means that some finite stage types both expressions after translating their free levels to indices: at stage kk, a level i<ki<k becomes kβˆ’1βˆ’ik-1-i, and larger indices are unchanged.✦ A typed substitution from Ξ“\Gamma to Ξ©\Omega assigns to each variable with declaration type AA, viewed in the full context, an image of tower type AΞΎA\xi.✦

The normal-form sort profiles and the axiom and product output profiles are the sets in (1). πΓ(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 set πΓ(T)\pi_\Gamma(T) for a normal term TT 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).✦

The primary signed graph is a signed directed graph on feasible profiles, with a positive edge Iβ†’JI\to J for a strict inclusion J⊊IJ\subsetneq I of feasible profiles. Each feasible product triple contributes a negative domain edge Iβ†’KI\to K and a positive codomain edge Jβ†’KJ\to K. A signed directed walk is a finite walk whose parity counts its negative edges; the empty walk has even parity.✦ Directed reachability permits either parity, whereas positive reachability uses only positive edges. A strongly connected component is the set of vertices mutually reachable with some fixed vertex.✦

Let CC be a family of profiles. Its observation layers are the profiles positively reachable in the primary graph from some nonempty Ax⁡(s)\operatorname{Ax}(s) with {s}∈C\{s\}\in C.✦ The secondary signed graph has the positive primary edges between observation layers; a feasible triple of observation layers also contributes its negative domain edge.✦ A direct layer is an observation layer II admitting a feasible triple (I,J,K)(I,J,K) with J,K∈CJ,K\in C.✦ An active layer reaches a direct layer in the secondary graph.✦ A plain layer has walks to direct layers of both parities.✦ A free layer of sign Ξ΅\varepsilon is a nonplain profile with a walk of parity Ξ΅\varepsilon to a direct layer.✦

A forbidden configuration consists of 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)\ne\varnothing, and Ax⁡(s)\operatorname{Ax}(s) positively reaches II in the primary graph.✦ Assume that no such configuration exists.

Normalization Candidates

The top candidate Top⁡T\operatorname{Top}_T consists of the typed strongly normalizing terms in (2). Argument-list reduction reduces one component by one full beta step; a strongly normalizing argument list admits no infinite sequence of these reductions. Top⁡T={M∣Ω⊒M:T,M is strongly normalizing}.\operatorname{Top}_T =\{M\mid\Omega\vdash M:T,\ M\text{ is strongly normalizing}\}.(2)✦ A tested stack nβ†’\vec n at TT is an argument list that is either empty or, when T=Ξ x:D.ET=\Pi x:D.E, has first argument n∈Top⁡Dn\in\operatorname{Top}_D and a remaining stack tested at (E[n/x])#(E[n/x])^\#. The ground candidate GTG_T is the set in (3). GT={M∣Ω⊒M:T,Mnβ†’ is strongly normalizing for every tested stack nβ†’ at T}.G_T=\{M\mid\Omega\vdash M:T,\ M\vec n\text{ is strongly normalizing for every tested stack }\vec n \text{ at }T\}.(3)✦ A normalization candidate at TT is a set AA with GTβŠ†AβŠ†Top⁡TG_T\subseteq A\subseteq\operatorname{Top}_T that is closed under typed head expansion.✦ This closure admits (Ξ»x:D.b)nnβ†’(\lambda x:D.b)\,n\,\vec n whenever it has type TT, the annotation, body, and first argument are strongly normalizing, the remaining argument list is strongly normalizing, and b[n/x]nβ†’βˆˆAb[n/x]\,\vec n\in A.✦ Write Cand⁡Ξ©(T)\operatorname{Cand}_\Omega(T) for these candidates.

An actual type is a normal sortable tower expression or a literal sort.✦ A candidate assignment bb is a family indexed by actual types TT, with a member of Cand⁡Ξ©(T)\operatorname{Cand}_\Omega(T) at each index.✦ The top assignment b⊀b_\top chooses Top⁡T\operatorname{Top}_T at each coordinate; b[T:=A]b[T:=A] replaces just the coordinate at TT.

Plain and Free Observations

A plain observation schema FF on a set of nodes NN is an assignment to each node nn of a set of keys aa, a target t(a)t(a) in NN for each key, and an optional domain d(a)d(a) in NN.✦ A continuation path is a finite sequence of successive keys.✦ A payload occurrence on a path selects a key on that path with a present domain.✦ The recursive domain dependency dβ‰Ίnd\prec n means that dd occurs as a domain after finitely many continuations from nn.✦ For a parameter family KK, single-frame parameters Par⁡a(K)\operatorname{Par}_a(K) are assignments of a value in K(d)K(d) to a present domain dd of aa; path parameters assign such a value to every payload occurrence. Empty paths have unique parameters. Prefixing a path combines its first frame parameters with its remaining parameters.✦

For a parameter family KK and base set BB, the plain table space 𝒯F(K,B;n)\mathcal T_F(K,B;n) is the set of functions assigning a result in BB to each path from nn and its parameters.✦ When β‰Ί\prec is well-founded, the recursive plain space 𝒫F(B;n)\mathcal P_F(B;n) is given by (4); its unfolding is the identification with this table space. 𝒫F(B;n)=𝒯F(𝒫F(B;β‹…),B;n)=∏p from n[(∏(d,o) a payload occurrence on p𝒫F(B;d))β†’B].\mathcal P_F(B;n)= \mathcal T_F(\mathcal P_F(B;\cdot),B;n) = \prod_{p\text{ from }n} \left[ \left(\prod_{(d,o)\text{ a payload occurrence on }p} \mathcal P_F(B;d)\right)\to B \right].(4)✦ The prefix decomposition is (5). The distinguished element with base b∈Bb\in B is the constant table.✦ 𝒫F(B;n)≃BΓ—βˆa at n[Par⁡a(𝒫F(B;β‹…))→𝒫F(B;t(a))].\mathcal P_F(B;n)\simeq B\times\prod_{a\text{ at }n} \left[ \operatorname{Par}_a(\mathcal P_F(B;\cdot)) \to\mathcal P_F(B;t(a)) \right].(5)✦

For the actual plain schema, a node is a normal sortable type TT with plain profile πΩ(T)\pi_\Omega(T).✦ A plain application key consists of a decomposition T=Ξ x:D.ET=\Pi x:D.E and a normal argument qq with Ω⊒q:D\Omega\vdash q:D and active profile πΩ(E[q/x])\pi_\Omega(E[q/x]).✦ Its target is (E[q/x])#(E[q/x])^\#.✦ Its domain node is DD when πΩ(D)\pi_\Omega(D) is active, and its domain is absent otherwise. Write 𝒫(T)\mathcal P(T) for the resulting actual plain observation space with candidate assignments as bases. A tagged plain observation is a pair (T,p)(T,p) with pβˆˆπ’«(T)p\in\mathcal P(T).✦ The default actual plain observation is the constant table with base b⊀b_\top.✦

For key set QQ, plain payload set VV, and opposite-value set YY, an optional frame payload is absent, an element of VV, or an element of YY.✦ A free observation frame pairs a key with such a payload.✦ A continuation stack is a finite list of frames; an exit stack is a continuation stack followed by one further frame designated as terminal. With bases BB and exit results OO, the free table space β„±(Y)\mathcal F(Y) consists of a BB-valued function on continuation stacks and an OO-valued function on exit stacks.✦ Mapping opposite values leaves keys and plain payloads fixed, and acts componentwise on stacks. Reindexing a table along a map Xβ†’YX\to Y precomposes its stack arguments.✦

The finite stages and signed spaces are defined in (6). The successor map is empty at stage zero and thereafter reindexes tables twice along the preceding successor map.✦ Stage inclusions iterate these successors.✦ $$Z_0=\varnothing,\qquad Z_{k+1}=\mathcal F(\mathcal F(Z_k)),\qquad \mathcal M=\varinjlim_k Z_k,\qquad \mathcal Q=\mathcal F(\mathcal M).$$(6) The finite-stage embedding sends z∈Zkz\in Z_k to its class in β„³\mathcal M.✦ Restriction of a positive table to stage kk reindexes along this embedding.✦ Finite-stage behavior at stage k+1k+1 reindexes along restriction to stage kk; represented negative behavior beh⁡:β„³β†’β„±(𝒬)\operatorname{beh}:\mathcal M\to\mathcal F(\mathcal Q) is its induced map on the direct limit. A table slice prefixes one frame to the continuing part of each stack.✦ The negative slice chooses a representative of the sliced negative behavior.✦

A constant table is a free table that returns fixed b∈Bb\in B and o∈Oo\in O on the two kinds of stack.✦ The default positive observation is that table, and the default negative observation is its stage-one class. A raw lambda table has a base bb, a body action from frames over 𝒬\mathcal Q to β„³\mathcal M, and an exit action to OO. It returns bb on the empty continuation, follows the selected body’s represented behavior after a first frame, and uses the exit action on a lone terminal frame.✦

The actual signed spaces use terms as keys, tagged plain observations as plain payloads, candidate assignments as bases, and optional tagged plain observations as exit results. Denote the resulting positive and negative spaces by 𝒬\mathcal Q and β„³\mathcal M. Their application frames have opposite payloads in β„³\mathcal M and 𝒬\mathcal Q, respectively.

Typed Values and Environments

A normalized active type is a normal sortable tower type with active profile.✦ An active actual type is a normalized active type, and a plain normalized active type is a plain node.

A raw observation value is an observation with a plain, positive, or negative tag.✦ A typed value at TT, written Value⁡(T)\operatorname{Value}(T), is a raw value whose tag fits TT: a plain tag records exactly TT, a positive tag requires a positive free profile, and a negative tag requires a negative free profile.✦ The base assignment of a typed value at TT is the candidate assignment at its empty observation: the first plain prefix coordinate, the empty positive continuation, or the empty continuation of represented negative behavior.✦

An optional payload fits a domain DD when it is absent at an inactive domain, or is present with a raw value fitting DD.✦ At an active domain its value can be extracted as a typed value.✦ Plain value injection tags an element of 𝒫(T)\mathcal P(T); plain extraction selects its representing observation. Positive and negative extraction select the corresponding signed observations. For a normalized active type TT with plain profile and a typed value v∈Value⁡(T)v\in\operatorname{Value}(T), plain tagging is the tagged plain observation consisting of the plain node of TT and the plain observation representing vv.✦ Typed projection at an active type keeps a fitting raw value and otherwise returns the distinguished value obtained by tagging the default observation appropriate to that type.✦ A checked exit projects a present plain result and uses the distinguished value for an absent result.✦

An active application key at TT consists of a decomposition T=Ξ x:D.ET=\Pi x:D.E and a normal argument qq with Ω⊒q:D\Omega\vdash q:D and active profile πΩ(E[q/x])\pi_\Omega(E[q/x]), where TT is active. A plain source permits its conversion to a plain application key.✦ Its active target is (E[q/x])#(E[q/x])^\#.✦ Plain payload decoding returns the domain’s plain tag when its domain is active and returns absence otherwise; plain payload encoding supplies the corresponding single frame parameters. Positive frame encoding retains a plain tag or an opposite negative value; negative frame encoding retains a plain tag or an opposite positive value. The respective decoders restore these raw tags and preserve absence.

A free application gate at TT, key qq, payload pp, and an exit flag holds when an active application key has argument qq, its domain admits pp, and its target is plain exactly when the exit flag is set.✦ The gated key for a free application gate is a chosen active application key satisfying the gate’s argument, payload, and exit conditions.✦ A lambda action at TT is a family of typed target values indexed by active application keys and fitting domain payloads.✦ Plain lambda prefixing places this action in the continuation coordinates of the plain prefix decomposition.✦

For a free source of either sign, lambda continuation returns the corresponding signed extraction of the action at a continuation gate; at a failing gate it returns the signed default with base b⊀b_\top and no exit. The lambda exit operation returns a plain tagging of the action at an exit gate and returns absence otherwise.✦ The positive lambda table uses these operations, with empty base b⊀b_\top.✦ Negative lambda behavior is the raw lambda table with negative continuation and the lambda exit operation.✦ The observation associated with a negative behavior is a chosen representative when one exists and the negative default otherwise.✦ Lambda observation values use the plain prefix or the appropriate signed lambda construction.✦

For a typed value v∈Value⁡(T)v\in\operatorname{Value}(T) at a normalized active type TT, an active application key aa at TT, and an optional payload fitting the domain of aa, observation application returns a typed value at the target of aa by the plain continuation coordinate, a free continuation slice, or a checked exit.✦ A prescribed-base observation at an active type is a typed observation value whose empty observation is a given candidate assignment and whose nonempty observations are those of the distinguished value at that type.✦

A typed observation environment e=(ΞΎe,ΞΈe)e=(\xi_e,\theta_e) over Ξ“\Gamma consists of a typed raw substitution ΞΎe:Ξ“β†’Ξ©\xi_e:\Gamma\to\Omega and an optional raw parameter ΞΈe(i)\theta_e(i) at every index, fitting (AΞΎe)#(A\xi_e)^\# at each declaration type AA found at ii.✦ Write Env⁡(Ξ“)\operatorname{Env}(\Gamma) for these environments. Environment images are raw actual terms. The substituted actual expression of Ξ“βŠ’M:s\Gamma\vdash M:s is (MΞΎe)#(M\xi_e)^\#, and the substituted actual type of Ξ“βŠ’M:T\Gamma\vdash M:T is (TΞΎe)#(T\xi_e)^\#; when the latter is active it also determines the substituted active type.

Environment extension by a typed raw term nn and a fitting parameter pp sends zero to n,pn,p and successor indices to the old images and parameters.✦ The extension relation Ext⁡(e,f,n)\operatorname{Ext}(e,f,n) in (7) leaves the new parameter unrestricted except for the requirement that ff be a typed observation environment, with the new parameter fitting the substituted declaration type in ff. Ext⁡(e,f,n)⇔ξf=ΞΎe[n/x] and ΞΈf(i+1)=ΞΈe(i)for every i.\operatorname{Ext}(e,f,n) \quad\Longleftrightarrow\quad \xi_f=\xi_e[n/x]\ \text{ and }\ \theta_f(i+1)=\theta_e(i)\quad\text{for every }i.(7) Two environments over Ξ“\Gamma are compatible when their images are convertible at every index below |Ξ“||\Gamma| and their parameters agree there.✦ Environments over possibly different contexts have the same data when their entire image and parameter maps agree.✦ Contexts Γ≃PΞ”\Gamma\simeq_P\Delta are equivalent when both are valid and have exactly the same judgements M:AM:A, with subject and expected type unchanged.✦

Product Tests and Evaluation

A product instance consists of a context Ξ“\Gamma, domain DD, body EE, a typed observation environment ee, and chosen formation sorts a,b,ca,b,c with Ξ“βŠ’D:a\Gamma\vdash D:a, x:D,Ξ“βŠ’E:bx:D,\Gamma\vdash E:b, and (a,b,c)βˆˆβ„›(a,b,c)\in\mathcal R.✦ Product formation supplies such an instance; a function judgement at Ξ x:D.E\Pi x:D.E also supplies one. For an instance tt, its raw domain, raw body, and raw instantiated target, and their normalizations, are defined in (8). Dtraw=DΞΎe,Dt=(Dtraw)#,Etraw=E(ΞΎe↑),Et=(Etraw)#,Ttraw(n)=E(ΞΎe[n/x]),Tt(n)=(Ttraw(n))#.\begin{aligned} D_t^{\mathrm{raw}}&=D\xi_e,& D_t&=(D_t^{\mathrm{raw}})^\#,\\ E_t^{\mathrm{raw}}&=E(\xi_e^\uparrow),& E_t&=(E_t^{\mathrm{raw}})^\#,\\ T_t^{\mathrm{raw}}(n)&=E(\xi_e[n/x]),& T_t(n)&=(T_t^{\mathrm{raw}}(n))^\#. \end{aligned}(8) Here ΞΎe↑\xi_e^\uparrow is the lifted substitution. Extending the instance by n:Dtn:D_t and a fitting payload uses the same raw nn.✦ When Tt(n)T_t(n) is active, the normalized argument frame has argument n#n^\#.✦ An active frame at the normalized product similarly determines its frame environment by extension with its argument and payload.✦

Payload-indexed body candidates b(n,p)b(n,p) form a family of candidates at Tt(n)T_t(n) indexed by every nn with Ω⊒n:Dt\Omega\vdash n:D_t and every fitting payload pp at DtD_t.✦ For a domain candidate dd, the tester set and fibers are (9); Payload⁡(Dt)\operatorname{Payload}(D_t) denotes the fitting optional payloads. At(d)={d,πΩ(Dt)∈C,Top⁡Dt,πΩ(Dt)βˆ‰C,π’žt(b;n)={βŒ€,Ω⋣n:Dt,{b(n,p)∣p∈Payload⁡(Dt)},Ω⊒n:Dt,πΩ(Tt(n))∈C,{Top⁡Tt(n)},Ω⊒n:Dt,πΩ(Tt(n))βˆ‰C.\begin{aligned} A_t(d)&= \begin{cases} d,&\pi_\Omega(D_t)\in C,\\ \operatorname{Top}_{D_t},&\pi_\Omega(D_t)\notin C, \end{cases}\\ \mathcal C_t(b;n)&= \begin{cases} \varnothing,&\Omega\not\vdash n:D_t,\\ \{b(n,p)\mid p\in\operatorname{Payload}(D_t)\}, &\Omega\vdash n:D_t,\ \pi_\Omega(T_t(n))\in C,\\ \{\operatorname{Top}_{T_t(n)}\}, &\Omega\vdash n:D_t,\ \pi_\Omega(T_t(n))\notin C. \end{cases} \end{aligned}(9) The indexed product test for a domain set AA and candidate families π’ž(n)\mathcal C(n) is (10). For a domain candidate dd at DtD_t and payload-indexed body candidates bb, the product test candidate of t,d,bt,d,b is the normalization candidate at Ξ x:Dt.Et\Pi x:D_t.E_t given by (10), with tester set At(d)A_t(d) and fibers π’žt(b;β‹…)\mathcal C_t(b;\cdot).✦ Prod⁡(D,E;A,π’ž)={h∈Top⁡Ξ x:D.E∣hn∈U for every n∈A and every Uβˆˆπ’ž(n)}.\operatorname{Prod}(D,E;A,\mathcal C) = \{h\in\operatorname{Top}_{\Pi x:D.E}\mid hn\in U\text{ for every }n\in A \text{ and every }U\in\mathcal C(n)\}.(10)✦

A typing derivation tree for Ξ“βŠ’M:T\Gamma\vdash M:T records the variable declaration or sort axiom and each chosen formation role, with the conversion to the expected type at each node.✦ A product node includes its domain and body sorts and the chosen product rule; an abstraction includes its annotation and body judgements and the product sort; an application includes its function and argument judgements and instantiated expected type.

A preliminary evaluation result for Ξ“βŠ’M:T\Gamma\vdash M:T at ee has an observation value Val⁡e(M:T)\operatorname{Val}_e(M:T) whenever πΩ((TΞΎe)#)\pi_\Omega((T\xi_e)^\#) is active, and a candidate readout Read⁡e(M:T)∈Cand⁡Ξ©((MΞΎe)#)\operatorname{Read}_e(M:T)\in \operatorname{Cand}_\Omega((M\xi_e)^\#). The optional evaluation parameter for a preliminary evaluation result for Ξ“βŠ’M:T\Gamma\vdash M:T at ee is the raw observation value Val⁡e(M:T)\operatorname{Val}_e(M:T) in the active case and absence otherwise.✦ The base readout reads the candidate coordinate at (MΞΎe)#(M\xi_e)^\# of the value’s base assignment when the actual subject profile lies in CC, the expected type is literally a sort ss with {s}∈C\{s\}\in C, and the actual expected type is active; otherwise it is Top⁡(MΞΎe)#\operatorname{Top}_{(M\xi_e)^\#}.✦ The base evaluation result pairs a supplied active value with this readout.✦

Structural observation evaluation follows the typing derivation tree.✦ Variable evaluation uses the corresponding environment parameter.✦ Sort evaluation uses the distinguished active value and the top readout.✦ Application evaluation applies the function’s observation to the normalized argument frame and the argument’s optional evaluation parameter.✦ Abstraction evaluation uses the body evaluations in extended environments as its lambda action, followed by the base evaluation result.✦

Product evaluation forms its evaluated product candidate from the domain readout and all fitting-payload body readouts in (10).✦ This candidate is its readout; its product observation updates the exact candidate coordinate.✦ The normal-form candidate readout Read⁡e#(A)\operatorname{Read}^{\#}_e(A) of an expression AA is the candidate obtained by evaluating a chosen typing tree for the generic normal form A#A^\# and reading its candidate at (AΞΎe)#(A\xi_e)^\#.✦

For an expression AA in Ξ“\Gamma and an observation environment ee over Ξ“\Gamma, the observation interpretation RA(e)R_A(e) is the set in (11). RA(e)={Read⁡e#(A),πΓ(A)∈Cand Ξ“βŠ’A:s for some s,Top⁡(AΞΎe)#,otherwise.R_A(e)= \begin{cases} \operatorname{Read}^{\#}_e(A),& \pi_\Gamma(A)\in C\ \text{and }\Gamma\vdash A:s\text{ for some }s,\\ \operatorname{Top}_{(A\xi_e)^\#},&\text{otherwise}. \end{cases}(11)✦

A component interpretation over Ξ©,C\Omega,C is a system of environments, their raw substitutions, an extension relation, and interpretations that realizes every typed raw substitution and admits extension by every typed image of a sortable declaration. Its extension relation extends the raw substitution by the new image. At expected types its interpretations are candidates, respect conversion and sorted weakening, and equal the top candidate whenever either the generic or actual profile lies outside CC. At a sorted product whose generic and actual profiles lie in CC, it admits product introduction from typed strongly normalizing functions passing every domain test in every extension, and specialization at typed source arguments whose actual images pass the domain test. Write π–’π—ˆπ—†π—‰π–¨π—‡π—(Ξ©,C)\mathsf{CompInt}(\Omega,C) for these interpretations.

The Claim

Theorem 1 (Observation component laws). Assume system weak normalization for the finite specification PP, let Ξ©\Omega be a saturated context tower, and let CC be a primary strongly connected component with no forbidden configuration.

The observation component interpretation is (12). ℐΩ,C=(Env⁡,e↦ξe,Ext⁡,R)βˆˆπ–’π—ˆπ—†π—‰π–¨π—‡π—(Ξ©,C).\mathcal I_{\Omega,C} =(\operatorname{Env},\,e\mapsto\xi_e,\,\operatorname{Ext},\,R) \ \in\ \mathsf{CompInt}(\Omega,C).(12)✦ For every expression AA and observation environment ee over its context, the candidate law is (13). RA(e)∈Cand⁡Ξ©((AΞΎe)#).R_A(e)\in\operatorname{Cand}_\Omega((A\xi_e)^\#).(13)✦

Let T=Ξ x:D.ET=\Pi x:D.E satisfy Ξ“βŠ’T:s\Gamma\vdash T:s, and suppose that πΓ(T)\pi_\Gamma(T) and πΩ(TΞΎe)\pi_\Omega(T\xi_e) belong to CC. For any term hh, product membership is characterized by (14). h∈RT(e)⇔h∈Top⁡(TΞΎe)# andhn∈RE(f)for every n∈RD(e) and every f with Ext⁡(e,f,n).\begin{aligned} h\in R_T(e)\quad\Longleftrightarrow\quad& h\in\operatorname{Top}_{(T\xi_e)^\#}\ \text{ and}\\ &hn\in R_E(f)\quad \text{for every }n\in R_D(e)\text{ and every } f\text{ with }\operatorname{Ext}(e,f,n). \end{aligned}(14)✦ For a source argument Ξ“βŠ’N:D\Gamma\vdash N:D, assume h∈RT(e)h\in R_T(e) and NΞΎe∈RD(e)N\xi_e\in R_D(e). The specialization law is (15). h(NΞΎe)∈RE[N/x](e).h\,(N\xi_e)\in R_{E[N/x]}(e).(15)✦

Let AA be an expected type in Ξ“\Gamma. For compatible environments e,fe,f over Ξ“\Gamma, interpretation invariance is (16). RA(e)=RA(f).R_A(e)=R_A(f).(16)✦ For equivalent contexts Γ≃PΞ”\Gamma\simeq_P\Delta and environments ee over Ξ“\Gamma, ff over Ξ”\Delta with the same data, recontextualization is (17). RA(e)=RA(f).R_A(e)=R_A(f).(17)✦

In the paper, the result reads: under system-wide weak normalization and the graph exclusion of the Β§Β 5 setting, the interpretation RT(ΞΎ,ΞΈ)R_T(\xi,\theta) gives candidates invariant under weakening and context conversion, with nonempty parameter extensions and the product test clause, and, for a generic normal product T=Ξ x:D.ET=\Pi x:D.E with profile in CC and Ξ“βŠ’N:D\Gamma\vdash N:D whose actual image NΞΎN\xi passes its domain test, a passing test of a candidate member hh entails h(NΞΎ)∈R(E[N/x])#(ΞΎ,ΞΈ)h\,(N\xi)\in R_{(E[N/x])^\#}(\xi,\theta), while the ordinary typed strongly normalizing clause applies when the instantiated actual profile lies in the paper’s ordinary profile class 𝒰\mathcal U.

What Is Checked

The claim is stated over the finite pure type specification, its full beta reduction and typing judgements, a saturated context tower, the primary component and secondary graph exclusion, and the observation environments with their typed raw substitutions.

The actual plain schema has well-founded recursive domain dependencies, including those reached after finitely many continuations.✦

The finite signed observation stages and their inclusions form a directed system.✦ Slicing represented negative behavior again has a negative representative.✦

Decoded plain payloads fit their domains.✦ An active application key whose source has a free sign and whose target is nonplain retains that sign at its target.✦

Every typing judgement admits a typing derivation tree✦, from which its subject and expected type judgement is recovered. For each product instance, normalization preserves the product structure✦, a tester typed at the normalized domain remains typed at the raw domain✦, and substitution of the body in a frame environment has exactly the frame’s normalized target.✦