# Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive?

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive ?

I'm not particularly interested in a detailed proof or counterexample, just a quick argument why this affirmation should hold or not.

-

No, they are different.

For a set $A$ to be r.e. means (for example) that there is a computer program that (given enough time and memory) prints the elements of $A$, one by one, possibly with repetitions, possibly not in increasing order. On the other hand, for $A$ to be recursive, means that there is a program that, for any $n$, tells us whether $n\in A$ or not.

For example: The set of axioms of Peano Arithmetic is recursive. There are infinitely many (as there are infinitely many instances of induction), but given a formula, it is very easy to see whether it is one of these axioms or not.

The theorems of Peano Arithmetic form an r.e. set: We can list it simply by enumerating all proofs.

On the other hand, assuming that these axioms are not contradictory, there is no algorithm that tells whether a given statement is a theorem or not (this is the famous Goedel incompleteness theorem). (Too bad? Things would be much simpler for us if we could have a machine verifying our conjectures for us.)

The halting problem was the first manifestation in computability theory of this difference between being recursive and being r.e. The linked Wikipedia page contains a sketch of the diagonal argument showing that the set $K$ is not recursive, where $K$ consists of all pairs $(a,b)$ such that $a$ codes a computer program, $b$ codes an input, and $a$ eventually halts with input $b$. On the other hand, it is obvious that $K$ is r.e.: List all triples $(a,b,c)$, $c$ a number, and print $(a,b)$ if and only if $a$ stops on input $b$ in precisely $c$ steps.

-