Overview

structural induction


Show Summary Details

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) let a be a smallest element of S, i.e. there is no x in S such that xa, then P(a) is true,(b) for each element s in S, if P(x) is true for each x in S with xs, 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 xa, then P(a) is true,

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

Subjects: Computing.


Reference entries

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