28 RELATIONS [CHAP. 2
Composition of Relations and Matrices
There is another way of findingR◦S. LetMRandMSdenote respectively the matrix representations of the
relationsRandS. Then
MR=a bcd
1
2
3
4⎡
⎢
⎢
⎣1000
0001
1101
0000⎤
⎥
⎥
⎦and MS=xyz
a
b
c
d⎡
⎢
⎢
⎣000
101
010
001⎤
⎥
⎥
⎦MultiplyingMRandMSwe obtain the matrix
xyzM=MRMS=1
2
3
4⎡
⎢
⎢
⎣000
001
102
000⎤
⎥
⎥
⎦The nonzero entries in this matrix tell us which elements are related byR◦S. ThusM=MRMSandMR◦Shave
the same nonzero entries.
2.6Types of Relations
This section discusses a number of important types of relations defined on a setA.Reflexive Relations
A relationRon a setAisreflexiveifaRafor everya∈A, that is, if(a, a)∈Rfor everya∈A. ThusRis
not reflexive if there existsa∈Asuch that(a, a) /∈R.
EXAMPLE 2.5 Consider the following five relations on the setA={ 1 , 2 , 3 , 4 }:
R 1 ={( 1 , 1 ), ( 1 , 2 ), ( 2 , 3 ), ( 1 , 3 ), ( 4 , 4 )}
R 2 ={( 1 , 1 )( 1 , 2 ), ( 2 , 1 ), ( 2 , 2 ), ( 3 , 3 ), ( 4 , 4 )}
R 3 ={( 1 , 3 ), ( 2 , 1 )}
R 4 =∅,the empty relation
R 5 =A×A,the universal relationDetermine which of the relations are reflexive.
SinceAcontains the four elements 1, 2, 3, and 4, a relationRonAis reflexive if it contains the four pairs
( 1 , 1 ), ( 2 , 2 ), ( 3 , 3 ), and( 4 , 4 ). Thus onlyR 2 and the universal relationR 5 =A×Aare reflexive. Note that
R 1 ,R 3 , andR 4 are not reflexive since, for example,( 2 , 2 )does not belong to any of them.
EXAMPLE 2.6 Consider the following five relations:
(1) Relation≤(less than or equal) on the setZof integers.
(2) Set inclusion⊆on a collectionCof sets.
(3) Relation⊥(perpendicular) on the setLof lines in the plane.
(4) Relation‖(parallel) on the setLof lines in the plane.
(5) Relation|of divisibility on the setNof positive integers.(Recallx|yif there existszsuch thatxz=y.)Determine which of the relations are reflexive.