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

Nonstandard Models of Arithmetic 27

MW: Enayat’s second major result is:

Theorem 7: Every countable recursively saturated model of PA+ΦT is a T-standard model of PA.

Filed under Conversations, Peano Arithmetic

Very Unique

My unique (but not very unique) microwave

Everyone has their pet peeves, and peeves about language abound. My pet peeve is with people who object that “very unique” is illogical. For example, this pithy statement:

Uniqueness is a binary condition. Something is unique or it is not. There are no degrees of uniqueness. Something cannot be partly unique, mostly unique, very unique, etc.

Filed under Logic, Rants

Selections from the History of Astronomy

Prev Next

Armillary Sphere, Facade of Santa Maria Novella (Wikimedia Commons)

Another post from the History Book Club, this time based on three books:

• To Explain the World: The Discovery of Modern Science, by Steven Weinberg.
• The Sun in the Church: Cathedrals as Solar Observatories, by J.L. Heilbron.
• The Composition of Kepler’s Astronomia Nova, by James Voelkel.

Filed under Astronomy, History Book Club

Topics in Nonstandard Arithmetic 10: Truth (Part 4)

Filed under Peano Arithmetic

Nonstandard Models of Arithmetic 26

MW: Continuing the recap… Continue reading

Filed under Peano Arithmetic

Nonstandard Models of Arithmetic 25

Previous Enayat post

MW: It’s been ages since John Baez and I discussed Enayat’s paper—not since October 2020! John has since moved on to fresh woods and pastures new. I’ve been reading novels. But I feel I owe it to our millions of readers to finish the tale, so here goes.

Filed under Peano Arithmetic

The Secret History of the Mongols

National Palace Museum, Taipei, Taiwan

Another post from the History Book Club.

Filed under History Book Club

Science and the Founding Fathers

Another post from the History Book Club. It seemed particularly appropriate for today (January 20th, Inauguration Day).

Science and the Founding Fathers: Science in the Political Thought of Thomas Jefferson, Benjamin Franklin, John Adams, and James Madison,
by I. Bernard Cohen, W.W. Norton & Company, 1995.