induction
<logic> A method of proving statements about well-ordered sets. If S is a
well-ordered set with ordering "<", and we want to show that a property P holds
for every element of S, it is sufficient to show that, for all s in S,
IF for all t in S, t < s => P(t) THEN P(s)
I.e. if P holds for anything less than s then it holds for s. In this case
we say P is proved by induction.
The most common instance of proof by induction is induction over the natural
numbers where we prove that some property holds for n=0 and that if it holds for
n, it holds for n+1.
(In fact it is sufficient for "<" to be a well-founded partial order on S, not
necessarily a well-ordering of S.)
(1999-12-09)
Nearby terms:
indirect address « indirect addressing « indirection
«
induction » inductive inference » inductive
relation » Industrial Programming, Inc.
|
