0.6 Discrete structures relation  (Page 7/13)

More examples:

The digraphs of R2 for several simple relations R are shown in Figure 7:

Properties of composite relations

Composite relations defined above have the following properties. Let R1 be a relation from A to B, and R2 and R3 be relations from B to C. Then

1. R1(R2R3) = (R1R2)R3

2. R1(R2 ∪R3) = R1R2 ∪R1R3

3. R1(R2 ∩R3) ⊆R1R2 ∩R1R3 Proofs for these properties are omitted.

Powers of relation

Let R be a binary relation on A. Then Rn for all positive integers n is defined recursively as follows:

Definition (power of relation):

Basis Clause: R0 = E, where E is the equality relation on A.

Inductive Clause: For an arbitrary natural number n, Rn+1 = RnR.

Note that there is no need for extremal clause here.

Thus for example R1 = R, R2 = RR, and R3 = R2R = (RR)R = R(RR) = RRR.

The powers of binary relation R on a set A defined above have the following properties.

1. Rm+n = RmRn,

2. (Rm)n = Rmn.

Special relations

Closure of binary relation

In our everyday life we often talk about parent-child relationship. This is a binary relation on the set of people in the world, dead or alive. Also we are often interested in ancestor-descendant relations. Although the latter relation can be obtained from the former, hence it is redundant in that sense, we do use ancestor-descendant relations which give us necessary information more directly. This ancestor-descendant relation relates two people if there is a sequence of parent-child relations from one to the other. It includes the parent-child relation as a subset. The ancestor-descendant relation is an example of the closure of a relation, in particular the transitive closure of the parent-child relation. In general, the closure of a relation is the smallest extension of the relation that has a certain specific property such as the reflexivity, symmetry or transitivity. Formally they are defined as follows:

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

(1) R' is reflexive,

(2) R ⊆R', and

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

Example: Let R be the less-than relation on the set of integers I, that is R = {<a, b>| a ∈I ⋀b ∈I ⋀a<b }.

Then the reflexive closure r(R) of R is the union of R and the equality relation on I, that is r(R) = {<a, b>| a ∈I ⋀b ∈I ⋀a ≤b }

The digraph of the reflexive closure of a relation is obtained from the digraph of the relation by adding a self-loop at each vertex if one is already not there.

Symmetric and transitive closures can be defined similarly.

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

(1) R' is symmetric,

(2) R ⊆R', and

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

Example: Let R be the less-than relation on the set of integers I. Then the symmetric closure of R, denoted by s(R) is s(R) = {<a, b>| a ∈I ⋀ b ∈I ⋀[ a<b ∨ a>b ] } that is {<a, b>| a ∈I ⋀b ∈I ⋀a ≠b }