1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted

Similar Discussions: Recursive Relations.
  1. Primitive recursive (Replies: 1)

  2. Umm recursiveness? (Replies: 2)

  3. Recursively enumerable? (Replies: 14)

  4. Transfinite recursion (Replies: 5)