Help proving subsets of the integers

In summary: A and B, if x ∈ A and y ∈ B, then x ##\subseteq## y. This is sometimes called the inclusion-exclusion principle.Could you show that for the integers, this is also the case?Yes, if x ∈ Z and y ∈ Z, then x ##\subseteq## y.This is sometimes called the inclusion-exclusion principle.
  • #1
pianoman3182
5
0
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?
 
Physics news on Phys.org
  • #2
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
pianoman3182 said:
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
pianoman3182 said:
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
pianoman3182 said:
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
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 to Help proving subsets of the integers

1. What are subsets of the integers?

Subsets of the integers refer to a collection of numbers that are part of the set of integers. These subsets can be formed by selecting specific numbers from the set of integers or by using mathematical operations on the integers.

2. How do you prove that a set is a subset of the integers?

To prove that a set is a subset of the integers, you need to show that all the elements in the set are also integers. This can be done by listing out all the elements in the set and demonstrating that each one is an integer or by showing that the set can be formed by using mathematical operations on integers.

3. Can a set be a subset of itself?

Yes, a set can be a subset of itself. This is because every set is a subset of itself by definition. In other words, all the elements in a set are also part of the set itself.

4. How can you prove that two sets are equal?

To prove that two sets are equal, you need to show that they have the same elements. This means that every element in one set is also present in the other set, and vice versa. This can be done by listing out the elements of both sets and comparing them.

5. What is the difference between a proper subset and an improper subset?

A proper subset is a subset of a set that does not include all the elements of the original set. In other words, there are elements in the original set that are not present in the proper subset. An improper subset, on the other hand, is a subset that includes all the elements of the original set. In this case, the proper subset is equal to the original set.

Similar threads

Proving an integer is composite
    • Calculus and Beyond Homework Help
Replies
13
Views
738
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
569
Every subset of a finite set is finite
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
Finding all subsets of a list of positive integers using backtracking
    • Programming and Computer Science
Replies
4
Views
1K
Showing when quadratic integer rings are isomorphic
    • Calculus and Beyond Homework Help
Replies
7
Views
1K
Discrete Math Proof: Necessary Condition for Divisibility by 6
    • Calculus and Beyond Homework Help
Replies
3
Views
3K
Strong Induction: Proving Every Int n>1 is a Product of Primes
    • Calculus and Beyond Homework Help
Replies
5
Views
1K
Prove that a locally constant function is constant on a connected X
    • Calculus and Beyond Homework Help
Replies
20
Views
2K
Showing that subgroups of G form a lattice
    • Calculus and Beyond Homework Help
Replies
4
Views
842
Prove 5|(3^(3n+1)+2^(n+1)) for every positive integer n.
    • Calculus and Beyond Homework Help
Replies
3
Views
4K

Hot Threads

Recent Insights

Back
Top