Proof. Let M be a computable injection structure with at least one infinite orbit. Non-uniformly fix $N_{0},N_{1}\in \omega \cup \{\infty \}$ as the number of orbits in A of type $\omega $ and $\zeta $ , respectively. A punctual presentation of P of A may be obtained as follows. At each stage s, enumerate $n_{0}+n_{1}$ many elements into P, where $n_{i}=\min \{s,N_{i}\}$ , extending the infinite orbits in the obvious way. Since at least one of $N_{0},N_{1}$ is non-zero, this ensures that P remains punctual. For any orbits of finite size, we simply wait for their size to be revealed in M (this is a c.e. wait), once revealed, we enumerate a finite cycle of the same size into P.

Proof. From Fact 1.4, we have that $\operatorname {\mathrm {\texttt {Cone}}}(\Delta _{1}^{0})\subseteq \operatorname {\mathrm {\texttt {PRCatSpec}}}(M)$ . In order to prove the remaining inclusion, for any total computable g, we produce punctual injection structures A and B, both isomorphic to M, such that any isomorphism $h:A\to B$ is such that $g\leq _{pr}h\oplus h^{-1}$ .

Encoding $g(0)$ : Since g is a total computable function, all we need is to encode is the stage s at which $g(0)[s]\downarrow $ . We shall do this by enumerating finite orbits into one structure A ‘quickly’ while ‘delaying’ their enumeration into B until after stage s is reached. The main tension here is that we have to keep both A and B punctual; we cannot arbitrarily delay enumerating elements. Since we assumed that M has at least one infinite orbit, and only finitely many infinite orbits, we can keep $A,B$ punctual by simply enumerating these infinite orbits in both $A,B$ . Moreover, to ensure that $A,B\cong M$ , we never enumerate finite orbits into either A or B unless it has already been enumerated in M. As discussed, whenever a finite orbit, say of size n, is enumerated into M, we immediately enumerate a finite orbit of size n into A. Then once $g(0)\downarrow $ , we also enumerate a finite orbit of size n into B. If $h:A\to B$ is an isomorphism, then by computing h on the elements within the finite orbit, we may recover the stage, where $g(0)$ converges.

Encoding g(x): The obvious generalisation of the strategy described above would be to compute h on the first x many finite orbits revealed in A, and then arguing that at least one of these images must have index larger than the stage at which $g(x)$ converges. However, we note here that this process is not necessarily primitive recursive in $h\oplus h^{-1}$ and x. In particular, an arbitrary punctual injection structure M could enumerate finite orbits only at extremely sparse stages, meaning that the index of the x-th finite orbit in M cannot be obtained in a primitive recursive way.

To solve this issue, in addition to encoding the stage at which $g(x)$ converges, we also encode the stage $G(x+1)$ at which M enumerates the $(x+1)$ -st finite orbit. More specifically, we enumerate the x-th finite orbit into B only after the $(x+1)$ -st finite orbit has been enumerated into A. (Recall that A immediately enumerates any finite orbit enumerated into M.)

Now, we may define $\Psi ^{h}$ as follows. Non-uniformly fix $G(0)$ , the stage at which A reveals the first finite orbit. From this stage, we may recover primitive recursively the indices of the elements in this finite orbit and then compute h on them. The image must produce indices large enough such that A has enumerated the next finite orbit and $g(0)$ has converged. Inductively, we may suppose that $\Psi ^{h}(x)=g(x)\oplus G(x+1)$ . To define $\Psi ^{h}(x+1)$ , use $G(x+1)$ to recover the indices of the $(x+1)$ -st finite orbit in A and compute h on all elements of the first $x+1$ many finite orbits in A. Since B never enumerates the $(x+1)$ -st finite orbit until A enumerates the $(x+2)$ -nd finite orbit and $g(x+1)$ converges, one of the h-images must produce an index $\geq G(x+2),g(x+1)$ . That is to say, $h\geq _{pr}g\oplus G\geq _{pr}g$ .

Proof. If an injection structure M is relatively $\Delta ^0_2$ -categorical, but not relatively $\Delta ^0_1$ -categorical, then its infinite orbits must be one of the following types:

1. (i) Finitely many $\zeta $ chains and infinitely many $\omega $ chains.

2. (ii) Only finitely many $\omega $ chains and infinitely many $\zeta $ chains.

Applying Fact 1.4, we clearly have that $\operatorname {\mathrm {\texttt {Cone}}}(\Delta _{2}^{0})\subseteq \operatorname {\mathrm {\texttt {PRCatSpec}}}(M)$ . It remains to prove that $\operatorname {\mathrm {\texttt {PRCatSpec}}}(M)\subseteq \operatorname {\mathrm {\texttt {Cone}}}(\Delta _{2}^{0})$ . That is, given g, a total $\Delta _{2}^{0}$ function, we define two punctual injection structures A and B, both isomorphic to M, such that $g\leq _{pr}h\oplus h^{-1}$ for any isomorphism $h:A\to B$ .

Fix a primitive recursive approximation $g^{*}$ such that $\lim _{s}g^{*}(x,s)=g(x)$ for all x, and fix some injection structure of Type (i) that has a punctual presentation. In A and B, we never enumerate any finite orbits until they are observed to close in the given punctual (or computable) injection structure M. More specifically, we only enumerate $\omega $ chains while waiting for finite orbits to be enumerated into the given punctual injection structure. Similarly, we may non-uniformly fix the finitely many $\zeta $ chains and enumerate them in a standard way during the construction. This ensures that A and B are of the same isomorphism type as the given punctual injection structure M. Obviously, we shall use the $\omega $ chains to encode the stabilising stages $s_{x}$ ; $g^{*}(x,s_{x})=g^{*}(x,s)$ for all $s\geq s_{x}$ .

Encoding $s_{x}$ : As mentioned above, we construct punctual structures $A=(\omega ,f_{A})$ and $B=(\omega ,f_{B})$ such that any isomorphism from A to B encodes g. In A, all $\omega $ chains will be standard; this allows us to access the left-most element of each $\omega $ chain in a primitive recursive way. We denote these elements as $a_{0,0},a_{1,0},a_{2,0},\dots $ . At each stage s, enumerate $a_{s,0}$ and for each $a_{i,j}$ currently in A, where $f_{A}(a_{i,j})$ has yet to be defined, enumerate $a_{i,j+1}:= f_{A}(a_{i,j})$ . This ensures that $f_{A}$ is primitive recursive and A is punctual.

In B, we shall use the left-most element of each $\omega $ chain in B to encode the stabilising stage s of $g^{*}(x,s)$ for various x. At stage $0$ , enumerate the element $b_{0}$ and let $b^{l}_{0,0}=b^{r}_{0,0}=b_{0}$ . The idea is that $b^{l}_{i,s}$ and $b^{r}_{i,s}$ will denote the current left-most and right-most elements of the i-th $\omega $ chain at stage s, respectively. At each stage s, recursively suppose that $b^{l}_{i,s-1}$ and $b^{r}_{i,s-1}$ have been defined for $i<s$ . If $g^{*}(x,s)\neq g^{*}(x,s-1)$ , then do the following:

1. (1) For each j where $x<j<s$ , define $f_{B}(b^{r}_{j-1,s-1})=b^{l}_{j,s-1}$ .

2. (2) For each $j<x$ , let $b^{l}_{j,s}=b^{l}_{j,s-1}$ and $b^{r}_{j,s}=b^{r}_{j,s-1}$ .

3. (3) Let $b^{l}_{x,s}=b^{l}_{x,s-1}$ and $b^{r}_{x,s}=b^{r}_{s-1,s-1}$ .

4. (4) Pick fresh indices $i_{x+1},i_{x+2},\dots ,i_{s}$ , and enumerate the elements $b_{i_{x+1}},b_{i_{x+2}},\dots, $ $b_{i_{s}}$ , defining $b^{l}_{j,s}=b^{r}_{j,s}=b_{i_{j}}$ for each $x<j\leq s$ .

Intuitively, if $g^{*}(x,s)\neq g^{*}(x,s-1)$ , then we ‘glue’ the j-th chain for $x<j<s$ to the x-th chain at stage s, while leaving the first x many chains the same. This ensures that any element in the subsequent chains will have indices $>s$ . Finally, to keep $f_{B}$ primitive recursive, for each element $b\in B$ enumerated at stage $s-1$ , enumerate some new element $b'$ and let $f_{B}(b)=b'$ if $f_{B}(b)$ is not yet defined. In addition, if b is such that $b=b^{r}_{i,s}$ for some i, re-define $b^{r}_{i,s}$ to be $b'$ .

Verification: Recall that any finite cycle or any $\zeta $ chain will be enumerated by ‘copying’ the given punctual injection structure. Thus, to verify that the construction produces the correct isomorphism type, it suffices to show that the procedure above produces infinitely many $\omega $ chains and nothing else. First, observe that for any b enumerated by the procedure above, $f_{B}(b)$ exists; if b was enumerated at stage s, by stage $s+1$ , $f_{B}(b)$ must have been defined. Thus, there is no right-most element produced by the procedure above. Next, to show that each chain has a left-most element, we argue that for each $i\in \omega $ , there exists $s\in \omega $ such that for all $t\geq s,\,b^{l}_{i,s}=b^{l}_{i,t}$ . It follows directly from the description that $b^{l}_{0,t}=b^{l}_{0,0}$ for all $t\geq 0$ . For $i>0$ , consider the stage $s^{*}$ such that $g^{*}(x,s^{*})=g^{*}(x,t)$ for all $t\geq s^{*}$ and for all $x<i$ . Since g is a total $\Delta _{2}^{0}$ function, such a stage $s^{*}$ must exist. Following the construction, $f_{B}^{-1}(b^{l}_{i,s})$ is only ever defined when $g^{*}(x,s)\neq g^{*}(x,s-1)$ for some $x<i$ . In particular, for all stages $t\geq s^{*}+1$ , we have that $g^{*}(x,t)=g^{*}(x,t-1)$ and so, $b^{l}_{i,t}=b^{l}_{i,s^{*}+1}$ .

Finally, let $h:A\to B$ be an isomorphism. Define $\Psi ^{h}$ , a primitive recursive scheme as follows. Given x, compute $g^{*}(x,\max \{h(a_{i,0})\mid i\leq x+1\})$ . By pigeonhole principle, at least one of $h(a_{i,0})=b^{l}_{j,s}$ for some $j\geq x+1$ and for some $s\in \omega $ . It then follows that $\max \{h(a_{i,0})\mid i\leq x+1\}$ is at least as big as the index of the left-most element of the $(x+1)$ -st $\omega $ chain in B, which encodes a stage large enough such that $g^{*}$ has stabilised for all $y\leq x$ . In particular, $g^{*}(x,\max \{h(a_{i,0})\mid i\leq x+1\})=g(x)$ .

For injection structures of Type (ii), we adopt a similar strategy. The only difference is that we must produce infinitely many $\zeta $ chains and nothing else when encoding g. That is, in addition to the procedure defined above, at each stage s, for each b currently defined as $b^{l}_{i,s}$ for some i, enumerate a new element $b'$ , define $f_{B}(b')=b$ , and re-define $b^{l}_{i,s}=b'$ . In A, we take a similar approach and extend the chains to the left at each stage by adding $a_{i,j}$ for $j<0$ and letting $f_{A}(a_{i,j})=a_{i,j+1}$ as before.

Using the modified construction, it is not too difficult to see that instead of $\omega $ chains, we now produce infinitely many $\zeta $ chains and nothing else. Furthermore, for each x, the $(x+1)$ -st $\zeta $ chain in B has the property that all elements within it have indices $\geq s$ , where s is such that for all $t\geq s$ and for all $y\leq x$ , $g^{*}(y,t)=g^{*}(y,s)$ . For the same reasons as before, $g(x)=g^{*}(x,\max \{h(a_{i,0})\mid i\leq x+1\})$ , and thus $g\leq _{pr}h$ . Theorem 2.3 is proved.

Proof. Let M be a relatively $\Delta _{3}^{0}$ -categorical, not- $\Delta ^0_2$ -categorical injection structure with a punctual presentation. That is, M has infinitely many $\omega $ chains and infinitely many $\zeta $ chains. This fact will be used implicitly in our encoding of $t_{x,s}$ and $s_{x}$ for various $x,s$ (the details will be provided shortly). Once again, by Fact 1.4, we have that $\operatorname {\mathrm {\texttt {Cone}}}(\Delta _{3}^{0})\subseteq \operatorname {\mathrm {\texttt {PRCatSpec}}}(M)$ , and it remains to prove that $\operatorname {\mathrm {\texttt {PRCatSpec}}}(M)\subseteq \operatorname {\mathrm {\texttt {Cone}}}(\Delta _{3}^{0})$ . Just as before, we focus only on the $\omega $ chains and $\zeta $ chains, enumerating finite orbits into our structures $A=(\omega ,f_{A})$ and $B=(\omega ,f_{B})$ only when they are shown to close in the given punctual copy M. Let g be a $\Delta _{3}^{0}$ function and let $g^{*}(x,s,t)$ be a primitive recursive approximation to g; $\lim _{s}\lim _{t}g^{*}(x,s,t)=g(x)$ . The strategy to encode g will be split into two parts. The first is to encode for each pair $(x,s)$ , the stage $t_{x,s}$ such that $g^{*}(x,s,t)=g^{*}(x,s,t_{x,s})$ for all $t\geq t_{x,s}$ . The second is to encode the stage $s_{x}$ for which $\lim _{t}g^{*}(x,s_{x},t)=g(x)$ . Then using the isomorphisms $h:A\to B$ and $h^{-1}:B\to A$ , we recover both $s_{x}$ and $t_{x,s_{x}}$ , respectively, and compute $g^{*}(x,s_{x},t_{x,s_{x}})$ .

Encoding $t_{x,s}$ : In A, for each $(x,s)$ , we keep a standard $\omega $ chain with left-most element $a_{\langle x,s\rangle ,0}$ . The idea is to encode $t_{x,s}$ using $h(a_{\langle x,s\rangle ,0})$ . Intuitively, this means that we should keep the indices of the left-most elements of each $\omega $ chain in B ‘large enough’. In B, we begin with $\omega $ chains with left-most elements $b_{0,0},b_{1,0},b_{2,0},\dots $ , respectively. At each stage t of the construction, we track the left-most elements of each of these $\omega $ chains in B, denoted by $b^{l}_{i,t}$ . For each i, let $b^{l}_{i,0}=b_{i,0}$ . At stage t, if $g^{*}(x,s,t)\neq g^{*}(x,s,t-1)$ , then for each $i\geq \langle x,s\rangle $ , enumerate some element $b^{*}$ with some index $\geq t$ and define $f_{B}(b^{*})=b^{l}_{i,t-1}$ and let $b^{l}_{i,t}=b^{*}$ . Since $\lim _{t}g^{*}(x,s,t)$ exists for each $(x,s)$ , there must be some stage $t^{*}$ for which $\lim _{t}g^{*}(x',s',t)=g^{*}(x',s',t^{*})$ for each $x'\leq x$ and $s'\leq s$ . After such a stage $t^{*}$ , $b^{l}_{i,t}$ for each $i\leq \langle x,s\rangle $ never again changes. Furthermore, $b^{l}_{\langle x,s\rangle ,t^{*}}$ must have index $\geq t^{*}$ .

Encoding $s_{x}$ : Let $P(x,s)$ be the predicate “ $\lim _{t}g^{*}(x,s,t)=g(x)$ .” Since this is equivalent to “for all $s'\geq s,\,\lim _{t}g^{*}(x,s,t)=\lim _{t}g^{*}(x,s',t)$ ,” $P(x,s)$ is a $\Pi _{2}^{0}$ predicate. We may further assume that there is a unique s for which $P(x,s)$ holds by requiring $s\geq x$ to be the least, and that for any $x<y$ , if $P(x,s_{x})$ and $P(y,s_{y})$ are both true, then $s_{x}<s_{y}$ . To keep the strategies disjoint, we encode the various $s_{x}$ using the infinitely many $\zeta $ chains. In B, we enumerate standard copies of $\zeta $ chains, indexed by $c_{i,j}$ for $i,j\in \omega $ , defining $f_{B}(c_{i,1})=c_{i,0}$ , $f_{B}(c_{i,2j})=c_{i,2(j+1)}$ and $f_{B}(c_{i,2j+3})=c_{i,2j+1}$ . Within A, let the possible $\zeta $ chains be encoded by $d_{i,j}$ for $i,j\in \omega $ . By a careful definition of $f_{A}$ , for a fixed s, the collection of $d_{s,j}$ becomes a $\zeta $ chain iff $P(0,s)\vee P(1,s)\vee \dots \vee P(s,s)$ holds. Intuitively, we ‘grow’ the chain of $d_{s,j}$ to the left only at stages where one of $P(x,s)$ currently holds for some $x\leq s$ . Since $P(x,s)$ is $\Pi _{2}^{0}$ , if it holds, then it must look to be true at infinitely many stages. Thus, at infinitely many stages, we extend the chain to the left, resulting in a $\zeta $ chain. Conversely, if there are infinitely many stages where we extend the chain containing $d_{s,0}$ to the left, at least one of $P(0,s),P(1,s),\dots ,P(s,s)$ must look to hold at infinitely many stages. That is to say, one of $P(x,s)$ is true for $x\leq s$ . To recover $s_{x}$ , we compute $h^{-1}(c_{i,0})$ for sufficiently many i, and we know that such an image must map to some $d_{s,j}$ contained in a $\zeta $ chain. Using pigeonhole principle, we then conclude that one such $d_{s,j}$ must have $s\geq s_{x}$ .

Construction: We summarise the various types of elements in A and B below. $\begin {array}{l|l} \text {Element type} & \text {Purpose} \\ \hline\hline {=|=} a_{i,j}\in A, \text { for all } i,j\in \omega. & \text {Standard } \omega \text { chains; encoding } t_{x,s} \text { where } i=\langle x,s\rangle .\\ b_{i,j}\in B, \text { for all } i\in \omega & \text {Non-standard } \omega \text { chains to be images for } h(a_{i,0}).\\ \quad \text { and all } j\geq i. & \\ \hline c_{i,j}\in B, \text { for all } i,j\in \omega. & \text {Standard } \zeta \text { chains; encoding } s_{x} \text { where } i=\langle x,s\rangle .\\ d_{i,j}\in A, \text { for all } i,j\in \omega. & \zeta \text { chain iff there exists } x\leq i \text { such that } P(x,i) \text { holds}. \end {array}$

At stage $0$ , enumerate $a_{0,0},d_{0,0}$ into A, $b_{0,0},c_{0,0}$ into B. Define $b^{l}_{0,0}=b^{r}_{0,0}=b_{0,0}$ and $d^{l}_{0,0}=d^{r}_{0,0}=d_{0,0}$ . At stage s, suppose that we have already defined for each $i<s$ , $b^{l}_{i,s-1},b^{r}_{i,s-1},d^{l}_{i,s-1}$ , and $d^{r}_{i,s-1}$ .

1. Step 1: Enumerate $a_{s,j}$ for each $j<s$ and $a_{i,s}$ for each $i\leq s$ into A. Then define $f_{A}(a_{s,j})=a_{s,j+1}$ for each $j<s$ and define $f_{A}(a_{i,s-1})=a_{i,s}$ for each $i\leq s$ . This ensures that at each stage s, $a_{i,j}$ for all $i,j\leq s$ has been enumerated and that $f_{A}$ is primitive recursive on all such elements.

2. Step 2: Enumerate $b_{s,s}$ into B and define $b^{l}_{s,s}=b^{r}_{s,s}=b_{s,s}$ . For each $i<s$ , let $j_{i}$ be the least index such that $j_{i}>j$ for any $b_{i,j}$ currently enumerated into B. If there is some $\langle x,n\rangle =i<s$ and $g^{*}(x,n,s)\neq g^{*}(x,n,s-1)$ , then enumerate $b_{k,j_{k}}$ and $b_{k,j_{k}+1}$ into B for all k such that $i\leq k<s$ , defining

   • • $b^{r}_{k,s}=f_{B}(b^{r}_{k,s-1})=b_{k,j_{k}+1}$ ,

   • • $b^{l}_{k,s}=b_{k,j_{k}}$ , and

   • • $f_{B}(b_{k,j_{k}})=b^{l}_{k,s-1}$ .

   Otherwise, only enumerate $b_{i,j_{i}}$ into B, define $b^{r}_{i,s}=f_{B}(b^{r}_{i,s-1})=b_{i,j_{i}}$ and $b^{l}_{i,s}=b^{l}_{i,s-1}$ .

3. Step 3: Enumerate $c_{s,2j},c_{s,2j+1}$ for each $j<s$ and $c_{i,2s},c_{i,2s+1}$ for each $i\leq s$ into B. Now define $f_{B}(c_{i,2(s-1)})=c_{i,2s}$ , and $f_{B}(c_{i,2s+1})=c_{i,2s-1}$ for each $i<s$ , and

   $$ \begin{align*}c_{s,2s+1}\xrightarrow{f_{B}}c_{s,2s-1}\xrightarrow{f_{B}}\dots\xrightarrow{f_{B}}c_{s,1}\xrightarrow{f_{B}}c_{s,0}\xrightarrow{f_{B}}c_{s,2}\xrightarrow{f_{B}}\dots\xrightarrow{f_{B}}c_{s,2s}. \end{align*} $$
   At each stage s, we have that B contains $c_{i,j}$ for each $i\leq s$ and each $j<2(s+1)$ , and $f_{B}$ is primitive recursive on all such elements.

4. Step 4: Enumerate $d_{s,0}$ into A, and define $d^{l}_{s,s}=d^{r}_{s,s}=d_{s,0}$ . For each $i<s$ , let $j_{i}$ be the least index such that $j_{i}>j$ for any $d_{i,j}$ currently enumerated into A. If there is some $x\leq i<s$ such that $P(x,i)$ fires (looks to be true at the current stage), then enumerate $d_{i,j_{i}}$ and $d_{i,j_{i}+1}$ into A, and define the following:

   • • $d^{r}_{i,s}=f_{A}(d^{r}_{i,s-1})=d_{i,j_{i}+1}$ ,

   • • $d^{l}_{i,s}=d_{i,j_{i}}$ , and

   • • $f_{A}(d_{i,j_{i}})=d^{l}_{i,s-1}$ .

   Otherwise, only enumerate $d_{i,j_{i}}$ into A, and define $d^{r}_{i,s}=f_{A}(d^{r}_{i,s-1})=d_{i,j_{i}}$ . Also let $d^{l}_{i,s}=d^{l}_{i,s-1}$ .

Whenever a finite orbit in the given punctual injection structure is revealed, we also enumerate a finite orbit of the same size into the structures A and B.

Verification: We make the following observations:

1. (i) For any $x,s$ , the collection $\{b_{\langle x,s\rangle ,j}\mid j\geq \langle x,s\rangle \}$ forms an $\omega $ chain with left-most element $b_{\langle x,s\rangle ,t}$ , where for all $t'\geq t$ and for any $\langle x',s'\rangle \leq \langle x,s\rangle $ , $g^{*}(x',s',t')=g^{*}(x',s',t)$ . (Note that $b_{\langle x,s\rangle ,j}$ for $j<\langle x,s\rangle $ is undefined as they are never enumerated into B.)

   For a fixed pair $x,s$ , since $\lim _{t}g^{*}(x,s,t)$ is assumed to exist, then there must be some finite stage $t_{x,s}$ such that for all $t\geq t_{x,s},\,g^{*}(x,s,t_{x,s})=g^{*}(x,s,t)$ . This implies that for all $t>\max \{t_{x',s'}\mid \langle x',s'\rangle \leq \langle x,s\rangle \}$ , we always define $b^{l}_{\langle x,s\rangle ,t+1}=b^{l}_{\langle x,s\rangle ,t}$ and $f_{B}^{-1}(b^{l}_{\langle x,s\rangle ,t})\uparrow $ . Thus, there is some finite stage t after which the left-most element in the collection $\{b_{\langle x,s\rangle ,j}\mid j\geq \langle x,s\rangle \}$ never again changes. That is, the collection forms an $\omega $ chain. From the argument above and an analysis of the actions in Step 2, it is easy to conclude that the index $j\in \omega $ for which $b_{\langle x,s\rangle ,j}=b^{l}_{\langle x,s\rangle ,t}$ is such that $j\geq t_{x',s'}$ for any $\langle x',s'\rangle \leq \langle x,s\rangle $ . Therefore, (i) is true.

2. (ii) For any $s\in \omega $ , the collection $\{d_{s,j}\mid j\in \omega \}$ forms a $\zeta $ chain iff there exists some $x\leq s$ such that $P(x,s)$ fires at infinitely many stages.

   To see why (ii) holds, we turn our attention to Step 4 of the construction. First suppose that for all $x\leq s$ , $P(x,s)$ fires only finitely often. In particular, there is some finite stage $s^{*}$ large enough such that after $s^{*}$ , $P(x,s)$ never again fires for all $x\leq s$ . An analysis of Step 4 in the construction will allow one to conclude that for all $s'\geq s^{*}$ , $d^{l}_{s,s'}=d^{l}_{s,s^{*}}$ , and that $f_{A}^{-1}(d^{l}_{s,s^{*}})\uparrow $ . In other words, the collection $\{d_{s,j}\mid j\geq s\}$ forms an $\omega $ chain.

   On the other hand, if there is some $x\leq s$ for which $P(x,s)$ fires infinitely often, then let these stages be denoted by $s_{0}<s_{1}<s_{2}<\dots $ . Obviously, at all such stages, we would have defined $d^{l}_{s,s_{i}}=f_{A}^{-1}(d^{l}_{s,s_{i}-1})$ , meaning that the collection $\{d_{s,j}\mid j\in \omega \}$ has no left-most element. Furthermore, as described in Step 4, we always define $d^{r}_{s,s'}=f_{A}(d^{r}_{s,s'-1})$ , thus also ensuring that $\{d_{s,j}\mid j\in \omega \}$ has no right-most element. Thus, $\{d_{s,j}\mid j\in \omega \}$ forms a $\zeta $ chain iff there is some $x\leq s$ for which $P(x,s)$ fires infinitely often.

To see that A and B are of the correct isomorphism type, it suffices to show that they consist of infinitely many $\omega $ chains and infinitely many $\zeta $ chains, as the finite orbits are enumerated whenever they are observed to close in the given punctual copy. Step 3 of the construction ensures that B consists of $\zeta $ chains of the form $\{c_{i,j}\mid j\in \omega \}$ for each $i\in \omega $ . By applying (i), we may also conclude that B contains infinitely many $\omega $ chains given by $\{b_{i,j}\mid j\geq i\}$ for each $i\in \omega $ . In fact, it is not difficult to see that these are exactly all the $\omega $ chains in B.

In A, it is easy to see that there are infinitely many $\omega $ chains, given by $\{a_{i,j}\mid j\in \omega \}$ for each $i\in \omega $ . Since $g(x)$ is a total $\Delta _{3}^{0}$ function, for each $x\in \omega $ , there must be some $s_{x}\in \omega $ such that $P(x,s_{x})$ fires infinitely often. Applying (ii) from above, we may then obtain that the chains $\{d_{s_{x},j}\mid j\in \omega \}$ for each $x\in \omega $ are all $\zeta $ chains. Thus, A contains both infinitely many $\omega $ chains and also infinitely many $\zeta $ chains. We also note here that as a consequence of (ii), the only $\zeta $ chains in A are of the form $\{d_{s_{x},j}\mid j\in \omega \}$ for some $x\in \omega $ .

Let $h:A\to B$ be an isomorphism. To recover $g(x)$ , consider the following procedure. Compute $h^{-1}(c_{i,0})$ for each $i\leq x$ . Since h is an isomorphism, we obtain that $h^{-1}(c_{i,0})$ must also be contained in some $\zeta $ chain of A. Recall that the only $\zeta $ chains of A are of the form $\{d_{s_{y},j}\mid j\in \omega \}$ for some $y\in \omega $ . By pigeonhole principle, at least one of $h^{-1}(c_{i,0})=d_{s,j}$ for some j and s where $s\geq s_{x}$ . Let $s^{*}$ be the maximum of all such s obtained from $h^{-1}(c_{i,0})$ . Clearly, $s^{*}$ has the property that $\lim _{t}g^{*}(x,s^{*},t)=\lim _{t}g^{*}(x,s',t)$ for any $s'\geq s^{*}$ . Or equivalently, $\lim _{t}g^{*}(x,s^{*},t)=\lim _{s}\lim _{t}g^{*}(x,s,t)$ .

Given $s^{*}$ from above, compute $h(a_{i,0})$ for all $i\leq \langle x,s^{*}\rangle $ . Each of these images must be the left-most element of an $\omega $ chain in B. Since B only contains $\omega $ chains of the form $\{b_{\langle y,s\rangle ,j}\mid j\geq \langle y,s\rangle \}$ , we have that each $h(a_{i,0})=b_{\langle y,s\rangle ,t}$ for some $y,s,t\in \omega $ . Pick $t^{*}$ with the following properties:

• • $h(a_{i^{*},0})=b_{\langle y,s\rangle ,t^{*}}$ for some $i^{*}\leq \langle x,s^{*}\rangle $ , and

• • for any other $b_{\langle y',s'\rangle ,t'}=h(a_{i,0})$ , $\langle y',s'\rangle \leq \langle y,s\rangle $ .

By pigeonhole principle, it must be that $\langle x,s^{*}\rangle \leq \langle y,s\rangle $ , and by (i), $t^{*}$ has the property that for any $t\geq t^{*},\,g^{*}(x,s^{*},t^{*})=g^{*}(x,s^{*},t)$ . In conclusion, $g^{*}(x,s^{*},t^{*})=\lim _{t}g^{*}(x,s^{*},t)=\lim _{s}\lim _{t}g^{*}(x,s,t)$ . Since the procedure described above is clearly primitive recursive, $g\leq _{pr}h\oplus h^{-1}$ , and thus, $\operatorname {\mathrm {\texttt {PRCatSpec}}}(M)\subseteq \operatorname {\mathrm {\texttt {Cone}}}(\Delta _{3}^{0})$ . Theorem 2.4 is proved.

Proof. Fix some computable but not primitive recursive function g, let $\{\Psi _{e}\}_{e\in \omega }$ be a list of all primitive recursive schemes, and let $\{B_{e}\}_{e\in \omega }$ be a list of all punctual structures in the language of one unary function symbol. We construct d, a $\Delta _{2}^{0}$ function oracle, and a punctual injection structure $A=(\omega ,f_{A})$ , satisfying the following requirements:

$$ \begin{align*} P_{e}:&\,\Psi_{e}^{d}\neq g.\\ Q_{e}:&\,d\geq_{pr}q_{e}\oplus q_{e}^{-1}\text{ where }q_{e}:A\to B_{e}\text{ is an isomorphism, or }A\not\cong B_{e}. \end{align*} $$

Strategy for one $Q_{e}$ requirement: Fix some punctual structure $B_{e}$ with a single unary function. If such a function is ever discovered to not be injective, then $Q_{e}$ is trivially satisfied. We may thus assume that $B_{e}$ is an injection structure.

When the construction begins, we enumerate only finite orbits of some given size n. Although $B_{e}$ is punctual and should enumerate its elements ‘quickly’, we note that arbitrary $B_{e}$ could still be much ‘slower’ than the structure A defined by us. The intention here is obviously to use d to encode this delay. More specifically, since we only enumerate finite orbits of size n, if $B_{e}$ ever shows some orbit not of size n (or more generally if $B_{e}$ is not a substructure of A), then we will never enumerate such a size into our structure A, ensuring that $A\not \cong B_{e}$ . Thus, $B_{e}$ should eventually enumerate an orbit of size exactly n. Once it does so, we define $d(0)$ to be the stage number at which this happens. The intention here is that $d(j)$ encodes the stage number at which $B_{e}$ enumerates the j-th orbit enumerated into A.

Strategy for one $Q_{e}$ and infinitely many $P_{e}$ : Fix some infinite sequence of sizes $n_{0}<n_{1}<n_{2},\dots $ , and begin the strategy for $Q_{e}$ as described previously. Enumerate only orbits of size $n_{0}$ and define $d(j)$ to be the stages at which $B_{e}$ enumerates a suitable $q_{e}$ -image for the j-th orbit in A. Repeat this process until $\Psi _{0}^{d}\neq g$ is witnessed. Since g is not primitive recursive and d currently contains only primitive recursive information, $\Psi _{0}^{d}\neq g$ must be witnessed at some finite stage $s_{0}$ . Once such a stage is reached, we define $d(s_{0})[s_{0}]=0$ . The idea is that $d(s_{0})$ should encode a stage large enough such that $B_{e}$ contains $A[s_{0}]$ as a substructure. As long as $A[s_{0}]$ is not a substructure of $B_{e}$ , $d(s_{0})$ remains at $0$ .

Suppose that for all $j<i$ , we have defined $s_{j}$ , and $\Psi _{j}^{d}\neq g$ is witnessed by the initial segment $d\restriction s_{j}$ . We now begin enumerating only orbits of size $n_{i}$ into our structure A. Just as before, if it is discovered that $B_{e}$ is not a substructure of A, then $Q_{e}$ will be satisfied by keeping $A\not \cong B_{e}$ . Similarly, $d(s_{i-1}+k)$ will encode the stage at which the k-th orbit of size $n_{i}$ is enumerated into $B_{e}$ . Continue this process until it is discovered that $\Psi _{i}^{d}\neq g$ . Since d consists of only primitive recursive information (with finitely many exceptions, i.e., $d(s_{j})$ for each $j<i$ ) and g is not primitive recursive, $\Psi _{i}^{d}\neq g$ must be witnessed at some finite stage $s_{i}$ . We may then recursively repeat this procedure as described above, defining $d(s_{i})[s_{i}]=0$ and enumerating orbits of size $n_{i+1}$ into A.

However, for $i>0$ , the failure of $\Psi _{i}^{d}$ to compute g is witnessed by the initial segment $d\restriction s_{i}$ . In particular, this initial segment includes $d(s_{j})$ for $j<i$ . At stages s where $A[s_{j}]$ is discovered to be a substructure of $B_{e}$ , the value of $d(s_{j})$ changes from $0$ to s, possibly changing the computation in such a way that $\Psi _{i}^{d}$ now looks to be equal to g. When this happens, we initialise all requirements $P_{k}$ for $k>j$ and return to enumerating only orbits of size $n_{j+1}$ and restarting our definition of $s_{k}$ for all $k>j$ . Clearly, each $P_{i}$ can only be initialised if $d(s_{j})$ changes for some $j<i$ , and thus each $P_{i}$ will be initialised only finitely often.

The general strategy: We order the requirements $Q_{0},P_{0},Q_{1},P_{1},\dots $ . During the construction, we maintain $n_{0}<n_{1}<\dots $ and $s_{0}<s_{1}<\dots $ as distinct sets of markers with the usual rules; whenever $n_{i}$ or $s_{i}$ changes, all $n_{j}$ or $s_{j}$ for $j>i$ will be kicked to some value $>n_{i}$ or $>s_{i}$ , respectively. As described earlier, we begin by enumerating orbits of size $n_{0}$ into A and record the stages at which these orbits are enumerated into $B_{0}$ . At each stage s of the construction, as long as $\Psi _{0}^{d\restriction s}=g$ , we kick $s_{i}$ for all $i\geq 0$ and define $s_{0}=s+1$ . Once $\Psi _{0}^{d\restriction s}\neq g$ is witnessed, let $s_{0}=s$ and define $d(s_{0})=0$ .

Suppose now that we have currently witnessed $\Psi _{j}^{d\restriction s_{j}}\neq g$ for each $j<i$ . We will attend to $Q_{0},Q_{1},\dots ,Q_{i}$ and $P_{i}$ in subsequent stages. Similar to before, we enumerate only orbits of size $n_{i}$ while waiting for the stage s such that $\Psi _{i}^{d\restriction s}\neq g$ . As long as $\Psi _{i}^{d\restriction s}=g$ , we kick $s_{k}$ for all $k\geq i$ at stage s. For inputs $x>s_{i-1}$ , we use $d(x)$ to record the stage at which the $(x-s_{i-1})$ -th orbit of size $n_{i}$ is enumerated into the structures $B_{0},B_{1},\dots ,B_{i}$ . More specifically, we define $d(s_{i-1}+k)$ to be an $(i+1)$ -tuple, where each bit is the stage at which $B_{j}$ enumerates the k-th ( $>0$ ) orbit of size $n_{i}$ for each $j\leq i$ . We continue this process until the first stage s where one of the following happens:

• • If $\Psi _{i}^{d\restriction s}\neq g$ , then define $d(s_{i})[s]$ to be the all zero i-tuple, and proceed to attend to $Q_{0},Q_{1},\dots ,Q_{i+1}$ , and begin the process to find $s_{i+1}$ .

• • For some $j<i$ , $A[s_{j}]$ is discovered to be a substructure of $B_{k}$ for some $k\leq j$ at stage s. At such a stage s, change the k-th bit of $d(s_{j})$ to s (recall that $d(s_{j})$ is a j-tuple), define $s_{j+1}=s+1$ and initialise the requirements $P_{j'},Q_{j'}$ for all $j'>j$ . Then return to attending to $Q_{0},Q_{1},\dots ,Q_{j+1}$ and restart the process to find $s_{j+1}$ .

Intuitively, the first case is when we manage to successfully define $s_{i}$ without any changes to $d\restriction s_{i-1}$ . The latter case is where some change is made in $d\restriction s_{i-1}$ before finding $s_{i}$ . When this happens, we return to the strategy for attending to the Q-requirements with indices $\leq j+1$ , and $P_{j+1}$ for the largest j where $d\restriction s_{j}$ did not change. We then also restart the definition of $d(x)$ for $x>s_{j}$ . Note that this does not injure the strategy for $Q_{0},\dots ,Q_{j}$ at all; we only need ensure that d computes an isomorphism between A and $B_{k}$ for $k\leq j$ . Therefore, only the strategies for the requirements $P_{j'}$ for $j'>j$ are ‘injured’ by this action.

There is an additional point to note when we have multiple $Q_{e}$ requirements. Recall that for a single $Q_{e}$ , if for some k, $B_{e}$ reveals more orbits of size k than A currently contains, then we are able to permanently keep $A\not \cong B_{e}$ . However, the different $Q_{e}$ might possibly interact in a way that ‘damages’ our strategy of recovering an isomorphism from d. In particular, the information we have encoded into d is not quite sufficient; we need to be able to compute where each structure $B_{e}$ places the orbits of size k for $n_{j}<k<n_{j+1}$ (which might have been enumerated into A before k is restrained from A). Thus, we shall also track the stages $t_{e}$ at which we ‘act’ for $Q_{e}$ (see the construction for the definition). If we never do so, then let $t_{e}\uparrow $ . Otherwise, $d(s_{j})$ will also encode the stage at which $A[t_{j+1}]$ becomes a substructure of $B_{l}$ for various $l\leq j$ . Since $A[t_{j+1}]$ being a substructure of $B_{l}$ is c.e., it is easy to see that the ‘injury’ to the P-requirements remain finite. (Recall that Q-requirements are never injured.)

Construction: Each stage of the construction could possibly last for a non-primitive recursive amount of time. During the construction, we also track sub-stages; stages of primitive recursive time at which we enumerate new elements into A.

At stage $0$ , define $n_{i}[0]=i+1$ and $s_{i}=i$ for each $i\in \omega $ . Begin enumerating orbits of size $n_{0}[0]$ into A, and do the following:

1. (i) If $B_{0}$ remains a substructure of A, then within primitive recursive time, $B_{0}$ must enumerate the first orbit of size $n_{0}[0]$ . When it does so, we record the sub-stage at which this happens using $d(0)$ .

2. (ii) If $B_{0}$ is not a substructure of A, then define $d(0)=0$ . Since $n_{0}$ is currently $1$ , and A only contains orbits of size $n_{0}[0]$ , in order for $B_{0}$ to not be a substructure of A, one of the following must happen:

   • • $B_{0}$ enumerates an orbit which has yet to close. By ensuring that our structure has no infinite orbits, $B_{0}$ can only be isomorphic to A if all orbits of $B_{0}$ are also finite. Thus, any orbit enumerated by $B_{0}$ has to eventually close. That is, we need not consider orbits which do not close.

   • • $B_{0}$ enumerates a (closed) orbit of size $k>n_{0}[0]$ . Then define $n_{0}[1]$ to be some number $>k$ , kicking all subsequent $n_{j}$ for $j>0$ . Throughout the construction, we shall only enumerate orbits of size $n_{i}[s]$ for some i at each stage s of the construction. This ensures that we shall never enumerate any orbit of size k into A, as $k<n_{0}[1]\leq n_{0}[s]<n_{1}[s]<\dots $ for all $s>0$ .

   • • $B_{0}$ enumerates more orbits of size $n_{0}$ than A. Then we similarly define $n_{0}[1]$ to be a fresh number. In subsequent stages of the construction, we will never enumerate any orbit of size $n_{0}[0]$ .

   If $n_{0}$ is defined to be some fresh number by an action above, then we say to have acted for $Q_{0}$ , and define $t_{0}$ to be the sub-stage at which we did so.

Once we have succeeded in defining $d(0)$ , proceed to stage 1.

At stage s, we say that

• • $Q_{i}$ requires attention if we have never acted for $Q_{i}$ (to be defined later), and there is some orbit of size $k\geq n_{i}[s]$ , such that $B_{i}$ contains more orbits of size k than A, and

• • $P_{i}$ requires attention if $\Psi _{i}^{d\restriction s}$ is currently equal to g.

In addition, if we have acted for $Q_{i}$ , then let $t_{i}$ be the sub-stage at which we did so. At the beginning of stage s, for any $i\geq 0$ and $j\leq i$ such that $s_{i}<s$ and we have yet to act for $Q_{j}$ , do the following:

• • If $t_{i+1}$ is defined, and the structures $A[s_{i}]$ and $A[t_{i+1}]$ are both substructures of $B_{j}$ , then define the j-th bit of $d(s_{i})$ to be the sub-stage at which this was first witnessed. Otherwise, let the j-th bit of $d(x)$ for all $x>s_{i-1}$ be $0$ .

• • If $t_{i+1}$ is undefined, then we only check whether $A[s_{i}]$ is a substructure of $B_{j}$ . If it is, then define the j-th bit of $d(s_{i})$ to be the first sub-stage at which it was witnessed. Otherwise, define the j-th bit of $d(x)$ for all $x>s_{i-1}$ to be $0$ .

Once all such changes are made, let i be the least for which $Q_{i}$ or $P_{i}$ requires attention.

If it was $Q_{i}$ which required attention, then define $n_{i}[s+1]$ to be some fresh number, and proceed to stage $s+1$ . We then say that we have acted for $Q_{i}$ and define $t_{i}$ to be the current sub-stage.

If it was $P_{i}$ which required attention, then define $s_{i}=s+1$ and define $d(x)$ for all $s_{i-1}<x<s_{i}=s+1$ as follows. While attempting to define $d(x)$ , we enumerate only orbits of size $n_{i}[s]$ into A. Let $j\leq i$ be given.

1. (i) Define the j-th bit of $d(x)$ to be $0$ if one of the following holds:

   • • $B_{j}$ is currently not a substructure of A. To be more specific, this means that there is some finite size k such that $B_{j}$ currently has more orbits of size k than A does.

   • • The j-th bit of $d(y)$ is currently $0$ for some $y<x$ . Intuitively, this means that $B_{j}$ currently does not look isomorphic to A.

   • • We have acted for $Q_{j}$ at some earlier stage. In fact, once we have acted for $Q_{j}$ , let the j-th bit of $d(x)$ for all $x>s_{j-1}$ be $0$ .

   In the following cases, we may thus assume that none of the above hold.

2. (ii) Define the j-th bit of $d(x)$ to be the sub-stage at which the $(x-s_{i-1})$ -th orbit of size $n_{i}[s]$ is enumerated into $B_{j}$ . Since $B_{j}$ is punctual, it has to enumerate new elements primitive recursively. In addition, new orbits either grow in size quickly or close and reveal their final size. Applying this with the fact that there are only a fixed number of orbits of size $<n_{i}[s]$ currently in A, and we are only enumerating orbits of size $n_{i}[s]$ into A, after some primitive recursive delay, one of the following must happen:

   • • $B_{j}$ enumerates the $(x-s_{i-1})$ -th orbit of size $n_{i}[s]$ . As mentioned earlier, we record the sub-stage at which this happens in the j-th bit of $d(x)$ .

   • • There is some $k\geq n_{j}[s]$ such that $B_{j}$ has more orbits of size k than A does. That is, $Q_{j}$ would require attention at the next stage, and if acted for, we claim that we never again enumerate any orbits of size k (to be verified later).

   • • There is some $k<n_{j}[s]$ such that $B_{j}$ has more orbits of size k than A does. In this case, we cannot forcefully kick higher priority $n_{j'}[s]\leq k$ for the sake of $Q_{j}$ . We instead ensure that each size appears only finitely often in A, meaning that we can non-uniformly fix $q_{j}^{-1}:B_{j}\to A$ on all orbits of size $<n_{j}$ , allowing us to satisfy $Q_{j}$ via computing $q_{j}\oplus q_{j}^{-1}$ from d (verified below). In the meantime, define the j-th bit of $d(y)$ to be $0$ for each $y>s_{j-1}$ .

Once we have successfully defined $d\restriction (s+1)$ , then proceed to stage $s+1$ .

Verification: We first make some preliminary observations. Notice that each $n_{e}$ only changes if $n_{e'}$ for some $e'<e$ changes, or we acted for $Q_{e}$ during the construction. Since we only act at most once for each $Q_{e}$ , it is easy to see that each $n_{e}$ stabilises eventually.

To see that d is $\Delta _{2}^{0}$ , observe that for each $x\in \omega $ , and for each $s_{i}$ , exactly one of $x>s_{i}$ , or $x\leq s_{i}$ is true for cofinitely many stages of the construction. Note that this is simply a consequence of how each $s_{i}$ only increases when it is changed, and that we do not claim or require that $s_{i}$ stabilises here. For a given x, since $x=s_{x}[0]$ , there exists a least i for which $x\leq s_{i}$ for cofinitely many stages. As a result, $d(x)$ must be an $(i+1)$ -tuple. For such an i, there is a stage $s^{*}$ such that $n_{i}$ never again changes after stage $s^{*}$ . We may further assume inductively that $s^{*}$ is also such that $d\restriction x$ never changes after $s^{*}$ . We argue that each bit of $d(x)$ stabilises. Fix some $j\leq i$ and consider the j-th bit of $d(x)$ :

• • If there is some $y<x$ such that the j-th bit of $d(y)$ is $0$ , then the j-th bit of $d(x)$ will also be defined to be $0$ . Furthermore, by the assumption that $d\restriction x$ never again changes after stage $s^{*}$ , the j-th bit of $d(x)$ will forever remain at $0$ .

• • We may thus suppose that the j-th bit of $d(y)$ is always $>0$ for each $y<x$ . We further split into the cases where either $x<s_{i}$ or $x=s_{i}$ . For $x<s_{i}$ , recall that the j-th bit of $d(x)[s]$ either records the sub-stage at which $B_{j}$ enumerates the $(x-s_{i-1})$ -th orbit of size $n_{i}[s]$ , or records $0$ if $B_{j}$ was discovered to not be a substructure of A at stage s. This means that there is some k such that $B_{j}[s]$ contains more orbits of size k than $A[s]$ does. There are then two further possibilities:

  • – If $k\geq n_{j}[s]$ , then we must have already acted for $Q_{j}$ , otherwise $n_{j}[s+1]\neq n_{j}[s]$ a contradiction to the assumption that $n_{i}$ , and thus $n_{j}$ , has already stabilised. However, if we have already acted for $Q_{j}$ , then the j-th bit of $d(y)$ for all $y>s_{j-1}$ is always defined to be $0$ . In particular, we obtain that the j-th bit of $d(x)$ remains at $0$ for the remainder of the construction as $x>s_{i-1}\geq s_{j-1}$ for any $j\leq i$ .

  • – If $k<n_{j}[s]$ , then recall from the construction (stage s (ii)) that the j-th bit of $d(x)$ is also defined to be $0$ . We claim that it never again changes after stage $s^{*}$ . Suppose for a contradiction that it does. Then that implies that we must have enumerated new orbits of size k into A, allowing $B_{j}$ to become a substructure of A. This means that k is necessarily $n_{l}[s]$ for some $l<j$ . However, this further implies that at some stage $t>x$ , we returned to attending to $P_{l}$ ; meaning that $s_{l}>x$ , a contradiction to the assumption that $i>l$ is the least for which $s_{i}\geq x$ for cofinitely many stages.

  For $x=s_{i}$ , the j-th bit of $d(x)$ records one of the following:

  • – the sub-stage at which $A[s_{i-1}]$ becomes a substructure of $B_{j}$ , or

  • – the sub-stage at which $A[t_{i}]$ becomes a substructure of $B_{j}$ , provided $t_{i}$ is defined and larger than $s_{i-1}$ , or

  • – $0$ otherwise.

  It is easy to see that the first two points are c.e. events once $s_{i-1}$ has stabilised and $t_{i}$ has been defined if ever. Thus, $d(x)$ never changes after some finite stage.

In conclusion, we have that each $n_{e}$ eventually stabilises, and that d is a $\Delta _{2}^{0}$ function. We are now ready to prove that $P_{e}$ and $Q_{e}$ are satisfied.

Each $P_{e}$ is satisfied: We proceed by induction on $e\in \omega $ and show that $s_{e}$ eventually stabilises at some finite value. Let e be the least such that $s_{e}$ changes infinitely often. From the construction, $s_{e}$ only changes if either $Q_{e}$ or $P_{e}$ requires attention or some $s_{e'}$ where $e'<e$ changes. Since e is assumed to be the least for which $s_{e}$ changes infinitely, then we may assume that either $Q_{e}$ or $P_{e}$ requires attention infinitely often:

• • Recall that $Q_{e}$ can only require attention at stage s if we have never acted for it. In particular, since $s_{e}$ is the least which changes infinitely often, $Q_{e}$ must eventually be the highest priority requirement which requires attention. At such a stage, we would have acted for $Q_{e}$ , and it will never again require attention in the construction. We may thus suppose that it is $P_{e}$ which requires attention infinitely often.

• • Suppose that $P_{e}$ requires attention infinitely often. Let $s^{*}$ be a stage large enough such that all of the following hold:

  • – $s_{0},s_{1},\dots ,s_{e-1}$ and $n_{0},n_{1},\dots ,n_{e}$ have all stabilised.

  • – $d(x)$ for all $x\leq s_{e-1}$ does not change after stage $s^{*}$ .

  • – $P_{e}$ requires attention at stage $s^{*}$ .

  By our assumption that e is the least for which $s_{e}$ changes infinitely and the earlier observations, such an $s^{*}$ must exist.

  If there is some stage $s>s^{*}$ at which $P_{e}$ does not require attention, then we claim that $P_{e}$ never again requires attention. Let s denote the first stage after $s^{*}$ at which $P_{e}$ does not require attention. Similarly, let $s'$ denote the first stage after s at which $P_{e}$ again requires attention. Recall that $P_{e}$ requires attention at some stage iff $\Psi _{e}$ temporarily computes g with the current d. More specifically, we have that $\Psi _{e}^{(d\restriction s)[s])}\neq g$ , $\Psi _{e}^{(d\restriction s')[s']}=g$ , and at some stage $s"$ between s and $s'$ , $d(x)[s"]\neq d(x)[s"+1]$ for some $x<s$ . It follows from the construction that $s_{e}[s]=s$ , and by the choice of $s^{*}$ , we obtain that $s_{e-1}<x<s_{e}[s"]$ . For each such x, $d(x)$ records either $0$ in the j-th bit or the sub-stage at which $B_{j}$ enumerates the $(x-s_{e-1})$ -th orbit of size $n_{e}$ . Consider the following cases:

  • – If the j-th bit of $d(x)[s]$ is non-zero, then it means that $B_{j}$ has enumerated the $(x-s_{e-1})$ -th orbit of size $n_{e}$ . Since $B_{j}$ is punctual, this enumeration cannot be ‘undone’, and the j-th bit of $d(x)$ cannot change unless the j-th bit of $d(y)$ changes to $0$ for some $y<x$ . By choice of $s^{*}$ such a y must be larger than $s_{e-1}$ , as $d\restriction (s_{e-1}+1)$ is assumed to have stabilised. But the j-th bit of $d(y)$ records the sub-stage at which $B_{j}$ enumerates the $(y-s_{e-1})$ -th orbit of size $n_{e}$ . This means that the j-th bit of $d(y)$ cannot possibly be $0$ .

  • – As noted above, if there is some $y<x$ such that the j-th bit of $d(y)$ is $0$ , then the j-th bit of $d(x)$ will similarly be $0$ . We may thus assume that x is the least for which the j-th bit of $d(x)[s]$ is $0$ . An analysis of the actions in the construction allows one to easily conclude that this can only happen if there is some $k\in \omega $ such that $B_{j}[s]$ contains more orbits of size k than A. Obviously, $k<n_{j}\leq n_{e}$ , otherwise, we would have acted for $Q_{j}$ at some stage after $s^{*}$ , contradicting the assumption that $n_{j}$ has stabilised. Note that we could not have acted for $Q_{j}$ before $s^{*}$ , otherwise the j-th bit of $d(y)$ would be $0$ for all $y\geq s^{*}$ (by definition of $d(x)$ ).

  In other words, $d(x)[s]$ once defined, never changes again for each $x<s$ , implying that $g\neq \Psi _{e}^{(d\restriction s)[s]}=\Psi _{e}^{d\restriction s}$ . That is, $P_{e}$ never again requires attention after stage s, contradicting the assumption that it requires attention infinitely often. Thus, we may assume that for all stages after $s^{*}$ , $P_{e}$ always requires attention.

  In addition, recall that we may discover in primitive recursive time whether $B_{j}$ enumerates the $(x-s_{e-1})$ -th orbit of size $n_{e}$ , or enumerates more orbits of size k than A does for some $k<n_{e}$ . Thus, for each $x>s_{e-1}$ , $d(x)$ can be computed primitive recursively. But this implies that $\Psi _{e}^{d}=g$ , contradicting the assumption that g is not primitive recursive. Therefore, $P_{e}$ cannot require attention for infinitely many stages.

It follows immediately that for each e, $P_{e}$ is satisfied as $\Psi _{e}^{d\restriction s_{e}}\neq g$ , and thus $\Psi _{e}^{d}\neq g$ .

Each $Q_{e}$ is satisfied: During the construction, note that we enumerate orbits of size $n_{e}$ only at stages where $P_{e}$ is the highest priority requirement which requires attention. Using the observation that $s_{e}$ also stabilises eventually, it follows that after stage $s_{e}$ , we never enumerate any orbit of size $k\leq n_{e}$ into A. Therefore, A only consists of finitely many orbits of size k for each $k\in \omega $ .

It remains to argue that each $Q_{e}$ is satisfied. Since each $n_{e}$ stabilises at a finite value and we only ever enumerate orbits of size $n_{e}[s]$ for some $e,s$ , A contains no infinite orbits. We may thus assume that $B_{e}$ also contains no infinite orbits, as $B_{e}$ cannot possibly be isomorphic to A otherwise. We split the proof into two cases as follows.

First, suppose that at some finite stage s, we acted for $Q_{e}$ . Recall that this means that at stage s, $Q_{e}$ is the highest priority requirement which required attention. In particular, we have yet to act for $Q_{e}$ at stage s, and there is some orbit of size $k\geq n_{e}[s]$ such that $B_{e}$ contains more orbits of size k than A. We claim that after we act for $Q_{e}$ , no more orbits of size k will be enumerated into A, thus preserving $B_{e}\not \cong A$ . When we act for $Q_{e}$ , we define $n_{e}$ to be some fresh number at stage s, and kick all subsequent $n_{e'}$ for $e'>e$ . That is to say, $k<n_{e'}[s']$ for each $e'\geq e$ and $s'>s$ . By the properties of the markers $n_{i}$ , we also have that $n_{i}[s]<n_{e}[s]\leq k$ for each $i<e$ , and thus $k\neq n_{i}[s]$ . Therefore, if we never act for any $Q_{i}$ for $i<e$ after stage s, $B_{e}$ cannot possibly be isomorphic to A, as no more orbits of size k are ever enumerated. On the other hand, if there is some stage $s'>s$ during which we act for $Q_{i}$ where $i<e$ , $n_{i}$ is similarly defined to be a fresh number at such a stage $s'$ . This once again ensures that $n_{i}[s"]>k$ for any $i\in \omega $ and any $s">s'$ . In conclusion, once we have acted for $Q_{e}$ , we never again enumerate any orbit of size k into A.

Now suppose that we never act for $Q_{e}$ during the construction. If $Q_{e}$ requires attention at infinitely many stages, then there must be some finite stage during which we act for it. Thus, there must be some stage s after which $Q_{e}$ never again requires attention. In particular, after such a stage, we must have that $B_{e}$ is always a substructure of A; as long as we are able to define $q_{e}:A\to B_{e}$ on orbits enumerated into A after such a stage, $q_{e}^{-1}$ is naturally also primitive recursive. We fix such a stage as $s^{*}$ , and define $q_{e}:A\to B_{e}$ as follows. Let k be the largest such that there is an orbit of size k in $B_{e}$ at stage $s^{*}$ . In addition, let $i\geq e$ be the least such that $n_{i}>k$ . Observe that after stage $s_{i}$ in the construction, we never enumerate any orbit of size $<n_{i}$ . In particular, by non-uniformly fixing $q_{e}$ on $A\restriction s_{i}$ , we need only define $q_{e}$ on orbits of size $\geq n_{i}>k$ .

Let $a_{0},a_{1},\dots $ , be the orbits enumerated into A after stage $s_{i}$ . We further assume that for each stabilising value of $n_{j}$ , we enumerate at least one orbit of size $n_{j}$ into A. In particular, for each $j\in \omega $ , $a_{j}$ has size at most $n_{i+j}$ . For convenience, we refer to $d(s_{j})$ for $j\in \omega $ as the special entries of d, and call $d(x)$ for all other x as the non-special entries. Note that we do not truly need to differentiate between the two; this definition is made purely for ease of argument. Define the primitive recursive scheme computing $q_{e}$ from d as follows. Given $j\in \omega $ , compute $d(x)$ for each $x\geq s_{i}$ until we have computed $d(s_{i}+2(j+1)+1)$ . Since each entry is either special or non-special, this process guarantees that we must either have computed d on at least $j+2$ many special entries, or at least $j+2$ many non-special entries.

We shall argue that by the sub-stage given by the maximum of the e-th bit of the various $d(x)$ computed by the procedure above, an appropriate $q_{e}$ image for $a_{j}$ must have been enumerated into $B_{e}$ . Consider the cases as follows:

• • Suppose that we have computed at least $j+2$ many special entries of d. That is, we have computed d on the entries $s_{i}<s_{i+1}<\dots <s_{i+j+1}\leq s_{i}+ 2(j+1)+1$ . Since $a_{j}$ has size at most $n_{i+j}$ , and all such orbits must have been enumerated into A before stage $s_{i+j+1}$ , then it follows that the e-th bit of $d(s_{i+j+1})$ encodes a sub-stage large enough such that $A[s_{i+j+1}]$ has become a substructure of $B_{e}$ , providing an appropriate $q_{e}$ image for $a_{j}$ .

• • Suppose that the previous case does not hold. That is, there exists $k\leq j$ such that $s_{i+k}\leq s_{i}+2(j+1)+1<s_{i+k+1}$ . From the assumption earlier that there is at least one orbit of size $n_{l}$ for each $l\in \omega $ , $a_{j}$ must have size $<n_{i+k+1}$ . If $a_{j}$ has size $<n_{i+k}$ , then using the same argument as before, the sub-stage at which a $q_{e}$ image for $a_{j}$ is enumerated into $B_{e}$ happens before the sub-stage given by the e-th bit of $d(s_{i+k})$ . In addition, if $a_{j}$ has size $>n_{i+k}$ , then $t_{i+k+1}\downarrow $ and $a_{j}$ must have been enumerated into A by stage $t_{i+k+1}$ . Recall that if $t_{i+k+1}\downarrow $ , then the e-th bit of $d(s_{i+k})$ is at least as big as the sub-stage at which $A[t_{i+k+1}]$ becomes a substructure of $B_{e}$ . Therefore, we may find an appropriate $q_{e}$ image for $a_{j}$ by such a sub-stage.

  We may thus assume that $a_{j}$ has size exactly $n_{i+k}$ . Applying the case assumption, we also obtain that we have computed d on at least $j+2$ many non-special entries, denoted by $x_{0}<x_{1}<\dots <x_{j+1}$ . Recall that on non-special entries, the e-th bit in $d(x)$ is a sub-stage at which $B_{e}$ enumerates the $(x-s_{l})$ -th orbit of size $n_{l}$ , where l is the largest such that $s_{l}<x$ . Therefore, each of the e-th bits of $d(x_{0}),d(x_{1}),\dots ,d(x_{j+1})$ , should encode the sub-stage at which some orbit of size $n_{l}$ enters $B_{e}$ for some $l\geq i$ . Since $a_{j}$ is the $(j+1)$ -st orbit of size $\geq n_{i}$ to be enumerated into A, it follows that at least one of the e-th entries of $d(x_{0}),d(x_{1}),\dots ,d(x_{j+1})$ , gives a sub-stage large enough at which an appropriate $q_{e}$ image for $a_{j}$ must have been enumerated into $B_{e}$ .

Thus, provided that $B_{e}\cong A$ , that is, the e-th bit of $d(x)$ is non-zero for all $x\geq e$ , we may primitive recursively compute an isomorphism $q_{e}:A\to B_{e}$ and its inverse using d. Theorem 3.1 is proved.

Proof. Let W be a non-recursive c.e. set and let $\{\Psi _{i}\}_{i\in \omega }$ and $\{A_{n}\}_{n\in \omega }$ be listings of all primitive recursive schemes and all punctual structures, respectively. We construct a total function $f:\omega \to \{0,1\}$ such that $f\equiv _{T}W$ and satisfying the following requirements:

$$ \begin{align*} R_{i,j,m,n}:&\text{ If }\Psi_{i}^{f}:A_{m}\to A_{n}\text{ and }\Psi_{j}^{f}:A_{n}\to A_{m}\text{ are isomorphisms such that }\\ & \Psi_{i}^{f}\circ\Psi_{j}^{f}\text{ is the}\text{ identity map, then }A_{m}\text{ and }A_{n}\text{ are punctually isomorphic.} \end{align*} $$

An initial description: To construct $f\equiv _{T}W$ , we use a standard permitting technique. Throughout the construction, there will be a set of markers $\{m_{0}<m_{1}<\dots \}\subseteq \omega $ such that $f(m_{i})=W(i)$ , and a marker $m_{i}$ may be moved during stages at which some $j<i$ is enumerated into W. This ensures that $W\leq _{T}f$ (to be proved later). To obtain $f\leq _{T}W$ , we will only change $f(x)$ at stage s if some $y\leq x$ is enumerated into W at stage s.

We now turn our attention to the requirements $R_{i,j,m,n}$ . Let $i,j,m,n\in \omega $ be given. The oracle f begins as the all $0$ function. For a single requirement $R_{i,j,m,n}$ , we maintain a pointer p which tracks the value at which $R_{i,j,m,n}$ is currently searching for an error; let $f^{*}:= (f\restriction p)^{\frown }1^{\omega }$ and check if both of the following holds:

• • $\Psi _{i}^{f^{*}}\circ \Psi _{j}^{f^{*}}$ is the identity.

• • $\Psi _{i}^{f^{*}}$ and $\Psi _{j}^{f^{*}}$ are both injective and preserve all functions and relations in the signature of $A_{m}$ and $A_{n}$ .

If no error is ever found at this value of p, then $\Psi _{i}^{f^{*}}$ must be a punctual isomorphism from $A_{m}$ to $A_{n}$ , since $f^{*}$ is clearly primitive recursive. On the other hand, if one of the conditions does not hold, it must be witnessed at some finite stage s with the oracle $f^{*}\restriction s$ . By changing $f\restriction s$ to $f^{*}\restriction s$ , and provided that $f\restriction s$ never again changes, this failure of one of the above conditions will be preserved, thus ensuring that $R_{i,j,m,n}$ is satisfied.

In order to stay consistent with the permitting strategy, permission must be provided by W for $f\restriction s$ to change. That is, some $x\leq p$ has to enter W at some stage after the error for $R_{i,j,m,n}$ is found in order for $f(y)$ , where $p\leq y<s$ , to change. For a fixed p, permission might never be obtained. To circumvent this, $R_{i,j,m,n}$ should search for errors at multiple locations. More specifically, for the strategy of $R_{i,j,m,n}$ , we also attempt to define a computable function $g_{e}$ , where $e=\langle i,j,m,n\rangle $ as follows. At each stage s of the construction, p will ‘point’ to some marker $m_{x}$ . Once an error for $R_{i,j,m,n}$ has been found at (the current value of) $m_{x}$ , define $g_{e}(x)$ to also be the current value of $W(x)$ . Then ‘point’ p to the marker $m_{x+1}$ and repeat the process. The function $g_{e}$ as defined is clearly computable, and provided that errors are always successfully found at each $m_{x}$ , $g_{e}$ will also be total. Since W is non-recursive, there must be some x at which x enters W at a stage after an error was found for $R_{i,j,m,n}$ at $m_{x}$ , thus allowing us to act for $R_{i,j,m,n}$ by changing the oracle f.

As the strategy of each requirement $R_{i,j,m,n}$ only depends on whether an error can be found, we use the pairing function, letting $e=\langle i,j,m,n\rangle $ , and simply refer to $R_{i,j,m,n}$ as $R_{e}$ . Similarly, $p_{e}$ and $g_{e}$ will, respectively, be the pointer and computable function associated with the strategy for $R_{e}$ .

The general strategy and injury: The priority of the requirements will be arranged as $R_{0},R_{1},\dots $ . Since the values of the markers are dynamic, when we say that $p_{e}$ points to $m_{x}$ , this means that the value of $p_{e}$ copies $m_{x}$ as it changes. At each stage of the construction, $R_{e}$ will always be searching for errors using $f_{e}:= (f\restriction p_{e})^{\frown }1^{\omega }$ . Once an error is found, define $g_{e}(x)$ to be the current value of $W(x)$ where x is such that $p_{e}$ currently points to $m_{x}$ . Also let $p_{e}$ now point to $m_{x+1}$ . As discussed in the initial description of the strategy, there is either some x for which no error is ever found for $R_{e}$ at x or x eventually enters W, providing permission for $R_{e}$ to act.

While the strategy for $R_{e}$ is being pursued, one of the following could happen:

• • The value of $m_{x}$ at which $R_{e}$ previously found an error changes.

• • The value of $m_{x}$ at which $p_{e}$ is currently pointing changes.

• • The oracle changes value at y for some $y<p_{e}$ .

In the above scenarios, it is evident that any potential satisfaction found for $R_{e}$ may now become undone, and we say that $R_{e}$ is injured. However, we shall show that in each of the above scenarios, progress in the strategy of a higher priority $R_{e'}$ must have been made. To give a brief description of why this is so, recall that $m_{x}$ changes only if some $x'<x$ enters W. In particular, W has just provided permission to change $f(y)$ for any $y\geq x'$ . That is, any $R_{e'}$ which had earlier found an error at $m_{x'}$ now has permission to act. As long as we arrange the construction such that such an $R_{e'}$ must be of higher priority or $e'=e$ , it is clear that the potential injury is finite. To this end, throughout the construction, $p_{e}<p_{e'}$ if $e<e'$ . In addition, for each x such that $p_{e}<m_{x}<p_{e'}$ , it must be that $R_{e'}$ has found an error at $m_{x}$ .

Construction: During the construction, each requirement $R_{e}$ will be declared either satisfied or unsatisfied. At the start of the construction, for each $e\in \omega $ , let $m_{e}[0]=e$ , point each $p_{e}$ at $m_{e}$ , and declare $R_{e}$ to be unsatisfied. Also define $f(x)=0$ for all $x\in \omega $ . At each stage s of the construction, do the following.

1. Step 1: For each $e\leq s$ such that $R_{e}$ is currently unsatisfied, search for an error for $R_{e}$ at $p_{e}$ with the oracles $(f\restriction p_{e})^{\frown }1^{s-p_{e}}$ , and run each computation till stage s.

2. Step 2: Let e be the least such that $R_{e}$ has found an error at $p_{e}$ and $R_{e}$ is currently unsatisfied. If no such e exists, then proceed to Step 3. Otherwise, let x be such that $p_{e}$ is currently pointing at $m_{x}$ . Then define $g_{e}(x)=W(x)[s]$ , and let $p_{e}$ now point to $m_{x+1}$ . For each $e'>e$ , declare $R_{e'}$ to be unsatisfied, define $g_{e'}(y)\uparrow $ for each $y\in \omega $ , and point $p_{e'}$ to $m_{x+1+e'-e}$ . For convenience, we refer to this action as initialising $R_{e'}$ .

3. Step 3: Let e be the least such that $R_{e}$ has found an error at $m_{x}[s]$ for which x has just entered W. Then define $f\restriction s$ to be $(f\restriction m_{x})^{\frown }1^{s-m_{x}}$ , declare $R_{e}$ to be satisfied, and initialise $R_{e'}$ for each $e'>e$ . Also for each $x'\geq x$ , define $m_{x'}[s+1]$ to be the least number $\geq s$ and $\neq m_{x"}[s+1]$ for any $x"<x'$ . Notice that f on all such inputs is currently $0$ . For each $x'\geq x$ that is currently contained in W, define $f(m_{x'}[s+1])=1$ .

Verification: To verify that the construction works, we prove the following statements:

1. (i) For each $x\in \omega $ , the value of $m_{x}:= \lim _{s}m_{x}[s]$ never changes after the stage s for which $W[s]\restriction x=W\restriction x$ , and $f(m_{x})=W(x)$ .

2. (ii) For each $e\in \omega $ , there is some $x_{e}\in \omega $ such that $p_{e}$ points at $m_{x_{e}}$ for cofinitely many stages.

Let $x\in \omega $ be given. Fix the least stage s such that $W[s]\restriction x=W\restriction x$ . The only action in the construction which possibly changes the value of $m_{x}$ is in Step 3. In particular, if $m_{x}[s+1]\neq m_{x}[s]$ , then at stage s, some $x'<x$ must have been enumerated into W. Since s is a stage at which $W[s]\restriction x=W\restriction x$ , this cannot happen after stage s, and thus $\lim _{s}m_{x}[s]=m_{x}[s+1]$ . To see why $f(m_{x})=W(x)$ , consider the following cases:

• • There is some stage t such that x enters W at stage t. If $t\geq s$ , then at stage t, Step 3 of the construction ensures that we define $f(m_{x}[t+1])=1$ . Since the value of $m_{x}$ never changes after stage s, it follows that $f(m_{x})=f(m_{x}[t+1])=1$ . On the other hand, if $t<s$ , then it must be that $s>0$ , and at stage s, some $x'<x$ enters W. Then the construction would have defined $f(m_{x}[s+1])=1$ since $x\in W[t]\subseteq W[s]$ and $x>x'$ . Just as before, since the value of $m_{x}$ never again changes after stage $s+1$ , $f(m_{x})=f(m_{x}[s+1])=1$ .

• • If $x\notin W$ , then we claim that $f(m_{x})=0$ . Observe that whenever some $x'<x$ enters $W[t]$ , $m_{x}[t+1]$ would be defined to be a fresh value; thus $f(m_{x}[t+1])[t]=0$ . This implies that $f(m_{x})=f(m_{x}[s+1])[s]=0$ since no $x'<x$ ever enters W after stage s.

Using (i), we may easily show that $f\equiv _{T}W$ . Given f and x, suppose that $m_{x'}$ has been computed for each $x'<x$ , and search for the stage s such that $W[s]\restriction x=\{x'\mid x'<x\text { and }f(m_{x'})=1\}$ . For such a stage s, it must be that $m_{x}[s+1]=m_{x}$ , and we may then retrieve $W(x)$ by computing $f(m_{x})$ . To compute $f(x)$ , since $f(x)$ possibly changes only when some $y\leq x$ enters W, at the stage s such that $W[s]\restriction (x+1)=W\restriction (x+1)$ , $f(x)[s+1]=\lim _{s}f(x)[s]$ .

From Steps 2 and 3 of the construction, it is evident that the markers $m_{x}$ at which each $p_{e}$ points is increasing (in x). Thus, if $p_{e}$ does not point at a single marker for cofinitely many stages, then $p_{e}$ points at each marker for only finitely many (possibly $0$ ) stages. Let $e\in \omega $ be the least such that this holds. Following the construction, a pointer $p_{e}$ only changes the marker it points at due to one of the following reasons:

• • An error for $R_{e}$ was found at $m_{x}$ at which $p_{e}$ is currently pointing. Then $p_{e}$ subsequently points at $m_{x+1}$ . (See Step 2 of the construction.)

• • $R_{e}$ has acted (see Step 3).

• • $R_{e}$ was initialised.

$R_{e}$ is only initialised if there is some $e'<e$ such that an error for $R_{e'}$ was found (see Step 2), or $R_{e'}$ has acted (see Step 3). In either of these situations, the marker $p_{e'}$ is pointing at changes. By the assumption that e is the least for which the marker $p_{e}$ points at changes infinitely often, we may assume that past some finite stage $s^{*}$ , $p_{e}$ cannot change due to $R_{e}$ being initialised. After such a stage, $p_{e}$ changes only if it has acted or if an error is found at the current marker $p_{e}$ is pointing at.

If $R_{e}$ has acted, then it must have been declared to be satisfied. Furthermore, as no other higher priority requirement acts after $s^{*}$ , Step 2 of the construction never again considers $R_{e}$ . In other words, once $R_{e}$ acts after stage $s^{*}$ , $p_{e}$ never again changes the marker it points at.

Finally, we consider the possibility that $R_{e}$ never acts after stage $s^{*}$ . Then the only way that $p_{e}$ changes the marker it points at infinitely often is if errors are found at each marker that $p_{e}$ points at. In addition, $R_{e}$ never receives permission to act upon these errors; there is some x such that for all $x'\geq x$ , $g_{e}(x')\downarrow =W(x')$ , contradicting the assumption that W is non-recursive.