structural induction

Updated About encyclopedia.com content Print Article Share Article
views updated

structural induction The principle of induction defined as follows. Let S be a set on which the partial ordering ← is defined and which contains no infinite decreasing sequences (where decreasing is defined by the ordering relation). If P is some predicate and if the following two conditions hold:

(a) let a be a smallest element of S, i.e. there is no x in S such that x a, then P(a) is true,

(b) for each element s in S, if P(x) is true for each x in S with x s, and from this it follows that P(s) is true,

then P(s) is true for all s in S. Structural induction tends to be used in proving properties of recursive programs.