Example of a not recursively enumerable set $A \subseteq \mathbb{N}$

Question

Can someone give me an example if a not recursively enumerable set $A \subseteq \mathbb{N}$ ?

I came up with this question, when trying to show, that there exist partial functions $f: \mathbb{N} \rightsquigarrow \mathbb{N}$ that are constant for some value (when they halt), but not recursive:

Since I know that a set is recursively enumerable iff it is the domain of a partial recursive function, to find an example of such a set, I would have to show that no matter which partial function whose domain is $A$ I would take, it wouldn't be recursive. I couldn't show the above, although it seems intuitively to be true to me. But since I could not show it and the existance of such a counterexample is even stronger (because I would have to show that a whole class of those partial functions aren't recursive) it made me wonder, wether such a set can exist.

Answer 1

Another way to show that such sets exists is by diagonalization. For example take the set of all (codes) of total recursive functions.

Assume there is an enumeration of it, that is there exists a Turing Machine that enumerates these functions (and let's say this enumeration is $(f_n)_{n\in\mathbb{N}}$). Now define a function $g$ as follows: $g(n)=f_n(n)+1$. Observe that this function is recursive and has as domain the whole natural numbers, therefore it is a total recursive function. But this is impossible since it differs from every total recursive function at at least one point.

Answer 2

The complement of any recursively enumerable but non-recursive set will do (if a r.e. set has a r.e. complement then it is recursive.) For example, the set of numbers which are not the Gödel numbers of a theorem of Peano Arithmetic is not recursively enumerable. Same for the set of numbers which encode (under some fixed encoding) a pair $(T, x)$ of a turing machine $T$ and an input $x$ such that the machine $T$ does not halt when given the input $x$.

Answer 3

To add yet another example, here is a set for which neither it nor its compliment are recursively enumerable: The set of all Turing machines accepting exactly 3 words. There are simple reductions from both the Halting problem and its complement to this set.

As a matter of fact, most sets are not recursively enumerable, since there are $\aleph$ sets (of finite strings over a finite alphabet - "languages") but only $\aleph_0$ Turing machines (and each r.e. set is uniquely defined by a Turing machine recognizing it).

Answer 4

A nice example different from the ones mentioned so far is as follows:

Fix a (recursive) coding of formulas by numbers, and let $A$ be the set of codes of sentences $\phi$ that are true of the natural numbers.

This set cannot be r.e. by the incompleteness theorem because $A$ codes a complete consistent theory that extends Peano Arithmetic (namely, the theory of ${\mathbb N}$). Note that in this example $A$ is a fairly complicated set from a computability-theoretic point of view: It codes recursively all recursive sets, all r.e. sets, all co-r.e. sets, etc.

In fact, an easy construction shows that there are as many sets $A$ coding complete consistent extensions of PA as there are real numbers: Enumerate all sentences as $\phi_0,\phi_1,\dots$ Build a tree: At the bottom we have PA. Given a node at depth $n$, and a theory $T_n$ attached to it, this node has at most two immediate successors: extend to $T_n+\phi_n$ if this is consistent, and to $T_n+\lnot\phi_n$ if this is consistent. If only one of them is consistent, this is the only extension. If $T_n$ is consistent, at least one of these two extensions is consistent. Since $T_n$ is a recursive extension of PA (being PA and finitely many additional "axioms"), it is not complete, so eventually we will have two extensions. This shows that the tree we obtain has $|2^{\mathbb N}|$ many branches, any one of which codes a complete consistent extension of PA. None of these extensions is r.e. as before.

Of course, we can produce many examples from the fact that there are only countably many r.e. sets but uncountably many subsets of ${\mathbb N}$. Many of these examples we won't be able to exhibit in any reasonable way. To illustrate, here is a technical example that is more set theoretic in nature:

If $M$ is a countable transitive model of enough set theory, then of course there are only countably many sets of natural numbers in $M$, and all r.e. sets are in $M$. Any set not in $M$ is an example. We can be more explicit; say, any $A$ that is Cohen generic over $M$ is an example. These $A$ can be built explicitly from an enumeration of $M$. Of course, it is a different story how "explicit" $M$ can be. But we can actually make $A$ definable by working inside $L$, taking as $M$ the least model of, say, ZF with replacement restricted to $\Sigma_2$ formulas, and letting $A$ be the least Cohen generic over $M$. Least refers here to the usual well-ordering of $L$.

The point of this last example is that the $A$ we obtain does not code much information in computability-theoretic terms; for example, the Halting problem over $A$ has the same degree as the Halting problem.