1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help proving subsets of the integers

  1. Sep 29, 2012 #1
    I just started taking a foundations of math course that deals with proofs and all that good stuff and I need help on a problem that I'm stuck on:

    Prove: [itex]Z[/itex]={3k:k[itex]\in[/itex][itex]Z[/itex]}[itex]\cup[/itex]{3k+1:k[itex]\in[/itex][itex]Z[/itex]}[itex]\cup[/itex]{3k+2:k[itex]\in[/itex][itex]Z[/itex]}

    [itex]Z[/itex] in this problem is the set of integers

    This is all that's given. I thought maybe I could use induction but we haven't reached that topic in class yet. All we've studies is direct proofs, contradiction, contrapositive and some set/set operations stuff.

    I have no idea where to start. Maybe element chasing like proving the Demorgan's Laws?
     
  2. jcsd
  3. Sep 29, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I would say it's got to be induction. The integers are all about induction. If you even want to define the integers formally it's basically induction.
     
  4. Sep 29, 2012 #3
    The thing is we haven't covered induction yet. That's what is bothering me
     
  5. Sep 29, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Agreed. But I can't think what else to do. What properties do you know of the integers that you can apply the other techniques to?
     
  6. Sep 29, 2012 #5
    Well I know the set of integers is closed under multiplication and addition and that's about it. Wait...is that what the problem is asking me to prove?
     
  7. Sep 29, 2012 #6
    Okay so I did some reading on induction in my textbook. The one problem I see with proof by induction for this problem is that there is no base case that is true unless I'm not seeing it.
     
  8. Sep 29, 2012 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No. Suppose they had asked you to show Z={5k:k∈Z}∪{5k+1:k∈Z}∪{5k+2:k∈Z}. Then that wouldn't be true, yes? It clearly doesn't follow from those properties.
     
  9. Sep 29, 2012 #8
    Okay so what then? If I can't use what I stated before, where do I even start tackling this proof? The closest thing I saw to this proof in the chapter on induction was proving that Power sets have 2n elements if there are "n" elements in a set. The other problems had to do with series and sums.
     
  10. Sep 30, 2012 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Well, 0 is in your union. Now suppose n is in your set. Can you show n+1 and n-1 are also in your union? Wouldn't that inductively show the union is Z?
     
  11. Sep 30, 2012 #10

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Sometimes, to prove A = B for sets A and B, the easiest way is to prove A ##\subset## B and B ##\subset## A. That is,
    [tex] x \in A \text{ implies } x \in B \text{ and } x \in B \text{ implies } x \in A.[/tex]

    RGV
     
    Last edited: Sep 30, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Help proving subsets of the integers
  1. Prove a subset (Replies: 15)

  2. Proving a subset (Replies: 4)

Loading...