CHAP. 2] RELATIONS 39
2.16. LetRbe the following equivalence relation on the setA={ 1 , 2 , 3 , 4 , 5 , 6 }:R={( 1 , 1 ), ( 1 , 5 ), ( 2 , 2 ), ( 2 , 3 ), ( 2 , 6 ), ( 3 , 2 ), ( 3 , 3 ), ( 3 , 6 ), ( 4 , 4 ), ( 5 , 1 ), ( 5 , 5 ), ( 6 , 2 ), ( 6 , 3 ), ( 6 , 6 )}Find the partition ofAinduced byR, i.e., find the equivalence classes ofR.Those elements related to 1 are 1 and 5 hence
[ 1 ]={ 1 , 5 }
We pick an element which does not belong to [1], say 2. Those elements related to 2 are 2, 3, and 6, hence
[ 2 ]={ 2 , 3 , 6 }
The only element which does not belong to [1] or [2] is 4. The only element related to 4 is 4. Thus
[ 4 ]={ 4 }
Accordingly, the following is the partition ofAinduced byR:
[{ 1 , 5 },{ 2 , 3 , 6 },{ 4 }]2.17. Prove Theorem 2.6: LetRbe an equivalence relation in a setA. Then the quotient setA/Ris a partition
ofA. Specifically,(i) a∈[a],for everya∈A.
(ii) [a]=[b]if and only if(a, b)∈R.
(iii) If[a] =[b],then[a]and[b]are disjoint.
(a) Proof of (i): SinceRis reflexive,(a, a)∈Rfor everya∈Aand thereforea∈[a].
(b) Proof of (ii): Suppose(a, b)∈R. We want to show that [a]=[b]. Letx∈[b]; then(b, x)∈R. But by hypothesis
(a, a)∈Rand so, by transitivity,(a, x)∈R. Accordinglyx∈[a]. Thus[b]⊆[a]. To prove that[a]⊆[b]we
observe that(a, b)∈Rimplies, by symmetry, that(b, a)∈R. Then, by a similar argument, we obtain[a]⊆[b].
Consequently,[a]=[b].
On the other hand, if[a]=[b], then, by (i),b∈[b]=[a] ;hence(a, b)∈R.
(c) Proof of (iii): We prove the equivalent contrapositive statement:If[a]∩[b] =∅then [a]=[b]
If[a]∩[b] =∅, then there exists an elementx∈Awithx∈[a]∩[b]. Hence(a, x)∈Rand(b, x)∈R.By
symmetry,(x, b)∈Rand by transitivity,(a, b)∈R. Consequently by (ii),[a]=[b].PARTIAL ORDERINGS
2.18. Letbe any collection of sets. Is the relation of set inclusion⊆a partial order on?
Yes, since set inclusion is reflexive, antisymmetric, and transitive. That is, for any setsA,B,Cinwe have: (i)A⊆A;
(ii) ifA⊆BandB⊆A, thenA=B; (iii) ifA⊆BandB⊆C, thenA⊆C.
2.19. Consider the setZof integers. DefineaRbbyb=arfor some positive integerr. Show thatRis a partial
order onZ, that is, show thatRis: (a) reflexive; (b) antisymmetric; (c) transitive.
(a) Ris reflexive sincea=a^1.
(b) SupposeaRbandbRa, sayb=aranda=bs. Thena=(ar)s=ars. There are three possibilities: (i)rs=1,
(ii)a=1, and (iii)a=−1. Ifrs=1 thenr=1 ands=1 and soa=b.Ifa=1 thenb= 1 r= 1 =a, and,
similarly, ifb=1 thena=1. Lastly, ifa=−1 thenb=−1 (sinceb=1) anda=b. In all three cases,a=b.
ThusRis antisymmetric.
(c) SupposeaRbandbRcsayb=arandc=bs. Thenc=(ar)s=arsand, therefore,aRc. HenceRis transitive.Accordingly,Ris a partial order onZ.