3
$\begingroup$

I understand that there exist first-order and second-order Peano axioms, but I am mainly concerned with latter. Specifically, the axioms as listed here.

As discussed here and here, it seems that the induction axiom is needed to create a set that matches our intuitive understanding of Natural numbers.

Can we say that the induction axiom constructs set of Natural numbers using successor function and $\boldsymbol{0}$ , and hence is providing us with a model of Natural numbers?

PS. I know very little about logic and model theory.

UPDATE: Comments correctly pointed out that I should explain my degree of knowledge about logic and model theory (See @Asaf Karagila and @Skyking comments). Here is some more details my understanding of a model is that it provides meaning to the undefined terms of axiomatic systems. The undefined terms are defined in a way that our informal intuitions are mathematically formalized (see this).

In addition, I understand that if an axiomatic system has a model then it is consistent.

What I am trying to understand is that:

  1. What are the undefined terms in the Peano axioms? to me they are $\boldsymbol{0}$ and the successor function.
  2. Since the successor function and $\boldsymbol{0}$ are the concepts that can be understood by our intuitions (they are concrete concepts in our time. I understand they haven't always been like this), does this mean the Peano axioms are providing us a model for the Natural numbers.
  3. I think $\boldsymbol{0}$ and the successor function are not enough to provide the model because as mentioned in the comments there exist sets that can be constructed using $\boldsymbol{0}$ and the successor function that arenot Natural numbers and hence the induction axiom is needed if we want our model to correctly math the Natural numbers.

There were also comments about the word construct, what I mean by construct is the use of already known objects to provide model for other structures. For example, Dedekind cuts of rational numbers to construct the reals. The use of he word construct for the Natural numbers occurred to me because of the wording here, in particular, the word generate, which I quote

" However, considering the notion of natural numbers as can be derived from the axioms, axioms 1, 6, 7, 8 do not imply that the successor function [generates] all the natural numbers different from 0. Put differently, they do not guarantee that every natural number other than zero must succeed some other natural number"

$\endgroup$
  • $\begingroup$ The Peano axioms themselves cannot possibly be used to construct (and validate) a model of the natural numbers; if they could do that they could prove their own consistency, which is impossible by the incompleteness theorem (unless they are inconsistent!). $\endgroup$ – Qiaochu Yuan Jun 27 '17 at 6:37
  • $\begingroup$ Thanks isn't it the case that the completeness axiom can be used to construct Real numbers using rational numbers by Dedekind cuts? Can something similar be done here? $\endgroup$ – Mathnewbie Jun 27 '17 at 6:45
  • 4
    $\begingroup$ It's going to be hard to explain accurately what is missing from your knowledge. You're using the word "construct" in a non technical way, and you admit to know being familiar with the fields of relevance. Not saying it's impossible, but this sort of feels like someone without any mathematical or physics background asking about the standard model of particle physics and what are electrons really are. $\endgroup$ – Asaf Karagila Jun 27 '17 at 6:57
  • $\begingroup$ @Asaf Karagila Thanks I am referring to construct in the way it is used in real analysis text books. I believe Dedekind cuts are used to construct Reals from Rationals. This construction results in complete ordered fields. I wondered if one could say Naturals can be constructed using 0 and the successor function using the induction axiom. $\endgroup$ – Mathnewbie Jun 27 '17 at 12:12
  • 1
    $\begingroup$ Informally, the induction axiom can also be looked at as a kind of "filter." Without it, you would still have set that contains every natural number, but you could not rule out the presence of additional "junk terms." The induction axiom "filters" them out. $\endgroup$ – Dan Christensen Jun 28 '17 at 12:25
5
$\begingroup$

No, the induction axiom does not construct the natural numbers, but in order for the induction axiom to hold (in addition to the other Peano Axioms), your model does need to be isomorph to the natural numbers. Indeed, it is almost the other way around: the induction axiom does not generate or construct or force there to be infinitely many ordered elements in any model, as this is what the other axioms already do, but rather the induction axiom makes sure that in any model there aren't any further elements. That is, the induction axiom restricts the model to be 'nothing more' than the natural numbers.

To give at least some intuitive idea about this: Any model of the Peano axioms without the induction axiom is already required to contain an infinite number of elements that exist somewhere in an infinite chain of successors starting with $0$, i.e. something like the natural numbers. To see that, note that we need a '$0$' object (axiom 1) and that this $0$ object needs a successor (Axiom 6), and that this successor of $0$ cannot be $0$ itself (Axiom 8). So, we need a second object. But this second object needs a successor (Axiom 6), which cannot be $0$ (Axiom 8), but also cannot be itself, for we cannot have two different objects with the same successor (Axiom 7). So, we need a third object ... and this process keeps repeating itself: every time we add the new object that we are forced to add as the successor of the last object we added before that, that new object needs a successor itself, and that successor cannot be $0$ (Axiom 8), nor can it be any of the other already existing objects, for then we would get two different objects with the same successor, which goes against Axiom 7. So, you could say that the natural numbers (or at least an infinite sequence of successive objects) is already 'constructed' by these 4 axioms.

OK, so where does the axiom of induction come in? Well, while the other axioms require for any model to contain an infinite sequence of successive element, these other axioms do not rule out any additional elements in the model: elements that do not occur in this infinite sequence of successors. Indeed, without the axiom of induction you could have as a model $\mathbb{N} \cup \{ apples, bananas \}$, ... as long as you define how the interpretation of the successor, addition and multiplication function symbols apply to $apples$ and $bananas$ ... but that can all be done without problem.

However, the induction axiom says that 'if $0$ has some property $P$, and if $s(n)$ has property $P$ whenever $n$ has property $P$, then all objects have property $P$. Well, if you have that $0$ has some property $P$, and that $s(n)$ has property $P$ whenever $n$ has property $P$, then obviously all the objects that exist somewhere in the infinite chain of successors have property $P$, but how can you say that all the additional objects also have to have property $P$? You can't of course. So, the fact that the induction axiom says that we can conclude that all objects have property $P$ effectively rules out any of those additional objects in the domain, and hence your model needs to be isomorph to the natural numbers.

$\endgroup$
  • 1
    $\begingroup$ This is at best unclear and at worst untrue. PA has non-standard models (see: en.wikipedia.org/wiki/Non-standard_model_of_arithmetic). So a model of PA (in fact there are countable models of the theory of $\mathbb{N}$ that) need not be isomorphic to $\mathbb{N}$. $\endgroup$ – dav11 Jun 28 '17 at 13:57
  • $\begingroup$ However, something you state, of interest to the OP is the use of the induction axiom: It doesn't have to do anything with the construction. The point is it allows us to prove certain things. For example, $1+2=3$, $1+2+3=6$ is not hard to check. But to conclude that $\sum_{i=1}^{n}i=n(n+1)/2$ this is not sufficient (as you would need to give a case by case proof for $n=3,4,5,6,....$). However induction allows you to get around this problem of needing "infinitely many" proofs. $\endgroup$ – dav11 Jun 28 '17 at 14:03
  • $\begingroup$ @dav11 Hmmm, from that same Wikipedia page you mention, it says that with the second-order induction axiom, there is only one kind of model, isomorph with the natural numbers. This is what I said in my post: without the induction axiom there are other models, but with the induction axiom any model will have to be isomorph to the natural numbers. Now, the page does mention that there is a 'weaker' form of induction that is only first-order, and then you do get non-standard modedls, but I was talking about the induction axiom as meant by Peano. $\endgroup$ – Bram28 Jun 28 '17 at 16:55
  • $\begingroup$ @dav11 While I do believe your downvote was misplaced in the first place, I did edit the post so that hopefully things will be more clear. $\endgroup$ – Bram28 Jun 28 '17 at 17:51
  • 1
    $\begingroup$ @dav11 Well, if you found it confusing, then it was not a good answer!! So, no worries, and your downvote did push me to try and improve the answer ... And I think it is better now, so thanks! :) $\endgroup$ – Bram28 Jun 28 '17 at 19:54
3
$\begingroup$

You will find a more commonly used presentation of Peano's Axioms here. The induction axiom doesn't "construct" anything. It is simply one of the essential properties of the set of nature numbers and the successor function defined on it. Without it, we would not be able to prove, for example, that no number is its own successor.

$\endgroup$
  • $\begingroup$ @DanielV The axiom of induction is correct as stated. Stated more formally, it would be $\forall P\subset N:[0\in P \land \forall x\in P:[ S(x)\in P] \implies P=N].$ It excludes every object that cannot be reached by repeated succession starting at $0.$ This would exclude the set of rational numbers, e,g. $1/2\notin \{ 0, S(0), S(S(0)), \cdots \}.$ $\endgroup$ – Dan Christensen Jun 28 '17 at 3:56
  • $\begingroup$ Thanks, I was misreading their prose. For some weird reason I was interpreting $S$ as the set being defined. "Every subset of $N$ that contains zero and is closed under succession contains $N$ (equivalently is equal to $N$)". That is what they meant.... $\endgroup$ – DanielV Jun 28 '17 at 6:48
  • $\begingroup$ Isn't that presentation incomplete, as it doesn't include addition and multiplication? Note that it is only those operations which separate the natural numbers (here assumed to be defined with $0$) from e.g. the positive integers (i.e. without $0$) or the even natural numbers (with $S(n)=n+2$). $\endgroup$ – celtschk Nov 19 '17 at 9:50

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.