Nonstandard Models of Arithmetic 28

Prev TOC Next

MW: I ended the last post with a puzzle. Here it is again, in more detail.

In Topics 4 I stated and proved Tarski’s Undefinability Theorem for any nonstandard N model of PA:

There is no formula True(x) in L(PA) such that for all sentences φ in L(PA),
N⊧φ iff N⊧True(⌜φ⌝).

And in Topics 10, I “collided” this with the Arithmetized Completeness Theorem (ACT), concluding:

So if N⊧Con(PA), then the ACT gives birth to a model of PA that is not elementarily equivalent to N (over L(PA)).

For if M is the model of PA given by the ACT, then it comes equipped (courtesy of the ACT) with a truth predicate SatM: if φ belongs to L(PA), then M⊧φ iff N⊧SatM(⌜φ⌝). So of course we can’t have M⊧φ iff N⊧φ.

On the other hand, in the last post we started with a recursively saturated N satisfying ΦT and used the ACT to construct a model U of T such that ωU is elementarily equivalent to N. Contradiction?

OK, it’s a touch indirect: our model ωU sits inside the model U constructed by the ACT. But this is a niggle—it’s easy to adapt the argument.

How exactly did we enforce Th(ωU)=Th(N)? Go back to the proof, and you’ll find that the ACT is a red-herring. The key was this step: using recursive saturation, find an aN satisfying

N⊧(φiai=1), for all i∈ℕ

where φi is i-th sentence of L(PA) (in some recursive enumeration—say i=⌜φ⌝ ), and ai is the i-th bit of a (when a is treated as a bitstring). So right away we have a truth predicate for N:

N ⊧ φ iff  Nn=⌜φ⌝ ∧ an=1.

But this predicate involves the parameter a, so it’s not in L(PA). And Tarski’s Undefinability Theorem doesn’t apply to formulas with parameters. (Just look at the proof.)

What about the use of the ACT? Is it OK if the theory in question involves a parameter? It is indeed: look at the very end of the Proof Sketch in Topics 10. However, the “collision” remark no longer holds in that case.

It’s fun to try to squeeze these theorems as hard as possible, and watch them squirm out of apparent contradictions. What about the special case of N=ℕ? For ℕ “we don’t need no stinkin’ parameters”—every element of ℕ can be named with a term “1+1+…+1”. (Or “0” or “1”.) Ah, but ℕ isn’t recursively saturated, so the argument producing a falls through.

All right, let’s return to a recursively saturated N. Then we do have an a encoding Th(N). How about replacing this parameter with a nonstandard length term “1+1+…+1”? Does the proof of the Undefinability Theorem still go through?

Seems to. But now consider how a encodes Th(N). We have N⊧(φiai=1), for all i∈ℕ—not necessarily for all iN. Our “truth predicate”, of nonstandard length, covers only standard sentences. Essentially we have replaced a formula of the form φ(x,a) with one of the form φb(x), where both a and b are nonstandard. The Undefinability Theorem says that there is no formula in L(PA) that “defines truth” for all sentences of L(PA). Interpreting the first “L(PA)” nonstandardly and the second standardly, is pulling a fast one.

That was illuminating, I hope. We’ll return to the proof of Enayat’s Theorem 7 next time.

Prev TOC Next


Filed under Conversations, Peano Arithmetic

3 responses to “Nonstandard Models of Arithmetic 28

  1. This note is long overdue, but abiding by the principle of better late than never, I would like to register my sincere applause for your indefatigable industry in the formidable task of providing a most readable expository account of a wide range of highly technical material.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.