Results 1 to 3 of 3

Math Help - Help with discrete math

  1. #1
    Newbie
    Joined
    Jun 2008
    Posts
    21

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by tygracen View Post
    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 4a+a=5a \\\ 5|5a to R is reflexive

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

    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 5|(4a+b) \iff 4a+b=5q_1,q_1 \in \mathbb{Z} and
    5|(4b+c) \iff 4b+c=5q_2,q_2 \in \mathbb{Z}


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

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

    a~c
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292

    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.
    Last edited by nikhil; June 27th 2008 at 10:10 AM. Reason: Spelling mistake
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 22nd 2008, 12:56 AM
  2. Help me, I am new to discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 25th 2008, 05:15 PM
  3. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 8th 2007, 10:07 AM
  4. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: April 26th 2007, 08:49 AM
  5. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 26th 2007, 12:01 AM

Search Tags


/mathhelpforum @mathhelpforum