# Simple set

In computability theory, a subset of the natural numbers is called simple if it is computably enumerable (c.e.) and co-infinite (i.e. its complement is infinite), but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not computable.

## Relation to Post's problem

Simple sets were devised by Emil Leon Post in the search for a non-Turing-complete c.e. set. Whether such sets exist is known as Post's problem. Post had to prove two things in order to obtain his result: that the simple set A is not computable, and that the K, the halting problem, does not Turing-reduce to A. He succeeded in the first part (which is obvious by definition), but for the other part, he managed only to prove a many-one reduction.

Post's idea was validated by Friedberg and Muchnik in the 1950s using a novel technique called the priority method. They give a construction for a set that is simple (and thus non-computable), but fails to compute the halting problem.

## Formal definitions and some properties

In what follows, $W_{e}$  denotes a standard uniformly c.e. listing of all the c.e. sets.

• A set $I\subseteq \mathbb {N}$  is called immune if $I$  is infinite, but for every index $e$ , we have $W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I$ . Or equivalently: there is no infinite subset of $I$  that is c.e..
• A set $S\subseteq \mathbb {N}$  is called simple if it is c.e. and its complement is immune.
• A set $I\subseteq \mathbb {N}$  is called effectively immune if $I$  is infinite, but there exists a recursive function $f$  such that for every index $e$ , we have that $W_{e}\subseteq I\implies \#(W_{e}) .
• A set $S\subseteq \mathbb {N}$  is called effectively simple if it is c.e. and its complement is effectively immune. Every effectively simple set is simple and Turing-complete.
• A set $I\subseteq \mathbb {N}$  is called hyperimmune if $I$  is infinite, but $p_{I}$  is not computably dominated, where $p_{I}$  is the list of members of $I$  in order.
• A set $S\subseteq \mathbb {N}$  is called hypersimple if it is simple and its complement is hyperimmune.