Recursive Definition

A definition is the identification of something by means of a description. For example, a "unicorn" is by definition "a horse that has a horn on its head." Every definition has at least two parts: the definiendum (= that which is to be defined, in our example "unicorn") and the definiens (= that which defines the definiendum, in our example "a horse that has a horn on its head"). But defining concepts is not always a simple task. Suppose we want to define "direct male ancestor." One could very simply say that the direct male ancestor of anyone is his father, his grandfather, his father's grandfather, and so on. This can be written as follows:

"x is a direct male ancestor of y" is by definition "x is the father of y, or x is the grandfather of y, or x is the father of the grandfather of y, and so on"

But the phrase "and so on" is not a clear phrase by the standards of mathematicians and logicians. This phrase is particularly useless for those who write programs for computers. This is because digital computers cannot execute the command "and so on." In such cases, one must use a "recursive definition." A recursive definition is a definition for a class of objects that can be arranged in a chain. A chain that may well have no end.

Every recursive definition generally has two parts:

1- The basis clause, in which the definiendum (or that which is to be defined) does not appear. And

2- The inductive step, in which the definiendum does appear.

Let me clarify the matter with a few examples. Suppose we want to define "direct male ancestor" without using the phrase "and so on." The recursive definition of this phrase is as follows:

Recursive definition (1): "x is a direct male ancestor of y" is by definition "x is the father of y, or x is the father of a direct male ancestor of y."

"x is the father of y" is the basis clause, and "x is the father of a direct male ancestor of y" is the inductive step. To clarify the discussion, suppose Mohammad is the father of Leila, and Kourosh is the father of Mohammad. Mohammad is the father of Leila, so, according to the basis clause of recursive definition (1), Mohammad is a direct male ancestor of Leila. But the inductive step of recursive definition (1) tells us that Kourosh is also a direct male ancestor of Leila. Because Kourosh is the father of a direct male ancestor of Leila, that is, the father of Mohammad. Again, if Esmail were the father of Kourosh, according to the inductive step of recursive definition (1), Esmail would also be a direct male ancestor of Leila, and so on and so on.

Two brief points regarding recursive definition:

A- A recursive definition appears, on the surface, to be a circular definition. A circular definition is one in which the definiendum of the definition shows up in its definiens. Circular definitions are not very useful. Because instead of identifying the concept, they return us to our starting point. In recursive definitions, it also seems as if the definiendum (in our example, "direct male ancestor") shows up in the definiens (in the inductive step in recursive definition (1)). But the truth is that recursive definitions are not circular.

B- The word induction in "inductive step" is not logical induction (arriving at a general proposition from particular observations). Rather, what is meant is mathematical induction. Induction in mathematics differs from logical induction. In fact, mathematical induction is proven through logical deduction. Recursive definition is sometimes called inductive definition, where again mathematical induction is meant.

Two more examples of recursive definitions of concepts:

Recursive definition of the concept of number (in the set of natural numbers):

"x is a number" is by definition "x is zero or x is the successor of a number."

According to this definition, four is a number because it is the successor of the successor of the successor of the successor of zero.

Recursive definition of empirical knowledge:

"Proposition p is known empirically" is by definition "p is known by direct sensory perception or p is known by valid inference from a set of propositions at least one of which is known empirically."

In conclusion, it should be said that recursive definition has many applications in computer science, mathematics, and logic. For example, the concept of a formula in logic is usually defined in a recursive manner, or in mathematics, the concept of a prime number can be defined in this way.

.

---

.

References:

1- Definitions, Dictionaries, and Meanings, Norman Swartz, Online

2- Introduction to Logic and its philosophy, Peter K. Schotch, Library and Archives Canada Cataloguing in Publication 2006, P. 15-16.

3- Technical Methods in Philosophy, John L. Pollock, Westview Press, 1990, P. 37-41

.

---

.

Recursive Definition

Kaveh Behbahani

.

---

.