Results 1 to 13 of 13

Math Help - Prove or disprove equivalence relation of union and intersection

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Prove or disprove equivalence relation of union and intersection

    Please check and critique the following proof:

    Let R_{1}and R_{2} be equivalence relations on a set A.

    a) Is R_{1}\cup R_{2} an equivalance relation on A? Prove or disprove.

    First we need to test the Reflexive property: Let a_{1}\in A such that (a_{1},a_{1})\in R_{1} and a_{2}\in A such that (a_{2},a_{2})\in R_{2}. Since (a_{1},a_{1})\in R_{1}, then (a_{1},a_{1})\in R_{1}\cup R_{2}. Similarly, (a_{2},a_{2})\in R_{2}, then (a_{2},a_{2})\in R_{1}\cup R_{2}. This proves that R_{1}\cup R_{2} is Reflexive.

    Second we need to test the Symmetric property: Let a_{1},b_{1}\in A such that (a_{1},b_{1}),(b_{1},a_{1})\in R_{1} and a_{2},b_{2}\in A such that (a_{2},b_{2}),(b_{2},a_{2})\in R_{2}. Clearly if (a_{1},b_{1}),(b_{1},a_{1})\in R_{1} then (a_{1},b_{1}),(b_{1},a_{1})\in R_{1}\cup R_{2}. Also if (a_{2},b_{2}),(b_{2},a_{2})\in R_{2} then (a_{2},b_{2}), (b_{2},a_{2})\in R_{1}\cup R_{2}. This proves that R_{1}\cup R_{2} is Symmetric.

    Third we need to test the Transitive property: Let a_{1},b_{1},c_{1}\in A such that (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1} and a_{2},b_{2},c_{2}\in A such that (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2}. Clearly if (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1} then (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}\cup R_{2}. Similarly if (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2} then (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{1}\cup R_{2}. Therefore R_{1}\cup R_{2} is Transitive. Since R_{1}\cup R_{2} is Reflexive, Symmetric, and Transitive, it is an equivalence relation on A.

    b) Is R_{1}\cap R_{2} an equivalence relation on A? Prove or disprove. Suppose a_{1}\in A such that (a_{1},a_{1})\in R_{1} and (a_{1},a_{1})\notin R_{2}. Then clearly (a_{1},a_{1})\notin R_{1}\cap R_{2}. Since R_{1}\cap R_{2} is not Reflexive, it is not an equivalence relation on A.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by oldguynewstudent View Post
    Please check and critique the following proof:

    Let R_{1}and R_{2} be equivalence relations on a set A.

    a) Is R_{1}\cup R_{2} an equivalance relation on A? Prove or disprove.

    First we need to test the Reflexive property: Let a_{1}\in A such that (a_{1},a_{1})\in R_{1} and a_{2}\in A such that (a_{2},a_{2})\in R_{2}. Since (a_{1},a_{1})\in R_{1}, then (a_{1},a_{1})\in R_{1}\cup R_{2}. Similarly, (a_{2},a_{2})\in R_{2}, then (a_{2},a_{2})\in R_{1}\cup R_{2}. This proves that R_{1}\cup R_{2} is Reflexive.
    You're working backwards!

    To show that R_1 \cup R_2 is reflexive, you need to show that  \forall a \in A, \ (a,a) \in R_1 \cup R_2
    This clearly follows from the fact that R_1, \ R_2 are reflexive.


    Second we need to test the Symmetric property: Let a_{1},b_{1}\in A such that (a_{1},b_{1}),(b_{1},a_{1})\in R_{1} and a_{2},b_{2}\in A such that (a_{2},b_{2}),(b_{2},a_{2})\in R_{2}. Clearly if (a_{1},b_{1}),(b_{1},a_{1})\in R_{1} then (a_{1},b_{1}),(b_{1},a_{1})\in R_{1}\cup R_{2}. Also if (a_{2},b_{2}),(b_{2},a_{2})\in R_{2} then (a_{2},b_{2}), (b_{2},a_{2})\in R_{1}\cup R_{2}. This proves that R_{1}\cup R_{2} is Symmetric.
    You're not following the definition! A relation R is symmetric if  (a,b) \in R \Rightarrow (b,a) \in R.
    Here, in order to show that R_1 \cup R_2 is symmetric, you need to show (a,b) \in R_1 \cup R_2 \Rightarrow (b,a) \in R_1 \cup R_2
    This, again, easily follows from your relations being symmetric.


    Third we need to test the Transitive property: Let a_{1},b_{1},c_{1}\in A such that (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1} and a_{2},b_{2},c_{2}\in A such that (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2}. Clearly if (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1} then (a_{1},b_{1}),(b_{1},c_{1})(a_{1},c_{1})\in R_{1}\cup R_{2}. Similarly if (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{2} then (a_{2},b_{2}),(b_{2},c_{2})(a_{2},c_{2})\in R_{1}\cup R_{2}. Therefore R_{1}\cup R_{2} is Transitive. Since R_{1}\cup R_{2} is Reflexive, Symmetric, and Transitive, it is an equivalence relation on A.
    Same reasoning. Here, you need to show that  (a,b) \in R \ \wedge \ (b,c) \in R \Rightarrow (a,c) \in R.
    Now try proving these conditions again (you'll find something is missing for transitiveness...)
    Once you've done that, b) will be much easier.

    b) Is R_{1}\cap R_{2} an equivalence relation on A? Prove or disprove. Suppose a_{1}\in A such that (a_{1},a_{1})\in R_{1} and (a_{1},a_{1})\notin R_{2}. Then clearly (a_{1},a_{1})\notin R_{1}\cap R_{2}. Since R_{1}\cap R_{2} is not Reflexive, it is not an equivalence relation on A.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1606
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    Let R_{1}and R_{2} be equivalence relations on a set A.
    a) Is R_{1}\cup R_{2} an equivalance relation on A? Prove or disprove.
    Part a is FALSE. Consider the set A=\{1,2,3\}.
    R_1=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}~\&~ R_2=\{(1,1),(2,1),(3,3),(2,2),(1,2)\}

    Consider the set \mathcal{A} of all relations of a set A.
    If R\in\mathcal{A} ~\&~S\in\mathcal{A} if R is reflexive then R\cup S must be reflexive.

    The union of two symmetric relations is also symmetric.

    But as the above counterexample shows that does hold for transitivity.


    Quote Originally Posted by oldguynewstudent View Post
    Let R_{1}and R_{2} be equivalence relations on a
    b) Is R_{1}\cap R_{2} an equivalence relation on A? Prove or disprove.
    Part b is true. You ought to prove it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Thank you both for your help. However, I am getting more confused.

    First Defunkt, I thought I was doing what you said needed to be done by showing arbitrary elements of both R_1 and R_2 were in the union to prove reflexive. So I don't see how exactly I was working backwards. I know my proofs are not "up to par" and I saw my professor yesterday to get help. I am trying to learn and not trying to be argumentative. Should I maybe have said a_1 and a_2 were arbitrary? Thank you for your patience and understanding.

    Plato, again thank you for your help.

    I don't see how transitivity does not work for the union. (1,2) (2,1) (2,3) (3,2) are all in the union.

    What if R_1={ (1,1),(2,2),(1,2),(2,1)} and R_2={ (3,3),(4,4),(3,4),(4,3)} with their intersection equal the null set. Would that be an equivalence relation?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1606
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    Plato, again thank you for your help. I don't see how transitivity does not work for the union. (1,2) (2,1) (2,3) (3,2) are all in the union.
    Let R_{1}and R_{2} be equivalence relations on a set A. R_{1}\cup R_{2} an equivalance relation on A? Prove or disprove.
    Consider the set A=\{1,2,3\}. R_1=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}~\&~ R_2=\{(1,1),(2,1),(3,3),(2,2),(1,2)\}
    The union is not transitive. (1,2)\in R_1\cup R_2~\&~ (2,3)\in R_1\cup R_2\text{ BUT }(1,3)\notin R_1\cup R_2
    Quote Originally Posted by oldguynewstudent View Post
    What if R_1={ (1,1),(2,2),(1,2),(2,1)} and R_2={ (3,3),(4,4),(3,4),(4,3)} with their intersection equal the null set. Would that be an equivalence relation?
    Where did the 4 come from? You cannot throw things about.
    The intersection of two transitive relations on the same set is transitive.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by Plato View Post
    Consider the set A=\{1,2,3\}. R_1=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}~\&~ R_2=\{(1,1),(2,1),(3,3),(2,2),(1,2)\}
    The union is not transitive. (1,2)\in R_1\cup R_2~\&~ (2,3)\in R_1\cup R_2\text{ BUT }(1,3)\notin R_1\cup R_2

    Where did the 4 come from? You cannot throw things about.
    The intersection of two transitive relations on the same set is transitive.
    I see the error now that you've drilled it into my thick skull. Thank you for your patience. We're just starting to go over equivalence relations. I really appreciate your help!

    For the intersection problem I was proposing two new relations where their intersection would result in the null set. We haven't had that theorem yet.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by oldguynewstudent View Post
    Thank you both for your help. However, I am getting more confused.

    First Defunkt, I thought I was doing what you said needed to be done by showing arbitrary elements of both R_1 and R_2 were in the union to prove reflexive. So I don't see how exactly I was working backwards. I know my proofs are not "up to par" and I saw my professor yesterday to get help. I am trying to learn and not trying to be argumentative. Should I maybe have said a_1 and a_2 were arbitrary? Thank you for your patience and understanding.

    Plato, again thank you for your help.

    I don't see how transitivity does not work for the union. (1,2) (2,1) (2,3) (3,2) are all in the union.

    What if R_1={ (1,1),(2,2),(1,2),(2,1)} and R_2={ (3,3),(4,4),(3,4),(4,3)} with their intersection equal the null set. Would that be an equivalence relation?
    You are getting a little confused here - you are given that  R_1 and R_2 are equivalence relations; now define R:= R_1 \cup R_2.
    You need to show that R is an equivalence relation.

    So for example, when checking for symmetry you will take two arbitrary elements of the set (not of R_1 and R_2!), let's say a and b, and check if (a,b) \in R \Rightarrow (b,a) \in R.
    What you showed when you tried proving symmetry is that  (a_1, b_1) \in R_1 \Rightarrow (a_1, b_1) \in R_1 \cup R_2 and (a_2, b_2) \in R_2 \Rightarrow (a_2, b_2) \in R_1 \cup R_2,
    but that is always true because R_1 \subseteq R_1 \cup R_2 and R_2 \subseteq R_1 \cup R_2!

    Also, if I came out offensive I am sorry - that was not my intention
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by Defunkt View Post
    You are getting a little confused here - you are given that  R_1 and R_2 are equivalence relations; now define R:= R_1 \cup R_2.
    You need to show that R is an equivalence relation.

    So for example, when checking for symmetry you will take two arbitrary elements of the set (not of R_1 and R_2!), let's say a and b, and check if (a,b) \in R \Rightarrow (b,a) \in R.
    What you showed when you tried proving symmetry is that  (a_1, b_1) \in R_1 \Rightarrow (a_1, b_1) \in R_1 \cup R_2 and (a_2, b_2) \in R_2 \Rightarrow (a_2, b_2) \in R_1 \cup R_2,
    but that is always true because R_1 \subseteq R_1 \cup R_2 and R_2 \subseteq R_1 \cup R_2!

    Also, if I came out offensive I am sorry - that was not my intention
    Not at all, I just did not want to come off argumentative. As Ricky said to Lucy "That 'splains it!" I understand how I was coming from the wrong angle now.

    I did not have a professor I could relate to for Discrete, this professor is speaking to my understanding for Combinatorics. So I am a little behind with these proofs but with great help like this, I am catching up.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1606
    Awards
    1
    Quote Originally Posted by Defunkt View Post
    You are getting a little confused here - you are given that  R_1 and R_2 are equivalence relations; now define R:= R_1 \cup R_2.
    You need to show that R is an equivalence relation.
    Defunkt, may I ask: “What is your point?”
    R:= R_1 \cup R_2 is not necessarily an equivalence relation.
    R:= R_1 \cap R_2 is necessarily an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Of course, but I was trying to show why the original approach (which led to the result that R_1 \cup R_2 is indeed an equivalence relation) was wrong.

    It was also my opinion that if he sees that transitivity doesn't always hold for a union of equivalence relations, then it would be easier to set up a counter example for the claim.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Okay, gentlemen, let's see if I have gained any understanding on this:

    Is R_{1}\cap R_{2} an equivalence relation on A? Prove or disprove. Take an arbitrary element a_{1}\in R_{1}\cap R_{2}\in A. Since a_{1}\in R_{1}\cap R_{2} then a_{1}\in R_{1} and a_{1}\in R_{2}. Since both R_{1} and R_{2} are equivalence relations on A, then (a_{1},a_{1})\in R_{1}\cap R_{2}. This shows R_{1}\cap R_{2} is reflexive.

    Now take two arbitrary elements a_{1},b_{1}\in R_{1}\cap R_{2}\in A. Since a_{1},b_{1}\in R_{1}\cap R_{2} then a_{1},b_{1}\in R_{1} and a_{1},b_{1}\in R_{2}. Since both R_{1} and R_{2} are equivalence relations on A, then (a_{1},b_{1}),(b_{1},a_{1})\in R_{1}\cap R_{2}. This shows R_{1}\cap R_{2} is symmetric.

    Fianlly take three arbitrary elements a_{1},b_{1},c_{1}\in R_{1}\cap R_{2}\in A. Since a_{1},b_{1},c_{1}\in R_{1}\cap R_{2} then a_{1},b_{1},c_{1}\in R_{1} and a_{1},b_{1},c_{1}\in R_{2}. Since both R_{1} and R_{2} are equivalence relations on A, then (a_{1},b_{1}),(b_{1},c_{1})\in R_{1}\cap R_{2}. This shows that R_{1}\cap R_{2} is transitive and therefore since the intersection meets all three requirements, it is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1606
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    R_{1}\cap R_{2} an equivalence relation on A? Prove or disprove. Take an arbitrary element a_{1}\in R_{1}\cap R_{2}\in A. Since a_{1}\in R_{1}\cap R_{2} then a_{1}\in R_{1} and a_{1}\in R_{2}. Since both R_{1} and R_{2} are equivalence relations on A, then (a_{1},a_{1})\in R_{1}\cap R_{2}. This shows R_{1}\cap R_{2} is reflexive.
    That notation is hopelessly confused! Unless you sort it out, you have no hope of ever understanding any of this.

    First R_1\subseteq A\times A, that is R_1 is a set of pairs.
    The diagonal \Delta_A=\{(a,a):a\in A\}.
    Any reflexive relation contains the diagonal: \Delta_A\subseteq R implies that R is reflexive.
    A relation is symmetric if it equals its inverse R=R^{-1}.

    So you should write (a,b)\in R~\&~(b,c)\in R then (a,c)\in R: That is transitive.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by Plato View Post
    That notation is hopelessly confused! Unless you sort it out, you have no hope of ever understanding any of this.

    First R_1\subseteq A\times A, that is R_1 is a set of pairs.
    The diagonal \Delta_A=\{(a,a):a\in A\}.
    Any reflexive relation contains the diagonal: \Delta_A\subseteq R implies that R is reflexive.
    A relation is symmetric if it equals its inverse R=R^{-1}.

    So you should write (a,b)\in R~\&~(b,c)\in R then (a,c)\in R: That is transitive.
    Thank you Plato, you have given me a new approach to this.

    Let me try a new problem to see if I am understanding this better, i.e. clean slate starting over:

    a\equiv b(mod{\atop }n) iff n|(a-b). Prove the congruence mod n is an equivalence relation on \mathcal{\mathbb{Z}}.

    To prove that a\equiv b(mod{\atop }n) is an equivalence relation on \mathcal{\mathbb{Z}}, first we show that it is reflexive.

    Let (a_{1},a_{1})\in\mathbb{Z}X\mathbb{Z}. We need to show that a_{1}\equiv a_{1}(mod{\atop }n) for any n\in\mathbb{Z}. n|(a_{1}-a_{1}) for any (a_{1},a_{1})\in\mathbb{Z}X\mathbb{Z}. So the relation is reflexive.

    Second we show that the relation is symmetric.

    Let (a_{1},b_{1})\in\mathbb{Z}X\mathbb{Z} we need to show that if a_{1}\equiv b_{1}(mod{\atop }n) then b_{1}\equiv a_{1}(mod{\atop }n). So we assume n|(a_{1}-b_{1}) does n|(b_{1}-a_{1})?? Yes, because b_{1}-a_{1}=-(a_{1}-b_{1}). Therefore the relation is symmetric.

    Third we check transitive.

    We need to show that if a\equiv b(mod{\atop }n) and b\equiv c(mod{\atop }n) then a\equiv c(mod{\atop }n). We have n|(a-b) and n|(b-c). So a=b+kn and b=c+jn, then a=c+jn+kn which can be written as a = c + (j+k)n. This proves the relation is transitive and also that it is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  2. Prove equivalence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: June 23rd 2010, 10:25 AM
  3. Replies: 3
    Last Post: March 18th 2010, 09:37 AM
  4. Prove or disprove that R^4 is a transitive relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 16th 2010, 03:52 PM
  5. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM

Search Tags


/mathhelpforum @mathhelpforum