- #1
bishy
- 13
- 0
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 [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.
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