IS2 In-class Homework Solution

IS2 In-class Homework Solution IS2 In-class Homework Solution

Question
Let R be a relation on the set A = {1,2,3,4,5,6,7,8,9} defined by the rule x R y if x-y is a multiple of 3.

Show that R is an equivalence relation and find the equivalence classes of R.

(multiples of 3 are {...,-9, -6,-3,0,3,6,9,...})

Solution

R = {

(1,7), (1,4), (2,5), (3,6), (4,7), (1,1), (2,2), (3,3),

(4,4), (5,5),(6,6), (7,7), (4,1), (5,2), (6,3), (7,4), (7,1), }

R is reflexive since (x,x) Î R for all x in A.
i.e. (1,1), (2,2), (3,3), (4,4), (5,5),
(6,6) and (7,7) are in R.
R is symmetric since (x,y) Î R implies (y,x) Î R
e.g. (1,7) Î R implies (7,1) Î R.
R is transitive since (x,y) Î R and (y,z) Î R implies (x,z) in R
e.g. (1,7) Î R and (7,4) Î R implies (1,4) Î R.
Since R is reflexive, symmetric and transitive it is an equivalence relation.

E[1]

{ y: (y,1) Î R} = {1,4,7}

E[2]

{ y: (y,2) Î R} = {2,5}

E[3]

{ y: (y,3) Î R} = {3,6}

E[4]

{ y: (y,4) Î R} = {1,4,7}

E[5]

{ y: (y,5) Î R} = {2,5}

E[6]

{ y: (y,6) Î R} = {3,6}

E[7]

{ y: (y,7) Î R} = {1,4,7}

{{1,4,7}, {2,5},{3,6}} is the set of equivalence classes of R, these form a partition of A.

File translated from T_EX by T_TH, version 2.10.
On 6 May 1999, 15:20.