# Recursive Relations.

1. Dec 18, 2007

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