| << Chapter < Page | Chapter >> Page > |
The Cartesian product A1 ×... ×An of sets A1 , ... , An , is also a relation, and it is called the universal 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.
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.
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.
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.
Notification Switch
Would you like to follow the 'Discrete structures' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|