If `P`

is a property of natural numbers such that

`P(0)`

holds, and- for every natural number
`n`

:`P(n)`

implies`P(n+1)`

,

then `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, `x`

, where `P(x)`

does not hold.
We know `x≠0`

by rule (1) above, therefore there is an `x-1`

such that `P(x-1)`

holds.
However, by rule (2) `P(x-1)`

implies `P(x)`

which is a contradiction.

K. Doets. *From Logic to Logic Programming.* MIT Press, 1994.

Copyright © 2014 Barry Watson. All rights reserved.