## Quick Reference

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* be a smallest element of *S*, i.e. there is no *x* in *S* such that *x* ≤ *a*, then *P*(*a*) is true,*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.

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

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

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.