# 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

Garrett Birkhoff , Birkhoff was the son of mathematician George David Birkhoff and Margaret Grafius Birkhoff. George Birkhoff, the father, was the first American mathem… Lysithea , Lysithea (Jupiter X) One of the lesser satellites of Jupiter, with a diameter of 24km. Domain , Domain
The domain of a relation is the set that contains all the first elements, x, from the ordered pairs (x,y) that make up the relation. In mathem… Equation , equation An expression that asserts the equality of two terms. To be precise, an equation has the following form. Let Σ be a signature and let t1(X1,… George Boole , Boole, George
Boole, George
(b. Lioncoln, England, 1815; d. Cork, Ireland, 1864)
mathematics.
George Boole was the son of John Boole, a cobbler whose… Diophantus Of Alexandria , Diophantus of Alexandria
Diophantus of Alexandria
(fl. ad. 250)
mathematics.
We know virtually nothing about the life of Diophantus. The dating of hi…

#### You Might Also Like

#### NEARBY TERMS

**structural induction**