P is a property of natural numbers such that
P holds for all natural numbers.
Rule (1) is known as the "base case" or "basis case". Rule (2) is known as the "induction step", or "inductive step".
A simple proof is by contradiction. Assume the result does not hold.
In this case there is a least natural number,
P(x) does not hold.
x≠0 by rule (1) above, therefore there is an
x-1 such that
However, by rule (2)
P(x) which is a contradiction.
K. Doets. From Logic to Logic Programming. MIT Press, 1994.
Copyright © 2014 Barry Watson. All rights reserved.