Defining the standard model of PA so that a space alien could understand

Question

First, some context. In one of the comments to an answer to the recent question Why not adopt the constructibility axiom V=L? I was directed to some papers of Nik Weaver at this link, on conceptualism. Many of the ideas in those papers appeal to me, especially the idea (put in my own words, but hopefully accurate) that the power set of the natural numbers is a work in progress and not a completed infinity like $\mathbb{N}$.

In some of those papers the idea of a supertask is used to argue for the existence of the completed natural numbers. One could think of performing a supertask as building a machine that does an infinite computation in a finite amount of time and space, say by doing the $n$th step, and then building a machine of half the size that will work twice as fast to do the $(n+1)$th step and also recurse. (We will suppose that the concept of a supertask machine is not unreasonable, although I think this point can definitely be argued.)

The way I'm picturing such a machine is that it would be a $\Sigma_1$ oracle, able to answer certain questions about the natural numbers. I suppose we would also have machines that do "super-supertasks", and so forth, yielding higher order oracles.

To help motivate my question, suppose that beings from outer space came to earth and taught us how to build such machines. I suppose that some of us would start checking the validity of our work as it appears in the literature. Others would turn to the big questions: P vs. NP, RH, Goldbach, twin primes. With sufficient iterations of "super" we could even use the machines to start writing our proofs for us. Some would stop bothering.

Others would want to do quality control to check that the machines were working as intended. Suppose that the machine came back with: "Con(PA) is false." We would go to our space alien friends and say, "Something is wrong. The machines say that PA is not consistent." The aliens respond, "They are only saying that Con(PA) is false."

We start experimenting and discover that the machines also tell us that the shortest proof that "Con(PA) is false" is larger than BB(1000). It is larger than BB(BB(BB(1000))), and so forth. Thus, there would be no hope that we could ever verify by hand (or even realize in our own universe with atoms) a proof that $0=1$.

One possibility would be that the machines were not working as intended. Another possibility, that we could simply never rule out (but could perhaps verify to our satisfaction if we had access to many more atoms), is that these machines were giving evidence that PA is inconsistent. But a third, important possibility would be that they were doing supertasks on a nonstandard model of PA. We would then have the option of defining natural numbers as those things "counted" by these supertask machines. And indeed, suppose our alien friends did just that--their natural numbers were those expressed by the supertask machines. From our point of view, with the standard model in mind, we might say that there were these "extra" natural numbers that the machines had to pass through in order to finish their computations--something vaguely similar to those extra compact dimensions that many versions of string theory posit. But from the aliens' perspective, these extra numbers were not extra--they were just as actual to reality as the (very) small numbers we encounter in everyday life.

So, here (finally!) come my questions.

Question 1: How would we communicate to these aliens what we mean, precisely, by "the standard model"?

The one way I know to define the standard model is via second order quantification over subsets. But we know that the axiom of the power set leads to all sorts of different models for set theory. Does this fact affect the claim that the standard model is "unique"? More to the point:

Question 2: To assert the existence of a "standard model" we have to go well beyond assuming PA (and Con(PA)). Is that extra part really expressible?

Answer 1

These are fundamental questions. We know that any computable set of axioms which holds of the natural numbers must also have nonstandard models. But, paraphrasing Hilary Putnam, if axioms cannot capture the "intuitive notion of a natural number", what possibly could?

As I see it, there are two possible positions on this. One is that we do know what the natural numbers are, and the fact that axioms cannot capture them shows some limitation in the axiomatic method, not in the concept of number itself. The other is that our inability to capture the natural numbers axiomatically shows that we do not actually have a definite conception of them.

I hold the first view, but I admit that the second has its appeal. Asking how we could communicate the idea of a standard model to aliens brings home the difficulty of affirming that we have a clear conception of something while admitting that we are unable to communicate it through language (in particular, axioms).

This leads to deep philosophical questions about how we can communicate anything through language. Cf. Wittgenstein's "private language" argument and his ideas about rule-following.

Here are some things I would say in defense of the view that our conception of $\mathbb{N}$ really is definite, despite the fact that we cannot capture it with (first order) axioms:

1. Skepticism about the natural numbers can be ramped up. What do you say to someone who denies that we have a clear conception of $10^{100}$? There are serious people who would say we don't. Frankly, I think I have a clearer conception of $\mathbb{N}$ than of $10^{100}$.

2. My sense is that everyone accepts that our conception of the natural numbers is definite until they learn the incompleteness theorems, but some people are so impressed by these results that they abandon the idea that there even is a definite set of natural numbers. But Wittgenstein's rule-following paradox shows that even axioms may lack the definite character we ascribe to them. So why would we take them as the be-all end-all?

3. Taking the view that anything meaningful is captured by axioms, and thus that $\mathbb{N}$ is indefinite, has some unpleasant consequences. Say you take the view that there is no distinguished "standard" model of PA: all that matters is what statements can be proven from the Peano axioms. Then you have to accept that "what statements can be proven from the Peano axioms" is itself indefinite. Because the length of a valid proof in PA is a natural number, so if we don't know what the natural numbers are then we don't know what are the possible lengths of proofs. There could be "proofs in PA" which are valid on one version of $\mathbb{N}$ but not on another. Can you really swallow this?

4. I think the strongest argument in favor of the definiteness of $\mathbb{N}$, and against the idea that PA, or any other axiomatization, is the be-all end-all, is the evident fact that we have an open-ended ability to go beyond any computable set of axioms, for instance by affirming their consistency. If you accept PA you should accept Con(PA), and the process doesn't stop there: you can then accept Con(PA + Con(PA)), and so on. This goes on to transfinite levels. If our understanding of $\mathbb{N}$ really were fully captured by some particular set of axioms then we would not feel we had a right to strengthen those axioms in any special way; the fact that we do feel we have this right shows that our understanding is not captured by any particular set of axioms.

This is my view.

Answer 2

Here in the realm of mathematical fiction....

I imagine aliens who do not have the natural number that we call 13. They also lack 41 and 1681 and many other numbers. They do not have the successor or addition functions.

Instead...they regard multiplication and comparison as fundamental. They don't know how to add possibilities, but they know how to multiply and compare them. They rarely count, but they have a keen eye for when one rectangle is bigger than another. So they often arrange things into rectangles, and they regard it as the professional duty of bakers to sell goods in 3x4 boxes.

Instead of Peano arithmetic, these aliens have a first-order theory in the language $(1,\cdot,<)$. Their $<$ has the same properties as ours; their $\cdot$ has the same universal properties as ours; and their $<$ and $\cdot$ are compatible.

They believe in the number $2$, i.e. the unique number $x$ such that $$1<x \wedge \neg \exists z\, (1<z<x)$$ Similarly they believe in the numbers $3$ and $7$, and $12=2\cdot 2\cdot 3$ and $14=2\cdot 7$. But they can detect a gap between $12$ and $14$ because $$\exists k\, \exists x\, (12 x < k x < 14 x) \wedge \nexists k\, (12 < k < 14)$$

Their induction takes the form $$P(1) \wedge \forall x(\forall y(y<x \rightarrow P(y))\rightarrow P(x)) \rightarrow \forall x(P(x))$$

They may define $x+y=z$ by something like our formula $$S(xz)S(yz)=S(zzS(xy))$$ but this does not play a large role in their arithmetic.

Finally, we observe an embedding of their natural numbers into ours, uniquely fixed by the desire to preserve both $\cdot$ and $<$. But if they believe that there is no number in between $12$ and $14$, and they have lived happily without any such need, what are we to say?

Meanwhile here in New York...I learned how to count from the numbers on an elevator in the apartment building, and there was no 13th floor.

Answer 3

The answer to this question depends on how skeptical you want to be.

Let's consider a simpler task. Can we communicate to the aliens what we mean by "3"? It's possible to imagine a scenario in which we are unable to do this. Imagine for example that the aliens don't look like human beings and don't communicate using anything like a human language, but instead resemble ants. We can imagine trying to train the aliens to understand "3" if we are able to identify something that they desire (food, for example) and putting food inside boxes marked with 3 copies of the same symbol, while leaving other boxes empty. After a sufficiently long training period, we might become convinced that the alien ants have mastered what we mean by "3", but how could we ever be sure? It's quite conceivable that the next time we put 3 symbols on a box, they might get confused. Perhaps we use a new type of symbol that they have trouble parsing. Or perhaps we use exactly the same type of symbol as in the past, but it turns out that the concept they have learned from us is, when translated into our language, something like "3 provided there is currently no syzygy of three planets, and 4 if there is currently a syzygy of three planets" (cf. Goodman's grue paradox). In principle we might detect such a thing if our training period were sufficiently long, but we would still be unsure whether some other clause is "hiding" in there, manifesting itself even more rarely than planetary syzygies do.

If "3" cannot be communicated, then certainly something infinite like the natural numbers cannot be communicated. But suppose we grant that somehow, "3" can be communicated. Could we communicate the standard model of PA as opposed to some nonstandard model of PA?

My view is that it is a very peculiar kind of skepticism that regards nonstandard models of PA as posing a particular problem for communication tasks. A nonstandard model of PA is, by any conceivable measure, a more complicated concept than the standard model of PA. For starters, what do we even mean by PA? PA contains an induction schema. Communicating what we mean by the induction schema for PA is no easier than communicating what the standard model is. If you think there is a difficulty disambiguating between PA and nonstandard models of PA, then how do you explain to someone that when you say "PA" you mean that the induction schema ranges over formulas whose length is a standard natural number as opposed to formulas that are nonstandardly long?

To be sure, you are free to be skeptical that we are able to communicate what we mean by PA. But this kind of communication difficulty is more fundamental than the difficulty of communicating the difference between a standard and a nonstandard model of PA, since the latter must at least presuppose that we know what PA is.

Another way to see that PA is a red herring is to replace PA with Robinson's arithmetic Q. Can we communicate to the aliens the distinction between a standard and a nonstandard model of Q? The same difficulty with infinity arises; specifics about PA are irrelevant.

It comes down to a question of whether we think we can communicate something infinite, and if so, why it is that we think we can do so. Technical details about logic and arithmetic are a distraction.

Answer 4

Re: question 1, there is a precise sense in which this task is impossible, but we can arguably get a "dynamic approximation."

First the negative response. Since first-order logic isn't enough, a case can be made (which I would agree with incidentally) that there is no satisfactory way to communicate this. A relevant result for this general principle is Lindstrom's theorem, which intuitively says that any logic stronger than first-order logic must be fundamentally "infinitary," by virtue of not having a finitary proof system or by virtue of having to take into account uncountable structures even at the most basic level.

Now the positive response. Although prima facie it involves an appeal to a large fragment of the set-theoretic universe, we can think of the "from above" characterization (= the smallest model of PA) as a dynamic communication. The idea being that whenever you and I have possibly non-isomorphic models of PA, we each try to find embeddings of our own model into the other. If one of us succeeds and the other fails, then we tentatively agree that that person is holding the standard model. If both of us succeed, then we tentatively agree both are. And if we both fail, we tentatively agree that neither of us is holding on to the standard model. Note that while this process can be wildly fluctuating, it is stable in the following weak sense: if you are holding the standard model and I'm holding a nonstandard model, we won't possibly believe that my model is standard.

Of course, there is an appeal to quantification here. Namely, checking whether a purported embedding is actually an embedding involves a universal quantifier. But in this case we're only quantifying over things we already have; in particular, we can make perfect sense of this even if both of us are holding nonstandard models.

So I think this isn't entirely silly, although I do believe it's lightyears away from satisfying (and indeed that the actual answer is that no satisfying method exists).

---

Re: question 2, what do you mean by "expressible?"

We can easily write a formula in the language of set theory asserting "$x$ is the smallest inductive set," and so in that sense we have expressibility in the language of set theory.

On the other hand this definition is very model-dependent, with nonisomorphic models of set theory giving potentially non-isomorphic "smallest inductive sets." By the compactness theorem this is unavoidable as long as we stay in the realm of first-order logic, so that can be interpreted as a negative answer.

Answer 5

Just an expanded comment. The standard model of PA can be characterized as the unique (up to isomorphism) model of PA such that all of its individuals are suitably named by numerals (like SSS...S0). Therefore, we can understand the standardness of the standard model as the matching between its individuals and the “metamathematical numbers.” Now, what if the metamathematics of aliens is nonstandard? As I see it, the metamathematics is not a model, so it is neither standard nor nonstandard. The metamathematical numbers are just subjects of the metamathematical discourse. Therefore, if we can explain the matching between the “metamathematical numbers” and the individuals of the standard model, then we can explain the standard model, because this matching can be seen as the essence of its standardness.

Answer 6

So the aliens taught you how to build a device and interpret its outputs as statements about first-order number theory. They say that it is performing "supertask" computations, or at least that's how we've translated their claims into Scientific English. But since we cannot check for ourselves, with our dull senses and limited memories, how do we know that's what's happening?

This is a serious question, because the assumption of the OP is that the device is somehow checking against some model of PA. Why do we believe the outputs correspond to what is satisfied in an actual model of PA? And which model? My point is that the particular reasons we have for believing in the reliability of this infinitary computer, or our particular understanding of how it is working, would be key to shedding light on whether the outputs are about a standard or nonstandard model of PA.

It could also give us the vocabulary to explain to the aliens what we mean by "standard model." Because if they have any knowledge of models of PA, enough to actually "touch" one, then surely they know that are many different ones. So we should be able to ask them why the computer tracks truths about their preferred model of PA and not a different one. This will have to depend on how the particulars of this sci-fi story are elaborated.

Answer 7

If PA is inconsistent, then by Gentzen's consistency proof, this means that the logical system of primitive recursive arithmetic (PRA) augmented with the well-ordering of ϵ₀ is inconsistent. The consistency of PRA is, I'm pretty sure, beyond reasonable debate, so the more likely explanation is that ϵ₀ is not well-ordered, and thus has an infinite descending sequence beneath it. Given that every ordinal below ϵ₀ can be expressed as a finite rooted tree, there would have to be some "finite" rooted tree in the aliens' system which has a nonstandard number of nodes, and thus can be decremented from forever.

I think that the existence and well-orderedness of ϵ₀ would be something they could learn about and accept, and any model that doesn't prove it is not the standard model.

Answer 8

I think the answer to your question really depends on how we take ourselves to understand a canonical model of PA. Ultimately I think it comes down to the way language about mathematics is grounded in a kind of modal semantics for physical procedures.

Consider a human child learning arithmetic for the first time. The first thing they might learn in a contemporary mathematics curriculum is how to associate physical arrangements of marks/dots with arbitrary arrangements of distinguishable objects. A basket containing six oranges can be associated with six equally spaced dots on a line, like $*$ $*$ $*$, or six equally spaced dots in a rectangle, like:

$$\begin{matrix} * & * \\ * & * \\ * & * \end{matrix} \text{ or } \begin{matrix} * & * & * \\ * & * & * \end{matrix} $$

They learn that adding a single item to the basket corresponds to adding an additional dot on the end of a line of dots, and removing an single item from the basket corresponds to removing a dot from the end of a line of dots. They learn how to rearrange rectangles of dots into lines of dots. They then learn how to associate lines of dots with, say, arrangements of decimal numerals and verbal utterances. They then learn to associate addition with concatenation of lines of dots, and multiplication with creating a rectangle of dots whose sides are associated with the multiplicands. They learn a procedure for manipulating two arrangements of decimal numerals to to produce an arrangement of decimal numerals representing their sum or product (the usual addition and multiplication algorithms), and verify by many examples that these physical procedures on arrangements of numerals correspond to the previous physical procedures on arrangements of dots.

What are they actually learning here, though? It looks like they are learning certain modal claims about physical procedures, essentially by induction in the sense of Hume. They learn, for example, that given two equally spaced lines of dots, it is always possible to form their concatenation. They learn that the procedure for association "a+b" to an arrangement of dots and "b+a" to an arrangement of dots necessarily result in arrangements of dots which, if they were to verbally count them, end at the same verbalization. I would claim they are learning these modal claims in the same way a physicist might learn certain modal claims about the motions of physical objects, like "For any possible closed physical system, momentum is conserved". I think these are rightly considered modal claims, not just universal claims, because they are about what would happen, not what is: we are learning about what would happen if we were to do various physical procedures, not about what is (of course this is an anti-Platonist view).

So how does this relate to your original question about aliens? Well, numbers correspond to arrangements of equally spaced dots that we could create (in a somewhat liberal interpretation of "could"). As mathematicians, we often assume that there is no limit to the amount of time or resources we have to perform a manipulation of symbols (which is expressed by the totality of the successor function -- for any linear arrangement of equally spaced dots, we always could add another dot to the end). We believe that this modal language is unambiguous, because it seems to connect directly to our experience of the physical world we live in.

But there is a good argument this is not so, or at least the naive interpretation of these modal claims as physical possibility does not work: there is a finite amount of matter and energy in the universe with which to create these arrangements of dots.

However, there still may be something about our universe which allows these modal claims to be grounded in something "real". If our universe was Newtonian or Minkowskian, then in a physical line segment of unit length, there exist arbitrarily large finite collections of non-zero points along that segment whose spacing between adjacent triples pairs of points $a < b < c$ in that collection has the distance between $b$ and $c$ equal to half the distance between $a$ and $b$. And any infinite such collection has the same order type. So we can find the order-type of the natural numbers, essentially, in the level of saturation of a unit interval of space (not quite in the model theoretic sense, but related). We might also believe time is unbounded, and that for any full time-like geodesic in our Minkowskian universe, any unbounded collection of equally-spaced points in time with an initial point is order-isomorphic to the natural numbers. On a theory of meaning based on the right notion of reference, our language could thus pick out a canonical model of arithmetic by reference to our actual universe.

Answer 9

Not sure about aliens but if we had to approach the task of explaining $\mathbb N$ to, say, the Pirahãs (who have presumably not been exposed to any modern mathematics), we would first have to answer Hamkins' question to the "mathematical oracle":

Do we have an absolute notion of "finite"?

Since the answer seems to be likely negative, the corresponding answer to your question is that the task would be impossible. Of course, the Pirahãs, who have the same cognitive capacity at birth as all humans, can be replaced here by anybody who has not been exposed to modern set theory, e.g., Leibniz, who would have rejected the formula $\mathbb N\in \mathcal P (\mathbb N)$ as meaningless even after getting all the necessary explanations with regard to the notation, because he viewed "infinite wholes" as contradictory entities (namely, contradicting the part-whole principle, along the lines of Galileo's paradox with $n\mapsto n^2$). On the other hand, Leibniz would have agreed that infinitesimals are more complicated than 1,2,3,... Indeed, the counting numbers are assignable, whereas infinitesimals are inassignable, in Leibniz's terminology.

Answer 10

I'm going to have to tell you that describing your "standard model" is possible if and only if you believe that there is a true embedding of the naturals into the real world.

Specifically, if you do then you can simply define your "standard model" as precisely that embedding. For example, if you believe that one can build a true universal Turing machine that has an indefinitely extensible tape (not infinite but always can be extended) and that can run for an indefinitely long time without making a single error, then you can obviously define natural numbers as all finite unary strings that can be written by some instance of that Turing machine, and define the arithmetic operations on those unary encodings as the Turing machines that you can explicitly write down for them. There can then be no ambiguity at all what you mean by your "standard model".

However, if you hold a more 'physical realist' view, the finiteness of the observable universe strongly suggests that there is no embedding of naturals into the real world, and hence no Turing machine of the kind described above (for reasons of both space constraints and occasional infidelity). If so, then describing your "standard model" is impossible simply because it does not even exist! Think about it; you cannot even describe it uniquely to yourself, since no computable formal system can pin it down.