An application of Gödel's incompleteness theorem?

AI Thread Summary
The discussion revolves around demonstrating the existence of a well-formed formula \mathcal{A}(x_1) in first-order arithmetic \mathcal{N} that is a theorem for all natural numbers but not universally provable. The initial approach involved using Gödel's incompleteness theorem, but concerns arose regarding circular reasoning with ω-consistency. It is clarified that \mathcal{N} is assumed to be consistent, and the task is to show its ω-incompleteness. The Gödel statement serves as an example, asserting that for all x_1, it cannot be proved in \mathcal{N} with a proof of a specific length. The discussion concludes that by analyzing finite proofs, one can establish the non-provability of the Gödel statement within the system.
D_Miller
Messages
17
Reaction score
0
I have a problem in my logic course which I can't get my head around:

I have to show that there is a well formed formula \mathcal{A}(x_1) in the formal first order system for arithmetics, \mathcal{N}, with precisely one free variable x_1, such that \mathcal{A}(0^{(n)}) is a theorem in \mathcal{N} for all n\in D_N, but where \forall x_1\mathcal{A}(x_1) is not a theorem in \mathcal{N}. Here D_N denotes the set of natural numbers.

My initial idea was to use the statement and proof of Gödel incompleteness theorem, but I get stuck in a bit of a circle argument with the ω-consistency, so perhaps my idea of using this theorem is all wrong.Edit: If it isn't obvious from the context, it is fair to assume that \mathcal{N} is consistent.
 
Physics news on Phys.org
The question is just asking you to show that \mathcal{N} is ω-incomplete, which Godel's theorem easily allows you to do, because the Godel statement is precisely a statement of the form \forall x_1\mathcal{A}(x_1) where \mathcal{A}(0^{(n)}) is a theorem in \mathcal{N} for all n\in D_N. Because the Godel statement G can be informally stated as "For all x_1, G cannot be proved in \mathcal{N} with an x_1-lines-long proof." However, for each specific n\in D_N, there are only finitely many proofs that are n lines long, so just by writing down all the valid proofs in \mathcal{N} that are n lines long, you can establish that there is no proof of G that is n lines long. (Or alternatively, you can state G as "For all x_1, G cannot be proved in \mathcal{N} with the (valid) proof whose Godel number is x_1", and then for each n\in D_N you can show that the proof with Godel number n does not prove G.) Does that make sense?
 
Last edited:
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top