## Recursive Definition of Relation

### Subjects to be Learned

• how to define relation recursively

### Contents

Certain relations can be defined recursively. Note that a relation is a set. Therefore a recursive definition of a relation follows the same format as that of sets. Here only examples are given. To review recursive definition click here.

Example 1: Let us define recursively the relation "less than" denoted by R< on the set of natural numbers N.
Note that R< = { <a, b> | a N    b N    a < b } = { <0, 1>, <0, 2> , ..., <1, 2>, .... }.

Basis Clause: <0, 1> R< ( or 0 R< 1 ), meaning 0 is less than 1.
Inductive Clause: For all x and y in N,   if <x, y> R< ,   then <x, y + 1> R< , and <x + 1, y + 1> R< .
Extremal Clause: Nothing is in R< , unless it is obtained from the Basis and Inductive Clauses.

Informally one can see that this definition is correct as follows:
First, <0, 1> is the "simplest" element in R< .
Next by arranging the ordered pairs in R< as follows, one can see that the two operations in the Inductive Clause generate them all:
<0, 1>, <0, 2>, <0, 3>, ............................. , <0, n>, .....
<1, 2>, <1, 3>, <1, 4>, ................. , <1, n>, .....
<2, 3>, <2, 4>, <2, 5>, ..... , <2, n>, .....
............................................
............................................

In each row, the first (leftmost) ordered pair gives the "smallest" ordered pair with the first number. For example <2, 3> is the smallest with 2 as the first component. It is obtained from the first ordered pair of the row immediately above it by using <x + 1, y + 1> of the Inductive Clause, apply that to <1, 2> to get <2, 3> , for example.
Within each row, the ordered pairs are obtained from the first one by using <x, y + 1> of the Inductive Clause successively.
Thus all the ordered pairs of R< are generated from <0, 1> by following the Inductive Clause.

Example 2: Let Ra + b = c be the set of triples of natural numbers <a, b, c> which satisfy a + b = c . Then Ra + b = c on the set of natural numbers N can be defined recursively as follows.

Basis Clause: <0, 0, 0> Ra + b = c .
Inductive Clause: For all x, y and z in N,   if <x, y, z> Ra + b = c ,   then <x + 1, y, z + 1> and <x, y + 1, z + 1> Ra + b = c .
Extremal Clause: Nothing is in Ra + b = c unless it is obtained from the Basis and Inductive Clauses.

### Test Your Understanding of Recursive Definition of Relation

Indicate which of the following statements are correct and which are not.
Click True or False , then Submit. There is one set of questions.

Next --Digraph

Back to Schedule