Target-Relative Necessity of Completion: When Readout Loss Obstructs, and What a Sufficient Extension Must Retain

Exact target solvability and its obstruction

Jeremy RodgersSection 4 of 16Original PDF ↗Publication DOI ↗

Exact target solvability and its obstruction

The criterion

Theorem 3.1 (Exact target-solvability criterion).

Let $p\colon S\to T$ be a readout and let $Q=(A_Q,a_Q)$ be a target on $S$ . The following are equivalent.

$Q$ is exactly solvable from the readout; that is, there is $\bar a_Q\colon T\to A_Q$ with $a_Q=\bar a_Q\circ p$ .
$a_Q$ is constant on every fiber of $p$ : for all $t\in T$ and all $s,s'\in F_t$ , $a_Q(s)=a_Q(s')$ .
For all $s,s'\in S$ , $\;p(s)=p(s') \implies a_Q(s)=a_Q(s')$ .

Moreover, when these hold, $\bar a_Q$ is unique.

Proof. Conditions (2) and (3) are restatements of one another: $s,s'$ lie in a common fiber precisely when $p(s)=p(s')$ .

(1) $\Rightarrow$ (3). Suppose $a_Q=\bar a_Q\circ p$ and $p(s)=p(s')$ . Applying $\bar a_Q$ to both sides of $p(s)=p(s')$ gives $a_Q(s)=\bar a_Q(p(s))=\bar a_Q(p(s'))=a_Q(s')$ .

(3) $\Rightarrow$ (1). We construct $\bar a_Q$ . Let $t\in T$ . Since $p$ is surjective, $F_t\neq\emptyset$ ; choose $s\in F_t$ and set $\bar a_Q(t) := a_Q(s).\tag{5}$ This is independent of the choice of $s$ : if $s'\in F_t$ is another element, then $p(s)=t=p(s')$ , so by (3) $a_Q(s)=a_Q(s')$ . Hence $\bar a_Q\colon T\to A_Q$ is a well-defined map. (That some element may be chosen from each nonempty fiber is all that is used; no choice principle beyond the definition of a well-defined value is required, since the value assigned is independent of the representative.) Now for any $s\in S$ , put $t=p(s)$ ; then $s\in F_t$ , and by (5) together with representative-independence, $\bar a_Q(p(s))=a_Q(s)$ . Thus $a_Q=\bar a_Q\circ p$ .

Uniqueness. Suppose $\bar a_Q$ and $\bar a_Q'$ both satisfy (4). Let $t\in T$ and choose $s\in F_t$ , possible by surjectivity. Then $\bar a_Q(t)=\bar a_Q(p(s))=a_Q(s)=\bar a_Q'(p(s))=\bar a_Q'(t)$ . As $t$ was arbitrary, $\bar a_Q=\bar a_Q'$ . ◻

Theorem 3.1 is the fiber–descent theorem of [8] specialized to the correct-answer map, and we have given the argument in full so that the present paper stands on its own. What is new here is not the criterion but the object it is applied to: by taking the descending map to be the answer to a nominated question rather than an arbitrary source relation, the criterion becomes a statement about the adequacy of the readout for that question, and hence acquires the target-relativity that the rest of the paper develops.

The obstruction

Corollary 3.2 (Exact target obstruction).

Suppose there exist $s_0,s_1\in S$ with $p(s_0)=p(s_1) \qquad\text{and}\qquad a_Q(s_0)\neq a_Q(s_1).\tag{6}$ Then $Q$ is not exactly solvable from the readout. Explicitly, for every map $b\colon T\to A_Q$ there exists $i\in\{0,1\}$ with $b(p(s_i))\neq a_Q(s_i)$ : no deterministic readout-only construction is correct at both $s_0$ and $s_1$ .

Proof. Let $b\colon T\to A_Q$ be arbitrary and write $t:=p(s_0)=p(s_1)$ . The value $b(t)\in A_Q$ is a single element. If $b(t)=a_Q(s_0)$ then, since $a_Q(s_1)\neq a_Q(s_0)$ , we get $b(p(s_1))=b(t)=a_Q(s_0)\neq a_Q(s_1)$ , so $b$ errs at $s_1$ . If instead $b(t)\neq a_Q(s_0)$ then $b(p(s_0))\neq a_Q(s_0)$ and $b$ errs at $s_0$ . In either case $b$ fails at one of the two states. Since $b$ was arbitrary, no map $T\to A_Q$ satisfies $a_Q=b\circ p$ , which is the negation of Definition 2.3; this also follows from Theorem 3.1 (3), whose hypothesis is contradicted by (6). ◻

The structure of this argument deserves emphasis, because it is the pattern on which all the necessity results of this paper are built, and because it is easy to counterfeit. We did not assume that no readout-only construction exists and then declare completion necessary. We assumed only (6) , a fact about the pair $(p,a_Q)$ , checkable in examples, and verified concretely in Section 10 , and then derived the failure of every candidate $b$ by a counting argument: $b(t)$ is one element of $A_Q$ , while correctness at $s_0$ and $s_1$ demands two different elements. Impossibility follows from variation of the correct-answer map along a fiber, not from a stipulation of impossibility.

Proposition 3.3 (Every readout-only construction is fiber-constant).

Let $X$ be any set and let $g\colon S\to X$ be a map that factors through the readout, i.e. $g=h\circ p$ for some $h\colon T\to X$ . Then $g$ is constant on every fiber of $p$ . Conversely, every map $S\to X$ constant on all fibers of $p$ factors through $p$ , uniquely.

Proof. If $g=h\circ p$ and $s,s'\in F_t$ , then $g(s)=h(t)=g(s')$ . The converse and the uniqueness are Theorem 3.1 applied with $A_Q$ replaced by $X$ and $a_Q$ by $g$ . ◻

Proposition 3.4 (Auxiliary readout-computed variables cannot repair the obstruction).

Assume (6). Let $W$ be any set and let $w\colon S\to W$ be an auxiliary quantity that is computed from the readout alone, meaning $w=\omega\circ p$ for some $\omega\colon T\to W$ . Then for every map $c\colon T\times W\longrightarrow A_Q,$ the induced construction $s\mapsto c(p(s),w(s))$ fails to equal $a_Q$ at $s_0$ or at $s_1$ .

Proof. Define $b\colon T\to A_Q$ by $b(t):=c(t,\omega(t))$ . Then for every $s\in S$ , $c\bigl(p(s),w(s)\bigr)=c\bigl(p(s),\omega(p(s))\bigr)=b(p(s)),$ so the construction $s\mapsto c(p(s),w(s))$ is exactly $b\circ p$ and hence, by Proposition 3.3, constant on fibers. By Corollary 3.2 it errs at $s_0$ or at $s_1$ . ◻

Proposition 3.4 closes an escape route that is attempted surprisingly often. One cannot evade a fiber-variation obstruction by manufacturing additional quantities out of the readout , derived fields, filtered or smoothed versions of $t$ , spectral transforms of $t$ , statistics of $t$ , or any other post-processing. Whatever is computed from $t$ is a function of $t$ ; composing functions of $t$ leaves one with a function of $t$ ; and a function of $t$ is constant on $F_t$ while $a_Q$ is not. Genuine repair must inject information that is not a function of the readout. That is what Section 6 formalizes.