induction

views updated

induction
1. A method of logical inference in which a general but not necessarily true conclusion is drawn from a set of particular instances. In machine learning, for example, the term induction is used to describe an approach to machine learning in which generalized structures or statements are inferred from particular examples.

2. A process for proving mathematical statements involving members of an ordered set (possibly infinite). There are various formulations of the principle of induction. For example, by the principle of finite induction, to prove a statement P(i) is true for all integers i ≥ i0, it suffices to prove that

(a) P(i0) is true;

(b) for all k ≥ i0, the assumption that P(k) is true (the induction hypothesis) implies the truth of P(k+1).

(a) is called the basis of the proof, (b) is the induction step.

Generalizations are possible. Other forms of induction permit the induction step to assume the truth of P(k) and also that of P(k–1), P(k–2), …, P(k–i)

for suitable i. Statements of several variables can also be considered. See also structural induction.

More From encyclopedia.com