induction

logic A method of proving statements about well-orderedsets. If S is a well-ordered set with ordering "#@", and we

want to show that a property P holds for every element of S,

it is sufficient to show that, for all s in S,

IF for all t in S, t s = P(t) THEN P(s)

I.e. if P holds for anything less than s then it holds for s.

In this case we say P is proved by induction.

The most common instance of proof by induction is induction

over the natural numbers where we prove that some property

holds for n=0 and that if it holds for n, it holds for n+1.

(In fact it is sufficient for "#@" to be a well-founded

partial order on S, not necessarily a well-ordering of S.)

(1999-12-09)