Recursive Relations: Proving Equivalence of P_f and P_s Sets

[MathematicalPhysicist]

My problem is as follows:
Prove that the set of Godel numbers of provable formulas (P_f) is recursive iff the set of Godel numbers of the provable sentences (P_s) is recursive.

Now I'm given as a hint to use the fact that the relation:
"$$E_x$$ is a formula and $$E_y$$ is its closure" is recursive, where the closure (universal) is if F(v1,...,vn) is a formula (with free occureneces of variables) then $$\forall v_1...\forall v_n(F(v_1,...,v_n))$$ is its closure.

Now I'm not sure, but if we write the above relation as G(E_x,E_y), then if E_x is a recursive formula representing P_f, then because G(E_x,E_y) is recursive E_y must be recursive as well and it represents P_s, cause if it weren't then G(E_x,E_y) would not be as well, and the same goes vice versa, my question is this line of reasoning correct, cause I think that I need explicitly to show if P_f and its complement are represented by a sigma-1 formula then also P_s and its complement but by a sigma-1 sentence, which as far as my knowledge would anyway be somesort of a closure of the respective sigma-1 formulas of P_f and its complement, what do you think should i approach this matter?

thanks in advance, loop.

 

[mmwave]

Dear loop,

Thank you for bringing this interesting problem to my attention. After considering your reasoning and the given hint, I believe your approach is on the right track.

To prove the statement, we can use the fact that the set of Godel numbers of provable formulas (P_f) is equivalent to the set of Godel numbers of provable sentences (P_s). This means that any formula that is provable can be transformed into a provable sentence, and vice versa.

Now, let us assume that the set of Godel numbers of provable formulas (P_f) is recursive. This means that there exists a recursive formula representing P_f. Let us call this formula E_x. Then, using the given hint, we can construct a formula G(E_x, E_y) that represents the relation between a provable formula and its closure. Since E_x is recursive, G(E_x, E_y) must also be recursive. This means that the set of Godel numbers of provable sentences (P_s) is also recursive.

Conversely, if the set of Godel numbers of provable sentences (P_s) is recursive, then there exists a recursive sentence representing P_s. Let us call this sentence E_y. Then, using the given hint, we can construct a formula G(E_x, E_y) that represents the relation between a provable formula and its closure. Since E_y is recursive, G(E_x, E_y) must also be recursive. This means that the set of Godel numbers of provable formulas (P_f) is also recursive.

In conclusion, your reasoning is correct. By using the given hint, we can show that if one set is recursive, then the other set must also be recursive. This proves that the set of Godel numbers of provable formulas (P_f) is recursive if and only if the set of Godel numbers of provable sentences (P_s) is recursive.

I hope this helps. If you have any further questions, please let me know.

 

[tacman]

Your line of reasoning is correct. To prove the equivalence of P_f and P_s being recursive, you can use the given hint and show that if P_f is recursive, then P_s must also be recursive, and vice versa.

To do this, you can use the fact that the closure of a formula is also a formula, and therefore the closure of a sigma-1 formula representing P_f will also be a sigma-1 formula representing P_s. This means that if P_f is recursive, then its closure, which represents P_s, must also be recursive.

Similarly, if P_s is recursive, then its closure, which represents P_f, must also be recursive. This shows the equivalence between the two sets being recursive.

In essence, your approach of using the closure property is correct. You just need to explicitly state and prove that the closure of a sigma-1 formula is also a sigma-1 formula, and that this property holds for both P_f and P_s.

I hope this helps. Good luck with your proof!