0
$\begingroup$

I started a discussion in comments to this answer, but it grew beyond what fits comments, so I'm promoting it to this separate question. Here is a recap:

$\Large\color{green}{\unicode{0x2BA9}}\,$ The fact that moving to full second-order semantics is no different than just working with the standard model is one reason that these semantics are not so useful. Anything we could do with full second-order semantics, we could do in our usual first-order semantics by just talking about the standard model explicitly. Any question that we cannot answer about the standard model when working in ZFC will be equally unanswerable when we work with full second-order semantics.

$\Large\color{maroon}{\unicode{0x2BAA}}\,$ “moving to full second-order semantics is no different than just working with the standard model” — I just wanted to confirm that there is no way to distinguish between standard and non-standard numbers within the first-order arithmetic, right? We need some level of ambient set theory to be able to talk about different models, then we can pinpoint the minimal model $\omega$ and call it “standard”, right? But if we want to formalize the ambient set theory, and choose to do it using first-order logic, then again there will be different models of that set theory, and if we look at those models from another ambient set theory, we will see that each of them thinks it exactly pinpoints the unique “standard” model for integers, but from outside we can see that those models are not isomorphic. Is my understanding here correct?

$\Large\color{green}{\unicode{0x2BA9}}\,$ Yes, exactly. A nonstandard model of PA has no way to tell which elements are standard and which are nonstandard. In the context of set theory, this issue has been discussed quite a bit recently in the context of the “multiverse axioms” […]

$\Large\color{maroon}{\unicode{0x2BAA}}\,$ Do you think it is a coherent and defensible philosophical position that actually we know how the true standard model of arithmetic looks (a single chain of natural numbers starting from $0$, and no other parts not connected to it), can distinguish it from other models, and can reliably communicate our understanding to other people, because we are able to think in terms of second-order logic with full semantics, at least, when we are talking about simple finitary objects like integers, or strings of symbols (such as wff)?

I cannot say for sure whether (or to what degree) my last question belongs to mathematics proper or to philosophy of mathematics. To clarify, I am not asking whether the standard model of natural numbers exists in some platonic sense. I hold a view that mathematics studies formal and formalizable reasoning, and ways to put our ideas into a precise enough form that they can be communicated to other people and understood by them, so that when we discuss them we can be confident we are on the same page. I have a feeling that when I think about various models of artithmetic, I can recognize or pinpoint the standard model among them. Perhaps, this is because my informal reasoning resembles the second-order logic with full semantics, where Dedekind’s proof of categoricity of arithmetic holds. I also have a feeling that when I want to discuss the standard model with another person, I can reliably communicate, using a mixture of formal and informal approaches, which model I have in mind. So, when I say something like “consider a formula of a finite length” or “the length of a proof is a standard natural number”, I am fairly confident that the other person understands exactly what I have in mind. But because the second-order logic does not have a complete proof system, and first-order theories (that are complex enough to be capable to represent arithmetic) are inherently non-categorical, I have a lingering doubt that my confidence here might be an illusion. So, my question is whether there is a way to reliably pinpoint the standard model of natural numbers and communicate it to other mathematicians (assuming they cooperate in good faith, and do not just try to troll me). Does Dedekind’s proof of categoricity play any role in it? Does it make sense to say our informal reasoning corresponds to second-order logic with full semantics?

Here are some references to provide more context to this discussion:

$\endgroup$
3

2 Answers 2

4
$\begingroup$

The question of whether/how we can uniquely identify the standard model is one that has received attention in the philosophical literature. One proposed positive answer goes through Tennenbaum's theorem. Briefly, here's the argument. Tennenbaum's theorem asserts that the standard model is the only model of arithmetic whose addition and multiplication are computable functions. Ordinary experience tells us that $+$ and $\times$ are computable, and we seem to have a good handle on what computability means via the Church–Turing phenomenon. So we can uniquely identify $\mathbb N$.

Of course, this argument has in turn faced attacks. For instance, this paper by Button and Smith critiques it. Their paper is quite nice, and does a good job at laying out the difficulties in this sort of argument about identifying $\mathbb N$.

$\endgroup$
9
  • 1
    $\begingroup$ I don't see how to make sense of computability without already some notion of $\mathbb{N}$. $\endgroup$ Apr 13, 2021 at 1:00
  • $\begingroup$ That's more or less the key point in the Button & Smith paper. $\endgroup$ Apr 13, 2021 at 1:13
  • 1
    $\begingroup$ Yeah, and I'm with them on this one. (That doesn't mean I dislike this answer of course!) $\endgroup$ Apr 13, 2021 at 1:13
  • 1
    $\begingroup$ Me too. I think it's an interesting argument, but it ultimately fails. $\endgroup$ Apr 13, 2021 at 1:14
  • $\begingroup$ @KamerynWilliams Thanks, that is an interesting paper! It points that an attempt to pinpoint the standard model using Tennenbaum’s theorem will necessary involve circular reasoning because to define a “recursive function” we need to use the notion of a “finite number” of steps. That’s seems a valid argument. But you also mentioned the Church–Turing thesis, which is not a mathematical theorem, but rather a well-established empirical principle that our intuitive notion of “computable function” (ignoring possible limitation on available time and space in the real world) exactly corresponds to … $\endgroup$ Apr 13, 2021 at 22:07
3
$\begingroup$

Per the compactness theorem, there's no "internal first-order test" which will identify $\mathbb{N}$. Additionally, many characterizations of $\mathbb{N}$ lean on quantification over finite objects, which may be unsatisfactory (e.g. "unique term model" uses closed terms, "unique computable model" uses halting computations, etc.).

On the other hand, there is an "algebraic" characterization of $\mathbb{N}$: we can characterize $\mathbb{N}$ externally as "the unique model of $\mathsf{Q}$ (say) which is embeddable into every other model of $\mathsf{Q}$." Now in terms of logical complexity this latter characterization is no better than "the unique model of first-order Peano arithmetic with no nonempty subsets without least elements." However, it is arguably in a sense more natural: it pins down $\mathbb{N}$ as an element of a "higher-order" structure (whose elements are the models of $\mathsf{Q}$) in a first-order way.

Does that count as "pinpointing and communicating?" Personally I think it's about the best we can hope for, and there's little more that can be said until the question is itself pinpointed and communicated more clearly.


Incidentally, here's an amusing aside:

Suppose $\mathcal{L}$ is a logic such that $(i)$ $\mathcal{L}$ has the downward Lowenheim-Skolem property and $(ii)$ there are $\mathcal{A}\equiv\mathcal{B}$ with $\mathcal{A}\not\equiv_\mathcal{L}\mathcal{B}$. Then the isomorphism type of the standard model of arithmetic is an $\mathcal{L}$-pseudoelementary class: there is a satisfiable $\mathcal{L}$-sentence $\varphi$ and a unary relation $U$ in the language of $\varphi$ such that $\mathcal{M}\models\varphi\implies U^\mathcal{M}\cong\mathbb{N}$. So informally: if you go much past first-order logic and don't bring uncountable sets into the picture you wind up being able to pin down $\mathbb{N}$ in a rather strong way!

(This result is proved along the way to Lindstrom's theorem, even if it's not stated explicitly; it's what the "smileyface argument" actually accomplishes.)

$\endgroup$
4
  • $\begingroup$ Or as the unique model of any reasonably basic arithmetic where every object has a closed term defining it (i.e. a numeral). $\endgroup$
    – Asaf Karagila
    Apr 12, 2021 at 23:51
  • $\begingroup$ But any definition of a closed term will again use some form of “a sequence of symbols whose length is a standard integer”, or just “a finite sequence” that tacitly implies we have the standard model of integers in mind that provides the meaning to “finite”. Or when we say “PA is actually consistent”, we mean there is no finite proof of 0 = 1 in it, despite that non-standard models of arithmetic have non-standard numbers that are Gödel numbers of such proofs (of non-standard length). $\endgroup$ Apr 13, 2021 at 0:16
  • 1
    $\begingroup$ @VladimirReshetnikov At some point you have to articulate some criteria for "pinpointing and communicating" (incidentally, note that my answer avoided mentioning finite sequences and used a finitely axiomatizable theory). $\endgroup$ Apr 13, 2021 at 0:26
  • $\begingroup$ @ěŕëĺíüęŕ͘ ěţěëŕ Coming back to this after a while, I'm curious what your thoughts are on the "algebraic" characterization in my answer. $\endgroup$ May 4, 2021 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.