Relation
Recursive Definition of Relation
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
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.