Relation

Recursive Definition of Relation



Subjects to be Learned

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 tex2html_wrap_inline64 N  tex2html_wrap_inline64  b tex2html_wrap_inline64 N  tex2html_wrap_inline64  a < b } = { <0, 1>, <0, 2> , ..., <1, 2>, .... }.

Basis Clause: <0, 1> tex2html_wrap_inline64 R< ( or 0 R< 1 ), meaning 0 is less than 1.
Inductive Clause: For all x and y in N,   if <x, y> tex2html_wrap_inline64 R< ,   then <x, y + 1> tex2html_wrap_inline64 R< , and <x + 1, y + 1> tex2html_wrap_inline64 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> tex2html_wrap_inline64 Ra + b = c .
Inductive Clause: For all x, y and z in N,   if <x, y, z> tex2html_wrap_inline64 Ra + b = c ,   then <x + 1, y, z + 1> and <x, y + 1, z + 1> tex2html_wrap_inline64 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

Back to Table of Contents