42.04.03 · mathematical-logic / computability-degrees

Computably Enumerable Sets: Creative and Simple Sets

shipped3 tiersLean: none

Anchor (Master): Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2-4 and the historical notes (the normal-form and projection theorems; Myhill's theorem $1\text{-complete} = \text{creative} = \text{recursively isomorphic to } K$; Post's construction of a simple set, the immune and hyperimmune complements, the lattice $\mathcal E$ of c.e. sets and the hypersimple / hyperhypersimple / maximal hierarchy); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 7-8, 11 (productive and creative sets, the recursion-theoretic productive function, Myhill's theorem, the reducibility lattice $\le_1, \le_m, \le_{tt}, \le_T$); Odifreddi 1989 *Classical Recursion Theory, Volume I* (North-Holland) Ch. II-III, V (the structure of $\mathcal E$, Post's program, the relation of productiveness to incompleteness)

Intuition Beginner

There are two ways a set of numbers can be "known to a computer," and the gap between them runs through this whole subject. The strong way is to decide the set: a program that, given any number, answers yes or no — is it in or out? — and always stops. The weak way is only to list the set: a program that keeps printing members, one after another, and is guaranteed to eventually print every member, but never has to announce that some number is not coming. A set you can list this way is called computably enumerable, or c.e. for short.

Listing is genuinely weaker than deciding. If you are listing a set and the number $7$ has not appeared yet, you cannot conclude $7$ is out — maybe it shows up at step a million, maybe never, and you have no way to tell which. The halting set from the previous unit is the headline example: you can list all the programs that stop on their own code by running them all a little at a time and printing each one as it halts, but you cannot decide membership, because that would solve the halting problem.

Inside the listable-but-undecidable sets there turn out to be two very different personalities. Some, like the halting set, are "creative": they actively resist being pinned down. Any time you try to describe what their complement contains, the set hands you back a fresh number you missed — a built-in counterexample machine. Others are "simple": they are tame in a precise sense, their complement is thin and holds no listable infinite pattern, and they sit strictly between the decidable sets and the creative ones. The discovery that both kinds exist is where the structure of computation opens up.

Visual Beginner

A c.e. set is what an enumerator prints. Picture a machine with an output tape that runs forever, occasionally adding a number to a growing list. The set is everything that will ever appear; non-members are simply the numbers that never appear, and nothing flags them.

   enumerator for a c.e. set A, running over time:

   stage 1 :  3
   stage 2 :  3   8
   stage 3 :  3   8   8      (repeats are fine)
   stage 4 :  3   8   8   15
   stage 5 :  3   8   8   15  2
   ...                          -> A = {2, 3, 8, 15, ...}

   Is 7 in A?  It has not appeared by stage 5.
               But it might appear at stage 5000, or never.
               The list never says "7 is OUT".  That one-sided
               silence is the whole difference from DECIDING A.

Now contrast the two personalities of an undecidable c.e. set by how their complements behave:

set type	the set is	its complement is	the complement holds...
computable	listable both ways	also listable	a full decision either way
creative (like the halting set)	listable	not listable	a recipe handing you a missed number
simple	listable	not listable	no infinite listable pattern at all

Read the bottom two rows as opposites of texture. The creative complement is rich enough to power a counterexample machine; the simple complement is so thin that no infinite listable family fits inside it. Both are undecidable, yet they sit at different places in the landscape.

Worked example Beginner

We show concretely that "listable" is weaker than "decidable," using a set everyone can picture: the set $A$ of numbers $n$ such that the program numbered $n$ eventually prints the digit $5$ when run on input $0$ .

Step 1. List $A$ . Run a master loop over stages $s = 1, 2, 3, \dots$ . At stage $s$ , simulate each of the first $s$ programs for $s$ steps on input $0$ . Whenever you find that program $n$ has printed a $5$ within its allotted steps, add $n$ to your output list. Every program that ever prints a $5$ will be caught at some finite stage, so this loop lists exactly $A$ . So $A$ is c.e.

Step 2. Try to decide $A$ , and watch it fail. To decide $A$ you would need, for a program that has not yet printed a $5$ , to say whether it ever will. But a program might run for a billion steps in silence and then print a $5$ , or run forever and never print one. Waiting longer never settles the "never" case.

Step 3. Make the failure sharp. Suppose you had a decider for $A$ . Take any program $P$ ; build a new program that simulates $P$ and prints a $5$ exactly if $P$ halts. Then this new program is in $A$ precisely when $P$ halts — so deciding $A$ would decide halting, which the previous unit showed is impossible.

What this tells us: $A$ is a perfectly ordinary set you can enumerate by brute simulation, yet no amount of waiting turns the enumeration into a decision. The one-sided nature of listing is not a weakness of your method; it is the actual boundary of what programs can know about other programs.

Check your understanding Beginner

Formal definition Intermediate+

Fix the standard enumeration ${φ_{e}}_{e \in N}$ of unary partial computable functions and the universal function $U$ from 42.04.01, with $φ_{e} (x) ↓$ meaning the computation halts. Write $W_{e} = dom (φ_{e}) = {x : φ_{e} (x) ↓}$ for the $e$ -th computably enumerable set; ${W_{e}}_{e \in N}$ is the canonical enumeration of all c.e. sets, with stage approximations $W_{e, s} = {x < s : φ_{e, s} (x) ↓}$ (the computation halting in $< s$ steps), so $W_{e} = ⋃_{s} W_{e, s}$ and each $W_{e, s}$ is a finite set computable uniformly in $e, s$ .

A set $A \subseteq N$ is computably enumerable (c.e.) if any one of the following equivalent conditions holds ^{[Soare Ch. 2]}: $A = dom (φ_{e})$ for some $e$ ; $A = \emptyset$ or $A = ran (g)$ for a total computable $g$ ; $A = {x : \exists s R (x, s)}$ is the projection of a computable relation $R$ ; $A$ is $Σ_{1}$ -definable, $A = {x : \exists y θ (x, y)}$ with $θ$ a bounded-quantifier (computable) formula. The normal-form theorem gives the projection witness uniformly: $x \in W_{e} ⟺ \exists s T (e, x, s)$ with the Kleene predicate $T$ computable. A set $A$ is computable if $χ_{A}$ is computable.

For the reducibilities, $A \leq_{m} B$ (many-one) means a total computable $f$ with $x \in A ⟺ f (x) \in B$ ; $A \leq_{1} B$ (one-one) adds that $f$ is injective; $A \leq_{tt} B$ (truth-table) allows a computable map from $x$ to a finite Boolean query of $B$ ; and $A \leq_{T} B$ (Turing, developed in co-produced 42.04.04) allows an oracle algorithm. These strengthen leftward: $\leq_{1} \Rightarrow \leq_{m} \Rightarrow \leq_{tt} \Rightarrow \leq_{T}$ . A c.e. set $C$ is $m$ -complete ( $1$ -complete) if $A \leq_{m} C$ ( $A \leq_{1} C$ ) for every c.e. $A$ .

A set $A$ is productive if there is a partial computable function $p$ (a productive function) such that whenever $W_{e} \subseteq A$ , then $p (e) ↓$ and $p (e) \in A ∖ W_{e}$ . A c.e. set $A$ is creative if $\overline{A}$ is productive. An infinite set is immune if it contains no infinite c.e. subset; a c.e. set $S$ is simple if $\overline{S}$ is infinite and immune.

Counterexamples to common slips Intermediate+

"c.e. means the range of a computable function, so every c.e. set is infinite." The empty set is c.e. (domain of the everywhere-undefined function), and finite sets are c.e. The range characterisation needs the clause " $A = \emptyset$ or $A = ran (g)$ ": a total $g$ has nonempty range, so $\emptyset$ is the lone exception, not a counterexample to c.e.-ness.
"A productive set is c.e." Productiveness is a property forcing a set to be very non-c.e.: a productive set has an infinite c.e. subset structure it always escapes, so it is never c.e. The creative sets are c.e.; their complements are the productive ones. The roles of $A$ and $\overline{A}$ must be kept straight.
"Simple just means undecidable." Simplicity is a specific structural property of the complement — infinite but immune. It implies undecidable and non- $m$ -complete, but most undecidable c.e. sets ( $K$ itself) are not simple. Simplicity is a deliberate construction, not a default.
" $\leq_{m}$ and $\leq_{1}$ give the same complete sets." They give the same complete c.e. degree by Myhill's theorem, but $\leq_{1}$ is strictly finer as a preorder in general; the coincidence at the top (creative $=$ $1$ -complete $=$ $m$ -complete) is a theorem, not a definition.

Key theorem with proof Intermediate+

The organising results are Post's complementation theorem, which fixes exactly when listability upgrades to decidability, and the creativity of $K$ , which certifies that the halting set is $m$ -complete by a productive function rather than by an ad-hoc reduction.

Theorem (Post's complementation theorem; $K$ is creative). A set $A$ is computable if and only if both $A$ and $\overline{A}$ are computably enumerable. The halting set $K = {e : φ_{e} (e) ↓}$ is creative: the identity function is a productive function for $\overline{K}$ .

Proof. If $A$ is computable then $χ_{A}$ is computable, so $A = dom (φ_{i})$ where $φ_{i} (x)$ halts iff $χ_{A} (x) = 1$ , and likewise $\overline{A} = dom (φ_{j})$ ; both are c.e. Conversely, suppose $A = W_{a}$ and $\overline{A} = W_{b}$ . To decide $x \in A$ , dovetail: run the stage approximations $W_{a, s}$ and $W_{b, s}$ for $s = 1, 2, \dots$ until $x$ appears in one of them. Since $A \cup \overline{A} = N$ , the number $x$ lies in exactly one, so it enters $W_{a, s}$ or $W_{b, s}$ at some finite stage; output "yes" if it entered $W_{a, s}$ , "no" if $W_{b, s}$ . This is a total computable decision procedure, so $A$ is computable.

For creativity, $K$ is c.e. (it is $dom (ψ)$ for $ψ (e) ≃ U (e, e)$ ). I claim the identity $p (e) = e$ is a productive function for $\overline{K}$ : if $W_{e} \subseteq \overline{K}$ , then $e \in \overline{K} ∖ W_{e}$ . Indeed $W_{e} \subseteq \overline{K}$ means $e \in / W_{e}$ would have to be checked — and $e \in W_{e} ⟺ φ_{e} (e) ↓ ⟺ e \in K$ , so $e \in W_{e} ⟺ e \in K$ . If $W_{e} \subseteq \overline{K}$ then $e \in W_{e}$ would give $e \in \overline{K}$ and $e \in K$ at once, impossible; hence $e \in / W_{e}$ , i.e. $e \in \overline{K} ∖ W_{e}$ . As $W_{e} \subseteq \overline{K}$ also forces $e \in / K$ , so $e \in \overline{K}$ , the value $p (e) = e$ lands in $\overline{K} ∖ W_{e}$ exactly as required. Thus $\overline{K}$ is productive and $K$ is creative. $□$

Bridge. Post's complementation theorem is the foundational reason c.e.-ness and computability are two genuinely different levels rather than one: a set is decidable precisely when both it and its complement are listable, so the asymmetry of the halting set — listable, with an unlistable complement — is the only way undecidability can happen for a c.e. set. The identity-as-productive-function calculation is exactly the diagonal $φ_{e} (e)$ of 42.04.02 read as a counterexample generator: where the previous unit ran the diagonal once to defeat a decider, here the same self-application is packaged as a uniform procedure that, given any attempted c.e. approximation $W_{e}$ to $\overline{K}$ , returns a witness it missed. This builds toward Myhill's theorem, where creativity is shown to pin down the entire $m$ -complete degree, and it appears again in the productiveness of arithmetic provability, where the productive function becomes the engine of Gödel incompleteness (cross-ref 42.01.09 pending). The central insight is that creativity is effective resistance to enumeration, so putting these together the halting set's hardness is not an accident of its definition but a structural feature certified by a single computable function.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that if $A$ is creative then $A$ is $m$ -complete: for every c.e. set $B$ , $B \leq_{m} A$ . (Use that $\overline{A}$ has a productive function $p$ , and the s-m-n theorem.)

Hint

For each $x$ build, by s-m-n, an index $h (x)$ with $W_{h (x)} = \emptyset$ if $x \in / B$ and $W_{h (x)} = {p (h (x))}$ -aware behaviour if $x \in B$ . Use the recursion theorem to know $h (x)$ in advance, then track where $p (h (x))$ lands.

Answer

Let $p$ be a productive function for $\overline{A}$ and $B = W_{b}$ c.e. Define a partial computable $θ (x, y)$ : on input $y$ , run $φ_{b} (x)$ ; if it halts (so $x \in B$ ), additionally output by halting on $y = p$ -value as arranged below. Concretely, by the s-m-n and recursion theorems build a total computable $g$ with $W_{g (x)} = \emptyset$ if $x \in / B$ , and $W_{g (x)} = {p (g (x))}$ if $x \in B$ (the recursion theorem lets the construction reference its own index $g (x)$ , so it can wait for $x \in B$ and then enumerate the single point $p (g (x))$ ). If $x \in / B$ then $W_{g (x)} = \emptyset \subseteq \overline{A}$ , so $p (g (x)) \in \overline{A} ∖ W_{g (x)}$ , giving $p (g (x)) \in / A$ . If $x \in B$ then $p (g (x)) \in W_{g (x)} = {p (g (x))}$ , so $W_{g (x)} \neq \subseteq \overline{A}$ is not forced — instead, since $W_{g (x)} = {p (g (x))}$ was placed to make $p (g (x)) \in A$ (the productive function's output is driven into $A$ ). Set $f (x) = p (g (x))$ : then $x \in B ⟺ f (x) \in A$ , a total computable reduction, so $B \leq_{m} A$ . Rubric: full credit for the recursion-theorem construction of $g$ and the case split showing $p (g (x))$ sits in $A$ iff $x \in B$ .

Exercise 4 (medium, symbolic).

Show that a simple set $S$ is neither computable nor creative (so not $m$ -complete).

Hint

If $S$ were computable, $\overline{S}$ would be c.e. and infinite — but an immune set has no infinite c.e. subset. If $S$ were creative, $\overline{S}$ would be productive — find an infinite c.e. subset hidden in any productive set.

Answer

Not computable: if $S$ were computable then $\overline{S}$ is c.e.; $\overline{S}$ is infinite by simplicity and is a c.e. subset of itself, contradicting immunity (which forbids an infinite c.e. subset of $\overline{S}$ ). Not creative: a productive set always contains an infinite c.e. subset — iterate the productive function $p$ starting from an index for $\emptyset$ to get $x_{0} = p (e_{\emptyset}) \in \overline{S}$ , then an index for ${x_{0}}$ to get $x_{1} = p (\cdot) \in \overline{S} ∖ {x_{0}}$ , and so on, building an infinite c.e. set inside $\overline{S}$ . If $S$ were creative, $\overline{S}$ would be productive and hence contain an infinite c.e. subset, contradicting immunity. So a simple set is neither computable nor creative, placing it strictly between the computable sets and the $m$ -complete sets. Rubric: full credit for the immunity contradiction in both directions and the iterated-productive-function construction of the infinite c.e. subset.

Exercise 5 (medium, multiple-choice).

In Post's construction of a simple set $S$ , members are enumerated to satisfy requirements $R_{e}$ : "if $W_{e}$ is infinite, put some element of $W_{e}$ greater than $2 e$ into $S$ ." What does the bound $> 2 e$ accomplish?

It makes $S$ computable.
It keeps $\overline S$ infinite, by reserving small numbers from being swallowed.
It makes $\overline S$ a c.e. set.
It forces $S$ to be $m$-complete.

Hint

Count how many elements $S$ can take below a given bound.

Answer

B. Each requirement $R_{e}$ contributes at most one element to $S$ , and that element exceeds $2 e$ , so among the numbers ${0, 1, \dots, 2 n}$ at most the requirements $R_{0}, \dots, R_{n - 1}$ can have placed elements — at most $n$ of the $2 n + 1$ numbers below $2 n$ are in $S$ , leaving infinitely many in $\overline{S}$ . Meeting every $R_{e}$ makes $\overline{S}$ immune (it meets every infinite c.e. set), so $S$ is simple. The bound is what keeps $\overline{S}$ infinite.

Exercise 6 (hard, symbolic).

Carry out Post's construction: build a c.e. set $S$ that is simple. Give the enumeration procedure and prove $\overline{S}$ is infinite and immune.

Hint

Dovetail the enumerations $W_{e, s}$ . At each stage, for the least $e$ whose requirement is unmet, look for an element $> 2 e$ appearing in $W_{e, s}$ and enumerate it into $S$ .

Answer

Construction. Enumerate $S = ⋃_{s} S_{s}$ with $S_{0} = \emptyset$ . At stage $s + 1$ , for each $e < s$ whose requirement $R_{e}$ is not yet declared satisfied, search $W_{e, s}$ for some $x$ with $x > 2 e$ and $x \in / S_{s}$ ; if found, put the least such $x$ into $S_{s + 1}$ and declare $R_{e}$ satisfied. (At most one $x$ enters per requirement.)

$S$ is c.e. since the procedure is an effective enumeration. Immunity of $\overline{S}$ : if $W_{e}$ is infinite, it contains some $x > 2 e$ , which is found at some stage, so $R_{e}$ is met and an element $> 2 e$ of $W_{e}$ is put into $S$ ; hence $W_{e} \neq \subseteq \overline{S}$ , so no infinite c.e. set lies inside $\overline{S}$ — $\overline{S}$ is immune. Infinitude of $\overline{S}$ : each $R_{e}$ enumerates at most one element into $S$ , and that element exceeds $2 e$ . So among ${0, 1, \dots, 2 n}$ only requirements $R_{0}, \dots, R_{n - 1}$ can have placed members, at most $n$ elements; thus at least $n + 1$ of the $2 n + 1$ numbers $\leq 2 n$ remain in $\overline{S}$ , for every $n$ . Hence $\overline{S}$ is infinite. Therefore $\overline{S}$ is infinite and immune, so $S$ is simple. Rubric: full credit for the $> 2 e$ bounded construction, the immunity argument from meeting every $R_{e}$ , and the counting argument for infinitude of $\overline{S}$ .

Exercise 7 (hard, symbolic).

Prove the easy half of Myhill's theorem: if $A$ is $1$ -complete then $A$ is creative. (The converse — creative $\Rightarrow$ $1$ -complete, with recursive isomorphism to $K$ — is harder and stated in the Master section.)

Hint

$K$ is creative with productive function $p_{K} = id$ . Pull $p_{K}$ back through the one-one reduction $K \leq_{1} A$ .

Answer

Suppose $A$ is $1$ -complete, so $K \leq_{1} A$ via an injective total computable $f$ with $e \in K ⟺ f (e) \in A$ . We build a productive function for $\overline{A}$ . Given an index $j$ with $W_{j} \subseteq \overline{A}$ , the c.e. set $f^{- 1} (W_{j}) = {e : f (e) \in W_{j}}$ is c.e. (as $f$ is computable and $W_{j}$ is c.e.), say $f^{- 1} (W_{j}) = W_{g (j)}$ for a total computable $g$ obtained by s-m-n. Since $W_{j} \subseteq \overline{A}$ and $e \in W_{g (j)} ⟺ f (e) \in W_{j} \subseteq \overline{A} ⟺ f (e) \in / A ⟺ e \in / K$ , we get $W_{g (j)} \subseteq \overline{K}$ . The identity is productive for $\overline{K}$ , so $g (j) \in \overline{K} ∖ W_{g (j)}$ , meaning $g (j) \in / K$ and $g (j) \in / W_{g (j)}$ . Then $f (g (j)) \in / A$ (as $g (j) \in / K$ ) and $f (g (j)) \in / W_{j}$ (else $g (j) \in W_{g (j)}$ ). So $p (j) = f (g (j))$ satisfies $p (j) \in \overline{A} ∖ W_{j}$ , a productive function for $\overline{A}$ . Hence $A$ is creative. Rubric: full credit for pulling the c.e. set back through $f$ , applying the identity productive function for $\overline{K}$ , and pushing the witness forward through $f$ .

Advanced results Master

Creativity and simplicity bound the c.e. sets from above and from the middle: every creative set is a copy of $K$ , simplicity produces a c.e. set provably below the complete degree, and the lattice $E$ of c.e. sets organises the refinements that Post hoped would force an intermediate Turing degree. The results below develop the isomorphism theorem, the simple-set hierarchy, and the productiveness that turns this structure theory into a proof of incompleteness.

Theorem 1 (Myhill's isomorphism theorem). For c.e. sets the three notions coincide: $A$ is creative $⟺$ $A$ is $m$ -complete $⟺$ $A$ is $1$ -complete, and any two creative sets are recursively isomorphic — there is a computable permutation $π$ of $N$ with $π (A) = B$ ^{[Rogers Ch. 7]}. In particular every creative set is recursively isomorphic to $K$ . The forward implications run creative $\Rightarrow$ $m$ -complete (the productive function drives any c.e. set into $A$ ) and creative $\Rightarrow$ $1$ -complete (the reduction can be made injective by padding the productive function's outputs to distinct values); the isomorphism is an effective Cantor-Schröder-Bernstein construction interleaving the two one-one reductions $A \leq_{1} B$ and $B \leq_{1} A$ into a single computable bijection. Myhill's theorem is the precise sense in which $K$ is the halting set: not merely $m$ -equivalent to every other complete c.e. set, but literally a relabelling of it.

Theorem 2 (productiveness and incompleteness). Let $T$ be a consistent, computably axiomatised theory extending a weak base for arithmetic, and let $Thm_{T} = {┌ σ ┐ : T ⊢ σ}$ be its (c.e.) set of theorems. The set of (codes of) true $Π_{1}$ sentences refuted-or-unprovable is productive, and concretely $\overline{Thm_{T}}$ restricted to true sentences is productive: a productive function, applied to any c.e. set of sentences $T$ proves, returns a true sentence $T$ does not prove ^{[Odifreddi Ch. III]}. This is Gödel's first incompleteness theorem read recursion-theoretically: because $K \leq_{m} Thm_{T}$ (halting is expressible and provable-when-true) while the set of true sentences is productive, no c.e. axiomatisation captures all arithmetic truth — the productive function exhibits the missed truth uniformly, and that truth is the Gödel sentence (cross-ref 42.01.09 pending). Productiveness is thus the structural form of incompleteness: a set that no enumeration can exhaust, with the escape witness computed from the attempted enumeration.

Theorem 3 (the simple-set hierarchy). Post refined simplicity to weaken the complement further. A c.e. set $S$ is hypersimple if $\overline{S}$ is infinite and hyperimmune — its principal function (the increasing enumeration of $\overline{S}$ ) is not dominated by any computable function — and hyperhypersimple if $\overline{S}$ is infinite and the c.e. sets disjoint from $S$ have no infinite c.e. "array" covering them; a maximal set is a c.e. $S$ whose complement is as thin as possible, with no c.e. set splitting $\overline{S}$ into two infinite pieces ^{[Soare Ch. 4]}. These form a strict hierarchy maximal $\Rightarrow$ hyperhypersimple $\Rightarrow$ hypersimple $\Rightarrow$ simple, each a structurally definable class in the lattice $E$ of c.e. sets under inclusion modulo finite difference. Friedberg's maximal-set theorem (every c.e. degree above $0$ that is high contains a maximal set, and maximal sets exist) shows $E$ has a rich definable structure.

Theorem 4 (Post's program and its outcome). Post's program sought a structural (lattice-theoretic) property of a c.e. set $S$ guaranteeing $\emptyset <_{T} S <_{T} K$ — an intermediate Turing degree — thereby solving "Post's problem" of whether such a degree exists without constructing one directly ^{[Soare Ch. 4]}. Simplicity blocks $m$ -completeness but not Turing-completeness; hypersimplicity blocks truth-table completeness ( $\leq_{tt}$ ) but a hypersimple set can still be Turing-complete; even maximality does not bound Turing degree below $K$ . The program in its original form does not reach an intermediate Turing degree: the gap between the $\leq_{m}$ , $\leq_{tt}$ structure that lattice properties control and the $\leq_{T}$ structure is real. Post's problem was finally settled by the priority method of Friedberg and Muchnik (co-produced 42.04.06), constructing two c.e. sets of incomparable Turing degree directly, both strictly between $\emptyset$ and $K$ .

Theorem 5 (Dekker's theorem; simple sets in every degree). Every nonzero c.e. Turing degree contains a simple set ^{[Rogers Ch. 8]}. Given any c.e. $A$ of nonzero degree with an injective computable enumeration ${a_{s}}$ , the deficiency set $D = {s : \exists t > s a_{t} < a_{s}}$ — stages later improved upon — is simple and Turing-equivalent to $A$ . Thus simplicity is not a degree-theoretic restriction at all: it constrains the $\leq_{m}$ structure (no simple set is $m$ -complete) while imposing nothing on Turing degree, the cleanest illustration of why Post's program could not succeed on its own terms.

Synthesis. The c.e. sets are where computability acquires structure, and creativity versus simplicity is the foundational reason that structure is two-dimensional rather than one. Myhill's theorem collapses the top: every creative set is recursively isomorphic to $K$ , so $m$ -completeness, $1$ -completeness, and creativity are one phenomenon, and this is exactly the productive function of the Key theorem read as a universal source — the diagonal $φ_{e} (e)$ of 42.04.02 turned into a relabelling map. Putting these together with Post's complementation theorem, undecidability for a c.e. set is the unlistability of its complement, and the complement's texture splits the undecidable c.e. sets into the creative (productive complement, a counterexample engine) and the simple (immune complement, no infinite c.e. pattern at all). The simple-set hierarchy and Dekker's theorem show this $\leq_{m}$ -stratification is dual to the Turing structure rather than parallel to it: simplicity bounds many-one and truth-table hardness yet leaves Turing degree free, which is the central insight behind the failure of Post's program and the bridge to the priority method 42.04.06 that builds the intermediate Turing degrees by direct construction. The productiveness theorem is the load-bearing connection outward — incompleteness 42.01.09 pending is the productiveness of provability, and the arithmetical hierarchy 42.04.05 that classifies these sets by quantifier complexity relativises the whole picture to oracles, with $K$ as the $Σ_{1}$ base of the jump and the c.e. sets as the projections that populate its first level.

Full proof set Master

Proposition 1 (equivalent characterisations of c.e.). For $A \subseteq N$ , the following are equivalent: (i) $A = dom (φ_{e})$ for some $e$ ; (ii) $A = \emptyset$ or $A = ran (g)$ for total computable $g$ ; (iii) $A = {x : \exists s R (x, s)}$ for computable $R$ .

Proof. (i) $\Rightarrow$ (iii): $x \in dom (φ_{e}) ⟺ \exists s T (e, x, s)$ by the normal-form theorem, so take $R (x, s) = T (e, x, s)$ . (iii) $\Rightarrow$ (ii): if $A = \emptyset$ done; else fix $a_{0} \in A$ via a witness pair and define $g$ on the computable set of pairs $⟨ x, s ⟩$ with $R (x, s)$ by $g (⟨ x, s ⟩) = x$ , padding to a total function with value $a_{0}$ off the witness set; then $ran (g) = A$ . (ii) $\Rightarrow$ (i): if $A = \emptyset$ it is $dom$ of the everywhere-undefined function; else define $ψ (x)$ to search $t$ for $g (t) = x$ and halt when found, so $dom (ψ) = ran (g) = A$ . Each step is uniform, giving the equivalence. $□$

Proposition 2 (Post's complementation theorem). $A$ is computable iff $A$ and $\overline{A}$ are both c.e.

Proof. ( $\Rightarrow$ ) If $χ_{A}$ is computable, $A = dom (φ_{i})$ with $φ_{i} (x) ↓ ⟺ χ_{A} (x) = 1$ , and $\overline{A} = dom (φ_{j})$ with $φ_{j} (x) ↓ ⟺ χ_{A} (x) = 0$ ; both c.e. ( $\Leftarrow$ ) Let $A = W_{a}$ , $\overline{A} = W_{b}$ . The procedure: on input $x$ , compute $W_{a, s}$ and $W_{b, s}$ for $s = 1, 2, \dots$ and halt at the first $s$ with $x \in W_{a, s} \cup W_{b, s}$ . Since $A \cup \overline{A} = N$ and $A \cap \overline{A} = \emptyset$ , $x$ enters exactly one at a finite stage; output $1$ if $x \in W_{a, s}$ , else $0$ . This computes $χ_{A}$ . $□$

Proposition 3 ( $K$ is creative; complementation gives non-c.e. complement). $\overline{K}$ is productive with productive function $id$ ; consequently $\overline{K}$ is not c.e.

Proof. If $W_{e} \subseteq \overline{K}$ , then $e \in W_{e} ⟺ φ_{e} (e) ↓ ⟺ e \in K$ . Were $e \in W_{e}$ , then $e \in \overline{K}$ (by $W_{e} \subseteq \overline{K}$ ) and $e \in K$ , contradiction; so $e \in / W_{e}$ , hence $e \in \overline{K}$ (as $e \in / K$ ). Thus $e \in \overline{K} ∖ W_{e}$ , so $id$ is productive for $\overline{K}$ . A productive set is never c.e.: if $\overline{K} = W_{e}$ for some $e$ , then $W_{e} \subseteq \overline{K}$ holds, so $id (e) = e \in \overline{K} ∖ W_{e} = \overline{K} ∖ \overline{K} = \emptyset$ , impossible. Hence $\overline{K}$ is not c.e. (recovering, via Proposition 2, that $K$ is not computable). $□$

Proposition 4 (creative $\Rightarrow$ $m$ -complete). If $A$ is creative then every c.e. $B$ satisfies $B \leq_{m} A$ .

Proof. Let $p$ be productive for $\overline{A}$ and $B = W_{b}$ . By the s-m-n and recursion theorems there is a total computable $x \mapsto h (x)$ with $W_{h (x)} = {p (h (x))}$ if $x \in B$ and $W_{h (x)} = \emptyset$ if $x \in / B$ (the construction enumerates $p (h (x))$ into $W_{h (x)}$ exactly when $φ_{b} (x) ↓$ , using its own index $h (x)$ supplied by the recursion theorem). If $x \in / B$ : $W_{h (x)} = \emptyset \subseteq \overline{A}$ , so $p (h (x)) \in \overline{A}$ , i.e. $p (h (x)) \in / A$ . If $x \in B$ : $p (h (x)) \in W_{h (x)}$ ; were $p (h (x)) \in \overline{A}$ we would need $W_{h (x)} \subseteq \overline{A}$ to invoke productiveness, but $p$ applied earlier forces $p (h (x)) \in / W_{h (x)}$ whenever $W_{h (x)} \subseteq \overline{A}$ — so $W_{h (x)} \neq \subseteq \overline{A}$ , giving $p (h (x)) \in A$ . Hence $f (x) = p (h (x))$ is total computable with $x \in B ⟺ f (x) \in A$ , so $B \leq_{m} A$ . $□$

Proposition 5 (Post's simple set). There is a c.e. set $S$ with $\overline{S}$ infinite and immune.

Proof. Enumerate $S = ⋃_{s} S_{s}$ , $S_{0} = \emptyset$ . At stage $s + 1$ : for the least $e < s$ with $R_{e}$ unsatisfied, if some $x \in W_{e, s}$ has $x > 2 e$ and $x \in / S_{s}$ , put the least such $x$ into $S_{s + 1}$ and mark $R_{e}$ satisfied. $S$ is c.e. Immunity: if $W_{e}$ is infinite it contains an $x > 2 e$ , found at some stage, so $R_{e}$ is met by enumerating an element of $W_{e}$ into $S$ ; hence $W_{e} \cap S \neq = \emptyset$ , so no infinite c.e. $W_{e}$ is contained in $\overline{S}$ . Infinitude of $\overline{S}$ : each $R_{e}$ adds at most one element, exceeding $2 e$ , so $∣ S \cap {0, \dots, 2 n} ∣ \leq ∣ {e : 2 e < 2 n} ∣ = n$ , leaving $\geq n + 1$ elements of ${0, \dots, 2 n}$ in $\overline{S}$ for every $n$ . So $\overline{S}$ is infinite. $S$ is simple. $□$

Proposition 6 (simple $\Rightarrow$ not $m$ -complete). No simple set is $m$ -complete.

Proof. Suppose $S$ is simple and $m$ -complete; then $\overline{K} \leq_{m} \overline{S}$ is not what we have, so argue via productiveness. An $m$ -complete c.e. set is creative (it is $1$ -complete by the padding in Theorem 1, hence creative by Exercise 7), so $\overline{S}$ would be productive. A productive set contains an infinite c.e. subset: iterate $p$ from an index $e_{0}$ for $\emptyset$ to get $x_{0} = p (e_{0}) \in \overline{S}$ , then an index $e_{1}$ for ${x_{0}}$ to get $x_{1} = p (e_{1}) \in \overline{S} ∖ {x_{0}}$ , and inductively an infinite c.e. set ${x_{0}, x_{1}, \dots} \subseteq \overline{S}$ . This contradicts the immunity of $\overline{S}$ . Hence $S$ is not $m$ -complete. $□$

Proposition 7 (Dekker's deficiency set is simple). If $A$ is c.e., infinite, and not computable, with injective computable enumeration ${a_{s}}_{s}$ (so $A = {a_{0}, a_{1}, \dots}$ ), then the deficiency set $D = {s : \exists t > s a_{t} < a_{s}}$ is simple and $D \equiv_{T} A$ .

Proof. $D$ is c.e.: $s \in D$ is witnessed by finding $t > s$ with $a_{t} < a_{s}$ , a c.e. search. The complement $\overline{D} = {s : \forall t > s a_{t} \geq a_{s}}$ consists of the "true stages" where the enumeration reaches a new running minimum-from-here; these are infinite (the enumeration takes infinitely many record-low values among its tail minima). Immunity of $\overline{D}$ : an infinite c.e. subset of $\overline{D}$ would let one compute, for each $n$ , a true stage past which the enumeration of $A$ never dips below $a_{s}$ , yielding a computable enumeration of $A$ in increasing order and hence $χ_{A}$ computable — contradicting that $A$ is not computable. So $\overline{D}$ is immune and $D$ is simple. Finally $D \equiv_{T} A$ : from $A$ one decides $D$ by the c.e. definition with a halting bound read off $A$ , and from $D$ one recovers the increasing enumeration of $A$ , so each computes the other. $□$

Connections Master

The halting problem and recursion theorem 42.04.02 supply the diagonal this unit converts into structure: the self-application $φ_{e} (e)$ that defeats a decider becomes the identity productive function for $\overline{K}$ , the s-m-n and recursion theorems drive the creative-to- $m$ -complete reduction (Proposition 4) and the simple-set construction (Proposition 5), and $K$ enters here as the canonical creative set. That unit owns the undecidability of $K$ and the many-one theory; this unit owns the c.e. structure theory — the equivalent characterisations, Post's complementation, creativity, and simplicity — built on top of it.
Turing reducibility and the c.e. degrees 42.04.04, co-produced, refine the $\leq_{m}$ relation of this unit to $\leq_{T}$ : the reducibility zoo $\leq_{1} \Rightarrow \leq_{m} \Rightarrow \leq_{tt} \Rightarrow \leq_{T}$ introduced in the Formal definition is completed there, where $K$ becomes the canonical $Σ_{1}$ object and the gap exposed by Dekker's theorem (Proposition 7) — simplicity constrains $\leq_{m}$ but not $\leq_{T}$ — motivates the degree structure. This unit owns the simple/creative dichotomy in the $\leq_{m}$ world; that unit owns the Turing-degree refinement.
The priority method and Post's problem 42.04.06, co-produced, resolves the question this unit's Theorem 4 leaves open: Post's program could not force an intermediate Turing degree by a structural property of c.e. sets, and the Friedberg-Muchnik construction builds two c.e. sets of incomparable Turing degree directly, both strictly between $\emptyset$ and $K$ . The simple-set construction of Proposition 5 is the historical and technical seed of the finite-injury method developed there.
Gödel incompleteness 42.01.09 pending is the productiveness of provability (Theorem 2): because $K \leq_{m} Thm_{T}$ while the set of true arithmetic sentences is productive, no c.e. axiomatisation captures all truth, and the productive function returns the Gödel sentence as the missed truth. The arithmetical hierarchy 42.04.05 classifies the c.e. sets of this unit as $Σ_{1}$ and relativises productiveness and creativity to oracles to build the jump hierarchy above $K$ .

Historical & philosophical context Master

The theory of computably enumerable sets is Emil Post's creation. In his 1944 paper "Recursively enumerable sets of positive integers and their decision problems" Post named the c.e. sets, proved the complementation theorem identifying the decidable sets as those whose complement is also c.e., and introduced the creative sets — c.e. sets whose complements carry a productive function that, given any attempted enumeration of the complement, returns a witness it omits ^{[Rogers Ch. 8]}. Post recognised that $K$ and the complete sets are all creative and that this was the recursion-theoretic content of Gödel's 1931 incompleteness theorem: the set of provable sentences of a consistent axiomatic arithmetic is c.e. but its true-sentence complement is productive, so the theory is incomplete by the very mechanism that makes the halting set creative. In the same paper Post constructed the first simple set, a c.e. set whose complement is infinite yet contains no infinite c.e. set, establishing a c.e. set that is undecidable but provably not many-one complete — the opening move of what became Post's problem.

John Myhill proved in 1955 that the creative sets are exactly the $1$ -complete (equivalently $m$ -complete) c.e. sets and that all of them are recursively isomorphic to $K$ , an effectivisation of the Cantor-Schröder-Bernstein theorem that fixed $K$ as the canonical complete c.e. set up to computable relabelling ^{[Soare Ch. 4]}. Post's program — to find a lattice-theoretic property of a c.e. set forcing its Turing degree strictly between $\emptyset$ and $K$ — drove the development of the simple, hypersimple, hyperhypersimple, and maximal sets and the study of the lattice $E$ of c.e. sets through the 1940s and 1950s. The program did not reach an intermediate Turing degree by structural means, and Post's problem was solved instead by Richard Friedberg and Albert Muchnik in 1956–1957 with the independently discovered priority (finite-injury) method, constructing two c.e. sets of incomparable Turing degree directly. James Dekker's deficiency-set construction showed every nonzero c.e. degree contains a simple set, separating the many-one structure that simplicity controls from the Turing structure it leaves free.

Bibliography Master

@article{post1944recursively,
  author  = {Post, Emil L.},
  title   = {Recursively enumerable sets of positive integers and their decision problems},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {50},
  number  = {5},
  year    = {1944},
  pages   = {284--316}
}

@article{myhill1955creative,
  author  = {Myhill, John},
  title   = {Creative sets},
  journal = {Zeitschrift f\"{u}r mathematische Logik und Grundlagen der Mathematik},
  volume  = {1},
  number  = {2},
  year    = {1955},
  pages   = {97--108}
}

@article{friedberg1957solution,
  author  = {Friedberg, Richard M.},
  title   = {Two recursively enumerable sets of incomparable degrees of unsolvability (solution of {Post's} problem, 1944)},
  journal = {Proceedings of the National Academy of Sciences},
  volume  = {43},
  number  = {2},
  year    = {1957},
  pages   = {236--238}
}

@article{muchnik1956unsolvability,
  author  = {Muchnik, Albert A.},
  title   = {On the unsolvability of the problem of reducibility in the theory of algorithms},
  journal = {Doklady Akademii Nauk SSSR},
  volume  = {108},
  year    = {1956},
  pages   = {194--197}
}

@article{dekker1954selection,
  author  = {Dekker, James C. E.},
  title   = {A theorem on hypersimple sets},
  journal = {Proceedings of the American Mathematical Society},
  volume  = {5},
  number  = {5},
  year    = {1954},
  pages   = {791--796}
}

@article{friedberg1958maximal,
  author  = {Friedberg, Richard M.},
  title   = {Three theorems on recursive enumeration. {I}. Decomposition. {II}. Maximal set. {III}. Enumeration without duplication},
  journal = {The Journal of Symbolic Logic},
  volume  = {23},
  number  = {3},
  year    = {1958},
  pages   = {309--316}
}

@book{soare2016turing,
  author    = {Soare, Robert I.},
  title     = {Turing Computability: Theory and Applications},
  series    = {Theory and Applications of Computability},
  publisher = {Springer},
  year      = {2016}
}

@book{rogers1967theory,
  author    = {Rogers, Hartley},
  title     = {Theory of Recursive Functions and Effective Computability},
  publisher = {McGraw-Hill},
  year      = {1967}
}

@book{odifreddi1989classical,
  author    = {Odifreddi, Piergiorgio},
  title     = {Classical Recursion Theory, Volume I},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {125},
  publisher = {North-Holland},
  year      = {1989}
}

@book{cutland1980computability,
  author    = {Cutland, Nigel},
  title     = {Computability: An Introduction to Recursive Function Theory},
  publisher = {Cambridge University Press},
  year      = {1980}
}

Prerequisites

42.04.02

Tier anchors

beginner: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2-3 (read the informal account of a set you can list but cannot decide: a machine that prints the members in some order, never announcing the non-members); Sipser 2013 *Introduction to the Theory of Computation* 3e (Cengage) §3.2, §4.2 for the recognisable-but-not-decidable distinction stated with enumerators before any degree theory
intermediate: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2-4 (the equivalent characterisations of a c.e. set — domain, range, projection, $\Sigma_1$; Post's complementation theorem; the enumeration $\{W_e\}$ and its uniformity; creative and productive sets and Myhill's isomorphism theorem; simple sets and the immune complement); Cutland 1980 *Computability: An Introduction to Recursive Function Theory* (Cambridge) Ch. 7-9 (creative and simple sets, reducibilities, Post's problem framed)
master: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2-4 and the historical notes (the normal-form and projection theorems; Myhill's theorem $1\text{-complete} = \text{creative} = \text{recursively isomorphic to } K$; Post's construction of a simple set, the immune and hyperimmune complements, the lattice $\mathcal E$ of c.e. sets and the hypersimple / hyperhypersimple / maximal hierarchy); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 7-8, 11 (productive and creative sets, the recursion-theoretic productive function, Myhill's theorem, the reducibility lattice $\le_1, \le_m, \le_{tt}, \le_T$); Odifreddi 1989 *Classical Recursion Theory, Volume I* (North-Holland) Ch. II-III, V (the structure of $\mathcal E$, Post's program, the relation of productiveness to incompleteness)

References

Soare, R. I. — Turing Computability: Theory and Applications · Springer, Theory and Applications of Computability (2016). Ch. 2-3 establish the equivalent characterisations of a computably enumerable (c.e.) set $A$: domain of a partial computable function, range of a (partial or total) computable function, the projection $\{x : \exists s\, R(x,s)\}$ of a computable relation, and $\Sigma_1$-definability in arithmetic; the normal-form theorem $\varphi_e(x)\!\downarrow \iff \exists s\, T(e,x,s)$ with the Kleene $T$-predicate computable; Post's complementation theorem that $A$ is computable iff both $A$ and $\overline A$ are c.e.; the canonical enumeration $\{W_e\}$ with $W_e = \mathrm{dom}(\varphi_e)$ and its stage approximations $W_{e,s}$, uniform in $e$; s-m-n index manipulation producing c.e. sets to specification. Ch. 4 develops productive and creative sets: $A$ is productive if there is a (partial) computable $p$ with $W_e \subseteq \overline A \Rightarrow p(e) \in \overline A \setminus W_e$, $A$ is creative if c.e. with productive complement, $K$ is the canonical creative set, every creative set is $m$-complete, and Myhill's theorem that creative $=$ $1$-complete $=$ recursively isomorphic to $K$; simple sets: Post's construction of a c.e. $S$ with $\overline S$ infinite but containing no infinite c.e. set (immune), so $S$ is neither computable nor $m$-complete (creative), the first wedge into Post's problem; the immune / hyperimmune / hyperhypersimple / maximal refinements and the lattice $\mathcal E$ of c.e. sets under $\subseteq$ modulo finite difference, with Post's program to find a lattice-theoretic property of a c.e. set forcing intermediate Turing degree.
Rogers, H. — Theory of Recursive Functions and Effective Computability · McGraw-Hill (1967). Ch. 5-7: the basis characterisations of c.e. sets (domain / range / projection / $\Sigma_1$), the enumeration theorem and the projection (uniformisation) theorem, Post's theorem on complementation, the reducibility lattice $\le_1 \Rightarrow \le_m \Rightarrow \le_{tt} \Rightarrow \le_T$ with the one-one, many-one, truth-table and Turing degrees; productive and creative sets with the explicit productive function for $\overline K$, the theorem that the creative sets are exactly the $m$-complete c.e. sets, and Myhill's theorem that they are exactly the $1$-complete c.e. sets and form a single recursive-isomorphism type (a Cantor-Schröder-Bernstein-style construction effectivised); Ch. 8: simple, hypersimple and hyperhypersimple sets, Post's constructions, the immune and hyperimmune complements, and Dekker's deficiency-set construction giving a simple set in every nonzero c.e. degree; Ch. 11: the productive function obtained from the recursion theorem and the productiveness of the set of (Gödel numbers of) true sentences of arithmetic.
Odifreddi, P. — Classical Recursion Theory, Volume I · North-Holland, Studies in Logic and the Foundations of Mathematics 125 (1989). Ch. II-III: the structure theory of c.e. sets — the equivalent definitions, the uniformity of $\{W_e\}$, the s-m-n manipulation, Post's complementation theorem, the reducibility hierarchy; productive and creative sets with Myhill's isomorphism theorem and the link to the recursion theorem; the arithmetisation that makes the set of provable (and the set of true) arithmetic sentences productive, exhibiting Gödel incompleteness as the productiveness of provability — no c.e. listing of an axiomatisable, sound theory can capture all truths because productiveness hands back a true-but-unlisted sentence; Ch. V: the lattice $\mathcal E$ of c.e. sets, simple / hypersimple / hyperhypersimple / maximal sets, the automorphisms of $\mathcal E$, Post's program and its eventual subsumption by the Friedberg-Muchnik priority solution to Post's problem.

Estimated time

beginner: 20m
intermediate: 50m
master: 95m