# Homework Help: Help proving subsets of the integers

1. Sep 29, 2012

### pianoman3182

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: $Z$={3k:k$\in$$Z$}$\cup${3k+1:k$\in$$Z$}$\cup${3k+2:k$\in$$Z$}

$Z$ 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. Sep 29, 2012

### Dick

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.

3. Sep 29, 2012

### pianoman3182

The thing is we haven't covered induction yet. That's what is bothering me

4. Sep 29, 2012

### Dick

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?

5. Sep 29, 2012

### pianoman3182

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?

6. Sep 29, 2012

### pianoman3182

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.

7. Sep 29, 2012

### Dick

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.

8. Sep 29, 2012

### pianoman3182

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.

9. Sep 30, 2012

### Dick

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?

10. Sep 30, 2012

### Ray Vickson

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,
$$x \in A \text{ implies } x \in B \text{ and } x \in B \text{ implies } x \in A.$$

RGV

Last edited: Sep 30, 2012