29
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't have the book so there may be more context that I am missing, but I think he is focusing on the "can be obtained from" part, because it doesn't eliminate 0.5 as you note. $\endgroup$ – copper.hat Dec 22 '14 at 15:46
  • $\begingroup$ What is the title of the book? $\endgroup$ – Trismegistos Dec 22 '14 at 17:16
  • $\begingroup$ My guess is that none of the answerers so far has gotten what you meant in your second question. If that is the case, consider explaining more. $\endgroup$ – Mariano Suárez-Álvarez Dec 23 '14 at 4:33
  • 6
    $\begingroup$ We can't know the properties of the "rogue elements", because they don't, in fact, exist. The point is that the first four axioms don't exclude the possibility of something unexpected being in $\mathbb{N}$. Maybe $i$ is in there, or $\omega_\omega$, or a woolly mammoth. There's no way to talk about the "properties" of completely unspecified things! But we don't want woolly mammoths in $\mathbb{N}$ so we add an axiom to the effect that we only allow the right things in there. $\endgroup$ – Kundor Dec 23 '14 at 4:51
  • 2
    $\begingroup$ You are correct that axiom 2.5 restricts what rogue elements you can add. You can't add $0.5$ as we usually understand it (so that $0.5+0.5=1)$ Every number except 0 needs a predecessor, then you need $-0.5$, then you need $-1$ to close under addition, then $0$ has a predecessor. You can have rogue elements that are greater than any natural. $\endgroup$ – Ross Millikan Dec 23 '14 at 15:05
22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could the first quadrant Gaussian integers also work for these "rogue" elements (without axiom 5)? $\endgroup$ – Cameron Williams Dec 23 '14 at 4:45
  • $\begingroup$ @CameronWilliams Yes. As could the fourth-quadrant Gaussian integers. You could even include Gaussian integers with negative real parts, as long as their successors are included and they have nonzero imaginary parts (so zero is not a successor). $\endgroup$ – KSmarts Dec 23 '14 at 14:17
  • 1
    $\begingroup$ The axiom does say that we can cover all our "wanted" Natural Numbers but it doesn't explicitly says that everything else is excluded. Maybe to resolve this situation we have to make use of the Set Theory as Hurkyl edited his answer. For then you can define the Natural Numbers to belong to the intersection of all such possible "problematic" sets. $\endgroup$ – user 170039 Dec 24 '14 at 4:06
  • $\begingroup$ This answer is wrong at the last sentence. The axiom of induction does not imply that all natural numbers can be counted from zero. This is obvious from the fact that there are non-standard models of PA. Worse still, second-order PA does not help at all since there are non-standard models of the meta-system MS (usually ZFC) unless MS is inconsistent itself! It only appears to help from within MS, but it's not exactly useful because there is no computable formal system for second-order PA. $\endgroup$ – user21820 Sep 10 '17 at 6:20
  • $\begingroup$ This answer has many flaws. One special flaw is the following: "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." When you say this statement how do you prove that there is no iterated successor of 0 where n++=a. And why does the Axiom of Induction requires that? $\endgroup$ – G.T. Apr 2 at 14:10
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ That's brilliant! But actually my questions aroused because in the book the chapter on Peano Axioms was before than that of the Set Theory chapter and I thought that there may be some approach independent of the Set Theory which resolves my question. $\endgroup$ – user 170039 Dec 23 '14 at 5:12
  • $\begingroup$ I'm not sure how we define "iterating" for the purpose of the first proof, but the second proof more than makes up for that, so +1. $\endgroup$ – David K Apr 5 '17 at 20:54
7
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Of course, if we take a disjoint union of $\mathbb N$ and $\mathbb Z$ where the $0$ comes out of $\mathbb N$, then both the propositions you list would be true. (Which mainly serves your last paragraph about how this question might actually be difficult) $\endgroup$ – Milo Brandt Dec 23 '14 at 4:31
  • 1
    $\begingroup$ @Meelo: As Asaf will tell us, the Peano axioms do not succeed in eliminating "rogue" numbers, because they have nonstandard models. However these are a bit like what you suggest, an initial segment congruent to $\mathbb{N}$ followed by an infinite "tail" (with neither least nor greatest element, of course). $\endgroup$ – hardmath Dec 23 '14 at 5:26
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there any free pdf version available online? $\endgroup$ – user 170039 Dec 23 '14 at 6:41
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It is not correct that the fifth axiom denies the existence of these side structures. The proofs that there are nonstandard models of all the Peano Axioms show that it does not do that. The "proof" in your blog fails. There could be a number $c$ that is not connected to the main sequence by the successor operation at all. You do not address that. $\endgroup$ – Ross Millikan Dec 23 '14 at 5:55
  • 1
    $\begingroup$ It is not true that the structures will be order-isomorphic. The countable models with nonstandard elements are not order-isomorphic to the standard $\Bbb N$. Per the Skolem theorem, there are also models with larger cardinality. $\endgroup$ – Ross Millikan Dec 23 '14 at 6:08
  • 1
    $\begingroup$ @user170039d: First order induction explicitly does not do that. It says that if a given predicate is true of 0 and true of successors it is true of all elements. That does not mean that you get to all elements by successor. It does mean that if there are "side chains", the elements satisfy all the predicates that you prove using induction. For example, induction can show that all elements besides 0 have a predecessor, so all the rogue elements must have a predecessor. With some more work, you can show that the rogue elements in a countable model $\endgroup$ – Ross Millikan Dec 23 '14 at 14:41
  • 2
    $\begingroup$ First order logic can't talk about sets of naturals. You can do that in ZFC, but not in PA. $\endgroup$ – Ross Millikan Dec 23 '14 at 15:49
  • 1
    $\begingroup$ When he states 2.5 that way, he is clearly working with first order induction. Otherwise it is stated as applying to subsets as you did. If you do second order induction, you can prohibit rogue elements. $\endgroup$ – Ross Millikan Dec 23 '14 at 16:05

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.