1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equivalence relations proofs

  1. Oct 23, 2008 #1
    1. The problem statement, all variables and given/known data

    question 1: Define ~ on Z by a ~ b if and only if 3a + b is multiple of 4.

    question 2: Let A = {1,2,3,4,5,6} and let S = P(A) (the power set of A). For [tex] a,b \in S [/tex] define a ~ b if a and b have the same number of elements. Prove that ~ defines an equivalence relationship on S.


    3. The attempt at a solution

    question 1: Here is an attempt at a proof. I'm not really sure how to go about proving transitivity, hope I did it right. If not some advice would be swell.

    ~ is reflexive since that implies 3a + a = 4a which clearly implies 4 | 4a

    ~ is symmetric since by communitative algebra laws 3a + b = b + 3a so [tex] (b,a) \in \mathcal{R} [/tex]

    ~ is transitive since if 4| 3a + b and 4| 3b + c then their sums must be divisible by 4.
    This gives something of the form 4| 3a + 4b + c but clearly 4b is divisible by 4 so it can be omitted then 4| 3a + c which implies [tex] (a,c) \in \mathcal{R} [/tex]

    Therefore its an equivalence relation

    question 2: I have absolutely no idea how to prove for transitivity here. I always thought transitivity could only be used to indicate a equality, if that would be the case then there would be no transitivity and therefore no relation but that clearly is not the case. Some advice on how to prove it would be nice.

    proof:

    since [tex] a \in P(S) [/tex] is a subset of P(S), then a is reflexive on P(S) trivially since the reflexion of a set is the set again.

    if [tex] a,b \in P(S) [/tex] and since [tex] a, b \subseteq P(S) [/tex] and by definition of a set, order does not matter.

    Then b can be interchanged with a such that [tex] b,a \in P(S) [/tex]

    Therefore it is symmetric.

    Proof of transitivity goes here
     
  2. jcsd
  3. Oct 23, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, that's not what "symmetric" means. If a~b means "3a+ b is a multiple of 4", then b~a means "3b+ a is a multiple of 4".

    [/quote] ~ is transitive since if 4| 3a + b and 4| 3b + c then their sums must be divisible by 4.
    This gives something of the form 4| 3a + 4b + c but clearly 4b is divisible by 4 so it can be omitted then 4| 3a + c which implies [tex] (a,c) \in \mathcal{R} [/tex][/quote]
    Now that's completely correct and very clever!

    What? By "a is reflexive" do you mean a~a? That is, that "~" is reflexive, not a. Also a being in P(S) does not mean it is a subset of P(S), but that it is a subset of S. Perhaps that was a typo. Most importantly, just saying it is a subset of S is not enough. For two sets to be "~", they must both be subsets of s and ......

    Again, you have dropped an important part of the definition of "~"! a~b if and only if a and b are subsets of S and .....

    [/quote]Proof of transitivity goes here[/QUOTE]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Equivalence relations proofs
Loading...