# 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?

-

@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