# Help proving subsets of the integers

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?

## Answers and Replies

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.

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

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

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?

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?

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.

Homework Helper
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?

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.

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.

Homework Helper
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.

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?

$$x \in A \text{ implies } x \in B \text{ and } x \in B \text{ implies } x \in A.$$