Results 1 to 3 of 3

Thread: Need help proving that two sets are equal

  1. #1
    Newbie
    Joined
    Aug 2014
    From
    Australia
    Posts
    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,769
    Thanks
    3027

    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$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Dec 17th 2012, 03:23 PM
  2. Equal power sets -> Equal sets?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jul 5th 2012, 09:23 AM
  3. Replies: 5
    Last Post: Nov 13th 2011, 11:41 AM
  4. Proving two sets are equal
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 22nd 2010, 09:21 AM
  5. Proving two sets equal
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Jan 25th 2008, 07:26 AM

Search Tags


/mathhelpforum @mathhelpforum