Author Archives: Michael Weiss

Topics in Nonstandard Arithmetic 7: Truth (Part 3)

Prev TOC Next

Previous “Truth” post

Last time we looked at Tarski’s inductive definition of truth formalized inside ZF set theory. Recall the setup: a first-order language L and a structure S for L. The domain of S is a set (not a proper class), which means that the relations and functions on the domain are too. The fruit of the effort was a formula in L(ZF), True(L,S,φ), which expresses “S is a set-based structure for L and φ is a sentence of L and S ⊧ φ”. (With minor changes, we get a parametrized version, True(L,S,φ,u). Here u is a finite list of elements of the domain of S to be assigned to the free variables in φ.)

In the first post in this series, we looked at {Trued}, an infinite sequence of formulas in L(PA); Trued expresses truth for formulas with parse-depth at most d. In this post, we’ll look at SatΣn, satisfaction for Σn formulas.

SatΣn is the “professional-grade” version of Trued; it’s what you’ll find in the textbooks in the bibliography, like Kaye. (I suppose “satisfaction” sounds more professional than “truth”.) Like Trued, it’s an infinite sequence of formulas. Like Trued, it limits its ambitions by complexity: parse-tree depth for Trued, and the number of quantifier alternations for SatΣn. So (for example) the axiom ∀xyz((z=0 ∨ ¬x<y) ∨ x·z<y·z) has depth 6, but belongs to Π1. (SatΠn amounts to the negation of SatΣn, since a Πn sentence is true iff its negation, a Σn sentence, is false.)

The main effort in defining SatΣn takes place at the ground level, defining SatΔ0. Surprising! And this definition shares DNA with True(L,S,φ) from ZF. Here are some analogies to conjure with:

PA : infinite sets  ::  ZF : proper classes
PA : finite sets  ::  ZF : sets.

In ZF, quantification over a set is a “bounded search”, in some sense. In PA, the same holds for quantification over a finite range.

The construction of True(L,S,φ) rested on the concept of an instantiation tree. We can do nearly the same thing for Δ0 sentences. Here’s an example, for the sentence ∃x<3 ∀y<x ψ(x,y):

I’ve made a different graphic choice from the diagram for the ZF case. Instead of regarding the instantiations “∀y<0 ψ(0,y)”, “∀y<1 ψ(1,y)”, and “∀y<2 ψ(2,y)” as all “living in the same node”, I’ve split them into separate nodes. This reflects a more fundamental difference: in the ZF case, all the quantifications are “bounded” by the same set, the domain of S. Here the bound varies from node to node.

The instantiation tree must be grown from the root down. Our Δ0 formula is a sentence, i.e., no free variables. Of course subformulas need not be closed. Any outermost quantifier must have a fixed bound—that is, a closed term for the bound, which can be evaluated. The associated quantifier node will have a bounded list of children, in which the quantified variable has acquired a fixed value. The example above is particularly simple, but something like

x<10 (¬ξ(x) ∨ ∃y<3x w<x+y (ζ(x,y,w)∧η(x,y,w)) )

goes much the same way. We’ll have 10 nodes under root, each a disjunction. The one with x=5 will have a right hand child ∃y<15… . One of those children has y=7, and is labeled ∀w<12 (i.e., x+y=5+7). Its 12 children are all conjunctions.

Truth evaluations proceed bottom up, of course, using the obvious rules. Now, can we code all this into PA? The diagrams look pretty when the bounds are all elements of ℕ, but over a nonstandard model the bounds can be nonstandard. That’s OK, provided we can code all this into a formula of PA. (And by ‘formula’, I mean an ordinary vanilla formula, not one of “nonstandard length” or anything like that.)

The short answer is, sure, no problem! PA is “basically the same as” ZF¬∞. The instantiation tree and its truth evaluation “look like” finite combinatorial objects, so of course PA can encode them. The “local behavior” aspect of the ZF case—a thousand quantifiers in the formula don’t bleed through to give a thousand quantifiers in True(…)—applies here too.

For the long answer, consult Kaye, Chapter 9. He begins by saying

This is the chapter that no one wanted to have to write: the material here is technical and difficult to describe clearly, yet it is very necessary for later work. I have put it off as long as possible, but cannot do so any longer.

Nineteen pages later, he gives the definition of SatΔ0. A few pages more establish its chief properties. Then in a quarter of a page, he defines the sequences SatΣn and SatΠn, building on top of SatΔ0. It’s much like Trued: a syntactic ∃x becomes semantic. Life is just a touch more complicated, because SatΣn must handle a block of existential quantifiers prepended to a Πn−1, formula; likewise for SatΠn. But PA has mastered lists, so this is barely a hiccup.

Just a few more remarks. If you do decide to read Kaye’s Chapter 9, be aware he does not explicitly use parse-trees. Instead, he ‘parses’ the Gödel numbers that represent strings of symbols. You will also find data structures that you can construe as instantiation trees, although he does not make this explicit. I confess I have not had the patience to go through his treatment line by line. My sympathy for the author’s pains!

As a reward for the detailed development, Kaye can show that SatΔ0 is a Δ1(PA) formula, and SatΣn and SatΠn are Σn(PA) and Πn(PA) formulas (respectively) for n>0. (The quantifiers “bleed through”.) A diagonal argument now shows that the Σnn hierarchy is a true hierarchy: for any model N of PA, there is a relation on N that is Σn(N) but not Πn(N), and vice versa.

As with Trued, PA proves the expected equivalence for any sentence φ with the right complexity. That is, if φ belongs to Σn(PA), then PA⊢φ↔SatΣn(⌜φ⌝). Likewise for the parametrized version. Note that this is a collection of proofs, one for each formula φ.

That’s all for now!

Previous “Truth” post

Prev TOC Next

2 Comments

Filed under Peano Arithmetic

Topics in Nonstandard Arithmetic 6: The Axioms

Prev TOC Next

This is a “reference” post. With all the posts already filed under Peano Arithmetic, I realize I never explicitly stated the axioms. Of course you can find them on Wikipedia and at a large (but finite) number of other places, but I thought I should put them down somewhere on this site.

Continue reading

Leave a comment

Filed under Peano Arithmetic

Topics in Nonstandard Arithmetic 5: Truth (Part 2)

Prev TOC Next

Next “Truth” post

Last time we looked at Tarski’s inductive definition of truth, expressed informally. We saw how for models of PA, it can be formalized as an infinite sequence of formulas True0, True1, …, formulas belonging to L(PA) itself. But not as a single formula in L(PA).

Continue reading

4 Comments

Filed under Peano Arithmetic

Topics in Nonstandard Arithmetic 4: Truth (Part 1)

Prev TOC Next

In post 15 of the Conversation, I observed:

  • Gödel’s two most famous results are the completeness theorem and the incompleteness theorem.
  • Tarski’s two most famous results are the undefinability of truth and the definition of truth.

The second bullet has occupied its share of pixels in the Conversation. Time for a summing up.

Continue reading

3 Comments

Filed under Peano Arithmetic

Non-standard Models of Arithmetic 20

Prev TOC Next

Trudy Campbell

MW: OK, let’s recap the setup: we have a three-decker ωUUV. So far as U is concerned, ωU is the “real, true omega”. V knows it isn’t. Enayat’s question: what properties must an omega have, for it to be the omega of a model of T? Here T is a recursively axiomatizable extension of ZF, and U is a model of it.

Continue reading

1 Comment

Filed under Conversations, Peano Arithmetic

Topics in Nonstandard Arithmetic 3: The Arithmetic Hierarchy (Part 2)

Prev TOC Next

Last time I defined ∃n and ∀n prefixes and formulas; Σn, Πn , and Δn relations (and functions) on ℕ; Σn(PA), Πn(PA), and Δn(PA) formulas in L(PA); and Σn(N), Πn(N), and Δn(N) relations (and functions) on a model N of PA. I won’t repeat all that, but a few bullet points may help load it into working memory:

Continue reading

Leave a comment

Filed under Peano Arithmetic

Topics in Nonstandard Arithmetic 2: The Arithmetic Hierarchy (Part 1)

Prev TOC Next

Continue reading

6 Comments

Filed under Peano Arithmetic

Nonstandard Arithmetic: A Long Comment Thread

TOC Post 7 Post 8

Posts 7 and 8 developed an extensive comment thread, mainly between Bruce Smith and John Baez. It was hard to follow in that format, so I converted it to a separate webpage.

Topics: (a) Why do standard models of ZF have standard ω’s? (b) Interactions between the Infinity Axiom and the Foundation Axiom (aka Regularity). (c) The compactness theorem. (d) The correspondence between PA and “ZF with infinity negated”: nonstandard numbers vs. ill-founded sets, and the Kaye-Wong paper (cited in post 8).

TOC Post 7 Post 8

33 Comments

Filed under Conversations, Peano Arithmetic

Topics in Nonstandard Arithmetic 1: Table Setting

TOC Next

John Baez and I have been having a conversation about nonstandard models of Peano arithmetic (PA). It started with “John’s dream”, as I’ll call it, which begat a goal: understand a paper by Enayat. For more on the dream and the goal, check out the second post.

Continue reading

Leave a comment

Filed under Peano Arithmetic

Non-standard Models of Arithmetic 19

Prev TOC Next

JB: Before we get into any proofs, I’d just like to marvel at Enayat’s Prop. 6, and see if I understand it correctly. I tried to state it in my own words on my own blog:

Every ZF-standard model of PA that is not V-standard is recursively saturated.

Continue reading

1 Comment

Filed under Conversations, Peano Arithmetic