Recursive Definition

- recursive/inductive definition
- basis clause
- basis
- inductive clause
- extremal clause

In this type of definition, first a collection of elements to be included initially in the set is specified. These elements can be viewed as the seeds of the set being defined. Next, the rules to be used to generate elements of the set from elements already known to be in the set (initially the seeds) are given. These rules provide a method to construct the set element by element starting with the seeds. These rules can also be used to test elements for the membership in the set.

A

- The
**basis clause**(or simply basis) of the definition establishes that certain objects are in the set. This part of the definition specifies the "seeds" of the set from which the elements of the set are generated using the methods given in the inductive clause. The set of elements specified here is called**basis**of the set being defined. - The
**inductive clause**(or simply induction) of the definition establishes the ways in which elements of the set can be combined to produce new elements of the set. The inductive clause always asserts that if objects are elements of the set, then they can be combined in certain specified ways to create other objects. Let us call the objects used to create a new object the**parents**of the new object, and the new object is their**child**. - The
**extremal clause**asserts that unless an object can be shown to be a member of the set by applying the basis and inductive clauses a finite number of times, the object is not a member of the set.

The set you are trying to define recursively is**the set that satisfies those three clauses.**

There are a number of other ways of expressing the extremal clause that are equivalent to the extremal clause given above. They are not required for this course but those interestedclick here.

The set

The basis for this set

Following this definition, the set of natural numbers

First by the Basis Clause,

Then by the Inductive Clause, since

Then by the Inductive Clause again,

Proceeding in this manner all the "natural numbers" are put into

Note that if we don't have the Extremal Clause,

For more precise and abstract definition of natural numbers

You might also want to look at the entry on natural number in Wikipedia.

The set

**Example 3.** Definition of the Set of Even Integers

The set ** EI** is the set that satisfies the following three clauses:

**Example 4.** Definition of the Set of Strings
over the alphabet
excepting empty string.

This is the set of strings consisting of ** a**'s and

The set

Here

For the "Basis Clause", try simplest elements in the set such as smallest numbers (

The set of propositions (propositional forms) can also be defined recursively. To see how it is defined

Click Yes or No , then Submit. There are two sets of questions.

- recursive definition of function

A few examples are given below.

They are all on functions from integer to integer except the last one.

The function

Note that here Extremal Clause is not necessary, because the set of natural numbers can be defined recursively and that has the extremal clause in it. So there is no chance of other elements to come into the function being defined.

Using this definition,

Since

Hence

Hence

The function

See above for the extremal clause.

The function

See Example 5 for the extremal clause.

The function

See Example 5 for the extremal clause.

This function