Encyclopedia

Simple set

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated February 4, 2026

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.

01Relation 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 nonexistence of 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.

02Formal 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.

Watch videos about Simple setExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Simple set”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.