Why is Axiom of Induction Needed as an Axiom? (Peano's Axioms)

[MathIsGrrreat]

I've already asked somebody through email this question, so I'll copy and paste part of my email:

Basically, I'm wondering why doesn't it fall from the other axioms, and if it does in fact not fall from the other axioms (which it apparently doesn't), why the axioms can't be slightly modified so that induction is implied. I've asked various people and they've said things like, "The axioms are set up to make the natural numbers work" but still doesn't exactly answer the question for me. If you're too busy (I've already bothered you once with this question), if you could refer me to somebody who might answer my question, that would be helpful.

If I remember correctly, when I talked to you, you said something about applying the axioms to things other than the natural numbers. Would you be able to give me a complete example of that, telling me what exactly the word "number" refers to in the Peano Axioms (as stated in http://mathworld.wolfram.com/PeanosAxioms.html)?

I'm pretty much thinking that the first four axioms are equivalent to the following kind of "program" (and if they aren't, then why wouldn't you want the first four axioms to be like this? - I feel like the first four axioms could be trivially reworded [no weird terminology] to be equivalent to this program):

- Put 0 in N
- Let S(n) be a function from N->N such that S(a)=S(b) => a=b (fourth axiom)
- Inside an infinite loop, for each element n in the set N, add the element S(n) to N

In which case, the fifth axiom isn't necessary because of a set S is defined to contain S and the successor of every number in S, then the set's definition is essentially equivalent to the program above (it contains 0, and then we apply the successor function to every number), except that set S may contain things that aren't "numbers" (because, before the line "Put 0 in N", there could already be arbitrary stuff in N, which we don't have to worry about since we only apply S(n) to numbers). I'm trying to use the broadest interpretation of "number" here. Also, note that the "program" above would necessarily generate some totally ordered set, per " Let S(n) be a function from N->N such that S(a)=S(b) => a=b".

He responded to the email, basically saying:


The word "number" literally means "a thing that satisfies these axioms", nothing else.

When you're thinking about axioms like this, it's a serious mistake to think of "numbers" as the familiar things you represent with digits. Words like "zero" and "successor" and "equal" are convenient labels for abstract relationships that obey certain rules, but they do NOT necessarily correspond to the everyday objects that those words normally describe.

The non-negative rational numbers, where "successor of x" means "x + 1/2", satisfy all axioms except induction.

1. 0 is a non-negative rational number.
2. If x is a non-negative rational number, then x+1/2 is a non-negative rational number.
3. There is no non-negative rational number x such that x + 1/2 = 0.
4. For all non-negative rational numbers x and y, if x + 1/2 = y + 1/2, then x = y.

Similarly, the real numbers, where "successor of x" means "e^x":

1. 0 is a real number.
2. If x is a real number, then e^x is a real number.
3. There is no real number x such that e^x = 0.
4. For all real x and y, if e^x = e^y, then x = y.


But, I still don't understand how that shows that the axiom of induction is necessary. Because, if you just looked at the set of non-negative rational numbers of the from x/2 (for x in {0,1,2,..}) in the first example, then that set would satisfy all five axioms, and it still seems like the axiom of induction in this case would be implied be the rest of the axioms.

He also added to the email:

A slightly better iterative construction looks like this:

- N = empty set
- n = 0
- repeat forever:
add n to N
n = Sn

Here n is a STRING and "0" and "S" are just symbols, without any semantic meaning. After a six iterations of the loop, we have N = {0, S0, SS0, SSS0, SSSS0, SSSSS0, SSSSSS0}.

Iterative construction is good intuition, but that's NOT what the Peano axioms actually formally say, and the difference between intuition and formal definitions is crucial. "Repeat forever" does not have a formal definition. To be completely formal, we should define N to be the smallest set that contains the string 0 and such that for every element x in N, the string Sx is also an element of N.

But the assumption that such a set exists is itself a non-trivial axiom of set theory called the Axiom of Infinity, which basically says "There is an infinite set on which induction is possible", or equivalently, "There is a set that contains all natural numbers": http://en.wikipedia.org/wiki/Axiom_of_infinity .


Thanks in advance.

 

[eigenperson]

Your correspondent has given you several examples of sets for which the first 4 axioms hold, but not the axiom of induction. That is enough to prove that the axiom of induction does not follow from the first 4 axioms. If the axiom of induction could be deduced from the first 4 axioms, then there would be no such sets!

Basically, if you don't have the axiom of induction, you can prove that a statement is true for 0, 1, 2, 3, 4, ... Nevertheless, that statement might not be true for all numbers, because there might be numbers that are not produced this way.

 

[Stephen Tashi]

But, I still don't understand how that shows that the axiom of induction is necessary. Because, if you just looked at the set of non-negative rational numbers of the from x/2 (for x in {0,1,2,..})

The first example was all the non-negative rational numbers, not merely those in {0,1,2,..}. However, the set of all non-negative rational numbers can be put in a 1-1 correspondence to the natural numbers. So if we want to show the axiom of induction is needed, it's better to look at the second example - the example of all the real numbers. Is the axiom of induction true for the set of all real numbers?

 

[Stephen Tashi]

Let's try using the non-negative reals as an example. Let "successor of x" mean x + 1/2.

1. 0 is a non-negative real number.
2. If x is a non-negative real number, then x + 1/2 is a non-negative real number.
3. There is no non-negative real number x such that x + 1/2 = 0.
4. For each pair of non-negative real numbers x and y, if x + 1/2 = y + 1/2 then x = y.

If induction applied to the set of non-negative real numbers then:

1. 0 is a rational number
2. if x is rational number then x + 1/2 is a rational number

"Therefore" each non-negative real number is a rational number

 

[blue_raver22]

I can understand your confusion and desire to find a simpler explanation for the axiom of induction. However, it is important to remember that mathematical axioms are carefully chosen and formulated to ensure consistency and completeness in a system. The Peano axioms, including the axiom of induction, were developed to provide a solid foundation for the natural numbers and their properties.

Let's consider your suggestion of modifying the axioms to make induction implied. While this may seem like a simpler solution, it would actually lead to inconsistencies and contradictions in the system. For example, let's say we have a set S that contains 0 and the successor of every element in S. This set S may contain non-numbers, as you mentioned, but it could also potentially contain numbers that are not part of the natural numbers. This would violate the first axiom, which states that 0 is the first natural number.

Furthermore, the axiom of induction is necessary to prove many important properties of the natural numbers, such as the commutative and associative properties of addition, the distributive property, and the fundamental theorem of arithmetic. Without this axiom, we would not be able to prove these properties and the system would not be complete.

Additionally, as my colleague mentioned, the axiom of induction is necessary for the existence of an infinite set on which induction is possible. This is a crucial aspect of the natural numbers, as they are infinite and unbounded. Without this axiom, we would not be able to fully capture the concept of infinity in our mathematical system.

In summary, while it may seem like the axiom of induction could be implied by the other axioms, it is actually a necessary and carefully chosen axiom to ensure the consistency and completeness of the system. I hope this helps to clarify the importance of the axiom of induction in Peano's axioms.