# Thread: Need help proving that two sets are equal

1. ## Need help proving that two sets are equal

I need help with the following.
Prove that:
{3q : q ∈ Z} U {3q + 1 : q ∈ Z} U {3q + 2 : q ∈ Z} = Z

2. ## Re: Need help proving that two sets are equal

Use the fact that the remainder of every integer when divided by 3 is 0, 1 or 2.

3. ## Re: Need help proving that two sets are equal

In general you prove that " $A= B$", for A and B sets, by proving " $A\subset B$" and " $B\subset A$".

And you prove " $X\subset Y$" by starting "if $x\in X$" and using the properties of X and Y to conclude "then $x\in Y$"

Here, you have $A= \{3q| q\in Z\}\cup \{3q+1| q\in Z\}\cup \{3q+ 2| q\in Z\}$ and B= Z.

To show that $A\subset Z$ is easy. is $x\in A$ then
i) $x\in \{3q| q\in Z\}$
Since Z is "closed under multiplication" x= 3q, for any q in Z, is in Z
or ii) $x\in \{3q+ 1| q\in Z\}$
Since Z is "closed under multiplication" and "closed under addition", x= 3q+ 1, for any q in Z, is in Z.
or iii) $x\in \{3q+ 2} q\in Z\}$
Again, since Z is "closed under multiplication" and "closed under addition", x= 3q+ 2, for any q in Z, is in Z.

Therefore A is a subset of Z.

To prove the other way is only slightly harder. If $x\in Z$, then dividing x by 3 gives remainder 0, 1, or 2 since the remainder has to be a non-negative integer less than 3: x/3 "has quotient q with remainder r" so that x/3= q+ r/3 and x= 3q+ r.
i) If the remainder is 0 then x= 3q where q is the quotient so $x\in \{3q| q\in Z\}$
ii) If the remainder is 1 then x= 3q+ 1 where q is the quotient so $x\in \{3q+ 1| q\in Z\}$
iii) If the remainder is 2 then x= 3q+ 2 where q is the quotient so $x\in \{3q+ 2| q\in Z\}$

In any case, $x\in A$ so $Z\subset A$

Together those give $A= \{3q| q\in Z\}\cup \{3q+1| q\in Z\}\cup \{3q+ 2| q\in Z\}= Z$.