Stratified Universality

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

1 \section{Carrier change, observer base change, and provenance}
2 \label{sec:block18-carrier-observer}
3 
4 A behavioral quotient is computed inside an observation category, but the represented computation also has a carrier algebra.  Additive convolution, Boolean support, max-plus aggregation, and convex support geometry do not combine routes by the same law.  This section separates carrier translation from observer minimization and gives exact obstruction objects for both.
5 
6 \subsection{Carrier factorization and joint semantic completion}
7 \label{subsec:block18-carrier-factorization}
8 
9 Let \(\mathcal R\) be a raw algebra of expressions or histories for a fixed operation signature.  Let
10 \[
11  s:\mathcal R\longrightarrow S,
12  \qquad
13  t:\mathcal R\longrightarrow T
14 \]
15 be homomorphisms into two semantic carriers.
16 
17 \begin{theorem}[Carrier factorization gate]
18 \label{thm:block18-carrier-factorization}
19 There is a unique homomorphism
20 \[
21  \varphi:\im(s)\longrightarrow T
22 \]
23 with \(t=\varphi s\) if and only if
24 \[
25  \kerpair(s)\subseteq\kerpair(t).
26 \]
27 When the condition fails, any pair \(x,y\in\mathcal R\) satisfying
28 \[
29  s(x)=s(y),
30  \qquad
31  t(x)\neq t(y)
32 \]
33 is an exact carrier-change obstruction witness.
34 \end{theorem}
35 
36 \begin{proof}
37 Factorization immediately implies constancy of \(t\) on every fiber of \(s\).  Conversely, define
38 \[
39  \varphi(s(x)):=t(x).
40 \]
41 The fiber condition makes this well defined.  Since both \(s\) and \(t\) preserve every primitive operation, so does \(\varphi\).  Uniqueness follows because \(s\) is surjective onto its image.
42 \end{proof}
43 
44 \begin{definition}[Joint semantic completion]
45 \label{def:block18-joint-completion}
46 Define
47 \[
48  j=(s,t):\mathcal R\longrightarrow S\times T,
49  \qquad
50  J_{s,t}:=\im(j).
51 \]
52 The projection
53 \[
54  p_s:J_{s,t}\longrightarrow\im(s)
55 \]
56 is the \emph{relative completion map} from the joint semantics to the source semantics.
57 \end{definition}
58 
59 \begin{theorem}[Universal joint completion]
60 \label{thm:block18-universal-joint-completion}
61 The object \(J_{s,t}\) is the coarsest quotient of \(\mathcal R\) preserving both \(s\) and \(t\).  More precisely, if
62 \[
63  c:\mathcal R\twoheadrightarrow C
64 \]
65 admits maps \(a:C\to S\) and \(b:C\to T\) with \(s=ac\) and \(t=bc\), then there is a unique map
66 \[
67  C\longrightarrow J_{s,t}
68 \]
69 compatible with both semantics.  Furthermore,
70 \[
71  t\text{ factors through }s
72  \quad\Longleftrightarrow\quad
73  p_s\text{ is an isomorphism}.
74 \]
75 \end{theorem}
76 
77 \begin{proof}
78 The pair \((a,b)\) factors \(j\) through \(c\), and the image universal property gives the map to \(J_{s,t}\).  If \(t=\varphi s\), then \(J_{s,t}\) is the graph of \(\varphi\), so \(p_s\) is invertible.  Conversely, if \(p_s\) is invertible, define \(\varphi=p_t p_s^{-1}\).
79 \end{proof}
80 
81 \subsection{Behavioral bridges and exact loss}
82 \label{subsec:block18-bridge-loss}
83 
84 Let \(f:X\to Y\) be a linear bridge between observational systems, with behavioral kernels \(N_X\subseteq X\) and \(N_Y\subseteq Y\).
85 
86 \begin{definition}[Task-compatible bridge]
87 \label{def:block18-task-compatible-bridge}
88 The bridge is \emph{task compatible} when
89 \[
90  f(N_X)\subseteq N_Y.
91 \]
92 Equivalently,
93 \[
94  N_X\subseteq f^{-1}(N_Y).
95 \]
96 Then there is a unique induced map
97 \[
98  \overline f:X/N_X\longrightarrow Y/N_Y.
99 \]
100 \end{definition}
101 
102 \begin{theorem}[Bridge-loss exact sequence]
103 \label{thm:block18-bridge-loss-exact}
104 For every task-compatible linear bridge, there is an exact sequence
105 \[
106  0\longrightarrow
107  \frac{f^{-1}(N_Y)}{N_X}
108  \longrightarrow
109  \frac{X}{N_X}
110  \xrightarrow{\overline f}
111  \frac{Y}{N_Y}
112  \longrightarrow
113  \frac{Y}{N_Y+f(X)}
114  \longrightarrow0.
115 \]
116 Thus
117 \[
118  L_f:=\frac{f^{-1}(N_Y)}{N_X}
119 \]
120 measures source distinctions collapsed by the bridge, while
121 \[
122  E_f:=\frac{Y}{N_Y+f(X)}
123 \]
124 measures target semantic states outside the essential image.
125 \end{theorem}
126 
127 \begin{proof}
128 The kernel of \(\overline f\) consists of classes \(x+N_X\) for which \(f(x)\in N_Y\), hence equals \(f^{-1}(N_Y)/N_X\).  The cokernel of \(\overline f\) is the quotient of \(Y/N_Y\) by \((f(X)+N_Y)/N_Y\), which is \(Y/(N_Y+f(X))\).
129 \end{proof}
130 
131 \begin{corollary}[Exact semantic equivalence gate]
132 \label{cor:block18-semantic-equivalence-gate}
133 The induced bridge \(\overline f\) is an isomorphism exactly when
134 \[
135  L_f=0
136  \qquad\text{and}\qquad
137  E_f=0.
138 \]
139 Faithfulness on the declared task and essential surjectivity on the declared task are therefore independent obligations.
140 \end{corollary}
141 
142 \begin{theorem}[Loss-composition extension]
143 \label{thm:block18-loss-composition}
144 For induced quotient maps
145 \[
146  Q_X\xrightarrow{\overline f}Q_Y\xrightarrow{\overline g}Q_Z,
147 \]
148 there is a natural exact sequence
149 \[
150  0\longrightarrow\ker\overline f
151  \longrightarrow\ker(\overline g\,\overline f)
152  \longrightarrow\ker\overline g\cap\im\overline f
153  \longrightarrow0.
154 \]
155 If \(\overline f\) is surjective, this reduces to
156 \[
157  0\longrightarrow L_f
158  \longrightarrow L_{gf}
159  \longrightarrow L_g
160  \longrightarrow0.
161 \]
162 \end{theorem}
163 
164 \begin{proof}
165 Map \(x\in\ker(\overline g\,\overline f)\) to \(\overline f(x)\).  Its image is exactly \(\ker\overline g\cap\im\overline f\), and its kernel is \(\ker\overline f\).  Surjectivity of \(\overline f\) identifies the intersection with \(\ker\overline g\).
166 \end{proof}
167 
168 \begin{boundary}[Loss is extension data]
169 \label{bnd:block18-loss-extension}
170 The preceding sequence need not split.  Consequently, composite information loss is not in general a scalar sum or a canonical direct sum of stagewise losses.  A numerical loss budget may be useful, but it is a further invariant of the exact extension rather than a replacement for it.
171 \end{boundary}
172 
173 \subsection{Carrier-indexed observer packets}
174 \label{subsec:block18-carrier-observer-packets}
175 
176 \begin{theorem}[Carrier-indexed observer packet theorem]
177 \label{thm:block18-carrier-indexed-observer}
178 Let \(S\) be a finite continuation-state set, let \((A,\oplus,0)\) be a commutative monoid, let \(B\) be a finite branch alphabet, and let
179 \[
180  \delta:S\times B\longrightarrow S
181 \]
182 be a state transition.  Suppose every branch \(b\in B\) acts by a monoid homomorphism
183 \[
184  L_b:A\longrightarrow A.
185 \]
186 Take an empty aggregation to be \(0\).  For a state packet \(a=(a_s)_{s\in S}\), define
187 \[
188  a'_t
189  :=
190  \bigoplus_{\delta(s,b)=t}L_b(a_s).
191 \]
192 If a finite family of raw histories has already been aggregated by their state using \(\oplus\), then this update gives exactly the same result as advancing every raw history separately and aggregating afterward.
193 \end{theorem}
194 
195 \begin{proof}
196 Expand the raw history update and group all terms by their predecessor state and new branch.  Associativity and commutativity permit the regrouping.  The identity
197 \[
198  L_b\!\left(\bigoplus_i x_i\right)
199  =
200  \bigoplus_i L_b(x_i)
201 \]
202 then moves aggregation through the branch action.  The displayed formula is the resulting statewise sum.
203 \end{proof}
204 
205 Two important realizations have the same state skeleton but different carriers.
206 \begin{enumerate}
207 \item For convex value semantics, \(A\) is the family of compact convex sets, including the empty set, \(\oplus\) is convex hull of union with identity \(\varnothing\), and \(L_b(C)=A_b^{\mathsf T}C\).
208 \item For linear polyphase routing, \(A\) is an additive convolution algebra, \(\oplus\) is coefficient addition, and \(L_b\) multiplies route kernels by the declared filter or transition weight.
209 \end{enumerate}
210 The theorem transports the observer skeleton only after the carrier law and the homomorphism obligations are specified.
211 
212 \subsection{Carrier no-go mechanisms}
213 \label{subsec:block18-carrier-no-go}
214 
215 \begin{theorem}[Cancellation barrier]
216 \label{thm:block18-cancellation-barrier}
217 Let \(R\) be a nonzero ring and let \(S\) be a nontrivial zerosumfree semiring, so
218 \[
219  a+b=0\Longrightarrow a=b=0.
220 \]
221 There is no unital semiring homomorphism \(R\to S\).
222 \end{theorem}
223 
224 \begin{proof}
225 A unital homomorphism \(\varphi\) would give
226 \[
227  0=\varphi(1+(-1))=1_S+\varphi(-1).
228 \]
229 Zerosumfreeness forces \(1_S=0\), contradicting nontriviality.
230 \end{proof}
231 
232 \begin{theorem}[Idempotence barrier]
233 \label{thm:block18-idempotence-barrier}
234 Let \(S\) be a nontrivial unital semiring with idempotent addition, and let \(R\) be an additively cancellative nontrivial semiring.  There is no unital semiring homomorphism \(S\to R\).
235 \end{theorem}
236 
237 \begin{proof}
238 In \(S\), \(1+1=1\).  Its image in \(R\) would satisfy \(1_R+1_R=1_R\), and additive cancellation would imply \(1_R=0\).
239 \end{proof}
240 
241 \begin{example}[Haar cancellation]
242 \label{ex:block18-haar-cancellation}
243 For the normalized Haar bank,
244 \[
245  \ell=\frac{x_0+x_1}{\sqrt2},
246  \qquad
247  d=\frac{x_0-x_1}{\sqrt2},
248 \]
249 and
250 \[
251  x_0=\frac{\ell+d}{\sqrt2},
252  \qquad
253  x_1=\frac{\ell-d}{\sqrt2}.
254 \]
255 At \(x=(1,0)\), the two route contributions to \(x_0\) are \(1/2,1/2\), while those to \(x_1\) are \(1/2,-1/2\).  Additive reconstruction returns \((1,0)\).  Replacing route addition by maximum returns \((1/2,1/2)\).  The convex/max carrier is therefore not an exact replacement for the signed additive carrier.
256 \end{example}
257 
258 \subsection{Observer base change and the relation module}
259 \label{subsec:block18-observer-base-change}
260 
261 Let \(E\subseteq K^M\) be the set of distinct residual future functions of a scalar series or observational system.  Set minimization retains the elements of \(E\) as distinct states.  Free linearization produces the vector space \(K^{(E)}\), while linear minimization retains only their span.
262 
263 \begin{theorem}[Observer base-change exact sequence]
264 \label{thm:block18-observer-base-change}
265 The evaluation map
266 \[
267  \pi:K^{(E)}\longrightarrow\Span_K(E),
268  \qquad
269  \sum_{e\in E}a_e[e]
270  \longmapsto
271  \sum_{e\in E}a_e e
272 \]
273 is surjective and fits into the exact sequence
274 \[
275  0\longrightarrow\Rel_K(E)
276  \longrightarrow K^{(E)}
277  \xrightarrow{\pi}\Span_K(E)
278  \longrightarrow0,
279 \]
280 where
281 \[
282  \Rel_K(E):=\ker\pi
283 \]
284 is the module of linear relations among distinct discrete residual states.  Hence Set minimization commutes with free linearization exactly when \(E\) is linearly independent.
285 \end{theorem}
286 
287 \begin{proof}
288 Surjectivity is the definition of the linear span.  The sequence is the kernel-cokernel sequence of \(\pi\).  The kernel vanishes exactly when the basis symbols \([e]\) remain linearly independent after evaluation.
289 \end{proof}
290 
291 \begin{theorem}[Exact polyphase separation]
292 \label{thm:block18-polyphase-hankel-separation}
293 Fix \(N\geq1\) and \(z\neq0\).  Let \(S_z\) be the cyclic shift on \(K^N\) satisfying
294 \[
295  S_z e_j=e_{j+1}\quad(j<N-1),
296  \qquad
297  S_z e_{N-1}=z e_0,
298 \]
299 so \(S_z^N=zI\).  Put
300 \[
301  M_N=I+S_z,
302  \qquad
303  f_N(n)=e_0^{\mathsf T}M_N^n e_0.
304 \]
305 Then the \(N\times N\) Hankel block
306 \[
307  H_{ij}=f_N(i+j),
308  \qquad 0\leq i,j<N,
309 \]
310 has determinant
311 \[
312  \det H=\pm z^{N-1}.
313 \]
314 Consequently its linear residual space has dimension \(N\).  If \(z>0\), the residual functions \(k\mapsto f_N(n+k)\) are pairwise distinct, so the exact discrete future quotient is infinite while the linear continuation dimension is \(N\).
315 \end{theorem}
316 
317 \begin{proof}
318 Factor \(H=OC\), where row \(i\) of \(O\) is \(e_0^{\mathsf T}M_N^i\), and column \(j\) of \(C\) is \(M_N^j e_0\).  For \(j<N\), the binomial expansion of \((I+S_z)^j e_0\) is a unit upper-triangular change from \((e_0,\ldots,e_{N-1})\), hence \(\det C=1\).  The rows \(e_0^{\mathsf T}S_z^k\), \(0\leq k<N\), are \(e_0^{\mathsf T}\) followed by \(z e_{N-k}^{\mathsf T}\), so their determinant is \(\pm z^{N-1}\).  The binomial row change is also unit triangular, proving the determinant formula.
319 
320 For positive \(z\),
321 \[
322  f_N(n)=\sum_{r=0}^{\lfloor n/N\rfloor}\binom n{Nr}z^r.
323 \]
324 The sequence is strictly increasing from index \(N-1\) onward.  Prefixes below \(N\) are distinguished by choosing the first suffix that crosses index \(N\), and later prefixes differ already at suffix zero.  Thus all residual functions are distinct.
325 \end{proof}
326 
327 The interpretation of finite Hankel rank as minimal weighted-linear realization dimension is classical weighted-automata theory \cite{CarlylePaz1971,LiRabusseauPrecup2018}.  The displayed family is retained here because it gives an exact internal example of an infinite discrete quotient and a finite linear quotient.
328 
329 \subsection{Observer-conditioned convex packets}
330 \label{subsec:block18-convex-provenance}
331 
332 Let \(S\) be a finite observer-state set, let \(B\) be a finite branch
333 alphabet, and let \(C_s\subseteq\mathbb R^d\) be a compact convex packet for
334 each state, with empty packets allowed.  Use the conventions
335 \[
336  h_{\varnothing}(x)=-\infty,\qquad
337  \operatorname{conv}(\varnothing)=\varnothing,\qquad
338  \max\varnothing=-\infty.
339 \]
340 For branch matrices \((A_b)_{b\in B}\) and a transition
341 \(\delta:S\times B\to S\), put
342 \[
343  C'_t
344  =
345  \operatorname{conv}
346  \bigcup_{\delta(s,b)=t}A_b^{\mathsf T}C_s.
347 \]
348 
349 \begin{theorem}[Observer-conditioned convex packet transport]
350 \label{thm:block18-convex-packet-transport}
351 For every state \(t\in S\) and direction \(x\),
352 \[
353  h_{C'_t}(x)
354  =
355  \max_{\delta(s,b)=t}h_{C_s}(A_bx).
356 \]
357 Repeated updates compose exactly with branch words.  Within each fixed observer state, replacing a finite atom family by any other finite generating family of the same convex hull preserves all future value queries generated by linear branch actions.
358 \end{theorem}
359 
360 \begin{proof}
361 For a linear map \(A\),
362 \[
363  h_{A^{\mathsf T}C}(x)=h_C(Ax).
364 \]
365 If the incoming fiber is empty, both sides of the formula are \(-\infty\).
366 Otherwise, the support function of the convex hull of a finite union is the
367 maximum of the component support functions, with the same conventions for
368 empty components.  These identities give the formula.  Finite unions of
369 compact sets have compact convex hulls in finite dimension, so every updated
370 packet stays in the declared carrier.  Iteration follows from composition of the linear maps and of \(\delta\).  Equality of convex hulls is preserved by linear images and convex hull of union, proving future value equivalence.
371 \end{proof}
372 
373 \begin{proposition}[Singular resurrection]
374 \label{prop:block18-singular-resurrection}
375 A provenance state carried only by a strictly interior atom may be inactive for every current nonzero linear query and yet become active after an admissible singular continuation.  In particular, if the zero map is admissible, every atom is sent to the same point and all provenance states tie.
376 \end{proposition}
377 
378 \begin{proposition}[Invertible hiding]
379 \label{prop:block18-invertible-hiding}
380 Assume the total convex body is full-dimensional, query directions are nonzero, and every admissible branch matrix is invertible.  A strictly interior atom remains strictly interior under every continuation and therefore cannot maximize a nonzero linear functional.  Its provenance remains permanently hidden from the declared value query.
381 \end{proposition}
382 
383 \begin{proof}
384 Invertible linear maps preserve relative interior and full dimension.  A nonzero linear functional cannot attain its maximum at a strict interior point of a compact full-dimensional convex body.
385 \end{proof}
386 
387 \begin{boundary}[Value, witness, and history are distinct tasks]
388 \label{bnd:block18-provenance-boundary}
389 Exact convex geometry determines value semantics and its derived normal-fan structure.  It does not determine branch identity, maximizing multiplicity, or raw history.  Value-only, one-witness, all-witness, and complete-history tasks therefore have different minimal quotients.  No provenance deletion rule is valid without the admissible continuation class and the downstream query family.
390 \end{boundary}
391 
392 \begin{resultbox}
393 \textbf{Carrier and observer result.}
394 Exact carrier replacement is equivalent to semantic factorization.  When it fails, the joint image is the universal completion preserving both semantics.  Behavioral bridges carry independent kernel-loss and essential-image defects.  Observer minimization then depends on the observation category: discrete residual equality and linear residual span are related by an exact relation module, not by automatic identification.
395 \end{resultbox}

Back to source controls

Back to Stratified Universality