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

- Jun 27th 2008, 07: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. - Jun 27th 2008, 07:48 AMTheEmptySet
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 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.