1. Limited time only! Sign up for a free 30min personal 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!

Help me Prove that such a set does NOT exist

  1. Apr 7, 2017 #1
    1. Let Q denote the theory of Robinson Arithmetic. A theory T is nice iff T is consistent, is p.r. adequate and extends Q. The fixed-point lemma states that for all nice theories T, for any formula φ, there is a sentence σ such that
      T ⊢σ↔φ("σ") Given a set of formulas X, let gn(X) = {"φ" | φ ∈ X} be the set of Godel numbers of formulas in X. (Quotation mark denote Godel numbers.) Prove that there is no decidable set R such that gn(Q) ⊆ R and gn({σ | ¬σ ∈ Q}) ⊆ R.

    Please help guys, I've been really sick for the last two week and missed all the relevant material, and now this is due tonight!
  2. jcsd
  3. Apr 7, 2017 #2
    This is what I have so far, but I have no idea if it's anywhere close to correct and I have like 4 chapters of my textbook that I need to cover the relevant materiel. My intuition is that either I have to show some sort of overlap between R and R-completment, or that I have to show that the decideability of R entails the decideability of Q (which is a contradiction).

    Attached Files:

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Help me Prove that such a set does NOT exist