0.6 Discrete structures relation

The digraph of the symmetric closure of a relation is obtained from the digraph of the relation by adding for each arc the arc in the reverse direction if one is already not there.

Definition (transitive closure): A relation R' is the transitive closure of a relation R if and only if

(1) R' is transitive,

(2) R ⊆R', and

(3) for any relation R'',   if R ⊆R''   and  R''   is transitive,  then  R' ⊆R'' , that is, R' is the smallest relation that satisfies (1) and (2).

Examples: The transitive closure of a parent-child relation is the ancestor-descendant relation as mentioned above, and that of the less-than relation on I is the less-than relation itself.

The digraph of the transitive closure of a relation is obtained from the digraph of the relation by adding for each directed path the arc that shunts the path if one is already not there.

Two more examples of closures are given in Figure 8 in terms of digraphs.

The arrows with two heads represent arrows going in opposite directions.

Properties of closure

The closures have the following properties. They are stated here as theorems without proof.

Theorem: Let E denote the equality relation, and Rc the inverse relation of binary relation R, all on a set A, where Rc = {<a, b>|<b, a>∈R}. Then

1. r(R) = R ∪ E

2. s(R) = R ∪Rc

3. t(R) = ${}_{i=1}^{\infty }$ Ri   =   ${}_{i=1}^n$ Ri,   if |A| = n.

4. R is reflexive if and only if   r(R) = R.

5. R is symmetric if and only if   s(R) = R.

6. R is transitive if and only if   t(R) = R.

Equivalence relation

On the face of most clocks, hours are represented by integers between 1 and 12. However, since a day has 24 hours after 12 hours, a clock goes back to hour 1, and starts all over again from there. Thus each pair of hours such as 1 and 13, 2 and 14, etc. share one number 1, 2, ...etc., respectively. The same applies when we are interested in more than 24 hours. 25th hour is 1, so are 37th, 49th etc. What we are doing here essentially is that we consider the numbers in each group such as 1, 13, 25, ..., equivalent in the sense that they all are represented by one number (they are congruent modulo 12). Being representable by one number such as we see on clocks is a binary relation on the set of natural numbers and it is an example of equivalence relation we are going to study here.

The concept of equivalence relation is characterized by three properties as follows:

Definition (equivalence relation): A binary relation R on a set A is an equivalence relation if and only if

(1) R is reflexive

(2) R is symmetric, and

(3) R is transitive.

Example 1: The equality relation (=) on a set of numbers such as {1, 2, 3} is an equivalence relation.

Example 2: The congruent modulo m relation on the set of integers i.e. {<a, b>| a ≡ b (mod m)}, where m is a positive integer greater than 1, is an equivalence relation.

Note that the equivalence relation on hours on a clock is the congruent mod 12, and that when m = 2, i.e. the congruent mod 2, all even numbers are equivalent and all odd numbers are equivalent. Thus the set of integers are divided into two subsets: evens and odds.