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:

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

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