0.5 Discrete structures recursion

Recursion

Recursive definition

Recursive definition

Sets which have too many elements to list them up, and for which there are no convenient or obvious predicates to specify their elements can often be defined using a recursive definition (also called inductive definition). It essentially gives a procedure to generate the members of the set one by one starting with some subset of its elements. 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 recursive definition of a set always consists of three distinct clauses:

1. 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.

2. 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.

3. 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.

Examples of Recursive Definition of Set

Example 1. Definition of the Set of Natural Numbers N

The set N is the set that satisfies the following three clauses:

Basis Clause: 0 ∈ N

Inductive Clause: For any element x in N, x + 1 is in N.

Extremal Clause: Nothing is in N unless it is obtained from the Basis and Inductive Clauses.

The basis for this set N is { 0 } . The x + 1 in the Inductive Clause is the parent of x, and x is the child of x + 1. Following this definition, the set of natural numbers N can be obtained as follows:

First by the Basis Clause,   0 is put into N. Then by the Inductive Clause, since 0 is in N,  0 + 1 (= 1) is in N. 0 is the parent of 1, and 1 is the child of 0. Then by the Inductive Clause again,   1 + 1 (= 2) is in N. 1 is the parent of 2, and 2 is the child of 1. Proceeding in this manner all the "natural numbers" are put into N.