In general, are subsets of recursively enumerable sets recursive sets?

2k Views Asked by At

I recently became interested in the solution to Hilbert's tenth problem, in reading about the succession of results that lead up to the proof I came across the notion of recursive sets and recursively enumerable sets. The distinction between the two sets is very subtle. I need some help in answering the question in the title.

Thank you in advance.

1

There are 1 best solutions below

6
On BEST ANSWER

No. Note that $\Bbb N$ is recursively enumerable. But since there are only countably many Turing machines, there are only countably many recursively enumerable sets, on the other hand there are uncountably many subsets to $\Bbb N$. So most sets are not recursively enumerable.

The same argument applies to every infinite RE set.