Home » Sets » Page 2

Prove union and intersection of a set with itself equals the set

Prove that and .

Proof. Let be an arbitrary element of . Then or ; hence, . Thus, .
Conversely, if is an arbitrary element of then since it is in . Thus, .
Therefore,

Proof. Let be an arbitrary element of . Then and ; hence, . So, .
Conversely, if is arbitrary, then and ; hence, . Thus, .
Therefore,

Prove distributive laws for unions and intersections of sets

Prove that and .

Proof (). Let be an arbitrary element of . This means that and . Further, since we know or . But then, this implies or depending on whether or , respectively. Then, since or , we have . Thus, .
For the opposite inclusion, we let be an arbitrary element of . This means that or . If then and , while if we have and . Thus, we have no matter what, and either or . Since or , we know . Since we already had that no matter what, we now have . Therefore, .
Hence, .∎

Proof (). Let be an arbitrary element of . This means or . If then and . Hence, . Otherwise, if then and . Hence, and ; therefore, . Therefore, .
For the reverse inclusion, let be an arbitrary element of . This means and . This implies that or and (since if then the fact that and means must be in both and ). If , then . On the other hand, if and , then . Hence, . Therefore, .
Therefore, .∎

Prove the associative laws for union and intersections of sets

Prove that and that .

Proof (Associativity of unions). First, let be any element in . This means that or . If then ; hence, . On the other hand, if , then . This means or . If , then . If , then . Hence, .
For the reverse inclusion, let be any element of . Then, or . If , we know or . If , then . If , then ; hence, . On the other hand, if , then , and so, . Therefore, .
Thus, .∎

Proof (Associativity of intersections). To expedite matters, will prove both inclusions at once: is in if and only if and , further, if and only if and . Similarly, if and only if and and . Thus, and have exactly the same elements (since if and only if and and if and only if ).
Thus, .∎

Prove the commutative laws of union and intersection

Prove and .

Proof If is any element in then, by definition of union, we have or . But, if is in or , then it is in or , and by definition of union, this means . Therefore, .
The other inclusion is identical: if is any element of , then we know or . But, or implies that is in or ; and hence, . Therefore, .
Hence, .∎

Proof If is any element in , then we know by definition of intersection that and . Hence, and , and so, . Therefore, .
The reverse inclusion is again identical: if is any element of , then we know and . Hence, and . This implies . Hence, .
So, .∎

Prove properties of set equality

Prove the following.

1. .
2. .
3. if and only if .

1. Proof. To show two sets are equal, we want to show that each is a subset of the other (i.e., we want to show that and ).
First, since the only element of is , and we have .
Second, the only element of is , and we have . Hence, . Thus, . ∎
2. Proof. Again, we want to show and .
First, since the elements of are and , and .
Second, the elements of are and . Since we have every element of is in ; thus, .
Therefore, . ∎
3. Proof. Assume . Since , we must have ; hence, every element of must be contained in . This means that both and are in . Since is the only element of , we must have .
Conversely, assume . Then and from part (a) we know ; hence .∎

Proving some relations between given sets

Let

Prove or disprove the following.

1. .
2. .
3. .
4. .
5. .
6. .
7. .
8. .
9. .

1. False.
These sets are not equal since they do not contain the same elements (since and ).
2. False.
Since contains an element (e.g. 1) that is not contained in , we have . (Again, this is asking us to observe that .)
3. False.
Again, but ; hence, .
4. True.
Proof. By definition of we have . Since , we have .∎
5. False.
Since , but , we have .
6. False.
The element is in , but is not in . Hence, .
7. True.
Proof. To show , we must show that every element in is also in , and that (so that is a proper subset). First, the only two elements of are the sets and . Since each of these sets is contained in by definition of , we have . Finally, since the set , but , we see that the inclusion is proper. Hence, . ∎
8. False.
Again, the problem is emphasizing the difference between an element and the set that contains that element. In this case and is not an element of (even though and are elements of , the set containing the sets and is not).
9. True.
Proof. By the definition of we have . Since , we have . ∎

Determining subsets of a given set

If determine all subsets of .

The subsets of are: , , , , , , , , , , , , , , , . We see that, indeed, there are 16 of them.

More proofs of set relations

Let and . Prove or disprove the following.

1. .
2. .
3. .
4. .
5. .
6. .

1. True.
Proof. Since 1 is the only element in , and , we have that every element of is contained in . Hence, . Further, since , but is not in , we see that . Therefore, . ∎
2. True.
Proof. Again, since , we have by part (a). ∎
3. True.
Proof. By the definition of we have that . Since , we have . ∎
4. True.
Proof. By definition ; hence, .∎
5. False.
Since 1 is not a set, we cannot have .
6. False.
Since 1 is still not a set, we cannot have .

Prove or disprove some set relations

If and prove or disprove the following:

1. .
2. .
3. .
4. .
5. .
6. .

1. True Proof. To show we must show that every element in is also in . Further (since Apostol seems to distinguish between and ) we want to show that .

First, since is the only element of , and , we see that every element of is indeed contained in . Hence, .

Then, since , but , we see that . Hence , so is a proper subset of , or . ∎

2. True
Proof. This follows immediately from part (a) since . ∎
3. Not True
This is not true since and the set is not an element of (since ).
4. True
Proof. There is really nothing to prove here. By definition, is the set containing 1, so 1 is in . ∎
5. Not true
This is not true since 1 is not a set, so is not a subset of .
6. Not true
Again, 1 is not a set, so cannot be a subset of .

Determining subset relations

Determine the inclusion relations between the sets:

• $A = \{ 1, -1 \}.$
• $B = \{ 1 \}.$
• $C = \{ 1 \}.$
• $D = \{ 2 \}.$
• $E = \{ 1, -17 \}.$
• $F = \{ 1,-17,-8-\sqrt{47},-8+\sqrt{47} \}.$

The relations are:

• $A \subseteq A,$
• $B \subseteq A,$
• $B \subseteq B,$
• $B \subseteq C,$
• $B \subseteq E,$
• $B \subseteq F,$
• $C \subseteq A,$
• $C \subseteq B,$
• $C \subseteq C,$
• $C \subseteq E,$
• $C \subseteq F,$
• $D \subseteq D,$
• $E \subseteq E,$
• $E \subseteq F,$
• $F \subseteq F.$