Define a relationRon Z by aRb if 4a + b is a multiple of 5. Show thatRdefines an equivalence relation or a partial order on N.

Printable View

- June 27th 2008, 08:26 AMtygracenHelp with discrete math
Define a relation

*R*on Z by a*R*b if 4a + b is a multiple of 5. Show that*R*defines an equivalence relation or a partial order on N. - June 27th 2008, 08:48 AMTheEmptySet
- June 27th 2008, 10:25 AMnikhilCheck this out
R is relation on z given by aRb if 4a+b = 5n (multiple of 5,n is any integer).

Recall that a relation is equivalence if it is

1) reflexive that is (a,a) belong to R for all a belonging to z(or the given set)

2)symmetric that is if aRb then bRa [if (a,b) is a element of R then (b,a) also an element in R]

3)transitive that is if aRb and bRc then aRc

now let us check the relation for these 3 parameters

1)reflexive

4a+b=5n therfor b=5n-4a

let a=5n-4a [(a,a) should be an element of R]which gives a=n hence for some value of n we will definitly get all elements of form (a,a) so its reflexive

2)Symmetric

aRb means 4a+b=5n. Lets check 4b+a. As 4b =20n-16a (multiply 4a+b=5n by 4) putting this value we get 4b+a=20n-15a or 5(4n-3a) which is a multiple of 5 so bRa is also a relation, hence it is symmetric

3) transitive

aRb imply 4a+b=5n.....1

bRc imply 4b+c=5m......2

now let us examine 4a+c

4a+c=4a+5m-4b=20a+5m-20n (using 1 and 2 for substitution)which is also a multiple of 5 hence it is also transitive. Therfor finally the given relation is reflexive,symmetric and transitive so the relation is equivalence relation.