# Non-recursive subset which is recursively enumerable

What is an example of recursively enumerable subset of the natural numbers which is not recursive?

-
Indices of Turing machines (in your favorite enumeration) that halt on the empty input? Gödel numbers of theorems of pure predicate calculus? –  Henning Makholm Mar 3 '12 at 19:36
@HenningMakholm I think your answer works if "your favorite enumeration" is a computable enumeration. –  Michael Hardy Mar 3 '12 at 21:21
@Michael, if it wasn't computable, why would it be anyone's favorite? :-) –  Henning Makholm Mar 3 '12 at 21:27

The set of universally valid formulas of first-order logic becomes such an example if you index formulas by natural numbers in a computable way. This is called Church's theorem, after Alonzo Church. He proved this in the 1930s. This means that although there is a fast proof-checking algorithm, there is no fast proof-finding algorithm.

The set of polynomial equations in several variables with integer coefficients that have integer solutions is another such example. That's called Matiyasevich's theorem. It was proved in 1970 by Uri Matiyasevich, who built on earlier work of Julia Robinson, Hillary Putnam, and Martin Davis. It disposed of Hilbert's tenth problem.

-
This is only true if the non-logical language contains binary relation symbol. Pure first-order logic, by itself, is decidable. –  David Harris Mar 4 '12 at 0:12
I'm not sure I've ever thought about the "pure" form. –  Michael Hardy Mar 5 '12 at 1:18