0
$\begingroup$

Let $\mathcal{N}$ be Peano's 1st order theory of arithmetic and $\mathscr{A}$ it's standard model (which we assume exists). Infer from Gödel's 1st Incompleteness Theorem that there exists a closed well founded formula say $B$ of $\mathcal{N}$ and a model $\mathscr{W}$ of $\mathcal{N}$, such that $B$ is ture in $\mathscr{A}$ and $B$ is false in $\mathscr{W}$. Any help is really needed and app recited. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ The theory is usually denoted by $\sf PA$ and the standard model by $\Bbb N$. Also, "wff" means well-formed formula, not well-founded formula. $\endgroup$ – Asaf Karagila Apr 10 '14 at 16:11
  • 1
    $\begingroup$ Don't let the words "Peano" and "Gödel" impress you. Being an incomplete theory exactly means to have at least two non elementary equivalent models. $\endgroup$ – Pece Apr 10 '14 at 18:56
2
$\begingroup$

Take a canonical Gödel G sentence for PA i.e. a wff that "says" of itself 'I am unprovable in PA'. Ask yourself:

  1. Is G provable from the axioms of PA?
  2. Is G true in every model of the axioms of PA?
  3. Is G true at least in the standard model of PA?
  4. What can you deduce from your last two answers?

Hint: for one of these answers you appeal to Gödel's completeness theorem for first-order logic, and the fact that PA is a first-order theory.

$\endgroup$
  • 1
    $\begingroup$ Picking $G$ is somewhat more specific than you really need. $\endgroup$ – user14972 Apr 10 '14 at 16:39
  • $\begingroup$ Yes, more specific than is needed, but the obvious choice ... $\endgroup$ – Peter Smith Apr 10 '14 at 17:15
  • $\begingroup$ Thanks, Peter This is my reasoning then, would appreciate if you could let me know if it is correct. From the 1st Incompleteness theorem we know we have a sentence $G$ and that $G$ is true, in $\mathbb{N}$ but not provable. So since $G$ is not provable, $PA$ & $\neg G$ is consistent. Therefore by Gödel's completeness theorem, there is a model $\mathscr{W}$ in which $G$ is false. Thanks again really appreciate a great don as yourself answering my question. We used your formal Logic book in my 1st and 2nd years. $\endgroup$ – Jens Apr 10 '14 at 19:14
  • $\begingroup$ Yes indeed. Exactly! (And always good to hear that the Logic book is being used out there!) $\endgroup$ – Peter Smith Apr 10 '14 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.