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.

Another form of induction is strong induction which is defined as:
if `P`

is a property of natural numbers such that
for every natural number `n`

and for all natural numbers `m<n`

,
`P(m)`

implies `P(n)`

,
then `P`

holds for all natural numbers.

We can prove strong induction using mathematical induction. What we want to prove is:

```
``````
[∀n.∀m<n.P(m)⇒P(n)] ⇒ ∀x.P(x)
```

For any proof of `A⇒B`

we assume `A`

and demonstrate `B`

.
So we assume

` ````
∀n.∀m<n.P(m)⇒P(n)
```

and let us call it our *initial assumption*.
We now have to demonstrate `∀x.P(x)`

.
Instead of proving this we'll prove the easier
`∀n.∀m<n.P(m)`

which
suffices as `∀n.∀m<n.P(m) ⇒ ∀x.P(x)`

.
We'll use mathematical induction to do this:

*Claim:* `∀n.∀m<n.P(m)`

.

*Base case:* Take `n=0`

and since there is no
`m<0`

the result holds.

*Induction step:* Take `n=k`

and assume `∀m<k.P(m)`

holds (our induction hypothesis).
Consider `n=k+1`

. We need to show that
`∀m<k+1.P(m)`

holds which is the same as
`∀m<k.P(m)∧P(k)`

.
The first conjunct (`∀m<k.P(m)`

) is our induction hypothesis and when this is
combined with the initial assumption this gives us the second conjunct (`P(k)`

).

Hence the result is established by mathematical induction.

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

Copyright © 2014 Barry Watson. All rights reserved.