0

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?

martian03
  • 75

1 Answers1

4

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.

Andreas Blass
  • 71,833
  • 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?

     – martian03 Mar 08 '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." - http://en.wikipedia.org/wiki/Recursively_enumerable_set – martian03 Mar 08 '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$. – hmakholm left over Monica Mar 08 '13 at 22:22