Inductive definition
definition by induction
The definition of some object or concept 
, depending on a non-negative integer parameter 
, according to the following scheme: a) the value of 
is given; and b) a rule is given for obtaining the value of 
from 
and the value of 
. A typical inductive definition is that of the function 
: a) 
; and b) 
. A more general inductive definition is definition by transfinite induction of an object 
, depending on a (transfinite) ordinal number 
. This definition is effected by providing some rule that enables one to obtain the value of 
in terms of the known values of 
for all 
. For example, the sum 
of two ordinal numbers 
and 
is defined thus:
 |
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 
: every axiom of 
is a theorem; if the premises of some derivation rule of 
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 
, possess a certain property 
, it suffices to show the following: every axiom of 
has property 
; if the premises of some derivation rule possess property 
, then the conclusion of this derivation rule also possesses property 
. 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) |
Comments
References
| [a1] | Y.N. Moschovakis, "Elementary introduction on abstract structures" , North-Holland (1974) |
Inductive definition. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Inductive_definition&oldid=17120