Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 2] RELATIONS 31

Transitive Closure

LetRbe a relation on a setA. Recall thatR^2 =R◦RandRn=Rn−^1 ◦R. We define

R∗=

⋃∞

i= 1

Ri

The following theorem applies:

Theorem 2.4: R∗is the transitive closure ofR.

SupposeAis a finite set withnelements. We show in Chapter 8 on graphs that

R∗=R∪R^2 ∪...∪Rn

This gives us the following theorem:

Theorem 2.5: LetRbe a relation on a setAwithnelements. Then

transitive(R)=R∪R^2 ∪...∪Rn

EXAMPLE 2.11 Consider the relationR={( 1 , 2 ), ( 2 , 3 ), ( 3 , 3 )}onA={ 1 , 2 , 3 }. Then:

R^2 =R◦R={( 1 , 3 ), ( 2 , 3 ), ( 3 , 3 )} and R^3 =R^2 ◦R={( 1 , 3 ), ( 2 , 3 ), ( 3 , 3 )}

Accordingly,

transitive(R)={( 1 , 2 ), ( 2 , 3 ), ( 3 , 3 ), ( 1 , 3 )}

2.8Equivalence Relations

Consider a nonempty setS. A relationRonSis anequivalence relationifRis reflexive, symmetric, and
transitive. That is,Ris an equivalence relation onSif it has the following three properties:

(1) For everya∈S,aRa. (2) IfaRb, thenbRa. (3) IfaRbandbRc, thenaRc.

The general idea behind an equivalence relation is that it is a classification of objects which are in some way
“alike.” In fact, the relation “=” of equality on any setSis an equivalence relation; that is:

(1)a=afor everya∈S. (2) Ifa=b, thenb=a. (3) Ifa=b,b=c,thena=c.

Otherequivalence relations follow.

EXAMPLE 2.12

(a) LetLbe the set of lines and letTbe the set of triangles in the Euclidean plane.

(i) The relation “is parallel to or identical to” is an equivalence relation onL.

(ii) The relations of congruence and similarity are equivalence relations onT.

(b) The relation⊆of set inclusion is not an equivalence relation. It is reflexive and transitive, but it is not

symmetric sinceA⊆Bdoes not implyB⊆A.