# structural induction

**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.

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**structural induction**