# 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 "$\displaystyle A= B$", for A and B sets, by proving "$\displaystyle A\subset B$" and "$\displaystyle B\subset A$".

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

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

To show that $\displaystyle A\subset Z$ is easy. is $\displaystyle x\in A$ then
i) $\displaystyle x\in \{3q| q\in Z\}$
Since Z is "closed under multiplication" x= 3q, for any q in Z, is in Z
or ii) $\displaystyle 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) $\displaystyle 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 $\displaystyle 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 $\displaystyle x\in \{3q| q\in Z\}$
ii) If the remainder is 1 then x= 3q+ 1 where q is the quotient so $\displaystyle x\in \{3q+ 1| q\in Z\}$
iii) If the remainder is 2 then x= 3q+ 2 where q is the quotient so $\displaystyle x\in \{3q+ 2| q\in Z\}$

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

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