# An application of Gödel's incompleteness theorem?

1. Jun 20, 2012

### D_Miller

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.

2. Jun 20, 2012

### lugita15

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: Jun 20, 2012