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