My problem is as follows:(adsbygoogle = window.adsbygoogle || []).push({});

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:

"[tex]E_x[/tex] is a formula and [tex]E_y[/tex] is its closure" is recursive, where the closure (universal) is if F(v1,...,vn) is a formula (with free occureneces of variables) then [tex] \forall v_1.....\forall v_n(F(v_1,...,v_n))[/tex] 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Recursive Relations.

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**