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