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

CHAP. 2] RELATIONS 37

TYPES OF RELATIONS AND CLOSURE PROPERTIES

2.9. Consider the following five relations on the setA={ 1 , 2 , 3 }:

R={( 1 , 1 ), ( 1 , 2 ), ( 1 , 3 ), ( 3 , 3 )}, ∅=empty relation

S={( 1 , 1 )( 1 , 2 ), ( 2 , 1 )( 2 , 2 ), ( 3 , 3 )},A×A=universal relation

T={( 1 , 1 ), ( 1 , 2 ), ( 2 , 2 ), ( 2 , 3 )}

Determine whether or not each of the above relations onAis: (a) reflexive; (b) symmetric; (c) transitive;

(d) antisymmetric.

(a) Ris not reflexive since 2∈Abut( 2 , 2 )/∈R.Tis not reflexive since( 3 , 3 )/∈Tand, similarly,∅is not reflexive.

SandA×Aare reflexive.

(b) Ris not symmetric since( 1 , 2 )∈Rbut( 2 , 1 )/∈R, and similarlyTis not symmetric.S,∅, andA×Aare symmetric.

(c) Tis not transitive since( 1 , 2 )and( 2 , 3 )belong toT, but( 1 , 3 )does not belong toT. The other four relations are

transitive.

(d) Sis not antisymmetric since 1=2, and( 1 , 2 )and( 2 , 1 )bothbelongtoS. Similarly,A×Ais not antisymmetric.

The other three relations are antisymmetric.

2.10. Give an example of a relationRonA={ 1 , 2 , 3 }such that:

(a) Ris both symmetric and antisymmetric.

(b) Ris neither symmetric nor antisymmetric.

(c) Ris transitive butR∪R−^1 is not transitive.

There are several such examples. One possible set of examples follows:

(a)R={( 1 , 1 ), ( 2 , 2 )};(b)R={( 1 , 2 ), ( 2 , 3 )}; (c)R={( 1 , 2 )}.

2.11. SupposeCis a collection of relationsSon a setA, and letTbe the intersection of the relationsSinC, that
is,T=∩(S|S∈C)Prove:

(a) If everySis symmetric, thenTis symmetric.

(b) If everySis transitive, thenTis transitive.

(a) Suppose(a, b)∈T. Then(a, b)∈Sfor everyS. Since eachSis symmetric,(b, a)∈Sfor everyS. Hence

(b, a)∈TandTis symmetric.

(b) Suppose (a,b) and (b,c) belong toT. Then (a,b) and (b,c) belong toSfor everyS. Since eachSis transitive, (a,c)

belongs toSfor everyS. Hence,(a, c)∈TandTis transitive.

2.12. LetRbe a relation on a setA, and letPbe a property of relations, such as symmetry and transitivity. Then

Pwill be calledR-closableifPsatisfies the following two conditions:

(1) There is aP-relationScontainingR.

(2) The intersection ofP-relations is aP-relation.

(a) Show that symmetry and transitivity areR-closable for any relationR.

(b) SupposePisR-closable. ThenP(R), theP-closure ofR, is the intersection of allP-relationsScontaining

R, that is,

P(R)=∩(S|Sis aP-relation andR⊆S)

(a) The universal relationA×Ais symmetric and transitive andA×Acontains any relationRonA. Thus (1) is

satisfied. By Problem 2.11, symmetry and transitivity satisfy (2). Thus symmetry and transitivity areR-closable for

any relationR.