The basic assumption or axiom of induction is, in logical symbols,
where P is any proposition and k and n are both natural numbers.
In other words, the basis P(0) being true along with the inductive case ("P(k) is true implies P(k + 1) is true" for all natural k) being true together imply that P(n) is true for any natural number n. A proof by induction is then a proof that these two conditions hold, thus implying the required conclusion.
This works because k is used to represent an arbitrary natural number. Then, using the inductive hypothesis, i.e. that P(k) is true, show P(k + 1) is also true. This allows us to "carry" the fact that P(0) is true to the fact that P(1) is also true, and carry P(1) to P(2), etc., thus proving P(n) holds for every natural number n.
Note that the first quantifier in the axiom ranges over predicates rather than over individual numbers. This is called a second-order quantifier, which means that the axiom is stated in second-order logic. Axiomatizing arithmetic induction in first-order logic requires an axiom schema containing a separate axiom for each possible predicate. The article Peano axioms contains further discussion of this issue.
Read more about this topic: Mathematical Induction
Famous quotes containing the words axiom of, axiom and/or induction:
“It’s an old axiom of mine: marry your enemies and behead your friends.”
—Robert N. Lee. Rowland V. Lee. King Edward IV (Ian Hunter)
“It is an axiom in political science that unless a people are educated and enlightened it is idle to expect the continuance of civil liberty or the capacity for self-government.”
—Texas Declaration of Independence (March 2, 1836)
“One might get the impression that I recommend a new methodology which replaces induction by counterinduction and uses a multiplicity of theories, metaphysical views, fairy tales, instead of the customary pair theory/observation. This impression would certainly be mistaken. My intention is not to replace one set of general rules by another such set: my intention is rather to convince the reader that all methodologies, even the most obvious ones, have their limits.”
—Paul Feyerabend (1924–1994)