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?

 

[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.

 

[pianoman3182]

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

 

[Dick]

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.

 

[Dick]

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 2ⁿ elements if there are "n" elements in a set. The other problems had to do with series and sums.

 

[Dick]

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 2ⁿ 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?

 

[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