Results 1 to 9 of 9

Math Help - Check this quick proof please[Equivalence relation ]

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    36

    Check this quick proof please[Equivalence relation ]

    Problem statement :

    Let Z = { ..., -2, -1, 0, 1, 2, ...} denote the set of integers. Let Z x Z denote the set of ordered pairs of integers: Z x Z= { (x, y) | x, y in Z} .

    Part (I). Define the relation ~ on Z by the rule a ~ b if and only if gcd(a,b) > 1 . Is an equivalence relation? If so, prove it; if not, give a counter example.


    Attempt:

    It has to satisfy reflexive,symmetric,and transitive property. But I realize that it does not satisfy the reflexive property because of its domain.

    Proof :
    Let a be an element from Z.

    ~ is reflexive if a~a

    Since a is an element from Z, let a = 1.

    a~a implies gcd(a,a) > 1. By definition, gcd(a,a) = a. Since a is 1.
    It fails the definition. Thus ~ is not an equivalence relation because a~a does not
    necessarily imply gcd(a,a) > 1.


    Is the above correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Matter_Math View Post
    Problem statement :

    Let Z = { ..., -2, -1, 0, 1, 2, ...} denote the set of integers. Let Z x Z denote the set of ordered pairs of integers: Z x Z= { (x, y) | x, y in Z} .

    Part (I). Define the relation ~ on Z by the rule a ~ b if and only if gcd(a,b) > 1 . Is an equivalence relation? If so, prove it; if not, give a counter example.


    Attempt:

    It has to satisfy reflexive,symmetric,and transitive property. But I realize that it does not satisfy the reflexive property because of its domain.

    Proof :
    Let a be an element from Z.

    ~ is reflexive if a~a

    Since a is an element from Z, let a = 1.

    a~a implies gcd(a,a) > 1. By definition, gcd(a,a) = a. Since a is 1.
    It fails the definition. Thus ~ is not an equivalence relation because a~a does not
    necessarily imply gcd(a,a) > 1.


    Is the above correct?
    Edit: Sorry I didn't read your post well enough. Yes you're right. Safe to ignore my original response. (I gave an alternate counterexample.)

    Edit 2: Actually the wording of this is a bit off: "Thus ~ is not an equivalence relation because a~a does not necessarily imply gcd(a,a) > 1." Just say that 1~1 is not true therefore it's not an equivalence relation. Alternatively, say a~a is not true for all a in Z. Alternatively, say that gcd(a,a) > 1 is not true for all a in Z. Note that 1~1 not being true constitutes a counterexample.



    ----- Original response -----

    Since it is not an equivalence relation, we give a counterexample.

    gcd(2,6) = 2
    gcd(6,15) = 3
    gcd(2,15) = 1
    Last edited by undefined; September 6th 2010 at 05:14 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Sweet. Thanks so much. You are of great help.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Matter_Math View Post
    Sweet. Thanks so much. You are of great help.
    You're welcome! Make sure to read my Edit #2 above since I didn't see your reply until just now.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Yep, I seen your edit.

    Now instead of starting a new thread. I have 1 more question. Its part 2, from the question above. Here is the question :

    Part (II). Define the relation ~ on Z x Z by the rule (a,b) ~ (a`,b`) if and only if there is a rational number r, so that a = a` * r and b = b` * r . Is an equivalence relation? If so, prove it; if not, give a counter example.


    It is an equivalence relation. Here is the proof that I am asking you to check please:

    ~ is reflexive because :
    (a,b) ~ (a,b) since a = a * 1, b = b * 1, thus r = 1

    ~ is symmetric because
    if (a,b) ~ (a`,b`) then a = a`*r , b = b`*r, for some rational r.
    then a` = 1/r * a , b` = 1/r * b.
    thus if (a,b) ~ (a`,b`) for some r
    then (a`,b`) ~ (a,b) for some 1/r

    ~ is transitive because :
    [a] if (a,b) ~ (a1,b1) iff a = a1 * r1, b = b1 * r1, for some rational r1
    [b] if (b,c) ~ (b2,c1) iff b = b2 * r2, c = c1 * r2, for some rational r2

    [c] the (a,c) ~ (a1,c1) iff a = a1 * r3, c = c1 * r3, for some rational r3

    since :
    a = a1 * r1 //From [a]
    a1 = 1/r1 * a

    a = a1 * r3 //From [b]
    a = (1/r1)*a * r3
    r1*a = r3*a
    r1 = r3

    c = c1 * r2 //From [b]
    c1 = 1/r2 * c

    c = c1 * r3 //From [c]
    c = (1/r2) * c * r3
    r2*c = r3*c
    r2 = r3


    Since r1 = r3, and r2 = r3, thus r1 = r2.


    Thus (a,b) ~ (a1,c1) for some rational r2.



    Is the above correct? I wasn't sure how to close the proof. Thank you again.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Matter_Math View Post
    Yep, I seen your edit.

    Now instead of starting a new thread. I have 1 more question. Its part 2, from the question above. Here is the question :

    Part (II). Define the relation ~ on Z x Z by the rule (a,b) ~ (a`,b`) if and only if there is a rational number r, so that a = a` * r and b = b` * r . Is an equivalence relation? If so, prove it; if not, give a counter example.


    It is an equivalence relation. Here is the proof that I am asking you to check please:

    ~ is reflexive because :
    (a,b) ~ (a,b) since a = a * 1, b = b * 1, thus r = 1

    ~ is symmetric because
    if (a,b) ~ (a`,b`) then a = a`*r , b = b`*r, for some rational r.
    then a` = 1/r * a , b` = 1/r * b.
    thus if (a,b) ~ (a`,b`) for some r
    then (a`,b`) ~ (a,b) for some 1/r

    ~ is transitive because :
    [a] if (a,b) ~ (a1,b1) iff a = a1 * r1, b = b1 * r1, for some rational r1
    [b] if (b,c) ~ (b2,c1) iff b = b2 * r2, c = c1 * r2, for some rational r2

    [c] the (a,c) ~ (a1,c1) iff a = a1 * r3, c = c1 * r3, for some rational r3

    since :
    a = a1 * r1 //From [a]
    a1 = 1/r1 * a

    a = a1 * r3 //From [b]
    a = (1/r1)*a * r3
    r1*a = r3*a
    r1 = r3

    c = c1 * r2 //From [b]
    c1 = 1/r2 * c

    c = c1 * r3 //From [c]
    c = (1/r2) * c * r3
    r2*c = r3*c
    r2 = r3


    Since r1 = r3, and r2 = r3, thus r1 = r2.


    Thus (a,b) ~ (a1,c1) for some rational r2.



    Is the above correct? I wasn't sure how to close the proof. Thank you again.
    Hmm I think all your reasoning is quite good except for one pesky fact: 1/r is undefined when r = 0. Thus we get a counterexample on symmetric property,

    true that (0,0) ~ (1,1) using r = 0

    but not true that (1,1) ~ (0,0).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Oh dang. In my work on paper, I had stated that "for rational r != 0". I wonder if the teacher meant for this to happen. I will ask him tomorrow.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Oh thanks undefined. That was a typo. I told my professor and he corrected it. Now everyone in class has to prove this and can't take the easy way out.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Matter_Math View Post
    Oh thanks undefined. That was a typo. I told my professor and he corrected it. Now everyone in class has to prove this and can't take the easy way out.
    You're welcome, always happy to prevent people from taking the easy way out.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence relation proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 3rd 2011, 05:18 AM
  2. Equivalence relation proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 17th 2011, 04:30 PM
  3. Equivalence Relation Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 25th 2011, 08:32 AM
  4. Quick equivalence relation problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2009, 06:43 PM
  5. Equivalence Relation Proof
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: August 5th 2009, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum