# recursively enumerable of Godel numbering

There are statements for natural number x, like followings

m: "x is even natural number"

n: "x+1 is odd number and x>1"

l: "x is positive integer multiple of two"

m, n, l has same boolean value for x. If m(x) is true, n(x), l(x) is also true. m(x) is false, n(x), l(x) is also false.

Let's define this statements are "equivalent for x." Hence n, l is equivalent for x with m.

Another example

q: "x is natural number and 3.5 < x < 10"

p: "x is integer and 3 < x < 19/2"

We can say "q is equivalent for x with p"

Now, let set M is "all Gödel numbers of the statements that are equivalent for x with statement m"

Set M is infinite set of natural numbers that is dependent for m.

My question: For given m (a statement of x), set M is recursively enumerable?

-

## 1 Answer

The set of Gödel numbers of statements that are equivalent to a fixed m is never recursively enumerable, no matter what the statement m is. The reason is that, for any statement s that does not involve x or other free variables, and that is therefore simply true or false, we have that s is true if and only if the compound statement "s iff m" is equivalent to m. So if we could recursively enumerate the (Gödel numbers of) statements equivalent to m, then we could also recursively enumerate the true statements s, which would contradict Tarski's theorem that the set of (Gödel numbers of) true statements of arithmetic is not even arithmetically definable, let alone recursively enumerable.

-
Thank you @Andreas Blass, but I am still confused. I can understand that "all true statement s" is not recursively enumerable. However, I am considering only statement that mentions x. Can you tell me more? – HoCheol SHIN Mar 8 '13 at 20:35
And can you tell me what this means? "Given a Gödel numbering of the computable functions, the set is recursively enumerable." - en.wikipedia.org/wiki/Recursively_enumerable_set – HoCheol SHIN Mar 8 '13 at 20:37
@HoCheolSHIN: If your $m$ is the Gödel number of a formula $\mu(x)$, and $\psi$ is any formula with no free variables, then the Gödel number of $\phi(x)\equiv (\mu(x)\leftrightarrow \psi)$ is equivalent to $\mu(x)$ (and should therefore be emitted by your enumeration of $M$) exactly when $\psi$ is a true statement. Therefore, if you had an enumeration of $M$, then you could convert it into an enumeration of all true statements simply filtering for outputs of the form $\mu(x)\leftrightarrow \psi$. – Henning Makholm Mar 8 '13 at 22:22