[proofplan] We construct $A$ by a finite-injury priority argument. The positive requirements make $A$ simple by meeting every infinite c.e. set while enumerating at most one witness per requirement and only above a size threshold. The negative requirements build a computable finite-change approximation to $A'$ by protecting apparent computations $\Phi_e^A(e)\downarrow$ with finite restraints. A priority induction proves that every requirement is injured only finitely often, so the positive requirements are met and the approximation to $A'$ converges correctly. [/proofplan] [step:Set up the requirements and the stage construction] Fix an effective enumeration $(W_e)_{e \in \mathbb{N}}$ of the computably enumerable subsets of $\mathbb{N}$, and fix an effective enumeration $(\Phi_e)_{e \in \mathbb{N}}$ of oracle Turing functionals. For a finite set $B \subseteq \mathbb{N}$ and a stage $s \in \mathbb{N}$, write $\Phi_{e,s}^B(e)\downarrow$ to mean that the computation with oracle $B$ has halted by stage $s$ on input $e$. When such a computation exists, let $u(e,B,s)$ denote its finite oracle use, meaning that only oracle questions below $u(e,B,s)$ are asked. We build an increasing computable sequence of finite sets \begin{align*} A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots \subseteq \mathbb{N}, \end{align*} and define \begin{align*} A := \bigcup_{s=0}^{\infty} A_s. \end{align*} Since the sequence $(A_s)_{s \in \mathbb{N}}$ is computable and increasing by finite extension, $A$ is computably enumerable. The requirements are ordered as \begin{align*} N_0 \prec P_0 \prec N_1 \prec P_1 \prec N_2 \prec P_2 \prec \cdots . \end{align*} The positive requirement $P_e$ is \begin{align*} W_e \text{ is infinite } \implies A \cap W_e \neq \varnothing. \end{align*} The negative requirement $N_e$ is to make the predicate $\Phi_e^A(e)\downarrow$ have a computable approximation with finitely many changes. For each $e \in \mathbb{N}$ and stage $s$, the construction maintains a value \begin{align*} g(e,s) \in \{0,1\}, \end{align*} which is the current guess for whether $\Phi_e^A(e)$ halts. It also maintains, for each $N_e$, either no protected computation or one protected computation $\Phi_{e,t}^{A_t}(e)\downarrow$ chosen at some stage $t \leq s$, together with its use $r_e(s) \in \mathbb{N}$. If $N_e$ has no protected computation at stage $s$, set $r_e(s)=0$. At stage $s+1$, define a current finite oracle $C_{s+1,0} \subseteq \mathbb{N}$ by \begin{align*} C_{s+1,0} := A_s. \end{align*} Process the requirements in priority order up to index $s+1$. After the first $k$ processed requirements at stage $s+1$, let $C_{s+1,k}$ denote the finite set obtained from $A_s$ by adding exactly the numbers enumerated by positive requirements already processed at this stage. Thus every computation tested by a negative requirement is tested against the current finite oracle after all stronger same-stage actions have already been incorporated. For $N_e$: let $k(e,s+1)$ be the number of requirements processed before $N_e$ at stage $s+1$, and set \begin{align*} B_{e,s+1} := C_{s+1,k(e,s+1)}. \end{align*} First cancel the protected computation of $N_e$, if one exists, exactly when some stronger requirement has enumerated at this stage a number below its protected use. If no protected computation remains and there is a computation $\Phi_{e,s+1}^{B_{e,s+1}}(e)\downarrow$ with use $u(e,B_{e,s+1},s+1)$, assign this computation to $N_e$, set \begin{align*} r_e(s+1) := u(e,B_{e,s+1},s+1), \end{align*} and set $g(e,s+1)=1$. If a protected computation remains after the cancellation check, keep it, keep its restraint, and set $g(e,s+1)=1$. If no protected computation remains and no new computation is selected, set $r_e(s+1)=0$ and $g(e,s+1)=0$. For $P_e$: if $P_e$ has already acted, do nothing. If $P_e$ has not acted, let $R_e(s+1)$ be the finite maximum of the current restraints $r_i(s+1)$ imposed by stronger negative requirements $N_i \prec P_e$. If no stronger negative requirement currently imposes a positive restraint, set $R_e(s+1)=0$. If there is an element \begin{align*} x \in W_{e,s+1} \end{align*} such that \begin{align*} x > \max\{R_e(s+1), 2e\}, \end{align*} choose the least such $x$, enumerate $x$ into the current finite oracle for stage $s+1$, and declare $P_e$ permanently satisfied. When this enumeration destroys a protected computation of a lower-priority negative requirement, that lower-priority computation is cancelled when that lower-priority requirement is next processed, or equivalently before it can be used to justify a value $g(i,s+1)=1$. After all requirements up to index $s+1$ have been processed, define $A_{s+1}$ to be the final current finite oracle produced at stage $s+1$. [guided] We fix the same data used in the exact construction. Let $(W_e)_{e \in \mathbb{N}}$ be an effective enumeration of the computably enumerable subsets of $\mathbb{N}$, and let $(\Phi_e)_{e \in \mathbb{N}}$ be an effective enumeration of oracle Turing functionals. For a finite set $B \subseteq \mathbb{N}$ and a stage $s \in \mathbb{N}$, the notation \begin{align*} \Phi_{e,s}^B(e)\downarrow \end{align*} means that the computation with oracle $B$ has halted by stage $s$ on input $e$. If this computation exists, its use is the natural number $u(e,B,s) \in \mathbb{N}$ such that the computation asks only oracle questions below $u(e,B,s)$. The object being built is an increasing computable sequence of finite sets \begin{align*} A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots \subseteq \mathbb{N}, \end{align*} and the final set is \begin{align*} A := \bigcup_{s=0}^{\infty} A_s. \end{align*} Because the sequence is computable and increases by finite extension, membership in the enumeration of $A$ is computably enumerable. The priority ordering is \begin{align*} N_0 \prec P_0 \prec N_1 \prec P_1 \prec N_2 \prec P_2 \prec \cdots . \end{align*} The positive requirement $P_e$ is \begin{align*} W_e \text{ is infinite } \implies A \cap W_e \neq \varnothing, \end{align*} and the negative requirement $N_e$ is to make the predicate $\Phi_e^A(e)\downarrow$ have a computable approximation with finitely many changes. For this approximation, the construction maintains \begin{align*} g(e,s) \in \{0,1\}, \end{align*} where $g(e,s)$ is the stage-$s$ guess for whether $\Phi_e^A(e)$ halts. The construction also maintains, for each $N_e$, either no protected computation or a protected computation $\Phi_{e,t}^{A_t}(e)\downarrow$ chosen at some stage $t \leq s$, together with a restraint $r_e(s) \in \mathbb{N}$. If no computation is protected, then \begin{align*} r_e(s)=0. \end{align*} The key point in the stage convention is that negative requirements must check computations against the current finite oracle, not against an obsolete oracle from before stronger same-stage actions. At stage $s+1$, start with \begin{align*} C_{s+1,0} := A_s. \end{align*} After the first $k$ requirements have been processed, let $C_{s+1,k}$ be the finite set obtained from $A_s$ by adding the witnesses enumerated so far at stage $s+1$. Thus, when $N_e$ is processed, all stronger same-stage positive actions have already been reflected in the finite oracle \begin{align*} B_{e,s+1} := C_{s+1,k(e,s+1)}, \end{align*} where $k(e,s+1)$ is the number of requirements processed before $N_e$. Now process $N_e$. If a previously protected computation of $N_e$ has been injured because a stronger requirement has enumerated a number below its protected use, cancel that computation. If no protected computation remains and \begin{align*} \Phi_{e,s+1}^{B_{e,s+1}}(e)\downarrow, \end{align*} then protect this current computation, set \begin{align*} r_e(s+1) := u(e,B_{e,s+1},s+1), \end{align*} and set \begin{align*} g(e,s+1)=1. \end{align*} If a protected computation remains after the cancellation check, retain its restraint and set \begin{align*} g(e,s+1)=1. \end{align*} If no protected computation remains and no new current computation is found, set \begin{align*} r_e(s+1)=0, \qquad g(e,s+1)=0. \end{align*} Now process $P_e$. If $P_e$ has already acted, it does nothing. If it has not acted, define $R_e(s+1)$ to be the maximum of the current restraints imposed by stronger negative requirements $N_i \prec P_e$, and define \begin{align*} R_e(s+1)=0 \end{align*} when there is no positive stronger restraint. If there is an element \begin{align*} x \in W_{e,s+1} \end{align*} with \begin{align*} x > \max\{R_e(s+1),2e\}, \end{align*} choose the least such $x$, add $x$ to the current finite oracle for the stage, and declare $P_e$ permanently satisfied. The inequality $x>R_e(s+1)$ protects stronger negative requirements, while $x>2e$ is the size bound later used to prove that $A$ is coinfinite. After all requirements up to index $s+1$ have been processed, define $A_{s+1}$ to be the final current finite oracle. This is effective: at stage $s+1$ only finitely many requirements are examined, each set $W_{e,s+1}$ is finite, each oracle used in a computation test is finite, and the relation $\Phi_{e,s+1}^{B_{e,s+1}}(e)\downarrow$ is decidable from finite information. Therefore the map \begin{align*} g: \mathbb{N} \times \mathbb{N} &\to \{0,1\} \\ (e,s) &\mapsto g(e,s) \end{align*} is computable, and the sequence $(A_s)_{s \in \mathbb{N}}$ is a computable increasing sequence of finite sets. [/guided] [/step] [step:Prove by finite injury induction that every requirement stabilizes] We prove by induction on the priority ordering that every requirement acts or changes its restraint only finitely often. For $P_e$, the assertion is immediate from the construction: $P_e$ acts at most once, because after it enumerates a witness into $A$ it is declared permanently satisfied. Now fix $e \in \mathbb{N}$ and suppose every requirement stronger than $N_e$ acts or changes restraint only finitely often. Then there is a stage $s_e$ after which no stronger positive requirement enumerates any number into $A$, and no stronger negative requirement changes its restraint. Hence after stage $s_e$, no stronger requirement can newly injure $N_e$ by changing $A$ below a protected use. After stage $s_e$, the requirement $N_e$ can change $g(e,\cdot)$ only in two situations: it selects a new apparent computation and changes the value to $1$, or a stronger action destroys the protected computation and changes the value to $0$. The second situation never occurs after $s_e$. The first situation can occur at most once after $s_e$, because once $N_e$ selects a protected computation after $s_e$, no stronger action later destroys it, and all lower-priority positive requirements are restrained from enumerating below its use. Therefore $N_e$ changes its restraint and its guess only finitely often. This completes the induction over the priority ordering. [/step] [step:Show that every positive requirement is satisfied] Fix $e \in \mathbb{N}$ and suppose $W_e$ is infinite. By the finite injury induction, there is a stage $s_0$ after which every stronger negative requirement $N_i \prec P_e$ has a stable restraint. Let \begin{align*} R := \max\{r_i(s) : s \geq s_0 \text{ and } N_i \prec P_e\}, \end{align*} where the maximum is over the finite set of stronger negative requirements and is therefore a well-defined natural number. Since $W_e$ is infinite and $W_{e,s}$ is an increasing computable enumeration of $W_e$, there is a stage $s_1 \geq s_0$ and an element $x \in W_{e,s_1}$ such that \begin{align*} x > \max\{R,2e\}. \end{align*} At the first stage at which such an element is available and $P_e$ is considered, the construction enumerates such an $x$ into $A$ unless $P_e$ has already acted. In either case, $A \cap W_e \neq \varnothing$. Thus every positive requirement $P_e$ is satisfied. [/step] [step:Use the witness bounds to prove that $A$ is coinfinite] For each $e \in \mathbb{N}$, the only requirement that can enumerate an element on behalf of $P_e$ acts at most once, and if it acts then it enumerates a number strictly larger than $2e$. Fix $n \in \mathbb{N}$. If $i > n$, then any element enumerated by $P_i$ is larger than $2i$, hence larger than $2n$. Therefore only the finitely many requirements \begin{align*} P_0, P_1, \dots, P_n \end{align*} can enumerate elements of $\{0,1,\dots,2n\}$. Since each of these requirements acts at most once, \begin{align*} |A \cap \{0,1,\dots,2n\}| \leq n+1. \end{align*} The finite set $\{0,1,\dots,2n\}$ has $2n+1$ elements, so at least $n$ of its elements are outside $A$. Since this holds for every $n$, the complement $\mathbb{N} \setminus A$ is infinite. Hence $A$ is coinfinite. Combining this with the previous step, $A$ is a computably enumerable coinfinite set meeting every infinite computably enumerable set. Therefore $A$ is simple. [/step] [step:Identify the limit of the negative approximation with $A'$] Fix $e \in \mathbb{N}$. By the finite injury induction, the sequence \begin{align*} g(e,0), g(e,1), g(e,2), \dots \end{align*} changes only finitely many times. Define \begin{align*} g_\infty(e) := \lim_{s \to \infty} g(e,s). \end{align*} We prove that \begin{align*} g_\infty(e)=1 \iff \Phi_e^A(e)\downarrow. \end{align*} First suppose $g_\infty(e)=1$. Then at some stage $t$, the requirement $N_e$ selected a protected computation $\Phi_{e,t}^{B_{e,t}}(e)\downarrow$ with use $u(e,B_{e,t},t)$, where $B_{e,t}$ was the current finite oracle at the moment $N_e$ was processed. By construction, $B_{e,t}$ already includes every stronger enumeration made earlier at stage $t$. Since this protected computation was never subsequently cancelled, no lower-priority requirement enumerates a number below $u(e,B_{e,t},t)$ while it is protected, and no later stronger action changes $A$ below that use. Hence \begin{align*} B_{e,t} \cap \{0,1,\dots,u(e,B_{e,t},t)-1\} = A \cap \{0,1,\dots,u(e,B_{e,t},t)-1\}. \end{align*} The finite oracle answers used by the computation are therefore the same for $B_{e,t}$ and $A$, so $\Phi_e^A(e)\downarrow$. Conversely suppose $\Phi_e^A(e)\downarrow$. Let $u \in \mathbb{N}$ be the finite use of this halting computation. Since $A$ is computably enumerable and only finitely many numbers below $u$ are relevant, there is a stage $t_0$ such that \begin{align*} A_{t_0} \cap \{0,1,\dots,u-1\} = A \cap \{0,1,\dots,u-1\}. \end{align*} There is also a stage $t_1 \geq t_0$ by which the finite computation is visible, so $\Phi_{e,t_1}^{A_{t_1}}(e)\downarrow$. After the last injury to $N_e$, if $N_e$ has not already preserved a permanent computation, it eventually sees this computation and protects it. Because there are no later injuries, the protected computation remains forever, and therefore $g_\infty(e)=1$. Thus $g_\infty$ is exactly the characteristic function of $A'$. [guided] We now connect the priority construction to the jump. For each $e$, the value $g(e,s)$ is a stage-$s$ guess for the statement \begin{align*} \Phi_e^A(e)\downarrow. \end{align*} The finite injury induction has already shown that the guesses in the $e$th column change only finitly many times, so the limit \begin{align*} g_\infty(e) := \lim_{s \to \infty} g(e,s) \end{align*} exists. We first prove that if $g_\infty(e)=1$, then $\Phi_e^A(e)\downarrow$. The value $1$ can persist only because $N_e$ has chosen some finite computation \begin{align*} \Phi_{e,t}^{B_{e,t}}(e)\downarrow \end{align*} with finite use $u(e,B_{e,t},t)$, where $B_{e,t}$ is the current finite oracle at the moment $N_e$ is processed at stage $t$. This distinction matters: $B_{e,t}$ already includes any stronger same-stage enumerations, so the computation is valid for the oracle that exists when it is protected. A computation with use $u(e,B_{e,t},t)$ asks only oracle questions below $u(e,B_{e,t},t)$. Since the computation is never cancelled, the construction has preserved the oracle answers below that use: \begin{align*} B_{e,t} \cap \{0,1,\dots,u(e,B_{e,t},t)-1\} = A \cap \{0,1,\dots,u(e,B_{e,t},t)-1\}. \end{align*} Therefore the same finite computation that halted relative to $B_{e,t}$ also halts relative to the final oracle $A$. Hence $\Phi_e^A(e)\downarrow$. Now suppose $\Phi_e^A(e)\downarrow$. This is a finite computation, so it uses only finitely many oracle bits. Let $u \in \mathbb{N}$ be its use. Since $A$ is the increasing union of the finite sets $A_s$, every element of $A$ below $u$ has entered by some finite stage. Therefore there is a stage $t_0$ such that \begin{align*} A_{t_0} \cap \{0,1,\dots,u-1\} = A \cap \{0,1,\dots,u-1\}. \end{align*} Once the oracle answers below $u$ have stabilized, the halting computation eventually appears at a finite stage; choose $t_1 \geq t_0$ such that \begin{align*} \Phi_{e,t_1}^{A_{t_1}}(e)\downarrow. \end{align*} After the last injury to $N_e$, this apparent computation cannot be destroyed by stronger requirements. Thus $N_e$ eventually protects it permanently, and the limiting value of the approximation is $1$. We have proved \begin{align*} g_\infty(e)=1 \iff \Phi_e^A(e)\downarrow, \end{align*} so $g_\infty$ is the characteristic function of $A'$. [/guided] [/step] [step:Compute the jump from $\varnothing'$ using the finite-change approximation] The map \begin{align*} g: \mathbb{N} \times \mathbb{N} &\to \{0,1\} \\ (e,s) &\mapsto g(e,s) \end{align*} is computable, and each column $s \mapsto g(e,s)$ changes only finitely many times. An oracle for $\varnothing'$ computes $g_\infty(e)$ as follows. Starting with $t=0$, ask the halting oracle whether there exists a stage $s>t$ such that \begin{align*} g(e,s) \neq g(e,t). \end{align*} This is a computably enumerable question in the parameter $(e,t)$, so it is decidable by $\varnothing'$. If the answer is yes, search effectively for the least such $s$, replace $t$ by $s$, and repeat. If the answer is no, output $g(e,t)$. Since the column $s \mapsto g(e,s)$ changes only finitely many times, this procedure halts. Its output is the eventual value $g_\infty(e)$, which is the characteristic function of $A'$ by the previous step. Hence \begin{align*} A' \leq_T \varnothing'. \end{align*} Conversely, $\varnothing' \leq_T A'$ because there is a computable function $h: \mathbb{N} \to \mathbb{N}$ such that $\Phi_{h(e)}^B(h(e))$ ignores its oracle $B \subseteq \mathbb{N}$ and simulates the ordinary Turing machine with index $e$ on input $e$. Therefore \begin{align*} e \in \varnothing' \iff \Phi_{h(e)}^A(h(e))\downarrow \iff h(e) \in A'. \end{align*} Thus $\varnothing' \leq_T A'$. Combining both reductions gives \begin{align*} A' \equiv_T \varnothing'. \end{align*} Therefore $A$ is low. [/step] [step:Conclude that the constructed set is low and simple] We have constructed a computably enumerable set $A \subseteq \mathbb{N}$. The positive requirements ensure that $A$ meets every infinite computably enumerable set, and the witness bounds ensure that $\mathbb{N} \setminus A$ is infinite. Hence $A$ is simple. The negative requirements give a computable finite-change approximation to $A'$, from which $A' \leq_T \varnothing'$ follows, while the standard oracle-ignoring reduction gives $\varnothing' \leq_T A'$. Hence $A' \equiv_T \varnothing'$, so $A$ is low. This proves the theorem. [/step]