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 Sat_M: if φ belongs to L(PA), then M⊧φ iff N⊧Sat_M(⌜φ⌝). 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 a∈N satisfying

N⊧(φ_i↔a_i=1), for all i∈ℕ

where φ_i is i-th sentence of L(PA) (in some recursive enumeration—say i=⌜φ⌝ ), and a_i 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  N ⊧ n=⌜φ⌝ ∧ a_n=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⊧(φ_i↔a_i=1), for all i∈ℕ—not necessarily for all i∈N. 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