Tao Analysis I - 3.1.5

Exercise 3.1.5

Let A, B be sets. Show that the three statements $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent (any one of them implies the other two).

Approach

There are three statements we need to show are equivalent. 

• $S_1: A \subseteq B$
• $S_2: A \cup B=B$
• $S_3: A \cap B=A$

To show an equivalence between two statements $S_i \iff S_j$ we need to show $S_i \implies S_j$ and $S_j \implies S_i$. This would suggest showing six implications in total. However, we only need to show the following three implications:

• $S_1 \implies S_2$
• $S_2 \implies S_3$
• $S_3 \implies S_1$

This is equivalent to showing equivalence amongst all $S_1$, $S_2$ and $S_3$, because there is a chain of implications between any $S_i$ and $S_j$, and also $S_j$ and $S_i$. For example $S_1 \implies S_2$ and $S_2 \implies S_3 \implies S_1$.

Show $S_1 \implies S_2$

Using $A \subseteq B$, we need to show both $A \cup B \subseteq B$ and $B \subseteq A \cup B$.

Let's start with the definition of $A \cup B$

$$x \in (A \cup B) \iff (x \in A) \lor (x \in B)$$

By hypothesis we have $A \subseteq B$, which is defined as

$$(A \subseteq B) \implies [(x \in A) \implies (x \in B)]$$

Or more simply, whenever we have $x \in A$, we can substitute $x \in B$.

So, substituting into the definition of union, we have

$$\begin{align}x \in (A \cup B) &\iff (x \in A) \lor (x \in B) \\ \\ &\implies (x \in B) \lor (x \in B) \\ \\ & \implies x \in B \end{align}$$

So $A \cup B \subseteq B$ if we're given $A \subseteq B$.

Now we need to show $B \subseteq A \cup B$. Let's consider

$$(x \in A) \implies (x \in A) \lor (x \in B)$$

This is true by definition of disjunction. In fact $(x \in A) \implies (x \in A) \lor (x \in C)$ for any $C$.

So $B \subseteq A \cup B$. Notice we didn't need to use $A \subseteq B$ here.

We have shown both $A \cup B \subseteq B$ and $B \subseteq A \cup B$, from which we conclude $A \cup B = B$. So $A \subseteq B \implies A \cup B=B$. $\square$

Show $S_2 \implies S_3$

Using $A \cup B=B$, we need to show $A \cap B = A$. To do this we need to show both $A \cap B \subseteq A$ and $A \subseteq A \cap B$.

Let's start with the definition of $A \cap B$.

$$\begin{align}x \in (A \cap B) &\iff (x \in A) \land (x \in B) \\ \\ &\implies (x \in A)\end{align}$$

Thus $A \cap B \subseteq A$.

Now let's show $A \subseteq A \cap B$.

Using the definition of disjunction, we have $A \subseteq A \cup B$. But by hypothesis, $A \cup B=B$, so we have recovered $S_1: A \subseteq B$.

Now let's consider the following which looks obvious,

$$(x \in A) \iff (x \in A) \land (x \in A)$$

Using  $S_1: A \subseteq B$, that is $(x \in A) \implies (x \in B)$, we can substitute $x \in B$ for $x \in A$,

$$(x \in A) \implies (x \in A) \land (x \in B)$$

That is, $A \subseteq A \cap B$.

We have shown both $A \cap B \subseteq A$, and $A \subseteq A \cap B$, from which we conclude $A \cap B = A$. $\square$

Show $S_3 \implies S_1$

Using $A \cap B=A$, we need to show $A \subseteq B$. This is not an equality so we don't need to show $B \subseteq A$, which is, in any case, false.

Using the hypotheses $A = A \cap B$, we immediately have

$$\begin{align}(x \in A) &\implies (x \in A) \land (x \in B) \\ \\ &\implies (x \in B)\end{align}$$

That is $A \subseteq B$. $\square$

Conclusion

We have shown the three implications, 

• $S_1 \implies S_2$
• $S_2 \implies S_3$
• $S_3 \implies S_1$

Thereby we have shown the three statements $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent.