Can You Prove These Equivalence Relations?

[bishy]

Homework Statement

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 a,b \in S define a ~ b if a and b have the same number of elements. Prove that ~ defines an equivalence relationship on S.

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 (b,a) \in \mathcal{R}

~ 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 (a,c) \in \mathcal{R}

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 a \in P(S) 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 a,b \in P(S) and since a, b \subseteq P(S) and by definition of a set, order does not matter.

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

Therefore it is symmetric.

Proof of transitivity goes here

 

[HallsofIvy]

Homework Statement

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 a,b \in S define a ~ b if a and b have the same number of elements. Prove that ~ defines an equivalence relationship on S.

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 (b,a) \in \mathcal{R}

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 (a,c) \in \mathcal{R}[/quote]
Now that's completely correct and very clever!

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 a \in P(S) is a subset of P(S), then a is reflexive on P(S) trivially since the reflexion of a set is the set again.p.

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 ...

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

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

Therefore it is symmetric.

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]