Simple set
# 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})<f(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.
