# Help with discrete math

• Jun 27th 2008, 07:26 AM
tygracen
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.
• Jun 27th 2008, 07:48 AM
TheEmptySet
Quote:

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 $\displaystyle 4a+a=5a \\\ 5|5a$ to R is reflexive

a~b then b~a
we know that $\displaystyle 5|(4a+b) \mbox{ or } 4a+b=5q, q \in \mathbb{Z}$

$\displaystyle 4b+a=4(5q-4a)+a=20q-15a=5(4q-3a) \mbox{ so } 5|(4b+a)$

if a~b b~c then a~c

so we know that $\displaystyle 5|(4a+b) \iff 4a+b=5q_1,q_1 \in \mathbb{Z}$ and
$\displaystyle 5|(4b+c) \iff 4b+c=5q_2,q_2 \in \mathbb{Z}$

$\displaystyle 4a+c=4a+(5q_2-4b)=(5q_1-b)+(5q_2-4b)=$

$\displaystyle -5b+5q_1+5q_2=5(-b+q_1+q_2) \iff 5|(4a+c)$

a~c
• Jun 27th 2008, 09:25 AM
nikhil
Check 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.