2

Suppose I create a Gödel sentence $G$ which is true in the natural numbers $N$, but false in some non-standard model $M$. I understand that $G$ is a very messy sentence, but is it possible to simpify it to a form where it's obvious that this sentence is true in $N$, but not in $M$?

I.e. the sentence could encode "every element can be reached by repeatedly adding $1$ to $0$".

Michael Hardy
  • 1
Frank Meulenaar
  • 121
  • Whatever reasonable way of encoding this would be true in $M$ as well as we do not have ways of expressing "finitely many times" in first order. What we do is a trick: We use that there is a definable bijection between $\mathbb N^{<\mathbb N}$ and $\mathbb N$ and use it to code finite sequences via numbers. To say that we can reach the element $n$ from $0$ by repeatedly adding $1$, what we say is that there is a sequence of length $n+1$, starting at $0$, ending at $n$, and such that for each $i$ with $i+1\le n+1$, the $i+1$-st member of the sequence is $1$ more than the $i$-th member. – Andrés E. Caicedo Aug 12 '13 at 19:09
  • Note that the trick has the disadvantage that we do not have a way of saying there that $n$ "is finite", and the same procedure that establishes that we can code such finite sequences gives us in $M$ sequences of this kind of non-standard length. – Andrés E. Caicedo Aug 12 '13 at 19:10
  • 2
    What we can do is give examples of sentences that are not coding metamathematical facts, so they have a more direct combinatorial flavor, and have the same property that they hold in $\mathbb N$ but fail in some nonstandard models. The prime example is the strong Ramsey theorem of Paris and Harrington. Other examples are the termination of Goodstein sequences, the fact that Hercules has a winning strategy in Hercules-Hydra games (Jeff-Paris), and the many examples that Harvey Friedman has produced throughout his research. – Andrés E. Caicedo Aug 12 '13 at 19:17

1 Answers1

2

Of course that depends on what exactly you call a "Gödel sentence", and what you consider "obvious".

But I think the answer has to be "no", though for somewhat unenlightening reasons. If your $M$ is supposed to be a model of Peano Arithmetic, the problem we run into is that even though one easily proves that non-standard models of PA must exist, it is very hard to describe one explicitly enough that it can be "obvious" that your simplified $G$ is false in it.

hmakholm left over Monica
  • 286,031
  • This can be made more precise: There is no recursive non-standard model of $\mathsf{PA}$ (Tennenbaum's theorem). Much less than $\mathsf{PA}$ is needed for this. On the other hand, "non-recursive" cannot be strengthened much, as any recursive consistent theory has a $\Delta_2$ model (by arguing carefully with Henkin's proof of the completeness theorem). – Andrés E. Caicedo Aug 12 '13 at 19:28
  • I kown about Tennenbaum's theorem, that's fine; I only want to see that $G$ will be false if there's something more than $N$, without understanding how $M$ then should exactly look like. – Frank Meulenaar Aug 13 '13 at 05:45
  • @FrankMeulenaar: You cannot do that either, because if $G$ was false in all nonstandard models, $PA+G$ would characterize the standard naturals uniquely, which Gödel's theorem itself says is impossible. – hmakholm left over Monica Aug 13 '13 at 09:57