Relation

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
*R*_{a + b = c}
be the set of triples of natural numbers
**<***a, b, c*> which satisfy *a + b *= *c* .
Then
*R*_{a + b = c}
on the set of natural numbers *N*
can be defined recursively as follows.

**Basis Clause:** **<***0, 0, 0*> *R*_{a + b = c} .

**Inductive Clause:** For all *x, y* and *z* in *N*,
if **<***x, y, z*>
*R*_{a + b = c} ,
then
**<***x + 1, y, z + 1*> and **<***x, y + 1, z + 1*>
*R*_{a + b = c} .

**Extremal Clause:** Nothing is in
*R*_{a + 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

Back to Table of Contents