Home » Union

# Prove relationships between complements, unions and intersections for classes of sets

Prove that for a class of sets we have,

Proof. Let be an arbitrary element of . This means that and , which means that is not in for any in the class . Hence, for every we have (since is in no matter what, and is not in for any that we choose, so it must be in ). But, for all means that is in the intersection ; and hence, .
For the reverse inclusion, let be any element in . This means that for every , i.e., and for every . Since for every , we then have . Hence, . Therefore, .
Hence, . ∎

Proof. Let be any element of . This means that and . Further, not in the intersection of the sets means that there is at least one , say , such that . Since and , we know . Then we can conclude . Thus, .
For the reverse inclusion, we let be any element in . This means there is at least one , say , such that , which means and . Since , we know ; therefore, . Hence, .
Therefore,

# Prove that the complement of an intersection is the union of the complements

Prove that .

Proof. First, let be any element in . By definition of complement, this means that and . Since we have either or which implies, coupled with the fact that is in , means or , respectively. Since is in at least one of these, is in the union . Therefore, .
For the reverse inclusion, let be an arbitrary element of . Then, either or .
If , then and ; hence, . Therefore, is in . On the other hand, if , then and ; hence, . This again implies is in . Therefore, .
Hence, .∎

# Prove that if A and B are subsets of C, then so is their union

Prove that if and , then .

Proof. Let be any element in . Then, by definition of union, we have or . If , then since . On the other hand, if , then as well since . Hence, .∎

# Yet more proofs on intersections and unions of sets

Prove that and .

Proof. First, it is clear that (see Exercise 12 of Section I.2.5, or simply note that implies since is in ).
For the reverse inclusion, if is any element of then or . But implies (and ). So, in either case ; hence, .
Therefore, .∎

Proof. From Exericse 12 (Section I.2.5) we know that for any set ; hence, .
For the reverse inclusion, if is any element in , then and ; hence, . Therefore, .
Hence, .∎

# Union and intersection of a set with the empty set

Prove that and that .

Proof. If , then or by definition of union. Since (by definition of ), we must have . Hence, .
On the other hand, if , then by definition of union, so .
Therefore, .∎

Proof. If , then by definition of intersection and . But, by definition of , there is no such that . Hence, must be empty. By uniqueness of the empty set then, we have .∎

# 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, .∎