Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

An application of Gödel's incompleteness theorem?

  1. Jun 20, 2012 #1
    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 [itex]\mathcal{A}(x_1)[/itex] in the formal first order system for arithmetics, [itex]\mathcal{N}[/itex], with precisely one free variable [itex]x_1[/itex], such that [itex]\mathcal{A}(0^{(n)})[/itex] is a theorem in [itex]\mathcal{N}[/itex] for all [itex]n\in D_N[/itex], but where [itex]\forall x_1\mathcal{A}(x_1)[/itex] is not a theorem in [itex]\mathcal{N}[/itex]. Here [itex]D_N[/itex] 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 [itex]\mathcal{N}[/itex] is consistent.
  2. jcsd
  3. Jun 20, 2012 #2
    The question is just asking you to show that [itex]\mathcal{N}[/itex] is ω-incomplete, which Godel's theorem easily allows you to do, because the Godel statement is precisely a statement of the form [itex]\forall x_1\mathcal{A}(x_1)[/itex] where [itex]\mathcal{A}(0^{(n)})[/itex] is a theorem in [itex]\mathcal{N}[/itex] for all [itex]n\in D_N[/itex]. Because the Godel statement G can be informally stated as "For all [itex]x_1[/itex], G cannot be proved in [itex]\mathcal{N}[/itex] with an [itex]x_1[/itex]-lines-long proof." However, for each specific [itex]n\in D_N[/itex], there are only finitely many proofs that are n lines long, so just by writing down all the valid proofs in [itex]\mathcal{N}[/itex] 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 [itex]x_1[/itex], G cannot be proved in [itex]\mathcal{N}[/itex] with the (valid) proof whose Godel number is [itex]x_1[/itex]", and then for each [itex]n\in D_N[/itex] you can show that the proof with Godel number n does not prove G.) Does that make sense?
    Last edited: Jun 20, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook