9
$\begingroup$

Having just read Noah Schweber's excellent answer to this question, I am reminded of something that has always mystified me. I was taught that the Peano Postulates are categorical (that is, any two models are isomorphic,) a fact which seems intuitively obvious. So, how can there be nonstandard models? In particular if I have some uncountable nonstandard model of PA, why can't I pick some element $s$, and consider the elements$$s, s+s, s+s+s, ...$$ to get a countable model inside the given model, just as I would construct the even positive integers inside the natural numbers by taking $s=2$? Surely the uncountable model and the countable model aren't isomorphic, are they?

I understand how the compactness theorem shows the existence of nonstandard models, and I have no problem with that. I just don't understand how to reconcile this with categoricity.

$\endgroup$

2 Answers 2

Reset to default
14
$\begingroup$

There are two different versions of "Peano arithmetic": a first-order version and a second-order version. The second-order version has as its induction axiom the statement that for any subset $S$ of the structure, if $0\in S$ and $x+1\in S$ for all $x\in S$, then $S$ is the entire structure. The first-order version has a much weaker induction axiom: it only applies to subsets $S$ which are definable in first-order logic (that is, subsets which can be described as the set of elements of the structure which make some first-order formula true). The first-order version is generally far more interesting from the perspective of logic and is what "Peano arithmetic" normally refers to, since it can be formulated as a first-order theory.

The second-order version of Peano arithmetic is categorical, but the first-order version is not. The answer you linked to is talking about the first-order version, not the second-order version.

$\endgroup$
5
  • $\begingroup$ Thanks. This also clears up a lot of fog I've had about first- and second- order theories. I always thought that "Peano Arithmetic" meant the second-order theory, and I could never figure out why it was considered a first-order theory. I just concluded that logic was one of those things I would never understand. Just to be sure I understand, I can't even state the proposition "Every natural number is even or odd," in the first-order theory, can I? $\endgroup$
    – saulspatz
    Commented Jan 20, 2018 at 3:23
  • $\begingroup$ Well, that may depend on what you mean by "even" and "odd". But one reasonable way to state that in first-order arithmetic is $\forall n\exists m (n=2m\vee n=2m+1)$. $\endgroup$
    – Eric Wofsey
    Commented Jan 20, 2018 at 3:25
  • $\begingroup$ Okay, I see. But I need the second-order induction to prove it, right? Is there an elementary book source that discusses these matters? $\endgroup$
    – saulspatz
    Commented Jan 20, 2018 at 3:32
  • 1
    $\begingroup$ @saulspatz: no, you can prove that in first-order PA. In fact, anything you can prove in second-order PA can also be proved in a non-categorical theory of arithmetic known as $Z_2$, which is also confusingly called "second order arithmetic". $\endgroup$
    – Carl Mummert
    Commented Jan 20, 2018 at 3:36
  • $\begingroup$ As I hope to explain in my answer, even the second order version is not categorical on its own; the categoricity depends on which semantics we use for second-order logic. Unfortunately, these things are not explained in many intro logic texts, even though they are well understood by practicing logicians. $\endgroup$
    – Carl Mummert
    Commented Jan 20, 2018 at 3:48
10
$\begingroup$

The way that we obtain categoricity in the second-order Peano axioms is not only about the axioms - it's also about the way we interpret them. We need to be talking about the "second order Peano axioms", rather than first-order Peano arithmetic, for the rest of this answer.

There are two different ways to treat the semantics of second order Peano arithmetic. They are known as "standard semantics" and "Henkin semantics".

In standard semantics, each model can have its own set of "natural numbers" $\mathbb{N}$, and then we interpret quantifiers over subsets of $\mathbb{N}$ as quantifying over all subsets of the set of numbers in the model.

In Henkin semantics, we allow each model to have both a set of "numbers" $\mathbb{N}$ and a set of "sets of numbers", and we interpret a quantifier over subsets of $\mathbb{N}$ as only quantifying over the collection of "sets of numbers" that is in the model. So standard semantics is the same as Henkin semantics with the extra restriction that we only consider models where the collection of subsets of $\mathbb{N}$ is the entire powerset of the set of naturals $\mathbb{N}$ of the model.

Given any set of (possibly second-order axioms) for arithmetic, we can choose either of these semantics. Either way, the set of provable consequences of the axioms is exactly the same. The only difference is in which models we consider.

Given this setup, we can prove that second-order Peano arithmetic with standard semantics is categorical, while second-order Peano arithmetic with Henkin semantics is not.

The key point here is that it is not the theory which is categorical - it is the combination of the theory and the collection of models that we consider that combine to make the theory categorical. If we consider a smaller collection of models, it is easier for the same theory to be categorical.

When we use methods such as compactness or the completeness theorem, we generate models in sense of Henkin semantics that may not be models in standard semantics. That fact explains how the categoricity of second order PA in standard semantics can be reconciled with the compactness theorem - standard semantics can ignore many possible interpretations of a set of axioms.

$\endgroup$
5
  • 2
    $\begingroup$ I've been puzzling and Googling over this for about 45 minutes, and I'm still not confident that I understand. Is to correct (at least approximately) to say that first-order Peano arithmetic is Henkin semantics where the allowable sets are those definable in first-order logic, or are they just two entirely different things? (I'm trying integrate your answer and Eric Wofsey's.) $\endgroup$
    – saulspatz
    Commented Jan 20, 2018 at 5:01
  • 1
    $\begingroup$ In first order Peano arithmetic, we have one sort of variables, and these variables are number variables. So we can write formulas that say things like "every number is even or is odd", "for every number there is a larger number that is prime", and more complicated expressions that only refer to numbers. There is a set of induction axioms, which says that for each formula $\phi(n)$ we have $[\phi(0) \land (\forall m)[\phi(m)\to\phi(m+1)]] \to (\forall n)\phi(n)$. $\endgroup$
    – Carl Mummert
    Commented Jan 20, 2018 at 12:49
  • 1
    $\begingroup$ In second order Peano arithmetic, the syntax is different. Now we have two sorts of variables. One of the two sorts is for numbers, and the other is for sets of numbers. So now we can write formulas that directly refer to sets of numbers - we have more formulas than we did before. To interpret these formulas, we can use either standard semantics or Henkin semantics - either way we still have second order arithmetic. $\endgroup$
    – Carl Mummert
    Commented Jan 20, 2018 at 12:51
  • 1
    $\begingroup$ There is quite a bit of info at en.wikipedia.org/wiki/Second-order_arithmetic $\endgroup$
    – Carl Mummert
    Commented Jan 20, 2018 at 12:54
  • $\begingroup$ I appreciate your patience, thanks again. $\endgroup$
    – saulspatz
    Commented Jan 20, 2018 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .