0.6 Discrete structures relation  (Page 3/13)

The Cartesian product A1 ×... ×An of sets A1 , ... , An ,  is also a relation, and it is called the universal relation.

Equality of relations

Definition (equality of binary relation):

Two binary relations R1 ⊆A1 ×A2 and R2⊆B1 ×B2 are equal if and only if A1 = B1, A2 = B2 , and R1 = R2 as a set.

For example, let R1 = {<1, 2>,<2, 2>} ⊆{1, 2} ×{1, 2} , and R2 = {<a, b>,<b, b>} ⊆{a, b} ×{a, b} . Then R1 = R2 if and only if  a = 1 and b = 2.

Definition (equality of n-ary relation):

An n-ary relation R1 ⊆A1 ×... ×An and an m-ary relation R2 ⊆B1 ×... ×Bm are equal if and only if  m = n, Ai = Bi for each i, 1 ≤i ≤n , and R1 = R2 as a set of ordered n-tuples.

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.

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.

Properties of binary relation, and operations

Digraph

A digraph is short for directed graph, and it is a diagram composed of points called vertices (nodes) and arrows called arcs going from a vertex to a vertex.