- #1
spenx01
- 4
- 0
I am a undergraduate philosophy student at METU (Turkey). I took a phd course called Foundations of Logic 2. Our book is Taymond M. Smullyan : “Gödel’s incompleteness Theorems”. I have a take-home exam due to this Friday. I have to solve four questions. Yet, I am unable to solve any of them. If you help me to solve any of these questions, I will be very glad because without this exam I cannot be graduate.
Questions:
NOTE: the overlined “n” – n whith a dash over it – is symbolised as "nn" here because of lack of symbols. Thus, nn =overdashed-n. And, V1 is variable.
1.) a) Prove that all finite sets are representable in PA(Peano Arithmetic).
b) Find a formula F(v1) such that F(v1) expresses the set of even numbers but represent only the set of numbers divisible by six in PA.
c) how can part (b) generalized?
d) Is the set A={n : En[nn] is False} expressible?
e) Find a formula F(v1) which represents N (set of natural numbers) in PA but ∀v1F(v1) is not provable in PA.
2.) Find the mistake in the following “proof”.
Claim : The set P of Gödel numbers of sentences provable in PA is not representable in PA.
Proof : Assume on the contrary that there is a formula H(v1) which represents P:
n∈P ↔ PA ⊢ H(nn)
let X be a fixed point of the formula ~H(v1), that is;
PA⊢X ≡ ~H(X) --- the second X here is overdashed)
Now,
PA ⊢ X ↔ g(X) ∈ P ↔ PA ⊢ H(X) ↔ PA ⊬ X
A contradiction. Hence P is not representable.
3.) Let S be an extension of the system ( R ). Prove that every representable set A has a Gödel sentence with respect to S.
Hint: First prove that : “If the diagonal function d(x) is acceptable in S, then for every set A representable in S, there is a Gödel sentence for A”. Then show that d is acceptable in S.
4.) Prove : “If the diagonal function d(x) is strongly definable in S and S is inconsistent, then the set P is not definable in S.
Questions:
NOTE: the overlined “n” – n whith a dash over it – is symbolised as "nn" here because of lack of symbols. Thus, nn =overdashed-n. And, V1 is variable.
1.) a) Prove that all finite sets are representable in PA(Peano Arithmetic).
b) Find a formula F(v1) such that F(v1) expresses the set of even numbers but represent only the set of numbers divisible by six in PA.
c) how can part (b) generalized?
d) Is the set A={n : En[nn] is False} expressible?
e) Find a formula F(v1) which represents N (set of natural numbers) in PA but ∀v1F(v1) is not provable in PA.
2.) Find the mistake in the following “proof”.
Claim : The set P of Gödel numbers of sentences provable in PA is not representable in PA.
Proof : Assume on the contrary that there is a formula H(v1) which represents P:
n∈P ↔ PA ⊢ H(nn)
let X be a fixed point of the formula ~H(v1), that is;
PA⊢X ≡ ~H(X) --- the second X here is overdashed)
Now,
PA ⊢ X ↔ g(X) ∈ P ↔ PA ⊢ H(X) ↔ PA ⊬ X
A contradiction. Hence P is not representable.
3.) Let S be an extension of the system ( R ). Prove that every representable set A has a Gödel sentence with respect to S.
Hint: First prove that : “If the diagonal function d(x) is acceptable in S, then for every set A representable in S, there is a Gödel sentence for A”. Then show that d is acceptable in S.
4.) Prove : “If the diagonal function d(x) is strongly definable in S and S is inconsistent, then the set P is not definable in S.