Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
6  
I'm always puzzled by these questions that can be answered by googling the keywords in the very question: click here to see how it's done. The second link I get is this one where you can find the example Alon gives in his answer as well. –  t.b. May 9 '11 at 7:31
1  
I think there was a whole discussion on Meta, either here or over at mathoverflow, about the ethics of answering with lmgt4u :-) your usage of it is certainly polite and appropriate. –  Alon Amit May 9 '11 at 9:01
    
@Alon: Thanks, I wasn't aware of that, else I'd have restrained myself (with difficulty, though). –  t.b. May 9 '11 at 9:14
1  
@ Theo Buehler: It seems you have forgotten how difficult math sometimes feels when you learn it first and after you have learned it. Of course when you already know the answer it pops right into your eyes when googling it. But if you are still in the process of learning it does not - the only argument I understoof fully was Apostolos' (actually the comment to his answer), because for the other ones I lack the previous necessary knowledge. So, please, make an effort the next time and put yourself in the learners shoes! –  user10324 May 15 '11 at 12:21
add comment

4 Answers

up vote 4 down vote accepted

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.

share|improve this answer
2  
The same thing can be done for sets, rather than functions; let $A_n$ enumerate all c.e. sets, and define $B$ so that $n \in B$ if and only if $n \not \in A_n$. Then $B$ is not among the sets in the list. –  Carl Mummert May 9 '11 at 15:33
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
2  
Andres, I just wanted to let you know that I really appreciate all the wonderful answers you give. Even if you're talking of things that are quite remote from my own field, I always have the impression to take away something worthwhile from them. Thanks a lot for your efforts! –  t.b. May 9 '11 at 20:59
    
@Theo: That's very kind. Many thanks. –  Andres Caicedo May 9 '11 at 21:07
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.