• Support PF! Buy your school textbooks, materials and every day products Here!

Help proving subsets of the integers

  • #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?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
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
The thing is we haven't covered induction yet. That's what is bothering me
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
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?
 
  • #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?
 
  • #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.
 
  • #7
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #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.
 
  • #9
Dick
Science Advisor
Homework Helper
26,258
618
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?
 
  • #10
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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:

Related Threads on Help proving subsets of the integers

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
779
  • Last Post
Replies
10
Views
812
  • Last Post
Replies
15
Views
3K
  • Last Post
Replies
4
Views
1K
Replies
11
Views
1K
  • Last Post
Replies
18
Views
901
Replies
14
Views
8K
  • Last Post
Replies
11
Views
5K
  • Last Post
Replies
5
Views
1K
Top