Thread: Help with discrete math

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

Originally Posted by tygracen

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

To be an equivalence relation it must be

Reflexive a~a

symmetric a~b then b~a

transitive if a~b and b~c then a~c

So we need to verify these properties

a~a to R is reflexive

a~b then b~a
we know that



if a~b b~c then a~c

so we know that and







a~c

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.