Inductive definition

definition by induction

The definition of some object or concept $ A ( n) $, depending on a non-negative integer parameter $ n $, according to the following scheme: a) the value of $ A ( 0) $ is given; and b) a rule is given for obtaining the value of $ A ( n+ 1 ) $ from $ n $ and the value of $ A ( n) $. A typical inductive definition is that of the function $ n! $: a) $ 0! = 1 $; and b) $ ( n+ 1 ) ! = n! ( n+ 1 ) $. A more general inductive definition is definition by transfinite induction of an object $ A ( \alpha ) $, depending on a (transfinite) ordinal number $ \alpha $. This definition is effected by providing some rule that enables one to obtain the value of $ A ( \alpha ) $ in terms of the known values of $ A ( \beta ) $ for all $ \beta < \alpha $. For example, the sum $ \gamma + \alpha $ of two ordinal numbers $ \gamma $ and $ \alpha $ is defined thus:

$$ \gamma + 0 = \gamma ,\ \ \gamma + \alpha = \sup _ {\beta < \alpha } ( \gamma + \beta + 1) \ \ \textrm{ for } \alpha > 0 . $$

Another extension of the notion of inductive definition is so-called generalized inductive definition, by which some class of objects is defined. This proceeds according to the following scheme: 1) certain (initial) objects of the class to be defined are given; 2) certain rules are given enabling one to obtain from objects already known to be in the class, objects of the class; and 3) those and only those objects that are obtained from the rules 1) and 2) are the objects of the required class (the latter rule is always taken for granted and is therefore often omitted). An example of a generalized inductive definition is the definition of the notion of a theorem for a given axiomatic system $ S $: every axiom of $ S $ is a theorem; if the premises of some derivation rule of $ S $ are theorems, then the conclusion of this derivation rule is also a theorem.

In order to prove that all objects of the class defined by some generalized inductive definition, for example every theorem of some axiomatic system $ S $, possess a certain property $ P $, it suffices to show the following: every axiom of $ S $ has property $ P $; if the premises of some derivation rule possess property $ P $, then the conclusion of this derivation rule also possesses property $ P $. Proofs of this kind are called proofs by induction, according to the definition of the corresponding concept (in the given example, a theorem) or according to the construction of the corresponding object, depending on the context.

References

[1]	J.R. Shoenfield, "Mathematical logic" , Addison-Wesley (1967)
[2]	K. Kuratowski, A. Mostowski, "Set theory" , North-Holland (1968)

References

[a1]	Y.N. Moschovakis, "Elementary introduction on abstract structures" , North-Holland (1974)