# Why are recursive sets also recursively enumerable?

Why is this? I'm not necessarily interested in a full proof, but just a quick, simple explanation that makes sense as to why this is.

• Which definitions of "recursive" and (in particular) "recursively enumerable" do you have to work from? – hmakholm left over Monica Mar 15 '16 at 16:36
• I'm using the following definitions: Recursive - algorithm decides if an input is in a set in a finite amount of time. Recursively enumerable - algorithm halts if element is in the set and does not if it isn't. – yuopiop Mar 15 '16 at 16:39
• x @Ellen: With those (nice and sensible) definitions: If you have an algorithm that shows your set is recursive, you can make it into an algorithm that shows that the set is r.e. by replacing print "yes" with halt and print "no" with loop forever. – hmakholm left over Monica Mar 15 '16 at 16:43

Say $S$ is a recursive set of natural numbers. Given $n$, you have an algorithm to decide whether $n\in S$. So construct a list of the elements of $S$ like so: If $1\in S$ then add $1$ to the list, otherwise don't. If $2\in S$ add $2$ to the list, otherwise don't. Etc. You have enumerated the elements of $S$.