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

computabilitycomputer science

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.

Best Answer

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$.

Related Question