Tag: Intersection

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

by RoRi

June 22, 2015

Prove that for a class of sets $\mathcal{F}$ we have,

$B \smallsetminus \bigcup_{A \in \mathcal{F}} A = \bigcap_{A \in \mathcal{F}} (B \smallsetminus A) \qquad \text{and} \qquad B \smallsetminus \bigcap_{A \in \mathcal{F}} A = \bigcup_{A \in \mathcal{F}} (B \smallsetminus A).$

Proof. Let $x$ be an arbitrary element of $B \smallsetminus \bigcup_{A \in \mathcal{F}} A$ . This means that $x \in B$ and $x \notin \bigcup_{A \in \mathcal{F}} A$ , which means that $x$ is not in $A$ for any $A$ in the class $\mathcal{F}$ . Hence, for every $A \in \mathcal{F}$ we have $x \in (B \smallsetminus A)$ (since $x$ is in $B$ no matter what, and $x$ is not in $A$ for any $A$ that we choose, so it must be in $B \smallsetminus A$ ). But, $x \in (B \smallsetminus A)$ for all $A \in \mathcal{F}$ means that $x$ is in the intersection $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ ; and hence, $B \smallsetminus \bigcup_{A \in \mathcal{F}} A \subseteq \bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ .
For the reverse inclusion, let $x$ be any element in $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ . This means that $x \in (B \smallsetminus A)$ for every $A \in \mathcal{F}$ , i.e., $x \in B$ and $x \notin A$ for every $A \in \mathcal{F}$ . Since $x \notin A$ for every $A$ , we then have $x \notin \bigcup_{A \in \mathcal{F}}$ . Hence, $x \in B \smallsetminus \bigcup_{A \in \mathcal{F}}$ . Therefore, $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A) \subseteq B \smallsetminus \bigcup_{A \in \mathcal{F}} A$ .
Hence, $B \smallsetminus \bigcup_{A \in \mathcal{F}} A = \bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ . ∎

Proof. Let $x$ be any element of $B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ . This means that $x \in B$ and $x \notin \bigcap_{A \in \mathcal{F}} A$ . Further, $x$ not in the intersection of the sets $A \in \mathcal{F}$ means that there is at least one $A \in \mathcal{F}$ , say $A'$ , such that $x \notin A'$ . Since $x \notin A'$ and $x \in B$ , we know $x \in (B \smallsetminus A')$ . Then we can conclude $x \in \bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ . Thus, $B \smallsetminus \bigcap_{A \in \mathcal{F}} \subseteq \bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ .
For the reverse inclusion, we let $x$ be any element in $\bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ . This means there is at least one $A \in \mathcal{F}$ , say $A'$ , such that $x \in (B \smallsetminus A')$ , which means $x \in B$ and $x \notin A'$ . Since $x \notin A'$ , we know $x \notin \bigcap_{A \in \mathcal{F}} A$ ; therefore, $x \in B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ . Hence, $\bigcup_{A \in \mathcal{F}} (B \smallsetminus A) \subseteq B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ .
Therefore, $B \smallsetminus \bigcap_{A \in \mathcal{F}} A = \bigcup_{A \in \mathcal{F}} (B \smallsetminus A).$ ∎

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

by RoRi

June 22, 2015

Prove that $A \smallsetminus (B \cap C) = (A \smallsetminus B) \cup (A \smallsetminus C)$ .

Proof. First, let $x$ be any element in $A \smallsetminus (B \cap C)$ . By definition of complement, this means that $x \in A$ and $x \notin (B \cap C)$ . Since $x \notin (B \cap C)$ we have either $x \notin B$ or $x \notin C$ which implies, coupled with the fact that $x$ is in $A$ , means $x \in (A \smallsetminus B)$ or $x \in (A \smallsetminus C)$ , respectively. Since $x$ is in at least one of these, $x$ is in the union $(A \smallsetminus B) \cup (A \smallsetminus C)$ . Therefore, $A \smallsetminus (B \cap C) \subseteq (A \smallsetminus B) \cup (A \smallsetminus C)$ .
For the reverse inclusion, let $x$ be an arbitrary element of $(A \smallsetminus B) \cup (A \smallsetminus C)$ . Then, either $x \in (A \smallsetminus B)$ or $x \in (A \smallsetminus C)$ .
If $x \in (A \smallsetminus B)$ , then $x \in A$ and $x \notin B$ ; hence, $x \notin (B \cap C)$ . Therefore, $x$ is in $A \smallsetminus (B \cap C)$ . On the other hand, if $x \in (A \smallsetminus C)$ , then $x \in A$ and $X \notin C$ ; hence, $x \notin (B \cap C)$ . This again implies $x$ is in $A \smallsetminus (B \cap C)$ . Therefore, $(A \smallsetminus B) \cup (A \smallsetminus C) \subseteq A \smallsetminus (B \cap C)$ .
Hence, $A \smallsetminus (B \cap C) = (A \smallsetminus B) \cup (A \smallsetminus C)$ .∎

If C is a subset of A and B, then it is a subset of their intersection

by RoRi

June 20, 2015

Prove that if $C \subseteq A$ and $C \subseteq B$ , then $C \subseteq A \cap B$ .

Proof. Let $x$ be any element in $C$ . Then, $x \in A$ since $C \subseteq A$ , and $x \in B$ since $B \subseteq C$ . Therefore, $x \in A \cap B$ . Hence, $C \subseteq A \cap B$ .∎

Yet more proofs on intersections and unions of sets

by RoRi

June 20, 2015

Prove that $A \cup (A \cap B) = A$ and $A \cap (A \cup B) = A$ .

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

Proof. From Exericse 12 (Section I.2.5) we know that $A \cap C \subseteq A$ for any set $C$ ; hence, $A \cap (A \cup B) \subseteq A$ .
For the reverse inclusion, if $x$ is any element in $A$ , then $x \in A$ and $x \in A \cup B$ ; hence, $x \in A \cap (A \cup B)$ . Therefore, $A \cap (A \cup B) \subseteq A$ .
Hence, $A \cap (A \cup B) = A$ .∎

Union and intersection of a set with the empty set

by RoRi

June 20, 2015

Prove that $A \cup \varnothing = A$ and that $A \cap \varnothing = \varnothing$ .

Proof. If $x \in A \cup \varnothing$ , then $x \in A$ or $x \in \varnothing$ by definition of union. Since $x \notin \varnothing$ (by definition of $\varnothing$ ), we must have $x \in A$ . Hence, $A \cup \varnothing \subseteq A$ .
On the other hand, if $x \in A$ , then $x \in A \cup \varnothing$ by definition of union, so $A \subseteq A \cup \varnothing$ .
Therefore, $A \cup \varnothing = A$ .∎

Proof. If $x \in A \cap \varnothing$ , then by definition of intersection $x \in A$ and $x \in \varnothing$ . But, by definition of $\varnothing$ , there is no $x$ such that $x \in \varnothing$ . Hence, $A \cap \varnothing$ must be empty. By uniqueness of the empty set then, we have $A \cap \varnothing = \varnothing$ .∎

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

by RoRi

June 20, 2015

Prove that $A \cup A = A$ and $A \cap A = A$ .

Proof. Let $x$ be an arbitrary element of $A \cup A$ . Then $x \in A$ or $x \in A$ ; hence, $x \in A$ . Thus, $A \cup A \subseteq A$ .
Conversely, if $x$ is an arbitrary element of $A$ then $x \in A \cup A$ since it is in $A$ . Thus, $A \subseteq A \cup A$ .
Therefore, $A \cup A = A. \qquad \blacksquare$

Proof. Let $x$ be an arbitrary element of $A \cap A$ . Then $x \in A$ and $x \in A$ ; hence, $x \in A$ . So, $A \cap A \subseteq A$ .
Conversely, if $x \in A$ is arbitrary, then $x \in A$ and $x \in A$ ; hence, $x \in A \cap A$ . Thus, $A \cap A \subseteq A$ .
Therefore, $A \cap A = A. \qquad \blacksquare$

Prove distributive laws for unions and intersections of sets

by RoRi

June 20, 2015

Prove that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ .

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

Proof ( $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ). Let $x$ be an arbitrary element of $A \cup (B \cap C)$ . This means $x \in A$ or $x \in (B \cap C)$ . If $x \in A$ then $x \in A \cup B$ and $x \in A \cup C$ . Hence, $x \in (A \cup B) \cap (A \cup C)$ . Otherwise, if $x \in (B \cap C)$ then $x \in B$ and $c \in C$ . Hence, $x \in A \cup B$ and $x \in A \cup C$ ; therefore, $x \in (A \cup B) \cap (A \cup C)$ . Therefore, $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$ .
For the reverse inclusion, let $x$ be an arbitrary element of $(A \cup B) \cap (A \cup C)$ . This means $x \in (A \cup B)$ and $x \in (A \cup C)$ . This implies that $x \in A$ or $x \in B$ and $x \in C$ (since if $x \notin A$ then the fact that $x \in A \cup B$ and $x \in A \cup C$ means $x$ must be in both $B$ and $C$ ). If $x \in A$ , then $x \in A \cup (B \cap C)$ . On the other hand, if $x \in B$ and $x \in C$ , then $x \in B \cap C$ . Hence, $x \in A \cup (B \cap C)$ . Therefore, $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$ .
Therefore, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ .∎

Prove the associative laws for union and intersections of sets

by RoRi

June 19, 2015

Prove that $A \cup (B \cup C) = (A \cup B) \cup C$ and that $A \cap (B \cap C) = (A \cap B) \cap C$ .

Proof (Associativity of unions). First, let $x$ be any element in $A \cup (B \cup C)$ . This means that $x \in A$ or $x \in (B \cup C)$ . If $x \in A$ then $x \in (A \cup B)$ ; hence, $x \in (A \cup B) \cup C$ . On the other hand, if $x \notin A$ , then $x \in (B \cup C)$ . This means $x \in B$ or $x \in C$ . If $x\in B$ , then $x \in (A \cup B) \implies x \in (A \cup B) \cup C$ . If $x \in C$ , then $x \in (A \cup B) \cup C$ . Hence, $A \cup (B \cup C) \subseteq (A \cup B) \cup C$ .
For the reverse inclusion, let $x$ be any element of $(A \cup B) \cup C$ . Then, $x \in (A \cup B)$ or $x \in C$ . If $x \in (A \cup B)$ , we know $x \in A$ or $x \in B$ . If $x \in A$ , then $x \in A \cup (B \cup C)$ . If $x \in B$ , then $x \in (B \cup C)$ ; hence, $x \in A \cup (B \cup C)$ . On the other hand, if $x \in C$ , then $x \in (B \cup C)$ , and so, $x \in A \cup (B \cup C)$ . Therefore, $(A \cup B) \cup C \subseteq A \cup (B \cup C)$ .
Thus, $A \cup (B \cup C) = (A \cup B) \cup C$ .∎

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

Prove the commutative laws of union and intersection

by RoRi

June 19, 2015

Prove $A \cup B = B \cup A$ and $A \cap B = B \cap A$ .

Proof $(A \cup B = B \cup A).$ If $x$ is any element in $A \cup B$ then, by definition of union, we have $x \in A$ or $x \in B$ . But, if $x$ is in $A$ or $B$ , then it is in $B$ or $A$ , and by definition of union, this means $x \in B \cup A$ . Therefore, $A \cup B \subseteq B \cup A$ .
The other inclusion is identical: if $x$ is any element of $B \cup A$ , then we know $x \in B$ or $x \in A$ . But, $x \in B$ or $x \in A$ implies that $x$ is in $A$ or $B$ ; and hence, $x \in A \cup B$ . Therefore, $B\ \cup A \subseteq A \cup B$ .
Hence, $A \cup B = B \cup A$ .∎

Proof $(A \cap B = B \cap A).$ If $x$ is any element in $A \cap B$ , then we know by definition of intersection that $x \in A$ and $x \in B$ . Hence, $x \in B$ and $x \in A$ , and so, $x \in B \cap A$ . Therefore, $A \cap B \subseteq B \cap A$ .
The reverse inclusion is again identical: if $x$ is any element of $B \cap A$ , then we know $x \in B$ and $x \in A$ . Hence, $x \in A$ and $x \in B$ . This implies $x \in A \cap B$ . Hence, $B \cap A \subseteq A \cap B$ .
So, $A \cap B = B \cap A$ .∎