Discrete Mathematical Structures by Pearson

Relations and Digraphs 2-9

From (i) and (ii), R = R

−1

.

Conversely Let R = R

−1

, then ( y, x) ∈ R ⇒ (x, y) ∈ R

−1

⇒ ( y, x) ∈ R, which shows that R is symmetric.

Example 11 If R is an equivalence relation on a set A, then prove that R

−1

is also an equivalence

relation on A.

Proof: Since R is an equivalence relation on a set A, it must be reflexive, symmetric, and

transitive.

1. Since R is reflexive, for every a, (a, a) ∈ R ⇒ (a, a) ∈ R

−1

and so R

−1

is reflexive.

2. Since R is symmetric (a, b) ∈ R ⇒ (b, a) ∈ R

Now (a, b) ∈ R ⇒ (b, a) ∈ R

−1

and (b, a) ∈ R ⇒ (a, b) ∈ R

−1

,

which shows that (a, b) ∈ R

−1

and (b, a) ∈ R

−1

and so R

−1

is symmetric.

3. Since ...