Help me Prove that such a set does NOT exist

norman95
Messages
6
Reaction score
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!
 
Physics news on Phys.org
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).
 

Attachments

  • Scan.jpeg
    Scan.jpeg
    65.5 KB · Views: 463
There are two things I don't understand about this problem. First, when finding the nth root of a number, there should in theory be n solutions. However, the formula produces n+1 roots. Here is how. The first root is simply ##\left(r\right)^{\left(\frac{1}{n}\right)}##. Then you multiply this first root by n additional expressions given by the formula, as you go through k=0,1,...n-1. So you end up with n+1 roots, which cannot be correct. Let me illustrate what I mean. For this...
Back
Top