Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.