[proofplan] We build $A$ by a priority construction meeting, for each index $e \in \mathbb{N}$, the requirement that if the c.e. set $W_e$ is infinite, then $A$ intersects $W_e$. Requirement $R_e$ is allowed to put at most one element into $A$, and it only chooses numbers larger than $2e$. This makes $A$ computably enumerable, guarantees every infinite c.e. set is met, and leaves infinitely many numbers permanently outside $A$ because only finitely many low-priority requirements can enumerate small numbers. [/proofplan]

[step:Fix an effective finite-stage enumeration of all computably enumerable sets] Fix an [effective enumeration](/page/Effective%20Enumeration) $(W_e)_{e \in \mathbb{N}}$ of all [computably enumerable sets](/page/Computably%20Enumerable%20Set) contained in $\mathbb{N}$. Fix a computable finite-stage approximation $(W_{e,s})_{e,s \in \mathbb{N}}$ such that, for every $e \in \mathbb{N}$ and $s \in \mathbb{N}$, the set $W_{e,s} \subset \mathbb{N}$ is finite, $W_{e,s} \subset W_{e,s+1}$, and \begin{align*} W_e = \bigcup_{s=1}^{\infty} W_{e,s}. \end{align*} For each $e \in \mathbb{N}$, define the requirement \begin{align*} R_e: \qquad W_e \text{ is infinite } \implies A \cap W_e \neq \varnothing. \end{align*} We shall construct an increasing computable sequence $(A_s)_{s \in \mathbb{N}}$ of finite subsets of $\mathbb{N}$ and then set \begin{align*} A := \bigcup_{s=1}^{\infty} A_s. \end{align*} [/step]

[step:Construct $A$ by allowing each requirement to enumerate one large witness]Set $A_1 := \varnothing$. At stage $s+1$, begin with the temporary finite set $B_{s+1,0} := A_s$. Process the requirements $R_0,R_1,\dots,R_s$ in increasing order of their indices. For each $e \leq s$, let $B_{s+1,e}$ denote the temporary finite approximation at the beginning of the turn for $R_e$. Say that $R_e$ is already satisfied at the beginning of its turn if some earlier stage has enumerated a witness specifically for $R_e$. If $R_e$ is already satisfied, make no change, and set $B_{s+1,e+1} := B_{s+1,e}$. If $R_e$ is not already satisfied and there exists an element \begin{align*} x \in W_{e,s} \setminus B_{s+1,e} \end{align*} with $x > 2e$, choose the least such $x$, set $B_{s+1,e+1} := B_{s+1,e} \cup \{x\}$, and declare $R_e$ satisfied. If no such $x$ exists, make no change, and set $B_{s+1,e+1} := B_{s+1,e}$. After all requirements $R_0,R_1,\dots,R_s$ have been processed, define $A_{s+1} := B_{s+1,s+1}$. This rule is effective: at stage $s+1$ only finitely many finite sets are searched, and the least eligible witness, when it exists, is computably found. Therefore the set \begin{align*} A = \bigcup_{s=1}^{\infty} A_s \end{align*} is computably enumerable.[/step]

[guided]The construction has two competing goals. To make $A$ meet every infinite c.e. set, we want requirement $R_e$ to search inside $W_e$ and put one element into $A$. To keep $A$ coinfinite, we restrict the kind of element that $R_e$ may put in: it may enumerate only a number $x > 2e$, and it may do this at most once. We define $A_1 := \varnothing$. At stage $s+1$, we begin with $B_{s+1,0} := A_s$ and process exactly the finitely many requirements $R_0,R_1,\dots,R_s$ in increasing order. For each $e \leq s$, the temporary finite set $B_{s+1,e}$ is the current approximation at the beginning of the turn for $R_e$. If $R_e$ has already placed a witness into $A$ at an earlier stage, then $R_e$ takes no further action and we set $B_{s+1,e+1} := B_{s+1,e}$. If $R_e$ has not already acted, we search the finite set $W_{e,s}$ for an element \begin{align*} x \in W_{e,s} \setminus B_{s+1,e} \end{align*} satisfying $x > 2e$. The subtraction by $B_{s+1,e}$ prevents us from trying to enumerate an element already placed into the current approximation, and the inequality $x > 2e$ is the restraint that will later make the complement infinite. If eligible elements exist, we choose the least one, set \begin{align*} B_{s+1,e+1} := B_{s+1,e} \cup \{x\}, \end{align*} and permanently declare $R_e$ satisfied. If no eligible element exists, we set $B_{s+1,e+1} := B_{s+1,e}$. After processing $R_0,R_1,\dots,R_s$, we define $A_{s+1} := B_{s+1,s+1}$. The search is computable because $W_{e,s}$ and $B_{s+1,e}$ are finite and effectively given at stage $s+1$. The construction therefore gives a computable enumeration of the elements that enter $A$. Since a set is computably enumerable precisely when its elements can be listed by a computable stage procedure, the resulting set \begin{align*} A = \bigcup_{s=1}^{\infty} A_s \end{align*} is computably enumerable.[/guided]

[step:Verify that every infinite computably enumerable set is met] Fix $e \in \mathbb{N}$ and suppose $W_e$ is infinite. If any requirement $R_k$ with $k \in \mathbb{N}$ has already enumerated an element of $W_e$ into $A$, including the case $k=e$, then $A \cap W_e \neq \varnothing$. Assume instead that no requirement has yet enumerated an element of $W_e$ into $A$ before a stage at which $R_e$ is considered. Because $W_e$ is infinite, the set \begin{align*} W_e \cap \{x \in \mathbb{N} : x > 2e\} \end{align*} is nonempty. Choose $y \in W_e$ with $y > 2e$. Since $W_e = \bigcup_{s=1}^{\infty} W_{e,s}$, there exists a stage $s_0 \in \mathbb{N}$ such that $y \in W_{e,s_0}$. At every stage $s \geq \max\{s_0,e\}$, the requirement $R_e$ is processed, and $y$ is present in $W_{e,s}$. At the first such stage at which $R_e$ is not already satisfied, either $y$ is still outside the current temporary approximation, in which case the construction finds at least one eligible witness and enumerates some element of $W_e$ into $A$, or $y$ has already entered the current temporary approximation, in which case an earlier action at that stage has already placed an element of $W_e$ into $A$. In either case, \begin{align*} A \cap W_e \neq \varnothing. \end{align*} Thus every infinite computably enumerable set is met by $A$. [/step]

[step:Prove that infinitely many numbers never enter $A$] For each $n \in \mathbb{N}$, consider the finite initial segment \begin{align*} I_n := \{1,2,\dots,2n\}. \end{align*} If a requirement $R_e$ enumerates an element $x \in I_n$, then the construction requires $x > 2e$. Since also $x \leq 2n$, we have \begin{align*} 2e < x \leq 2n, \end{align*} and hence $e < n$. Therefore only the requirements \begin{align*} R_0,R_1,\dots,R_{n-1} \end{align*} can ever enumerate elements of $I_n$. Each of these $n$ requirements enumerates at most one element, so \begin{align*} |A \cap I_n| \leq n. \end{align*} Since $|I_n| = 2n$, it follows that \begin{align*} |I_n \setminus A| \geq 2n - n = n. \end{align*} Thus, for every $n \in \mathbb{N}$, the complement $\mathbb{N} \setminus A$ contains at least $n$ elements. Hence $\mathbb{N} \setminus A$ is infinite. [/step]

[step:Conclude that the constructed set is simple] We have proved that $A$ is computably enumerable, that $\mathbb{N} \setminus A$ is infinite, and that $A$ intersects every infinite computably enumerable subset of $\mathbb{N}$. Therefore $A$ is a [simple set](/page/Simple%20Set). This proves the existence of a simple computably enumerable set. [/step]