Exercises

If $x\in A$ then, by the definition of union, x is also an element of the union of A with any other set, in particular, $x\in A \cup B$. Therefore, by the definition of a subset, $A \subseteq A \cup B$.

First, show that $A \cup \overline{A} \subseteq U$.

This relationship is trivial since every set is a subset of the universal set.

Second, show that $U \subseteq A \cup \overline{A}$.

Let $x\in U$. If x is not in A then it must be in A's complement and is therefore in $A \cup \overline{A}$. On the other hand, if x is not in the complement of A then it must be in A and again must be in $A \cup \overline{A}$. In either case, every element of U must also be in $A \cup \overline{A}$ so $U \subseteq A \cup \overline{A}$.

Since $A \cup \overline{a}$ and $ U$ are each subsets of the other, they must be equal to each other.

Note: Notice that I didn't start off by saying something like, "x must be in either A or its complement." That's actually what we were trying to prove.

First, show that $A \cup \overline{A} \subseteq U$.

This relationship is trivial since every set is a subset of the universal set.

Second, show that $U \subseteq A \cup \overline{A}$.

Let $x\in U$. If x is not in A then it must be in A's complement and is therefore in $A \cup \overline{A}$. On the other hand, if x is not in the complement of A then it must be in A and again must be in $A \cup \overline{A}$. In either case, every element of U must also be in $A \cup \overline{A}$ so $U \subseteq A \cup \overline{A}$.

Since $A \cup \overline{a}$ and $ U$ are each subsets of the other, they must be equal to each other.

Note: Notice that I didn't start off by saying something like, "x must be in either A or its complement." That's actually what we were trying to prove.

This is a true statement. If $x\in A - B$ then, by the definition of "difference", x must be in A but not in B. Because x is in A, by the definition of a subset, $A - B \subseteq A$.

First, show that $\overline{A} \cup \overline{B} \subseteq \overline{A \cap B}$.

Let $x\in\overline{A} \cup \overline{B}$. By the definition of union, we must have either $x\in\overline{A}$ or $x\in\overline{B}$ which means that x is not in at least one of A or B. This means that, $x\notin A \cup B$ so $x\in\overline{A \cup B}$.

Since every x in $\overline{A} \cup \overline{B}$ is also in $\overline{A \cap B}$, we have $\overline{A} \cup \overline{B} \subseteq \overline{A \cap B}$.

Second, show that $\overline{A \cap B} \subseteq \overline{A} \cup \overline{B}$.

If $x\in\overline{A \cap B}$ then x isn't in $A \cap B$ which means it either isn't in A, in which case it is in $\overline{A}$, or it isn't in B, in which case it is in $\overline{B}$. Since x is in at least one of their sets, it must be in their union so $\overline{A \cap B} \subseteq \overline{A} \cup \overline{B}$.

Since $\overline{A} \cup \overline{B}$ and $ \overline{A \cap B}$ is each a subset of the other, they must be equal to each other.

First, show that $\overline{A} \cup \overline{B} \subseteq \overline{A \cap B}$.

Let $x\in\overline{A} \cup \overline{B}$. By the definition of union, we must have either $x\in\overline{A}$ or $x\in\overline{B}$ which means that x is not in at least one of A or B. This means that, $x\notin A \cup B$ so $x\in\overline{A \cup B}$.

Since every x in $\overline{A} \cup \overline{B}$ is also in $\overline{A \cap B}$, we have $\overline{A} \cup \overline{B} \subseteq \overline{A \cap B}$.

Second, show that $\overline{A \cap B} \subseteq \overline{A} \cup \overline{B}$.

If $x\in\overline{A \cap B}$ then x isn't in $A \cap B$ which means it either isn't in A, in which case it is in $\overline{A}$, or it isn't in B, in which case it is in $\overline{B}$. Since x is in at least one of their sets, it must be in their union so $\overline{A \cap B} \subseteq \overline{A} \cup \overline{B}$.

Since $\overline{A} \cup \overline{B}$ and $ \overline{A \cap B}$ is each a subset of the other, they must be equal to each other.

$\overline{A} \cap \overline{B} \subset \overline{A \cup B}$

What does de Morgan's Law say about these sets?

$\overline{A} \cap \overline{B} \subset \overline{A \cup B}$

This is not true. de Morgan's Law, that we discussed in one of the lectures, says that $\overline{A} \cap \overline{B}$ and $\overline{A \cup B}$ are, in fact, equal and one set can't be both equal to another and a proper subset of it.

$A \cap \overline{A} = \emptyset$

You need to show that $A \cap \overline{A}$ has no elements. Try doing this by contradiction.

$A \cap \overline{A} = \emptyset$

We need to show that the set $A \cap \overline{A}$ has no elements in it. Assume that it does. By the definition of intersection, that element must be in both A and $\overline{A}$. But this means that the element must be in both A and the set of all elements that aren't in A. There is no such element which is a contradcition so there is no such element which means $A \cap \overline{A}$ has no elements in it. Since the empty set is the only set with no elements, this means $A \cap \overline{A} = \emptyset$.

If $A\subseteq B$ then $A \cup \overline{B} = \emptyset$.

This isn't true. If $x\in A$ then x is in the union of A with any other set including $\overline{B}$. If $A \cup \overline{B}$ has elements in it then it can't be the empty set.

If $A \subseteq B$ then $A \cap \overline{B} = \emptyset$.

We need to show that $A\cap \overline{B}$ has no elements.

Let $x\in A$. Since A is a subset of B that means that x must also be in B which also means that it isn't in $\overline{B}$.

Since every element of $A$ isn't in $\overline{B}$, their intersection has no elements which means it's equal to the empty set.

If $A \subseteq B$ then $A \cap \overline{B} = \emptyset$.

We need to show that $A\cap \overline{B}$ has no elements.

Let $x\in A$. Since A is a subset of B that means that x must also be in B which also means that it isn't in $\overline{B}$.

Since every element of $A$ isn't in $\overline{B}$, their intersection has no elements which means it's equal to the empty set.

First, we need to show that $\bigcup \limits_{i=1}^n (A_i - B) \subseteq \left(\bigcup \limits_{i=1}^n A_i\right) - B$

Let $x\in\bigcup \limits_{i=1}^n (A_i - B)$. Then, by the definition of union, there exists an i such that $x\in (A_i-B)$. Since x is in at least one of the $A_i$ it must be in their union so $x\in\bigcup \limits_{i=1}^n A_i$. However, we also know that that particular $x$ is not in $B$ so $x\in\left(\bigcup \limits_{i=1}^n A_i\right) - B$.

Second, we need to show that $\left(\bigcup \limits_{i=1}^n A_i\right) - B \subseteq \bigcup \limits_{i=1}^n (A_i - B)$

Let $x\in \left(\bigcup \limits_{i=1}^n A_i\right) - B$. This means that $x\in \left(\bigcup \limits_{i=1}^n A_i\right)$ but $x\notin B$. Since $x$ is in that union, there must exist an $i$ such that $x\in A_i$ which means that, for that $i$, $x\in(A_i-B)$. Finally, by the definition of union, $x\in \bigcup \limits_{i=1}^n (A_i - B)$.

Since, every $x$ in $\left(\bigcup \limits_{i=1}^n A_i\right) - B$ is also in $ \bigcup \limits_{i=1}^n (A_i - B)$ we must have $\left(\bigcup \limits_{i=1}^n A_i\right) - B \subseteq \bigcup \limits_{i=1}^n (A_i - B)$.

Finally, since each of the sets $\left(\bigcup \limits_{i=1}^n A_i\right) - B$ and $\bigcup \limits_{i=1}^n (A_i - B)$ is a subset of the other, they must be equal.

Show that $A - B$, $B - A$ and $A \cap B$ is a partition of $A \cup B$.

You need to show two things here: first, that the union of the three sets is $A \cup B$ and, second, that they are mutually disjoint.

Show that $A - B$, $B - A$ and $A \cap B$ is a partition of $A \cup B$.

First, we need to show that the sets are mutually disjoint.

If $x\in A - B$ then $x$ isn't in $B$ so it can't be in $B - A$ or $A \cap B$.

If $x\in B - A$ then $x$ isn't in $A$ so it can't be in $A - B$ or $A \cap B$.

If $x\in A \cap B$ then $x$ is in both $A$ and $B$ so it can't be in $A - B$ since that set contains no elements of $B$ and it can be in $B - A$ since that set contains no elements of $A|$.

Second, we need to show that $(A - B)\cup (B-A) \cup (A\cap B) = A \cup B$.

If $x\in A \cup B$ then there are three posibilities:

2. $x\in B$ but $x otin A$ in which case $x\in B - A$.

3. $x\in A$ abd $x\in B$ in which case $x\in A \cap B$.

Since $x$ is in at least one of those sets, it must be in their union so $A \cup B\ \subseteq (A - B)\cup (B-A) \cup (A\cap B)$.

If $x\in (A - B) \cup (B-A) \cup (A\cap B)$ then if $x$ is $A-B$ then it's in $A$. If it's in $B-A$ then it's in $B$ and if it's in $A\cap B$ then it's in both $A$ and $B$. In any of those cases, it's in at least one of $A$ and $B$ so it's also in their union which gives us $(A - B)\cup (B-A) \cup (A\cap B) \subseteq A \cup B$

Since each of the two sets is a subset of the other, they must be equal.

Since the sets $A - B$, $B - A$ and $A \cap B$ are mutually disjoint and their union equals $A\cup B$ they represent a partition of $A\cup B$.