A question on Terence Tao's representation of Peano Axioms

Question

While reading Terence Tao's book on Analysis I had some questions regarding the implication of the Peano Axioms.

After writing the following four axioms (which I will write without changing their original numbering),

Axiom 2.1

$0$ is a natural number.

Axiom 2.2

If $n$ is a natural number then $n{+\!+}$ is also a natural number. (Here $n{+\!+}$ denotes the successor of $n$ and previously in the book the notational implication has been bijected to the familiar $1, 2\ldots$).

Axiom 2.3

$0$ is not the successor of natural number; i.e. we have $n{+\!+}\neq 0$ for every natural number $n$.

Axiom 2.4

Different natural numbers must have different successors; i.e., if $n, m$ are natural numbers and $n\neq m$, then $n{+\!+}\neq m{+\!+}$.

Now let me quote the portion of the text from which my question arises,

"As one can see from this proposition, it now looks like we can keep all of the natural numbers distinct from each other. There is however still one more problem: while the axioms (particularly Axioms $2.1$ and $2.2$) allow us to confirm that $0,1,2,3,\ldots$ are distinct elements of $\mathbb{N}$, there is the problem that there may be other "$\color{red}{\text{rogue}}$" elements in our number system which are not of this form:...

...What we want is some axiom which says that the only numbers in $\mathbb{N}$ are those which can be obtained from $0$ and the increment operation - in order to exclude elements such as $0.5$. But it is difficult to quantify what we mean by "can be obtained from" without already using the natural numbers, which we are trying to define. Fortunately, there is an ingenious solution to try to capture this fact:

Axiom 2.5

Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n{+\!+})$ is also true. Then $P(n)$ is true for every natural number $n$.

The informal intuition behind this axiom is the following. Suppose $P(n)$ is such that $P(0)$ is true, and such that whenever $P(n)$ is true, then $P(n{+\!+})$ is true. Then since $P(0)$ is true, $P(0{+\!+}) = P(1)$ is true. Since $P(1)$ is true, $P(1{+\!+}) = P(2)$ is true. Repeating this indefinitely, we see that $P(0), P(1), P(2), P(3),$ etc. are all true- however this line of reasoning will never let us conclude that $P(0.5)$, for instance, is true. $\color{blue}{\text{Thus Axiom 2.5 should not hold for number systems which contain}}$ "$\color{blue}{\text {unnecessary}}$"$\color{blue}{\text {elements such as $0.5$.}}$

My questions are precisely regarding the colored statements.

1. How can we assume the existence of "$\color{red}{\text{rogue}}$" elements in our number system? To be precise, how can one who doesn't know anything about the number system and the numbers try to convince himself of the existence of such elements?

2. Which $P(n)$ only holds for the natural numbers? In other words, how the addition of the fifth axiom resolves the problem of the rogue elements?

---

Added:-

After reading the various answers below, I think that I should elaborate why the answers below doesn't completely satisfy me.

What KSmarts said in response to my first question seems circular to me. To quote from his answer,

Suppose that in addition to the expected natural numbers $0,1,2,$ etc $\color{green}{\color{green}{\text{there are numbers}}\ a,b, \color{green}{\text{and}}\ c \ \color{green}{\text{so that}}\ a{+\!+}=b, b{+\!+}=c,\ \color{green}{\text{and}}\ c{+\!+}=a}$. This does not contradict any of the first four axioms, so it is a valid construction under those axioms. However, it does not correspond to what we expect of the natural numbers, so there is another axiom to restrict this construction.

The colored portion is the reason for which I think that the answer is circular. Precisely my question is that how do we convince someone the existence of those $a,b,c$'s who doesn't know anything about the numbers?

Hurkyl raised a good point which tries to resolve the above question,

For your first question, it's not that we assume that rogue elements exist, it's that we cannot assume they do not exist. If we wish that they do not exist, we must choose a definition that allows us to prove it.

"...it's that we cannot assume they do not exist." Exactly! But in my view we can choose a definition to "prove" that such rogue elements don't $\color{darkviolet}{\text{only when}}$ we know the properties of those elements. For then we can "construct" the definition in a way which excludes the possibility of such rogue elements.

So,

How can we know the properties that only belongs to the rogue elements, unless we have a proper idea of the nature of those rogue elements?

And it's precisely in the light of this question that my second question naturally arises. If we know the properties of the rogue elements, then we can define the property $P$ to be the "complement" of the properties which satisfy question my last question.

Answer 1

Part 1

You can't necessarily assume that these rogue numbers exist, however, under the first four axioms, you can't say definitively that they don't exist, which is really the point.

Suppose that in addition to the expected natural numbers $0,1,2,$ etc., there are numbers $a,b,$ and $c$ so that $a{+\!+}=b,\ b{+\!+}=c,$ and $c{+\!+}=a$. This does not contradict any of the first four axioms, so it is a valid construction under those axioms. However, it does not correspond to what we expect of the natural numbers, so there is another axiom to restrict this construction.

Part 2

The property $P(n)$ is arbitrary, it does not need to be specifically defined for the purposes of the axiom. Informally, the fifth axiom states that induction works. Given a property $P(n)$, the two statements that $P(0)$ is true and if $P(n)$ is true, then $P(n{+\!+})$ is true are sufficient to show that $P(n)$ is true for all natural numbers $n$.

Put another way, this means that $0$ and all of its iterated successors make up all of the natural numbers. In the previous example, with $a,b,$ and $c$, there is no iterated successor of $0$, that is, no "regular" natural number $n$, where $n{+\!+}=a$. So, this construction is no longer valid with the axiom of induction.

Edit:

I chose a finite set of hypothetical numbers in Part 1 simply for convenience. What properties these objects have, and what their successors are, is irrelevant. All that matters is that they fit the first four axioms, in that everything in the set has a successor that is also in the set, nothing has a successor that is $0$, and no two distinct objects have the same successor. There are, in fact, infinitely many things that could be in this set, and no way to define them all. In addition to the problem of not being numbers that we "want," this also means that the natural numbers, as defined so far, are not uniquely defined up to isomorphism.

There is one other property that we know these rogue numbers have, and that is whatever we use to define them as "rogue". That is, while they are a valid part of the natural numbers that we have constructed so far, they aren't a part of the natural numbers that we want to construct. So the natural question (no pun intended) is what other property or properties do we want the natural numbers to have?

Naively, the natural numbers are the "counting" numbers. For any natural number $n$, if we start at zero and repeatedly take the successor, we would (theoretically) be able to get $n$, eventually. So, presumably, the rogue numbers are numbers that you can't "count" to. This is what the fifth axiom, the axiom of induction, deals with. If $P(0)$, and $P(n)\Rightarrow P(n+1)$, then you can show $P(1)$, $P(2)$, and so on for any number that you can count to from zero. The axiom states that this covers all of the natural numbers. Everything else is excluded. It doesn't matter if they are irrational numbers, Gaussian integers, letters, transfinite and infinitesimal surreals, or, as Kundor commented, wooly mammoths. If you can't count to it from zero, it isn't a natural number.

Answer 2

For your first question, it's not that we assume that rogue elements exist, it's that we cannot assume they do not exist. If we wish that they do not exist, we must choose a definition that allows us to prove it.

Regarding your second question, in the language of Peano arithmetic, everything is a natural number. Thus, the only questions we can ask in the language of Peano arithmetic are questions about natural numbers.

If we could mathematically express the idea that a natural number "can be constructed by starting with $0$ and iterating ${+\!+}$", then we could make the following proof:

• $0$ "can be constructed by starting with $0$ and iterating ${+\!+}$"
• Suppose that $n$ "can be constructed by starting with $0$ and iterating ${+\!+}$":
  • Take such a construction
  • Apply ${+\!+}$ to it
  • Therefore $n+1$ "can be constructed by starting with $0$ and iterating ${+\!+}$":
• Since we've proven the base case and the inductive hypothesis, we know that all natural numbers "can be constructed by starting with $0$ and iterating ${+\!+}$".

---

I'm going to again answer something slightly different than what you asked. Set theory has a nice trick for this situation: rather than figure out what the rogue elements look like and try to exclude them, you instead figure out how to pick out just the things you want. Suppose you had some model of axioms 2.1 through 2.4 that contained rogue elements. There should be some subset that is also a model of axioms 2.1 through 2.4, but doesn't contain any rogue elements.

However, there there might be many subsets that are models: how do we find the one that we want? Well, the one that we want contains only the numbers that 'must' exist, so it should be the smallest subset that is still a model of axioms 2.1 through 2.4!

So, if we were defining properties of sets rather than formal theories, we would complete the definition with

2.5a. There does not exist a proper subset of the subset natural numbers that satisfies axioms 2.1 through 2.4

Now, this trick generally works best with constructions rather than properties; in this example, the natural numbers are "constructed" out of the constant $0$ and the operator ${+\!+}$. All of the numbers we actually want are things that are specific things that are required to exist, rather than requesting the existence of something with a property.

Putting the emphasis on this, the set theoretic version would be phrased as

2.5b. There does not exist a proper subset of the natural numbers that contains 0 and is closed under ${+\!+}$

Now, we can recover the principle of mathematical induction by using the correspondence between sets and predicates: rather than thinking about a subset $S$ of the natural numbers and which numbers are elements of $S$, we think of a unary predicate $P$ on the natural numbers and which numbers satisfy $P$. Rephrasing in this language

2.5c. Except for the always true predicate, there does not exist a unary predicate $P$ on the natural numbers such that $P(0)$ is true and that $P(n{+\!+})$ is true whenever $P(n)$ is.

This is pretty much the same thing as the axiom 2.5 that you wrote.

Answer 3

The point of "excluding" rogue numbers is that there are larger number systems beyond the natural numbers, in which facts that we know about natural numbers no longer hold.

For example, consider the non-negative real numbers with the usual operations of addition and multiplication, and with "successor" interpreted as $x \scriptsize{+\!+}\normalsize = x+1$, consistent with how we treat the natural numbers. Then your first four axioms are true in this enlarged model, but there are properties of the natural numbers that can be proven by induction (the fifth axiom) that fail in this enlarged model.

For example, there are no natural numbers $n$ such that $n^2 = 2$ (which we could prove by induction), but there is a non-negative real number $x$ such that $x^2 = 2$. A better example, in the sense of immediate tie to axioms, is the proposition that $0$ is the only number which is not a successor (third axiom). The proof by induction is straightforward (since apart from base case $n=0$ we only deal with successor elements), but this fails in the enlarged model (there are an infinite number of positive real numbers in $(0,1)$, which are not successors in the defined sense, being one plus a non-negative real number).

If we knew in any concise way the answer to the second part of this Question, "Which $P(n)$ only holds for the natural numbers?", then we would know a great deal more than we do now. In fact the undecidability of theorems of the Peano axioms means that no finite decision procedure can be given for this part of the Question (unless the Peano axioms are inconsistent, unbeknownst to us).

Answer 4

The important thing for your question 1 is whether we want to prove that rogue elements exist or we want to prove that they do not. We believe we cannot prove that rogue elements exist, because we believe that $\Bbb N$ without rogue elements is a model for the Peano axioms. (We can't prove that within PA, but that is not your question). We can also show that we cannot prove that rogue elements do not exist by showing that the PA axioms (unless they are inconsistent), including the fifth axiom, have a model with rogue elements. It is hard to "get a handle" on the rogue elements. They are all greater than all the standard elements, so any property that applies to all sufficiently large numbers applies to all of them. Any property that applies to infinitely many numbers applies to some of them. I found a good discussion in "The Incompleteness Phenomenon" by Goldstern and Judah.

Answer 5

1. The intuition behind the formulation of induction principle is that you can "prove" that a certain property $Q$ is not "a valid" property for the natural numbers. For instance, suppose we have the property $Q(n):=n\text{ have decimal part}$. Now, if we define $P(n):=\text{no } Q(n)=n\text{ have no decimal part}$. Thus, using induction, cleary $P(0)$ is true, and $P(n)\implies P(n\!+\!\!+)$ is true, for any natural number $n$. Hence, we conclude that every natural number have no decimal part. (Obviously the notions like $Q$ are no defined in that section, but this "proof" should give some idea how the induction principle exclude another "no-natural number objects".)

In conclusion, the induction principle says that every natural number either is zero or is the successor of another natural number (in brief, you can show by induction that every natural number is de predecessor of another natural number), i.e., for every natural number $n$ either $n=0$ or $n=m\!+\!\!+$ for some natural number $m$. So any other object is not a natural number.

2. Tao says it is a little vague what property $P$ means, but you can consider properties involving natural numbers like $$P(n):= n \text{ is a natural number such that}\dotsc$$ For example

• $n$ is odd,
• $n^{2^n}+f(n)>1$,
• $n$ solves $(n+x)^3=n^3+x^3+3nx(n+x)$, etc.

Thus there are no restrictions for $P$; but one can consider that $P$ treats about natural numbers.

Answer 6

The first four axioms describe a structure that would include an infinite, unbranching "chain" of elements starting at $0$, a structure I call the main sequence. It corresponds to the set of natural numbers. The first four axioms, however, cannot rule out the possibility that other elements in this structure may exist apart from this main sequence. There could be infinitely many such side structures -- either finite loops or infinite structures like the integers that go off to infinity in two directions. The fifth axiom explicitly denies the existence of any such side structures. It states, in effect, that there are no elements outside of the main sequence.

See graphical representations in "What is a number again?" (January 22, 2014) at my math blog.