Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 12, 2013 #1
    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)? [Broken]

    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.
    Last edited by a moderator: May 6, 2017
  2. jcsd
  3. Nov 12, 2013 #2
    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.
  4. Nov 13, 2013 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    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?
  5. Nov 13, 2013 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook