Understanding Peano's Axioms: The Role of Mathematical Induction

[alexfloo]

I'm having a bit of trouble understanding why the principle of induction is included as one of Peano's axioms. It seems like it should not be independent of the others. Obviously it can be stated as:

• If a predicate P is true only of natural numbers, $P(0)$ is true, and also $P(n)\rightarrow P(S(n))$, then it is true exactly of the natural numbers.

Now, the first two of Peano's axioms define the set of natural numbers:

• $0 \in \mathbb{N}$
• $n\in \mathbb{N} \rightarrow S(n)\in\mathbb{N}$

The third axiom essentially states that no other objects are natural numbers.

Now presume T is the set of all objects for which the predicate P holds. Presume P is a predicate such that P(0), and that $P(n)\rightarrow P(S(n))$. Then clearly:

• $0 \in T$
• $n\in T\rightarrow S(n)\in T$

This is identical to the definition of $\mathbb{N}$, so it follows that $T\supset\mathbb{N}$.

This appears to be a proof of the principle of mathematical inductions from the first three of Peano's axioms. Where did I go wrong?

 

[SW VandeCarr]

I'm having a bit of trouble understanding why the principle of induction is included as one of Peano's axioms. It seems like it should not be independent of the others. Obviously it can be stated as:

• If a predicate P is true only of natural numbers, $P(0)$ is true, and also $P(n)\rightarrow P(S(n))$, then it is true exactly of the natural numbers.

I don't know the answer to your question except to say that the principle of induction is to prove a statement is true in the first instance and therefore applies to all subsequent instances according to the same rule (ie every integer has a successor). This works in terms of the natural numbers, but how do you generalize it to all integers? Are Peano's axioms meant only to apply to the natural numbers?

 

[alexfloo]

Peano's axioms are only a description of the natural numbers (including zero). If I said integers somewhere instead, it was a mistake.

My understanding is that mathematical induction is not inherently the case in the natural numbers. That is, it is only an intuition, and therefore must formalized as an axiom. The was I've read that axiom in texts is always either the way described it above, or the (equivalent) "Any set which contains zero and the successor of every one of its members contains all the natural numbers."

By this formulation of the axiom, though, it appears to follow from the other axioms, since the natural numbers are "a set which contains zero as well as the successor of every one of its members." This seems like a pretty trivial proof, but I'm sure I must be missing something, since I've seen so many (reputable) sources that attest that induction is independent of the other axioms.

 

[SW VandeCarr]

Peano's axioms are only a description of the natural numbers (including zero). If I said integers somewhere instead, it was a mistake.

No, you didn't say integers. I just thought the axioms should be strong enough to prove every integer has a successor. In any case, I believe this can be proven using the Axiom of Choice.

 

[alexfloo]

Peano's axioms are basically a definition of the natural numbers, so they give no notion of the idea that negative numbers even exist, let alone have any properties at all. If you were to include along with them an additional axiom along the lines of "For every number n there exists an n' such that n+n'=0", then you probably could prove that every integer has a successor, but if you only have Peano's axioms, then the integers don't technically "exist."

In any case, I believe this can be proven using the Axiom of Choice.

Do you mean induction or the successor relation for integers? If you mean induction, do you have a link to the proof somewhere?

 

[SW VandeCarr]

Peano's axioms are basically a definition of the natural numbers, so they give no notion of the idea that negative numbers even exist, let alone have any properties at all. If you were to include along with them an additional axiom along the lines of "For every number n there exists an n' such that n+n'=0", then you probably could prove that every integer has a successor, but if you only have Peano's axioms, then the integers don't technically "exist."
Do you mean induction or the successor relation for integers? If you mean induction, do you have a link to the proof somewhere?

No, I don't mean induction necessarily; only that the integers can be well ordered using the Axiom of Choice.

 

[Stephen Tashi]

alexfloo,

A problem that I see in your proof is that you are using only two axioms of the natural numbers and you claim that these two axioms "are identical to the definition" of the natural numbers. ( In modern formulations of Peano's axioms, I think there are more than 3 axioms, even if you leave out the axion of induction.)

 

[praeclarum]

No, you didn't say integers. I just thought the axioms should be strong enough to prove every integer has a successor. In any case, I believe this can be proven using the Axiom of Choice.

Actually, it can be proven without choice, without infinity, and without regularity in ZF set theory.

I'm having a bit of trouble understanding why the principle of induction is included as one of Peano's axioms. It seems like it should not be independent of the others. Obviously it can be stated as:

• If a predicate P is true only of natural numbers, $P(0)$ is true, and also $P(n)\rightarrow P(S(n))$, then it is true exactly of the natural numbers.

Now, the first two of Peano's axioms define the set of natural numbers:

• $0 \in \mathbb{N}$
• $n\in \mathbb{N} \rightarrow S(n)\in\mathbb{N}$

The third axiom essentially states that no other objects are natural numbers.

Now presume T is the set of all objects for which the predicate P holds. Presume P is a predicate such that P(0), and that $P(n)\rightarrow P(S(n))$. Then clearly:

• $0 \in T$
• $n\in T\rightarrow S(n)\in T$

This is identical to the definition of $\mathbb{N}$, so it follows that $T\supset\mathbb{N}$.

This appears to be a proof of the principle of mathematical inductions from the first three of Peano's axioms. Where did I go wrong?

As far as I know, the Peano postulates do not rely on the concept of a definition for natural numbers. If you construct natural numbers as a defined term, then it can be proven in ZF set theory.

The Peano axioms are independent of each other, however. You cannot prove the principle of induction, because although you know that
0 in N
and A in N -> s(A) in N
that, in itself, does not mean that N is *limited* to 0 and all its successors. Which is what the principle of induction relies on.

 

[pmsrw3]

My understanding is that mathematical induction is not inherently the case in the natural numbers. That is, it is only an intuition, and therefore must formalized as an axiom. The was I've read that axiom in texts is always either the way described it above, or the (equivalent) "Any set which contains zero and the successor of every one of its members contains all the natural numbers."

By this formulation of the axiom, though, it appears to follow from the other axioms, since the natural numbers are "a set which contains zero as well as the successor of every one of its members." This seems like a pretty trivial proof, but I'm sure I must be missing something, since I've seen so many (reputable) sources that attest that induction is independent of the other axioms.

"Any set that contains 0 and the successor of every one of its members is the set of all natural numbers" is the inverse of "The set of all natural numbers contains 0 and the successor of every one of its members."

 

[alexfloo]

I did leave out some of the postulates (I was aware of that at the time, I just didn't realize until now that they were in fact relevant here). In the formulation presented by the Wolfram MathWorld site, we have, in addition to the two I listed, "Zero is not the successor of any number" and "S(n)=S(m) -> n=m" (and also the induction principle).

I interpreted these two as implying that there are no natural numbers beyond zero and its successors, but on closer inspection I don't believe that can actually proved from these four postulates. It can, however, be proved if we include the induction principle, correct?

So, if we start only with the first four axioms, is it correct to say that "0 and those objects attained from a finite number of successions of zero are the only natural numbers" is equivalent to the induction principle? It appears that the two postulates can be proved from each other *if* we first admit the other four axioms. Is that correct, or am I still mistaken?

 

[praeclarum]

I did leave out some of the postulates (I was aware of that at the time, I just didn't realize until now that they were in fact relevant here). In the formulation presented by the Wolfram MathWorld site, we have, in addition to the two I listed, "Zero is not the successor of any number" and "S(n)=S(m) -> n=m" (and also the induction principle).

I interpreted these two as implying that there are no natural numbers beyond zero and its successors, but on closer inspection I don't believe that can actually proved from these four postulates. It can, however, be proved if we include the induction principle, correct?

So, if we start only with the first four axioms, is it correct to say that "0 and those objects attained from a finite number of successions of zero are the only natural numbers" is equivalent to the induction principle? It appears that the two postulates can be proved from each other *if* we first admit the other four axioms. Is that correct, or am I still mistaken?

If I am to interpret what you say as:
N = { x : x = 0 \/ E. y ( y e. N /\ s(y) = x ) } (translation: The set of natural numbers is equal to the collection of all sets that are either equal to 0 or a successor of some natural number)
Then that (I think) could be proven from the 5 Peano postulates, but don't quote me on that...I'm not completely sure.

 

[alexfloo]

I actually think this is pretty well cleared up for me now:

It definitely follows from the first two postulate (assuming the order that I mentioned them) that the naturals are a superset of the set containing only zero and its successors. We then consider the question of whether this inclusion is proper.

It seems clear that the first four postulates are not sufficient. For instance, consider the set $\mathbb{N}\cap \{a\}$ for any object a that is not a natural number (and define S(a)=a). This set satisfies all the first four of Peano's postulates.

It's also seems clear to me now that "No objects other than 0 and its successors are natural numbers." is a consequence of induction. Furthermore assuming that proposition, we can also prove the induction principle, because the failed proof above would then be valid.

So in essence, the importance of the 5th postulate in creating a model of the natural numbers is simply that it, in some sense, excludes any objects not described by the first four?

 

[Kindayr]

I think you're forgetting a postulate, that should clear things up that is found within Goodfriend's "A Gateway to Higher Mathematics":

Let P be a nonempty set. Let s: P$\rightarrow$P , and consider an element e$\in$P. The ordered triplet (P, s, e) is called a Peano Space provided the following three properties hold:

1) s is one-to-one.
2) $\forall$n$\in$P, s(n)$\neq$e.
3) Suppose A is any subset of P such that

a) e$\in$P, and
b) $\forall$n$\in$P, we have (n$\in$A)$\Rightarrow$(s(n)$\in$A)​

Then A=P.​

The function s is called a successor function. The element e is called an initial element with respect to s. Properties 1 through 3 are called Peano's Postulates.

Particularly property 3 shows that there isn't any 'junk' in P, and so induction can work. It isn't hard to show that (N, s(n)=n+1, 0) is a Peano space, and so it follows that induction works.

I hope this helps.

 

[Kindayr]

Just to show how it proves induction works on any Peano space, (again from Goodfriend)

For mathematical induction, we want to show that $\forall$n$\in$P, Q(n) is true for some predicate Q.

Let (P, s, e) be a Peano space. Then if S is a subset of P that follows the properties of postulate 3, then S = P. So suppose Q(e) and that $\forall$n$\in$P, Q(n)$\Rightarrow$Q(s(n)). Let S={n$\in$P|Q(n)}, then S=P. So $\forall$n$\in$P:Q(n), as required.

Again, I hope this helps.

EDIT: Switched from the Naturals to a general Peano space. However you can just show that the Naturals are a Peano space and so induction has to work on them.

 

[alexfloo]

That does help. Your comment that #3 "shows that there isn't any 'junk' in P" is exactly what I was speculating, but I'd never seen it stated outright.

So the first axioms identify a well-ordered chain within N, (which is therefore ripe for induction) and the induction axiom implies that (because induction is possible on the whole set, not just that chain) that there is nothing aside from the chain.

Thanks a lot, Kindayr.

EDIT: Replace N with any suitable triple, i.e., Peano space.

 

[Kindayr]

No problem, I also fixed my last post to show it as a general peano space as opposed to just the naturals.

The books pretty nice, though I don't know how much it costs as I received it as a gift from a professor. It smoothly takes you from basic set theory to some nice junior-level university math in only a hundred or so pages. Not a light read, but definitely opened my eyes to pure math :)

 

[alexfloo]

It looks like my university library has it, so I definitely plan on giving it a look. I've seen a few analysis texts that attempt to give a development of the reals from set theory to the naturals and upward, but they all skip about half of it. It's not hard to fill in the blanks conceptually, but it'd be nice to see more of the process.

 

[Kindayr]

A fun exercise would be to prove that a Peano Space exists. It does it in the text, but its a good proof nonetheless.

Hint, use the Axiom of Infinity.