Proof. Let \[S:=\overline{\{a_j : j\in\mathbb{N}\}}.\] We first prove that \(\sigma(A)=S\). If \(\lambda\notin S\), then \[d_\lambda := \inf_{j\in\mathbb{N}}|a_j-\lambda|>0 .\] Define \(R_\lambda:\ell^2(\mathbb{N})\to\ell^2(\mathbb{N})\) by \[(R_\lambda y)_j=(a_j-\lambda)^{-1}y_j .\] Then \(R_\lambda\) is bounded and \[\|R_\lambda\|=\sup_{j\in\mathbb{N}}|a_j-\lambda|^{-1} = d_\lambda^{-1}.\] Moreover \(R_\lambda y\in \mathcal{D}(A)\), since \[a_j(a_j-\lambda)^{-1} = 1+\lambda(a_j-\lambda)^{-1}\] is uniformly bounded in \(j\). Hence \(R_\lambda=(A-\lambda I)^{-1}\), so \(\lambda\in\rho(A)\).

Conversely, let \(\lambda\in S\). If \(\lambda=a_j\) for some \(j\), then \(A-\lambda I\) has a non-trivial kernel, so \(\lambda\in\sigma(A)\). Otherwise there are indices \(j_n\) such that \(a_{j_n}\to\lambda\). Since \(\|e_{j_n}\|=1\) and \[\|(A-\lambda I)e_{j_n}\|=|a_{j_n}-\lambda|\to 0,\] the operator \(A-\lambda I\) cannot have a bounded inverse. Thus \(\lambda\in\sigma(A)\). This proves \[\sigma(A)=\overline{\{a_j : j\in\mathbb{N}\}}.\]

For \(w\in\rho(A)\), the preceding computation gives \[\|(A-wI)^{-1}\| = \frac{1}{\inf_{j\in\mathbb{N}}|a_j-w|} = \frac{1}{\operatorname{dist}(w,\sigma(A))}.\] Therefore the open resolvent-level pseudospectrum is \[\{w:\operatorname{dist}(w,\sigma(A))<\varepsilon\},\] and the closed CH23 convention gives \[\sigma_\varepsilon(A) = \{w:\operatorname{dist}(w,\sigma(A))\le \varepsilon\}.\] For \(K=\{z\}\), this is exactly \[z\in\sigma_\varepsilon(A) \quad\Longleftrightarrow\quad \inf_{j\in\mathbb{N}}|a_j-z|\le \varepsilon .\] ◻

Proof. The six problems in \(\mathcal{U}^{\sharp}_{2,J,\varepsilon}\) are the singleton-window restrictions of the CH23 decision problems \[\Xi_3(A,K)=1_{\{\sigma(A)\cap K=\varnothing\}}, \qquad \Xi_4(A,K)=1_{\{\sigma_\varepsilon(A)\cap K=\varnothing\}},\] on the diagonal, general \(\ell^2(\mathbb{N})\), and graph domains.

By [4] for \(j=3,4\) the corresponding compact-intersection decision problems on the diagonal, general, and graph domains satisfy the sharp classification \[\notin \Delta^G_2 \qquad\text{and}\qquad \in \Pi^A_2.\] The paragraph following [4] states that the lower bounds remain valid when the compact sets are restricted to a fixed compact subset of \(\mathbb{R}\), and by [4] the same classification remains valid for singleton compact sets \(K=\{z\}\).

By the conventions in [4], membership in \(\Delta^G_{m+1}\) means general type-\(G\) SCI at most \(m\). Hence \[\mathcal{P}\notin\Delta^G_2\] implies \[\operatorname{SCI}_G(\mathcal{P})>1.\] Thus every one of the six singleton-window problems has \[\operatorname{SCI}_G(\mathcal{P})\ge2.\]

On the other hand, the inclusion \(\mathcal{P}\in\Pi^A_2\) gives an arithmetic tower of height at most \(2\), hence in particular a general type-\(G\) tower of height at most \(2\), since arithmetic towers are special cases of general towers. Therefore \[\operatorname{SCI}_G(\mathcal{P})=2\] for every \[\mathcal{P}\in \mathcal{U}^{\sharp}_{2,J,\varepsilon}.\] ◻

Proof. We prove both raw finite-query reductions.

Fix once and for all \[x_0\in J\] and a singleton \[L:=\{x_0\}.\] Fix also a bijection \[\nu:\mathbb{N}\to\mathbb{N} \times\mathbb{N}_0, \qquad r\mapsto(p(r),j(r)).\] This identifies \[\ell^2(\mathbb{N}) \cong \ell^2(\mathbb{N} \times\mathbb{N}_0)\] by a fixed unitary relabeling.

Step 1: A raw transport from exact spectrum to fixed-\(\varepsilon\) pseudospectrum: Let \[(A,K)\in\Omega_{\mathrm{diag}}(J), \qquad K=\{z\}, \qquad Ae_j=a_je_j.\] Define a diagonal operator \[B=B(A,K)\] on \[\ell^2(\mathbb{N} \times\mathbb{N}_0)\] by \[Be_{p,j}=b_{p,j} e_{p,j},\] where \[b_{p,j} := x_0+\varepsilon+|a_j-r_{p+2}(K)|+\frac{1}{p}.\] Equivalently, after the fixed relabeling \(\nu\), \(B\) is a diagonal operator on \(\ell^2(\mathbb{N})\).

This \(B\) is the maximal diagonal operator with diagonal entries \(b_{p,j}\). Hence it is closed and densely defined. Therefore \[B\in\Omega_{\mathrm{diag}}.\] Define \[E_{\sigma\to\varepsilon}(A,K):=(B(A,K),L)\] and let the decoder be \[D=\operatorname{id}_{\{0,1\}}.\]

We prove the output identity. Put \[\delta:=\inf_j|a_j-z|.\] By 1, \[\Xi_\sigma(A,K)=0 \quad\Longleftrightarrow\quad \delta=0.\]

Assume first that \(\delta=0\). For each \(p\), choose \(j_p\) such that \[|a_{j_p}-z|<\frac{1}{p}.\] Since \[|r_{p+2}(K)-z|\le2^{-(p+3)},\] we have \[|a_{j_p}-r_{p+2}(K)| \le |a_{j_p}-z|+|z-r_{p+2}(K)| < \frac{1}{p}+2^{-(p+3)} \longrightarrow 0.\] Hence \[b_{p,j_p} \longrightarrow x_0+\varepsilon.\] Thus \[x_0+\varepsilon\in\sigma(B).\] Consequently \[\operatorname{dist}(x_0,\sigma(B))\le\varepsilon.\] Since \(B\) is diagonal normal, \[x_0\in\sigma_\varepsilon(B).\] Therefore \[\Xi_{\sigma_\varepsilon}(B,L)=0=\Xi_\sigma(A,K).\]

Assume next that \(\delta>0\). Choose \(p_0\) such that for every \(p\ge p_0\), \[|z-r_{p+2}(K)|<\frac{\delta}{2}.\] Then for \(p\ge p_0\) and every \(j\), \[|a_j-r_{p+2}(K)|\ge |a_j-z|-|z-r_{p+2}(K)| \ge \frac{\delta}{2}.\] Hence \[|b_{p,j}-x_0| = \varepsilon+|a_j-r_{p+2}(K)|+\frac{1}{p} \ge \varepsilon+\frac{\delta}{2}\] for \(p\ge p_0\). For the finitely many levels \(p<p_0\), \[|b_{p,j}-x_0| \ge \varepsilon+\frac{1}{p} \ge \varepsilon+\min_{1\le p<p_0}\frac{1}{p}\] if \(p_0>1\); if \(p_0=1\) there are no such levels. Thus there exists an \(\eta>0\), such that \[|b_{p,j}-x_0|\ge\varepsilon+\eta.\] Therefore \[\operatorname{dist}(x_0,\sigma(B))>\varepsilon,\] so \[x_0\notin\sigma_\varepsilon(B).\] Thus \[\Xi_{\sigma_\varepsilon}(B,L)=1=\Xi_\sigma(A,K).\]

We now verify finite-query reconstruction. A target diagonal coefficient at coordinate \(r\), with \[\nu(r)=(p,j),\] is \[b_{p,j} = x_0+\varepsilon+|\mu_j(A,K)-\rho_{p+2}(A,K)|+\frac{1}{p},\] so it is reconstructed from the finite transcript \[(\mu_j,\rho_{p+2})\] by the map \[(u,v)\mapsto x_0+\varepsilon+|u-v|+\frac{1}{p}.\] The compact-window approximants of \(L\) are fixed constants. Hence every target evaluation in the compressed diagonal interface is finitely reconstructed from source evaluations and \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}}.\]

Step 2: A raw transport from fixed-\(\varepsilon\) pseudospectrum to exact spectrum: Let again \[(A,K)\in\Omega_{\mathrm{diag}}(J), \qquad K=\{z\}, \qquad Ae_j=a_je_j.\] Define a diagonal operator \[C=C(A,K)\] by \[Ce_{p,j}=c_{p,j}e_{p,j},\] where \[c_{p,j} := x_0+\max\{0,|a_j-r_{p+2}(K)|-\varepsilon\}+\frac{1}{p}.\] As above, \(C\) is a maximal closed diagonal operator. Hence \[C\in\Omega_{\mathrm{diag}}.\] Define \[E_{\varepsilon\to\sigma}(A,K) := (C(A,K),L),\] and again take \[D=\operatorname{id}_{\{0,1\}}.\]

Put \[\delta:=\inf_j|a_j-z|.\] By 1, \[\Xi_{\sigma_\varepsilon}(A,K)=0 \quad\Longleftrightarrow\quad \delta\le\varepsilon.\]

Assume first that \(\delta\le\varepsilon\). For every \(p\), choose \(j_p\) such that \[|a_{j_p}-z|<\varepsilon+\frac{1}{p}.\] Then \[|a_{j_p}-r_{p+2}(K)|-\varepsilon \le |a_{j_p}-z|+|z-r_{p+2}(K)|-\varepsilon < \frac{1}{p}+2^{-(p+3)}.\] Therefore \[0\le \max\{0,|a_{j_p}-r_{p+2}(K)|-\varepsilon\} < \frac{1}{p}+2^{-(p+3)}.\] Hence \[c_{p,j_p}\longrightarrow x_0.\] Thus \[x_0\in\sigma(C),\] and consequently \[\Xi_\sigma(C,L)=0=\Xi_{\sigma_\varepsilon}(A,K).\]

Assume next that \(\delta>\varepsilon\). Choose \(p_0\) such that for all \(p\ge p_0\), \[|z-r_{p+2}(K)|<\frac{\delta-\varepsilon}{2}.\] Then for \(p\ge p_0\) and every \(j\), \[|a_j-r_{p+2}(K)|-\varepsilon \ge |a_j-z|-|z-r_{p+2}(K)|-\varepsilon \ge \frac{\delta-\varepsilon}{2}.\] Hence \[|c_{p,j}-x_0| \ge \frac{\delta-\varepsilon}{2}\] for \(p\ge p_0\). For the finitely many levels \(p<p_0\), \[|c_{p,j}-x_0|\ge \frac{1}{p}.\] Thus there is \(\eta>0\) such that \[|c_{p,j}-x_0|\ge\eta.\] Therefore \[x_0\notin\sigma(C),\] so \[\Xi_\sigma(C,L)=1=\Xi_{\sigma_\varepsilon}(A,K).\]

The finite-query reconstruction is again explicit. A target diagonal coefficient at coordinate \(r\), with \(\nu(r)=(p,j)\), is \[c_{p,j} = x_0+\max\{0,|\mu_j(A,K)-\rho_{p+2}(A,K)|-\varepsilon\}+\frac{1}{p}.\] It is reconstructed from \[(\mu_j,\rho_{p+2})\] by the map \[(u,v)\mapsto x_0+\max\{0,|u-v|-\varepsilon\}+\frac{1}{p}.\] The compact-window target evaluations are the fixed approximants of \(L\). Hence every target evaluation in the compressed diagonal interface is finitely reconstructed from source evaluations and \[\mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}} \le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^\sigma_{J,\mathrm{diag}}.\]

Combining the two reductions gives \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \equiv_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}}.\] ◻

Proof. We prove the spectral statements; the pseudospectral statements are identical, using unitary invariance of the \(\varepsilon\)-pseudospectrum.

For diagonal-to-general, use the encoding \[E(A,K):=(A,K),\] where the same diagonal operator is viewed as an element of the CH23 general \(\ell^2(\mathbb{N})\)-operator class. The decoder is \[D=\operatorname{id}_{\{0,1\}}.\] The target identity holds because the underlying operator and compact input are unchanged, i.e. \[\sigma(E(A,K))=\sigma(A).\] A target matrix-entry evaluation satisfies \[\langle Ae_j,e_i\rangle = \begin{cases} \mu_j(A,K),&i=j,\\ 0,&i\neq j. \end{cases}\] Thus each matrix entry is reconstructed from either one diagonal source evaluation or a constant. Compact-window approximants are passed through unchanged. For diagonal operators, the bounded-dispersion auxiliary data can be chosen canonically, for instance with \[f(n)=n, \qquad c_n=2^{-n},\] because \[(I-P_n)AP_n=0, \qquad (I-P_n)A^*P_n=0.\] These auxiliary target evaluations are therefore reconstructed by constants. Hence \[\mathcal{P}^\sigma_{J,\mathrm{diag}}\le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^\sigma_{J,\mathrm{gen}}.\]

For diagonal-to-graph, fix a connected countable graph \[\mathcal{G}=(V,E_{\mathcal{G}}), \qquad V=\{v_1,v_2,\ldots\},\] and the unitary \[U:\ell^2(\mathbb{N})\to\ell^2(V), \qquad Ue_j=\mathbf{1}_{v_j}.\] Encode then \[E(A,K):=(UAU^{-1},K).\] If \[Ae_j=a_je_j,\] then \[UAU^{-1}\mathbf{1}_{v_j}=a_j\mathbf{1}_{v_j}.\] Thus the graph coefficient is \[\alpha(v_i,v_j) = \begin{cases} a_j,&i=j,\\ 0,&i\neq j. \end{cases}\] Local support sets may be chosen as \[S_{v_j}:=\{v_j\}.\] Therefore all graph coefficient and local-support evaluations are reconstructed from diagonal source evaluations and constants. Compact-window approximants are unchanged. The target identity follows from \[\sigma(UAU^{-1})=\sigma(A).\] Hence \[\mathcal{P}^\sigma_{J,\mathrm{diag}}\le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^\sigma_{J,\mathrm{graph}}.\] For the fixed-\(\varepsilon\) pseudospectral block, the same encodings work because \[\sigma_\varepsilon(UAU^{-1}) = \sigma_\varepsilon(A),\] and because representation inclusion does not change the operator. This proves the two pseudospectral reductions. ◻

Proof. By 1, every member of \(\mathcal{U}^\sharp_{2,J,\varepsilon}\) has exact raw height \(2\). By 2, \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \equiv_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}}.\] By 2, \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^\sigma_{J,\mathrm{gen}}, \qquad \mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^\sigma_{J,\mathrm{graph}},\] and \[\mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}} \le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{gen}}, \qquad \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}} \le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{graph}}.\] Using \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \equiv_{\mathrm{raw},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}},\] we conclude that \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{raw},\mathrm{fq}} \mathcal{P}\] for \(\mathcal{P}\in \mathcal{U}^\sharp_{2,J,\varepsilon}\). Now let \[[\mathcal{Q}]_{\mathrm{raw}} \in D^{\mathrm{raw}}_2(\mathcal{U}^\sharp_{2,J,\varepsilon})\] be raw-minimal. Since \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{raw},\mathrm{fq}} \mathcal{Q},\] we have \[[\mathcal{P}^\sigma_{J,\mathrm{diag}}]_{\mathrm{raw}} \preceq [\mathcal{Q}]_{\mathrm{raw}}.\] By minimality of \([\mathcal{Q}]_{\mathrm{raw}}\), this forces \[[\mathcal{Q}]_{\mathrm{raw}} = [\mathcal{P}^\sigma_{J,\mathrm{diag}}]_{\mathrm{raw}}.\] Hence \[\operatorname{MinDeg}^{\mathrm{raw}}_2(\mathcal{U}^\sharp_{2,J,\varepsilon}) = \{[\mathcal{P}^\sigma_{J,\mathrm{diag}}]_{\mathrm{raw}}\}.\] The equality \[[\mathcal{P}^\sigma_{J,\mathrm{diag}}]_{\mathrm{raw}} = [\mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}}]_{\mathrm{raw}}\] follows directly from 2. ◻

Proof. We prove reflexivity and transitivity separately.

Reflexivity: Let \[\mathbf{P}=(\Xi_P,\Omega_P,Y_P,\Lambda_P)\] be a typed SCI problem. By (A1), \[\operatorname{id}_{\Omega_P}\in\mathcal{E}_{\mathfrak m}(\mathbf{P}, \mathbf{P}),\qquad \operatorname{id}_{Y_P}\in\mathcal{D}_{\mathfrak m}(\mathbf{P}, \mathbf{P}).\] For every \(\lambda\in\Lambda_P\), use the one-entry source transcript \((\lambda)\) and the reconstruction \[\vartheta_\lambda(t):=t.\] Again by (A1), this reconstruction is \(\mathfrak m\)-admissible. For every \(x\in\Omega_P\), \[\operatorname{id}_{Y_P}(\Xi_P(\operatorname{id}_{\Omega_P}(x))) = \Xi_P(x),\] and \[\lambda(\operatorname{id}_{\Omega_P}(x)) = \vartheta_\lambda(\lambda(x)).\] Hence \[\mathbf{P}\le_{\mathfrak m,\mathrm{fq}} \mathbf{P}.\]

Transitivity: Assume \[\mathbf{S}\le_{\mathfrak m,\mathrm{fq}} \mathbf{P} \qquad\text{and}\qquad \mathbf{P}\le_{\mathfrak m,\mathrm{fq}} \mathbf{Q}.\] Let the first transport be witnessed by \[E_{S,P}:\Omega_S\to\Omega_P, \qquad D_{P,S}:Y_P\to Y_S,\] and by reconstruction data for the evaluations of \(\mathbf{P}\). Let the second transport be witnessed by \[E_{P,Q}:\Omega_P\to\Omega_Q, \qquad D_{Q,P}:Y_Q\to Y_P,\] and by reconstruction data for the evaluations of \(\mathbf{Q}\).

Define \[E_{S,Q}:=E_{P,Q}\circ E_{S,P}, \qquad D_{Q,S}:=D_{P,S}\circ D_{Q,P}.\] By (A2), \[E_{S,Q}\in\mathcal{E}_{\mathfrak m}(\mathbf{S}, \mathbf{Q}), \qquad D_{Q,S}\in\mathcal{D}_{\mathfrak m}(\mathbf{Q}, \mathbf{S}).\] For \(x\in\Omega_S\), the output identity is \[\begin{align} D_{Q,S}\bigl(\Xi_Q(E_{S,Q}(x))\bigr) &= D_{P,S} \Bigl( D_{Q,P} \bigl( \Xi_Q(E_{P,Q}(E_{S,P}(x))) \bigr) \Bigr) \\ &= D_{P,S} \bigl( \Xi_P(E_{S,P}(x)) \bigr) \\ &= \Xi_S(x). \end{align}\]

It remains to construct the finite reconstruction data. Fix \[\lambda\in\Lambda_Q.\] The second transport supplies a finite \(\mathbf{P}\)-transcript \[\vec{\beta}_\lambda=(\beta_1,\ldots,\beta_r), \qquad \beta_i\in\Lambda_P,\] and a reconstruction \[\varphi_\lambda\in\Theta_{\mathfrak m}(\lambda;\vec{\beta}_\lambda)\] such that, for every \(y\in\Omega_P\), \[\lambda(E_{P,Q}(y)) = \varphi_\lambda(\beta_1(y),\ldots,\beta_r(y)).\] For each \(i\), the first transport supplies a finite \(\mathbf{S}\)-transcript \[\vec{\gamma}_i=(\gamma_{i,1},\ldots,\gamma_{i,m_i})\] and a reconstruction \[\psi_i\in\Theta_{\mathfrak m}(\beta_i;\vec{\gamma}_i)\] such that, for every \(x\in\Omega_S\), \[\beta_i(E_{S,P}(x)) = \psi_i(\gamma_{i,1}(x),\ldots,\gamma_{i,m_i}(x)).\] Let \(\vec{\gamma}\) be the concatenation of all \(\vec{\gamma}_i\), and define \(\theta_\lambda\) from \(\vec{\gamma}\) by the substitution formula in (A3). By (A3), \[\theta_\lambda\in\Theta_{\mathfrak m}(\lambda;\vec{\gamma}).\] More further, for every \(x\in\Omega_S\), \[\begin{align} \lambda(E_{S,Q}(x)) &= \lambda(E_{P,Q}(E_{S,P}(x)))\\ &= \varphi_\lambda \bigl( \beta_1(E_{S,P}(x)),\ldots,\beta_r(E_{S,P}(x)) \bigr)\\ &= \theta_\lambda(\vec{\gamma}(x)). \end{align}\] Thus every \(\mathbf{Q}\)-evaluation is finitely reconstructed from \(\mathbf{S}\)-evaluations by \(\mathfrak m\)-admissible data. Hence \[\mathbf{S}\le_{\mathfrak m,\mathrm{fq}} \mathbf{Q}.\] ◻

Proof. Assume first that \(\mathbf{S} \leq_{\mathrm{TTE},\mathrm{fq}} \mathbf{P}\). By definition of the TTE finite-query modality, the transport is witnessed by a computably realized encoding \[E:\Omega_S\to\Omega_P,\] a computably realized decoder \[D:Y_P\to Y_S,\] and, uniformly in an index \(e\) for each target evaluation \(\lambda_e\in\Lambda_P\), a finite list of source evaluations \[\gamma_{i(e,1)},\ldots,\gamma_{i(e,m_e)}\] together with an index for a computable partial reconstruction map \[\widehat{\vartheta}_e: \subseteq V^S_{i(e,1)}\times\cdots\times V^S_{i(e,m_e)} \to V^P_e\] such that \[\lambda_e(E(x)) = \widehat{\vartheta}_e \bigl( \gamma_{i(e,1)}(x),\ldots,\gamma_{i(e,m_e)}(x) \bigr)\] for all \(x\in\Omega_S\). This is exactly a uniform finite \(\Lambda_P\)-trace through \(\Lambda_S\). The output identity in the definition of \(\mathbf{S} \leq_{\mathrm{TTE},\mathrm{fq}} \mathbf{P}\) is precisely \[D(\Xi(E(x)))=\Psi(x).\] Hence (ii) holds.

Conversely, assume (ii). The computable maps \(E\) and \(D\) supply the TTE-admissible encoding and decoder. The uniform finite trace supplies, uniformly in every target evaluation index \(e\), the finite source transcript and computable partial reconstruction map required in the definition of \(\leq_{\mathrm{TTE},\mathrm{fq}}\). The output identity gives the target identity condition. Therefore \[\mathbf{S}\leq_{\mathrm{TTE},\mathrm{fq}} \mathbf{P}.\]

It remains only to verify the Weihrauch statement. Let \(p\) be a name of \(x\in\Omega_S\). Since \(\Phi_E\) realizes \(E\), the name \(\Phi_E(p)\) is a name of \(E(x)\). If \(G\vdash\widehat{\Xi}\), then \(G(\Phi_E(p))\) is a name of \(\Xi(E(x))\). Since \(\Phi_D\) realizes \(D\), the value \[\Phi_D(G(\Phi_E(p)))\] is a name of \[D(\Xi(E(x)))=\Psi(x).\] Thus \(\Phi_D\circ G\circ \Phi_E\) realizes \(\widehat{\Psi}\). The postprocessor \(\Phi_D\) does not use the original source name \(p\), so the reduction is strong Weihrauch reducibility. ◻

Proof. Let \[\mathcal{C}:=\{0,1\}^{\mathbb{N}_0}\] be the Cantor space with its standard representation. For \(n\in\mathbb{N}_0\), let \[\pi_n:\mathcal{C}\to\{0,1\}, \qquad \pi_n(x):=x(n),\] be the coordinate projections. Define also the computable injective map \[\tau:\mathcal{C}\to[0,1], \qquad \tau(x):=\sum_{n=0}^{\infty} \frac{2x(n)}{3^{n+1}}.\] The map \(\tau\) is injective: if \(x\neq y\) and \(n_0\) is the least index with \(x(n_0)\neq y(n_0)\), then \[|\tau(x)-\tau(y)| \geq \frac{2}{3^{n_0+1}} - \sum_{n>n_0}\frac{2}{3^{n+1}} = \frac{1}{3^{n_0+1}} >0.\]

Define the two represented typed SCI problems \[\mathbf{S} := \bigl( \operatorname{id}_{\mathcal{C}}, \mathcal{C}, \mathcal{C}, \{\pi_n : n\in\mathbb{N}_0\} \bigr)\] and \[\mathbf{P} := \bigl( \operatorname{id}_{\mathcal{C}}, \mathcal{C}, \mathcal{C}, \{\pi_n : n\in\mathbb{N}_0\}\cup\{\tau\} \bigr).\] The value space of each \(\pi_n\) is the discrete represented space \(\{0,1\}\), and the value space of \(\tau\) is \([0,1]\) with its usual Cauchy representation.

After forgetting the SCI interfaces, both represented target maps are just \[\operatorname{id}_{\mathcal{C}} : \mathcal{C}\to\mathcal{C}.\] Hence \[\widehat{\Psi}\equiv_{\mathrm{sW}} \widehat{\Xi}\] is witnessed in both directions by the identity preprocessor and identity postprocessor.

We now show that nevertheless \[\mathbf{S} \nleq_{\mathrm{raw},\mathrm{fq}} \mathbf{P}.\] Suppose, toward a contradiction, that there is a raw finite-query transport from \(\mathbf{S}\) to \(\mathbf{P}\). Let \[E:\mathcal{C}\to\mathcal{C}, \qquad D:\mathcal{C}\to\mathcal{C}\] be its encoding and decoder. Since the two target maps are identities, the output identity of the transport says \[D(E(x))=x,\] where \(x\in\mathcal{C}\). In particular, \(E\) is injective.

Now apply the finite-query reconstruction requirement to the target evaluation \[\tau\in\Lambda_P.\] There must be finitely many source evaluations \[\pi_{n_1},\ldots,\pi_{n_m}\] and a reconstruction map \[\vartheta: \operatorname{im}(\pi_{n_1},\ldots,\pi_{n_m}) \to[0,1]\] such that for every \(x\in\mathcal{C}\), \[\tau(E(x)) = \vartheta(x(n_1),\ldots,x(n_m)).\] Choose distinct \(x,x'\in\mathcal{C}\) such that \[x(n_j)=x'(n_j)\] for \(j=1,\ldots,m\). Then the preceding identity gives \[\tau(E(x))=\tau(E(x')).\] Since \(\tau\) is injective, this implies \[E(x)=E(x').\] Applying \(D\) and using \(D\circ E=\operatorname{id}_{\mathcal{C}}\), we get \[x=D(E(x))=D(E(x'))=x',\] contradicting the choice of \(x\neq x'\). Hence no raw finite-query transport exists. Since every TTE finite-query transport is, in particular, a raw finite-query transport after forgetting effectivity, \[\mathbf{S} \nleq_{\mathrm{TTE},\mathrm{fq}} \mathbf{P}.\] ◻

Proof. We verify the three conditions of 16.

The raw modality: For \(\mathrm{raw}\), every encoding is admissible, every finite transcript reconstruction is admissible, and the decoder class is the class of continuous maps between output metric spaces. Identity encodings and identity reconstructions are therefore admissible. The identity decoder is continuous, and compositions of continuous decoders are continuous. Since all reconstruction maps are allowed, the composite reconstruction in (A3) is automatically raw-admissible. Hence \(\mathrm{raw}\) is admissible.

The continuous modality: For \(\mathrm{cont}\), identity encodings, decoders, and transcript reconstructions are continuous. Compositions of continuous encodings and decoders are continuous. For reconstructions suppose \[\varphi:\operatorname{im}(\vec{\beta})\to V_\lambda\] is continuous and each \[\psi_i:\operatorname{im}(\vec{\gamma}_i)\to V_{\beta_i}\] is continuous. The product map \[\Psi: \operatorname{im}(\vec{\gamma}) \to \operatorname{im}(\vec{\beta})\] defined by \[\Psi(t_{1,1},\ldots,t_{r,m_r}) := (\psi_1(t_{1,1},\ldots,t_{1,m_1}),\ldots, \psi_r(t_{r,1},\ldots,t_{r,m_r}))\] is continuous for the subspace product topologies. Hence \[\theta:=\varphi\circ\Psi\] is continuous. Thus \(\mathrm{cont}\) is admissible.

The Borel-with-continuous-decoder modality: For \(\mathrm{Bor}_{E,\vartheta;D=\mathrm{cont}}\), identity encodings and identity reconstructions are Borel, and identity decoders are continuous. Compositions of Borel encodings are Borel, and compositions of continuous decoders are continuous.

For transcript reconstructions, use the trace measurable structure from 19. If \[\varphi:\operatorname{im}(\vec{\beta})\to V_\lambda\] is Borel and each \[\psi_i:\operatorname{im}(\vec{\gamma}_i)\to V_{\beta_i}\] is Borel, then the product map \[\Psi: \operatorname{im}(\vec{\gamma}) \to \operatorname{im}(\vec{\beta})\] defined as in the \(\mathrm{cont}\) case is measurable with respect to the trace sigma algebras. Indeed, for each coordinate projection \(\pi_i\) on \[V_{\beta_1}\times\cdots\times V_{\beta_r},\] the coordinate map \[\pi_i\circ\Psi=\psi_i\circ\pi_{\vec{\gamma}_i}\] is measurable. Since the product sigma algebra is generated by coordinate cylinders, \(\Psi\) is measurable. Hence \[\theta=\varphi\circ\Psi\] is Borel. Thus \(\mathrm{Bor}_{E,\vartheta;D=\mathrm{cont}}\) is admissible.

The decoder-only Borel modality: For \(\mathrm{Bor}_D\), encodings and transcript reconstructions are unrestricted. The decoder class consists of Borel maps. Identity maps are Borel, and compositions of Borel maps are Borel. Since reconstructions are unrestricted, the composite reconstruction is automatically admissible. Hence \(\mathrm{Bor}_D\) is admissible.

The full Borel modality: For \(\mathrm{Bor}_{\mathrm{full}}\), encodings, decoders, and transcript reconstructions are all Borel. Identity maps are Borel and compositions of Borel maps are Borel. The transcript part is handled exactly as in the \(\mathrm{Bor}_{E,\vartheta;D=\mathrm{cont}}\) case. Hence \(\mathrm{Bor}_{\mathrm{full}}\) is admissible.

The TTE modality: For \(\mathrm{TTE}\), identity maps on represented spaces have computable realizers, and compositions of computably realized maps have computable realizers. Hence identity and composition closure hold for encodings and decoders.

For reconstructions, suppose a target evaluation \(\lambda\) of \(\mathbf{Q}\) is uniformly reconstructed from \(\mathbf{P}\)-evaluations \[\beta_1,\ldots,\beta_r\] by a computable partial map \(\widehat\varphi\). Suppose each \(\beta_i\) is uniformly reconstructed from \(\mathbf{S}\)-evaluations \[\gamma_{i,1},\ldots,\gamma_{i,m_i}\] by a computable partial map \(\widehat\psi_i\). From an index for \(\lambda\), the TTE data compute the list of \(\beta_i\)’s and an index for \(\widehat\varphi\). From each index for \(\beta_i\), the TTE data compute the list of \(\gamma_{i,j}\)’s and an index for \(\widehat\psi_i\). By effective pairing, finite list concatenation, and effective composition of partial computable maps on represented spaces, one computes uniformly an index for \[\widehat\theta := \widehat\varphi\circ (\widehat\psi_1,\ldots,\widehat\psi_r).\] Its domain contains the relevant transcript image, and on that image it gives the required composite reconstruction. Therefore the TTE modality is admissible.

Representation-preserving and geometric refinements: Let \(\mathfrak a\) be one of the admissible base modalities. By assumption, the representation-preserving encoding classes \(\mathcal{R}(\mathbf{S}, \mathbf{P})\) contain identities and are closed under composition; the same holds for the geometric classes \(\mathcal{G}(\mathbf{S}, \mathbf{P})\). Therefore intersecting the encoding class of \(\mathfrak a\) with \(\mathcal{R}\) or with \(\mathcal{G}\) preserves identity and composition closure. The decoder and reconstruction classes are inherited from \(\mathfrak a\), already shown admissible. Hence \(\mathrm{rep}^{\mathfrak a}\) and \(\mathrm{geom}^{\mathfrak a}\) are admissible. ◻

Proof. (a) A TTE transport has computably realized \(E\), \(D\), and uniformly computable \(\vartheta_\lambda\). By the standing assumption on the represented spaces, computably realized maps are continuous. Hence every TTE transport is a continuous transport, i.e. \[\mathrm{TTE}\preceq\mathrm{cont}.\] Every continuous map between standard topological measurable spaces is Borel. Therefore a continuous encoding and continuous transcript reconstruction are also Borel, while the decoder remains continuous. Thus \[\mathrm{cont}\preceq\mathrm{Bor}_{E,\vartheta;D=\mathrm{cont}}.\] Finally, \(\mathrm{Bor}_{E,\vartheta;D=\mathrm{cont}}\) restricts \(E\) and \(\vartheta\) but still has continuous decoder \(D\). Since the raw modality allows all encodings and all transcript reconstructions with continuous decoder, every \(\mathrm{Bor}_{E,\vartheta;D=\mathrm{cont}}\)-transport is raw, i.e. \[\mathrm{Bor}_{E,\vartheta;D=\mathrm{cont}}\preceq\mathrm{raw}.\]

(b) A raw transport has continuous decoder. Every continuous map is Borel, and \(\mathrm{Bor}_{D}\) imposes no restriction on encodings or transcript reconstructions. Hence every raw transport is a decoder-only Borel transport, i.e. \[\mathrm{raw}\preceq\mathrm{Bor}_{D}.\]

(c) By definition, \[\mathcal{R}(\mathbf{S}, \mathbf{P}) \subseteq \mathcal{G}(\mathbf{S}, \mathbf{P}).\] Therefore every representation-preserving encoding is geometric. Also every geometric encoding admitted by the \(\mathfrak a\)-refinement is, in particular, an \(\mathfrak a\)-admissible encoding. The decoder and reconstruction components are the same as in \(\mathfrak a\). Hence \[\mathrm{rep}^{\mathfrak a} \preceq \mathrm{geom}^{\mathfrak a} \preceq \mathfrak a .\] The chains follow by substituting \[\mathfrak a=\mathrm{TTE},\mathrm{cont},\mathrm{raw}\] and using part (a).

(d) The full Borel modality is not automatically below \(\mathrm{raw}\), because it allows Borel decoders that are not continuous. Here is a concrete witness. Let \[h:\mathbb{R}\to\{0,1\}, \qquad h(x) := \begin{cases} 0,&x\le 0,\\ 1,&x>0. \end{cases}\] Let \[\mathcal{S}_h := (h,\mathbb{R},\{0,1\},\{\operatorname{id}_{\mathbb{R}}\})\] and \[\mathcal{P}_{\mathbb{R}}:=(\operatorname{id}_{\mathbb{R}},\mathbb{R},\mathbb{R}, \{\operatorname{id}_{\mathbb{R}}\}).\] Then \[\mathcal{S}_h \le_{\mathrm{Bor}_{\mathrm{full}},\mathrm{fq}} \mathcal{P}_{\mathbb{R}}\] via \[E=\operatorname{id}_{\mathbb{R}}, \qquad D=h,\] since \(h\) is Borel. But \[\mathcal{S}_h \not{\le}_{\mathrm{raw},\mathrm{fq}} \mathcal{P}_{\mathbb{R}}.\] Indeed, any raw transport would require a continuous decoder \[D:\mathbb{R}\to\{0,1\}\] such that \[D(E(x))=h(x).\] Because \(\mathbb{R}\) is connected and \(\{0,1\}\) is discrete, every continuous \(D:\mathbb{R}\to\{0,1\}\) is constant. Hence \(D(E(x))\) is constant, contradicting the nonconstancy of \(h\).

Conversely, \(\mathrm{raw}\) is not automatically below \(\mathrm{Bor}_{\mathrm{full}}\), because \(\mathrm{raw}\) allows non-Borel encodings and non-Borel transcript reconstructions. Let \[A\subseteq[0,1]\] be non-Borel and nontrivial, and let \[\chi_A:[0,1]\to\{0,1\}\] be its characteristic function. Define \[\mathcal{S}_A := (\chi_A,[0,1],\{0,1\},\{\operatorname{id}_{[0,1]}\})\] and let \[\mathcal{B} := (\operatorname{id}_{\{0,1\}},\{0,1\},\{0,1\}, \{\operatorname{id}_{\{0,1\}}\})\] be the bit problem. Then \[\mathcal{S}_A \le_{\mathrm{raw},\mathrm{fq}} \mathcal{B}\] via the set-theoretic encoding \[E(x)=\chi_A(x)\] and the identity decoder. If \[\mathcal{S}_A \le_{\mathrm{Bor}_{\mathrm{full}},\mathrm{fq}} \mathcal{B}\] held, then there would be a Borel encoding \[E:[0,1]\to\{0,1\}\] and a Borel decoder \[D:\{0,1\}\to\{0,1\}\] with \[D(E(x))=\chi_A(x).\] But then \[A=(D\circ E)^{-1}(\{1\})\] would be Borel, a contradiction. Thus there is no general modality order between \(\mathrm{Bor}_{\mathrm{full}}\) and \(\mathrm{raw}\). ◻

Proof. We first prove computability. Let \(p\) be an evaluation-name of \(x\in\Omega_S\). To compute an evaluation-name of \(E(x)\), a TTE machine receives an index for a target evaluation \(\lambda\in\Lambda_P\). By hypothesis, uniformly from this index it computes indices for \[\gamma_{\lambda,1},\ldots,\gamma_{\lambda,m_\lambda}\] and an index for a computable partial realizer of \(\widehat\vartheta_\lambda\).Using the source name \(p\), it computes names of the source evaluation values \[\gamma_{\lambda,1}(x),\ldots,\gamma_{\lambda,m_\lambda}(x).\] It then applies the computable realizer for \(\widehat\vartheta_\lambda\). The result is a name of \(\lambda(E(x))\). This procedure is uniform in \(\lambda\), hence computes an evaluation-name of \(E(x)\). Thus \(E\) has a computable realizer.

For continuity, recall that the target instance space carries the initial topology with respect to the evaluations in \(\Lambda_P\). Hence \(E\) is continuous if and only if \[\lambda\circ E:\Omega_S\to V_\lambda\] is continuous for every \(\lambda\in\Lambda_P\). But \[\lambda(E(x)) = \widehat\vartheta_\lambda \bigl( \gamma_{\lambda,1}(x),\ldots,\gamma_{\lambda,m_\lambda}(x) \bigr),\] where each \(\gamma_{\lambda,i}\) is continuous by definition of the source initial topology and \(\widehat\vartheta_\lambda\) is continuous by assumption. Therefore \(\lambda\circ E\) is continuous for every \(\lambda\), and hence \(E\) is continuous. ◻

Proof. We use the two encodings from 2. We verify that they are continuous and that their finite transcript reconstructions are continuous.

First consider the encoding \[E_{\sigma\to\varepsilon}(A,K)=(B(A,K),L), \qquad L=\{x_0\},\] where, writing \[K=\{z\}, \qquad Ae_j=a_j e_j,\] the diagonal entries of \(B(A,K)\) are indexed by pairs \[(p,j)\in\mathbb{N} \times\mathbb{N}_0\] and given by \[b_{p,j} = x_0+\varepsilon+|a_j-r_{p+2}(K)|+\frac{1}{p} .\] Fix once and for all a bijection \[\nu:\mathbb{N}\to\mathbb{N} \times\mathbb{N}_0, \qquad r\mapsto(p(r),j(r)).\] Thus \(B(A,K)\) is regarded as a diagonal operator on \(\ell^2(\mathbb{N})\) after this fixed relabeling.

Let \(\lambda\) be a target evaluation for the pseudospectral diagonal problem. If \(\lambda\) is a diagonal coefficient query at coordinate \(r\), then \[\nu(r)=(p,j)\] and \[\lambda(E_{\sigma\to\varepsilon}(A,K)) = b_{p,j} = x_0+\varepsilon+|\mu_j(A,K)-\rho_{p+2}(A,K)|+\frac{1}{p} .\] This is the composition of the finite source transcript \[(\mu_j,\rho_{p+2})\] with the continuous map \[(u,v)\longmapsto x_0+\varepsilon+|u-v|+\frac{1}{p} .\] If \(\lambda\) is an off-diagonal matrix-entry query, then \[\lambda(E_{\sigma\to\varepsilon}(A,K))=0,\] which is a constant continuous reconstruction. If \(\lambda\) is a compact-window approximant query, then \[\lambda(E_{\sigma\to\varepsilon}(A,K))\] is the fixed approximant to \(L=\{x_0\}\), again a constant continuous reconstruction. Thus every target evaluation in the compressed diagonal interface after \(E_{\sigma\to\varepsilon}\) is a continuous finite-transcript function of source evaluations.

By 3, the encoding \(E_{\sigma\to\varepsilon}\) is continuous. The decoder is the identity map on \(\{0,1\}\), hence continuous. The output identity was proved in 2. Therefore \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{cont},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}}.\]

For the reverse direction, use the encoding \[E_{\varepsilon\to\sigma}(A,K)=(C(A,K),L),\] where \[C(A,K)e_{p,j}=c_{p,j}e_{p,j},\] and \[c_{p,j} = x_0+\max\{0,|a_j-r_{p+2}(K)|-\varepsilon\}+\frac{1}{p} .\] A target diagonal coefficient at coordinate \(r\), with \(\nu(r)=(p,j)\), is \[c_{p,j} = x_0+ \max\{0,|\mu_j(A,K)-\rho_{p+2}(A,K)|-\varepsilon\} +\frac{1}{p} ,\] which is obtained from the finite transcript \[(\mu_j,\rho_{p+2})\] by the continuous map \[(u,v)\longmapsto x_0+\max\{0,|u-v|-\varepsilon\}+\frac{1}{p} .\] The compact-window approximant queries are constant, as above. Thus every target evaluation in the compressed diagonal interface after \(E_{\varepsilon\to\sigma}\) is a continuous finite-transcript function of source evaluations. Therefore \(E_{\varepsilon\to\sigma}\) is continuous. The decoder is again the identity, and the output identity was proved in 2. Hence \[\mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}} \le_{\mathrm{cont},\mathrm{fq}} \mathcal{P}^\sigma_{J,\mathrm{diag}}.\] Combining the two reductions proves the continuous equivalence. ◻

Proof. We prove that the two collapse transports from 2 satisfy the TTE finite-query requirements.

For the first encoding \[E_{\sigma\to\varepsilon}(A,K)=(B(A,K),L),\] a target diagonal coefficient query at coordinate \(r\), with \[\nu(r)=(p,j),\] is computed from the source evaluations \[\mu_j(A,K)=a_j, \qquad \rho_{p+2}(A,K)=r_{p+2}(K)\] by \[(u,v) \longmapsto x_0+\varepsilon+|u-v|+\frac{1}{p} .\] This map is computable on standard representations of complex numbers and reals, since addition, subtraction, complex modulus, and addition of the computable constants \(x_0,\, \varepsilon, \, 1/p\) are computable operations. The finite source transcript \[(\mu_j,\rho_{p+2})\] is computable uniformly from \(r\), because \(\nu\) is a fixed computable bijection.

The target compact-window approximants for \(L=\{x_0\}\) are computable uniformly in the query index by the assumption on the fixed approximant sequence for \(L\).

Thus the hypotheses of 3 hold effectively and uniformly for \(E_{\sigma\to\varepsilon}\). Hence \(E_{\sigma\to\varepsilon}\) has a computable realizer. The decoder is the identity on the discrete represented space \(\{0,1\}\), hence computable. The output identity is the one already proved in 2. Therefore \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{TTE},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}}.\]

For the reverse encoding \[E_{\varepsilon\to\sigma}(A,K)=(C(A,K),L),\] a target diagonal coefficient query at coordinate \(r\), with \[\nu(r)=(p,j),\] is computed from the same finite transcript \[(\mu_j,\rho_{p+2})\] by \[(u,v) \longmapsto x_0+\max\{0,|u-v|-\varepsilon\}+\frac{1}{p} .\] This map is computable because \[(s,t)\mapsto \max\{s,t\}\] is computable on represented real numbers, and the remaining operations are computable. Again the transcript is computable uniformly from \(r\), and all compact-input target queries are computable constant reconstructions.

Hence \(E_{\varepsilon\to\sigma}\) has a computable realizer, the decoder is computable, and the output identity is the one proved in 2. Therefore \[\mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}} \le_{\mathrm{TTE},\mathrm{fq}} \mathcal{P}^\sigma_{J,\mathrm{diag}}.\] The two TTE reductions give the claimed TTE equivalence. Since \[\mathrm{TTE}\preceq\mathrm{cont}\preceq\mathrm{raw},\] the corresponding continuous and raw equivalences also follow, agreeing with 5 and 2. ◻

Proof. We first prove well-definedness. Suppose \[\mathbf{P} \equiv_{\mathfrak m,\mathrm{fq}} \mathbf{P}', \qquad \mathbf{Q}\equiv_{\mathfrak m,\mathrm{fq}} \mathbf{Q}',\] and suppose \[\mathbf{P}\le_{\mathfrak m,\mathrm{fq}} \mathbf{Q}.\] Then \[\mathbf{P}'\le_{\mathfrak m,\mathrm{fq}} \mathbf{P} \le_{\mathfrak m,\mathrm{fq}} \mathbf{Q} \le_{\mathfrak m,\mathrm{fq}} \mathbf{Q}'\] by transitivity of the preorder. Hence \[\mathbf{P}'\le_{\mathfrak m,\mathrm{fq}} \mathbf{Q}'.\] Thus the order relation does not depend on the chosen representatives.

Reflexivity follows because \[\mathbf{P}\le_{\mathfrak m,\mathrm{fq}} \mathbf{P}\] for every \(\mathbf{P}\). Transitivity follows directly from transitivity of \(\le_{\mathfrak m,\mathrm{fq}}\). For antisymmetry, suppose \[[\mathbf{P}]_{\mathfrak m}\preceq [\mathbf{Q}]_{\mathfrak m} \qquad\text{and}\qquad [\mathbf{Q}]_{\mathfrak m}\preceq [\mathbf{P}]_{\mathfrak m}.\] Then \[\mathbf{P} \le_{\mathfrak m,\mathrm{fq}} \mathbf{Q} \qquad\text{and}\qquad \mathbf{Q}\le_{\mathfrak m,\mathrm{fq}} \mathbf{P},\] so \[\mathbf{P}\equiv_{\mathfrak m,\mathrm{fq}} \mathbf{Q}.\] Therefore \[[\mathbf{P}]_{\mathfrak m}= [\mathbf{Q}]_{\mathfrak m}.\] Hence the quotient relation is a partial order. ◻

Proof. For each \(i\), condition (B2) gives \[\mathbf{S}_i\le_{\mathfrak m,\mathrm{fq}} \mathbf{P}\] for \(\mathbf{P}\in \mathcal{U}_i\). Hence \[[\mathbf{S}_i]_{\mathfrak m}\preceq [\mathbf{P}]_{\mathfrak m}.\]

We first show that the source degrees are pairwise distinct. Suppose \(i\neq j\). If \[[\mathbf{S}_i]_{\mathfrak m}= [\mathbf{S}_j]_{\mathfrak m},\] then in particular \[\mathbf{S}_i \le_{\mathfrak m,\mathrm{fq}} \mathbf{S}_j.\] But \(\mathbf{S}_j\in \mathcal{U}_j\), so this contradicts condition (B3) for the source \(\mathbf{S}_i\) and the block \(\mathcal{U}_j\). Thus \[[S_i]_{\mathfrak m}\neq [S_j]_{\mathfrak m} \quad \bigl( \forall i\neq j \bigr).\]

Next let \[[\mathbf{Q}]_{\mathfrak m} \in D_k^{\mathfrak m}(\mathcal{U}).\] Then \(\mathbf{Q}\in \mathcal{U}_i\) for a unique \(i\). By (B2), \[[\mathbf{S}_i]_{\mathfrak m} \preceq [\mathbf{Q}]_{\mathfrak m}.\] Thus every exact degree lies above one of the source degrees.

We now prove that each \([\mathbf{S}_i]_{\mathfrak m}\) is minimal. Suppose \[[\mathbf{Q}]_{\mathfrak m} \preceq [\mathbf{S}_i]_{\mathfrak m}.\] Let \(\mathbf{Q} \in \mathcal{U}_j\). If \(i\neq j\), then (B2) gives \[\mathbf{S}_j \le_{\mathfrak m,\mathrm{fq}} \mathbf{Q}.\] Together with \[\mathbf{Q} \le_{\mathfrak m,\mathrm{fq}} \mathbf{S}_i\] this implies \[\mathbf{S}_j \le_{\mathfrak m,\mathrm{fq}} \mathbf{S}_i,\] contradicting (B3) for the source \(\mathbf{S}_j\) and the target block \(\mathcal{U}_i\), since \(\mathbf{S}_i \in \mathcal{U}_i\). Therefore \(j=i\). But then (B2) gives \[\mathbf{S}_i \le_{\mathfrak m,\mathrm{fq}} \mathbf{Q}.\] Since also \[\mathbf{Q} \le_{\mathfrak m,\mathrm{fq}} \mathbf{S}_i,\] we have \[[\mathbf{Q}]_{\mathfrak m}= [\mathbf{S}_i]_{\mathfrak m}.\] So \([\mathbf{S}_i]_{\mathfrak m}\) is minimal.

Finally, if \(\mathbf{P}\in \mathcal{U}_i\), then \([\mathbf{S}_i]_{\mathfrak m} \preceq [\mathbf{P}]_{\mathfrak m}\) by (B2). If another minimal source degree \([\mathbf{S}_j]_{\mathfrak m}\) lay below \([\mathbf{P}]_{\mathfrak m}\) with \(j\neq i\), then \[\mathbf{S}_j \le_{\mathfrak m,\mathrm{fq}} \mathbf{P}\] would contradict (B3). Hence the unique minimal degree below \([\mathbf{P}]_{\mathfrak m}\) is \([\mathbf{S}_i]_{\mathfrak m}\). ◻

Proof. Since every member of \(\mathcal{U}\) has exact raw height \(k\), every member of \(\mathcal{U}\) represents an element of \(D_k^{\mathfrak m}(\mathcal{U})\). By assumption, \[\mathbf{S} \le_{\mathfrak m,\mathrm{fq}} \mathbf{P}\] for \(\mathbf{P}\in \mathcal{U}\). Hence \[[\mathbf{S}]_{\mathfrak m} \preceq [\mathbf{P}]_{\mathfrak m}\] for \(\mathbf{P}\in \mathcal{U}\). Let \([\mathbf{Q}]_{\mathfrak m}\) be a minimal element of \(D_k^{\mathfrak m}(\mathcal{U})\). Then \[[\mathbf{S}]_{\mathfrak m} \preceq [\mathbf{Q}]_{\mathfrak m}.\] By minimality of \([\mathbf{Q}]_{\mathfrak m}\), this forces \[[\mathbf{S}]_{\mathfrak m}= [\mathbf{Q}]_{\mathfrak m}.\] Therefore the only minimal degree is \([\mathbf{S}]_{\mathfrak m}\). ◻

Proof. Let \[h:=\mathrm{SCI}_G(\mathbf{P}).\] If \(h=\infty\), there is nothing to prove. Assume \(h<\infty\). If \(h=0\), let \[\Gamma:\Omega\to \mathcal{M}\] be a general algorithm with \[\Gamma(B)=\Xi(B)\] for \(B\in\Omega\). If \(h\ge1\), let \[\Gamma_{n_h,\ldots,n_1}:\Omega\to \mathcal{M}\] be a raw type-\(G\) tower of height \(h\) for \(\mathbf{P}\). Thus \[\Xi(B) = \lim_{n_h\to\infty}\cdots\lim_{n_1\to\infty} \Gamma_{n_h,\ldots,n_1}(B)\] for \(B\in\Omega\). Now let \[E:\Sigma\to\Omega, \qquad D:(\mathcal{M},d) \to (\mathcal{N},\rho)\] and the finite reconstruction packages \[f(E(A)) = \vartheta_f \bigl( \gamma_{f,1}(A),\ldots,\gamma_{f,m_f}(A) \bigr)\] for \(f\in\Lambda_P\), witness \[\mathbf{S} \le_{\mathrm{raw},\mathrm{fq}} \mathbf{P}.\] We write \(\Gamma_{\mathbf{n}}\) for either \(\Gamma\) in the case \(h=0\), or for \(\Gamma_{n_h,\ldots,n_1}\) in the case \(h\ge1\). Define \[\widetilde{\Gamma}_{n_h,\ldots,n_1}(A) := D\bigl(\Gamma_{n_h,\ldots,n_1}(E(A))\bigr),\] where \(A\in\Sigma\).

We first check that each \[\widetilde{\Gamma}_{n_h,\ldots,n_1}\] is a raw general algorithm for \(\mathbf{S}\). Fix \(A\in\Sigma\). Let \[F_A := \Lambda_{\Gamma_{n_h,\ldots,n_1}}(E(A)) \subseteq \Lambda_P\] be the finite target query set used by the target general algorithm at \(E(A)\). Define the source query set \[\widetilde{\Lambda}(A) := \bigcup_{f\in F_A} \{\gamma_{f,1},\ldots,\gamma_{f,m_f}\}.\] This is a finite, possibly empty, subset of \(\Lambda_S\).

Suppose \(A'\in\Sigma\) agrees with \(A\) on all evaluations in \[\widetilde{\Lambda}(A).\] Then, for every \(f\in F_A\), \[f(E(A')) = \vartheta_f \bigl( \gamma_{f,1}(A'),\ldots,\gamma_{f,m_f}(A') \bigr) = \vartheta_f \bigl( \gamma_{f,1}(A),\ldots,\gamma_{f,m_f}(A) \bigr) = f(E(A)).\] Since \(\Gamma_{n_h,\ldots,n_1}\) is a general algorithm, this implies \[\Gamma_{n_h,\ldots,n_1}(E(A')) = \Gamma_{n_h,\ldots,n_1}(E(A)),\] and therefore \[\widetilde{\Gamma}_{n_h,\ldots,n_1}(A') = \widetilde{\Gamma}_{n_h,\ldots,n_1}(A).\] It also implies that the target query set at \(E(A')\) equals the target query set at \(E(A)\), hence the source query set \(\widetilde{\Lambda}(A')\) equals \(\widetilde{\Lambda}(A)\). Thus \[\widetilde{\Gamma}_{n_h,\ldots,n_1}\] satisfies the two defining finite-information conditions for a raw general algorithm.

It remains to check convergence. If \(h=0\), then \[\widetilde{\Gamma}(A) := D(\Gamma(E(A))) = D(\Xi(E(A))) = \Psi(A),\] so \(\mathbf{S}\) has height \(0\).

If \(h\ge1\), then for every \(A\in\Sigma\), \[\Psi(A) = D(\Xi(E(A))).\] Since \(D\) is continuous and \[\Xi(E(A)) = \lim_{n_h\to\infty}\cdots\lim_{n_1\to\infty} \Gamma_{n_h,\ldots,n_1}(E(A)),\] we may pass \(D\) through the iterated limits, one limit at a time, and obtain \[\Psi(A) = \lim_{n_h\to\infty}\cdots\lim_{n_1\to\infty} D(\Gamma_{n_h,\ldots,n_1}(E(A))).\] Thus \(\mathbf{S}\) has a raw type-\(G\) tower of height \(h\). Therefore \[\mathrm{SCI}_G(\mathbf{S}) \le h=\mathrm{SCI}_G(\mathbf{P}).\] ◻

Proof. Since \(\mathfrak m\preceq\mathrm{raw}\), the transport \[\mathbf{S} \le_{\mathfrak m,\mathrm{fq}} \mathbf{P}\] implies \[\mathbf{S} \le_{\mathrm{raw},\mathrm{fq}} \mathbf{P}.\] The conclusion follows from 5. ◻

Proof. Assume first that \[\mathcal{F} \subseteq \mathcal{O}_k(\mathcal{U}).\] Let \(\mathbf{P}\in \mathcal{F}\). Since \(\mathbf{P} \in\mathcal{O}_k(\mathcal{U})\), and since \(B^{\mathfrak m}_k(\mathcal{U})\) is a modal exact basis, \[\mathbf{P} \in \bigl\{ \mathbf{Q} \in \mathcal{U}_{\le k} : \exists \mathbf{B}\in B^{\mathfrak m}_k(\mathcal{U}) \text{ with } \mathbf{B}\le_{\mathfrak m,\mathrm{fq}} \mathbf{Q} \bigr\}.\] Hence there exists \[\mathbf{B} \in B^{\mathfrak m}_k(\mathcal{U})\] such that \[\mathbf{B} \le_{\mathfrak m,\mathrm{fq}} \mathbf{P}.\] Thus \(\mathcal{F}\) is covered by the modal basis.

Conversely, assume that \(\mathcal{F}\) is covered by the modal basis. Let \(\mathbf{P} \in \mathcal{F}\). Choose \[\mathbf{B} \in B^{\mathfrak m}_k(\mathcal{U})\] such that \[\mathbf{B} \le_{\mathfrak m,\mathrm{fq}} \mathbf{P}.\] Because \[B^{\mathfrak m}_k(\mathcal{U}) \subseteq \mathcal{O}_k(\mathcal{U}),\] we have \[\mathrm{SCI}_G(\mathbf{B})=k.\] By raw-soundness and 6, \[k=\mathrm{SCI}_G(\mathbf{B}) \le \mathrm{SCI}_G(\mathbf{P}).\] But \[\mathbf{P} \in \mathcal{F} \subseteq \mathcal{U}= \mathcal{U}_{\le k},\] so \[\mathrm{SCI}_G(\mathbf{P}) \le k.\] Therefore \[\mathbf{P} \in\mathcal{O}_k(\mathcal{U}).\] Since \(\mathbf{P}\in \mathcal{F}\) was arbitrary, \[\mathcal{F} \subseteq \mathcal{O}_k(\mathcal{U}).\] ◻

Proof. For each \(\mathbf{P} \in \mathcal{F}\), choose \(\mathbf{W}_P \in \mathcal{W}\) with \[\mathbf{W}_P \le_{\mathfrak m,\mathrm{fq}} \mathbf{P}.\] Since \(\mathbf{W}_P \in \mathcal{O}_k(\mathcal{U})\), \(\mathrm{SCI}_G(\mathbf{W}_P)=k\). By raw-soundness, \[k=\mathrm{SCI}_G(\mathbf{W}_P) \le \mathrm{SCI}_G(\mathbf{P}).\] Since \(\mathbf{P} \in \mathcal{U}= \mathcal{U}_{\le k}\), \(\mathrm{SCI}_G(\mathbf{P})\le k\). Hence \[\mathrm{SCI}_G(\mathbf{P})=k.\] Thus every \(\mathbf{P}\in \mathcal{F}\) has exact height \(k\). ◻

Proof. It suffices to check the claim for each elementary encoding and then use induction over finite compositions.

For unitary conjugacy, basis relabeling, graph relabeling, and representation inclusion, there is a fixed unitary \[U:H_\rho\to H_{\rho'}\] such that, for the encoded instance \(E(A,K)=(A_E,K)\), \[\operatorname{op}_{\rho'}(A_E) = U\,\operatorname{op}_\rho(A)\,U^{-1}.\] Hence, for every \(z\in\mathbb{C}\), \[\operatorname{op}_{\rho'}(A_E)-zI = U(\operatorname{op}_\rho(A)-zI)U^{-1}.\] Therefore \[\sigma(\operatorname{op}_{\rho'}(A_E)) = \sigma(\operatorname{op}_{\rho}(A)),\] and, on the common resolvent set, \[(\operatorname{op}_{\rho'}(A_E)-zI)^{-1} = U(\operatorname{op}_{\rho}(A)-zI)^{-1}U^{-1}.\] Thus \[\|(\operatorname{op}_{\rho'}(A_E)-zI)^{-1}\| = \|(\operatorname{op}_{\rho}(A)-zI)^{-1}\|,\] and consequently \[\sigma_\varepsilon(\operatorname{op}_{\rho'}(A_E)) = \sigma_\varepsilon(\operatorname{op}_{\rho}(A)).\] Since the compact input \(K\) is unchanged, both window predicates are preserved.

For neutral direct-sum stabilization, there are fixed data \(T_0,W\) such that \[\operatorname{op}_{\rho'}(A_E) = W(\operatorname{op}_\rho(A)\oplus T_0)W^{-1}.\] By unitary invariance and the direct-sum resolvent identity, \[\sigma(\operatorname{op}_{\rho'}(A_E)) = \sigma(\operatorname{op}_{\rho}(A))\cup\sigma(T_0),\] and \[\sigma_\varepsilon(\operatorname{op}_{\rho'}(A_E)) = \sigma_\varepsilon(\operatorname{op}_{\rho}(A))\cup\sigma_\varepsilon(T_0).\] The \((J,\varepsilon)\)-neutrality assumption gives \[\sigma(T_0)\cap K=\varnothing, \qquad \sigma_\varepsilon(T_0)\cap K=\varnothing\] for every singleton \(K\subset J\). Hence both window predicates are preserved.

Finite compositions preserve the two predicates because each elementary encoding preserves them. This proves the lemma. ◻

Proof. The diagonal-to-diagonal reductions are reflexivity.

For diagonal-to-general, use the representation-inclusion encoding \[E(A,K):=(A,K),\] where the same diagonal operator is viewed as a member of the general \(\ell^2(\mathbb{N})\)-operator class. This encoding is one of the generators of \(\mathrm{geom}^{\mathrm{CH23}}_{J,\varepsilon}\). The decoder is \[D=\operatorname{id}_{\{0,1\}}.\] By representation inclusion, the underlying operator and compact input are unchanged. Hence the exact spectral and fixed-\(\varepsilon\) pseudospectral target identities hold.

For the finite-query reconstruction, a target matrix-entry query satisfies \[\langle Ae_j,e_i\rangle = \begin{cases} \mu_j(A,K),&i=j,\\ 0,&i\neq j. \end{cases}\] Compact-window approximants are passed through unchanged. The general-class auxiliary bounded-dispersion data can be chosen canonically for diagonal operators, for example \[f(n)=n, \qquad c_n=2^{-n},\] because \[(I-P_n)AP_n=0, \qquad (I-P_n)A^*P_n=0.\] Thus all target evaluations are reconstructed from finitely many source evaluations and constants. This proves both \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{geom}^{\mathrm{CH23}}_{J,\varepsilon},\mathrm{fq}} \mathcal{P}^\sigma_{J,\mathrm{gen}}\] and \[\mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}} \le_{\mathrm{geom}^{\mathrm{CH23}}_{J,\varepsilon},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{gen}}.\]

For diagonal-to-graph, fix a connected countable graph \[\mathcal{G}=(V,E_{\mathcal{G}}), \qquad V=\{v_1,v_2,\ldots\},\] and the unitary \[U:\ell^2(\mathbb{N})\to\ell^2(V), \qquad Ue_j=\mathbf{1}_{v_j}.\] Encode by \[E(A,K):=(UAU^{-1},K).\] This is a composition of a unitary relabeling and a graph-representation inclusion, hence is \(\mathrm{geom}^{\mathrm{CH23}}_{J,\varepsilon}\)-admissible.

If \[Ae_j=a_je_j,\] then \[UAU^{-1}\mathbf{1}_{v_j}=a_j\mathbf{1}_{v_j}.\] Thus the graph coefficient function satisfies \[\alpha(v_i,v_j) = \begin{cases} a_j,&i=j,\\ 0,&i\neq j. \end{cases}\] Therefore each graph coefficient evaluation is reconstructed from either one diagonal source evaluation or a constant. Local support sets may be chosen as \[S_{v_j}:=\{v_j\},\] so local support queries are constant reconstructions. Compact-window approximants are unchanged by this procedure.

The output identities follow from unitary invariance: \[\sigma(UAU^{-1})=\sigma(A), \qquad \sigma_\varepsilon(UAU^{-1}) = \sigma_\varepsilon(A).\] This proves the two diagonal-to-graph reductions. ◻

Proof. Choose \[x\in\operatorname{int}(J), \qquad K:=\{x\}.\]

Step 1: No geometric reduction from the exact spectral source to a pseudospectral target: Suppose, toward contradiction, that for some \[\star\in\{\mathrm{diag},\mathrm{gen},\mathrm{graph}\}\] there is a geometric finite-query transport \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \le_{\mathrm{geom}^{\mathrm{CH23}}_{J,\varepsilon},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\star}.\] Let \(E\) be its geometric encoding and let \(D:\{0,1\}\to\{0,1\}\) be its decoder.

Consider the scalar diagonal operators \[A_0:=xI, \qquad A_1:=\left(x+\frac{\varepsilon}{2}\right)I.\] For the exact spectral source, \[\sigma(A_0)=\{x\}, \qquad \sigma(A_1)=\left\{x+\frac{\varepsilon}{2}\right\}.\] Thus \[\sigma(A_0)\cap K\neq\varnothing, \qquad \sigma(A_1)\cap K=\varnothing.\] With the \(0/1\) convention this gives \[\Xi_\sigma(A_0,K)=0, \qquad \Xi_\sigma(A_1,K)=1.\]

On the other hand, since \(A_0\) and \(A_1\) are normal scalar operators, \[\operatorname{dist}(x,\sigma(A_0))=0, \qquad \operatorname{dist}(x,\sigma(A_1))=\frac{\varepsilon}{2}.\] Hence \[x\in\sigma_\varepsilon(A_0), \qquad x\in\sigma_\varepsilon(A_1).\] By 7, the geometric encoding preserves the pseudospectral window predicate. Therefore \[\Xi_{\sigma_\varepsilon}(E(A_0,K))=0, \qquad \Xi_{\sigma_\varepsilon}(E(A_1,K))=0.\] The output identity of the transport would now require \[D(0)=0 \qquad\text{and}\qquad D(0)=1,\] which is impossible. Therefore \[\mathcal{P}^\sigma_{J,\mathrm{diag}} \not\le_{\mathrm{geom}^{\mathrm{CH23}}_{J,\varepsilon},\mathrm{fq}} \mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\star}.\]

Step 2: No geometric reduction from the pseudospectral source to an exact spectral target: Suppose, toward contradiction, that for some \[\star\in\{\mathrm{diag},\mathrm{gen},\mathrm{graph}\}\] there is a geometric finite-query transport \[\mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}} \le_{\mathrm{geom}^{\mathrm{CH23}}_{J,\varepsilon},\mathrm{fq}} \mathcal{P}^\sigma_{J,\star}.\] Let again \(E\) be its geometric encoding and \(D:\{0,1\}\to\{0,1\}\) its decoder.

Define \[B_0:=\left(x+\frac{\varepsilon}{2}\right)I, \qquad B_1:=(x+2\varepsilon)I.\] Then \[\sigma(B_0)\cap K=\varnothing, \qquad \sigma(B_1)\cap K=\varnothing.\] Hence the exact spectral target output is \[\Xi_\sigma(B_0,K)=1, \qquad \Xi_\sigma(B_1,K)=1.\] By 7, the geometric encoding preserves this exact spectral window predicate, so \[\Xi_\sigma(E(B_0,K))=1, \qquad \Xi_\sigma(E(B_1,K))=1.\]

For the pseudospectral source, \[\operatorname{dist}(x,\sigma(B_0))=\frac{\varepsilon}{2} \le\varepsilon,\] so \[x\in\sigma_\varepsilon(B_0), \qquad \Xi_{\sigma_\varepsilon}(B_0,K)=0.\] But \[\operatorname{dist}(x,\sigma(B_1))=2\varepsilon>\varepsilon,\] so \[x\notin\sigma_\varepsilon(B_1), \qquad \Xi_{\sigma_\varepsilon}(B_1,K)=1.\] The output identity of the transport would now require \[D(1)=0 \qquad\text{and}\qquad D(1)=1,\] which is again impossible. Therefore \[\mathcal{P}^{\sigma_\varepsilon}_{J,\varepsilon,\mathrm{diag}} \not\le_{\mathrm{geom}^{\mathrm{CH23}}_{J,\varepsilon},\mathrm{fq}} \mathcal{P}^\sigma_{J,\star}.\] ◻

Proof. This follows directly from 1, 8 and 9. Hence the hypotheses of 7 hold with \(r=2\). ◻

Proof. This is a combination of 1 and 9. ◻