Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive Relations.

  1. Dec 18, 2007 #1


    User Avatar
    Gold Member

    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:
    "[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.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted