# Computer Dictionary Online

Medical Dictionary   Law Dictionary   Legal Dictionary   Website Design
 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z

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)

 Contact the Computer Dictionary Online  ::  Link to the Computer Dictionary Online  ::  Disclaimer for Computer Dictionary Online Computer Dictionary Online Copyright © 2018