Can Gödel's Incompleteness Theorems Help Solve Logic Exam Questions?

[spenx01]

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.

 

[Valkarie]

Answers:1a) All finite sets are representable in PA by enumerating the elements of the set. This is done by expressing each element as a natural number, and then constructing a formula that states “there exists an element x such that x is equal to the nth element of the set” where n is the natural number representing the element. 1b) The formula F(v1) that represents the set of even numbers but represents only the set of numbers divisible by six in PA is F(v1) = v1=2n, where n is a natural number. 1c) This can be generalized by replacing the number two with any other number (e.g. 3, 4, etc.) to represent the set of multiples of that number. 1d) Yes, the set A={n : En[nn] is False} is expressible using the following formula: A(v1) = ∃x∀y(y≠x → ~En[y]). 1e) The formula F(v1) which represents N (set of natural numbers) in PA but ∀v1F(v1) is not provable in PA is F(v1) = v1=n+1, where n is a natural number.2) The mistake in the proof is that the premise that X is a fixed point of the formula ~H(v1) is incorrect. Since H(v1) is a formula that represents P, X cannot both be in P and not in P at the same time. 3) Let S be an extension of the system R. To prove that every representable set A has a Gödel sentence with respect to S, 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. To show that d is acceptable in S, note that since S is an extension of R, it must also be consistent. Therefore, the diagonal function d(x) is strongly definable in S and thus is acceptable in S. 4) To prove that if the diagonal function d(x) is strongly definable in

 

[piercas]

I am not an expert in philosophy or logic, so I am not able to provide a solution to these questions. It would be best to seek help from your professor or a tutor who is knowledgeable in this subject matter. They will be able to guide you in solving these questions and provide you with the necessary resources and support. Additionally, it is important to understand the material and concepts on your own in order to truly grasp the subject matter and succeed in your studies. Good luck with your exam.