Definition - Recursive Definitions

Recursive Definitions

A recursive definition, sometimes also called an inductive definition, is one that defines a word in terms of itself, so to speak, albeit in a useful way. Normally this consists of three steps:

1. At least one thing is stated to be a member of the set being defined; this is sometimes called a "base set".
2. All things bearing a certain relation to other members of the set are also to count as members of the set. It is this step that makes the definition recursive.
3. All other things are excluded from the set

For instance, we could define natural number as follows (after Peano):

1. "0" is a natural number.
2. Each natural number has a distinct successor, such that:
   • the successor of a natural number is also a natural number, and
   • no natural number is succeeded by "0".
3. Nothing else is a natural number.

So "0" will have exactly one successor, which for convenience we can call "1". In turn, "1" will have exactly one successor, which we would call "2", and so on. Notice that the second condition in the definition itself refers to natural numbers, and hence involves self-reference. Although this sort of definition involves a form of circularity, it is not vicious, and the definition has been quite successful.