# Help me Prove that such a set does NOT exist

Tags:
1. Apr 7, 2017

### norman95

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. Apr 7, 2017

### norman95

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).

File size:
75.5 KB
Views:
26