This question is from Tao's Analysis I and has got me stumped for a while. Even though, it's intuitive that the three statements are equivalent, when it came to writing a rigorous proof using mathematical logic, I flunked. Could please help me verify my proof?
Let $A$, $B$ be sets. Show that the three statements $A\subseteq B$, $A \cup B=B$ and $A \cap B = A$ are logically equivalent.
Proof. (My informal attempt).
(a) $1 \iff 2.$
We are given that $A \subseteq B$. We are interested to show that $A \cup B = B$.
($\Rightarrow$ direction)
Let $x$ be an arbitrary element of $A \cup B$. Then, atleast of the possibilities $x \in A$ or $x \in B$ hold. If $x \in A$, then $x \in B$, since $A \subseteq B$. If $x \in B$, then we are done. In both possibilities, $x$ belongs to $B$. So, $(A \cup B) \subseteq B$.
($\Leftarrow$ direction)
The converse is also true, since for any set $A$, we have $B \subseteq (B \cup A)$.
$\therefore$ $A \cup B = B.$
(b) $2 \iff 3.$
We are given that $A \cup B = B$. This means that $A \subseteq B$. We are interested to show that $A \cap B = A$.
($\Rightarrow$ direction)
Let $x$ be an arbitrary element in $A \cap B$. Then, both the propositions $x \in A$ and $x in B$ are true. Since, $A \subseteq B$, $x \notin (B\setminus A)$. For if $x \in (B \setminus A)$, then $x \in B$, but $x \notin A$, so $x\notin A \cup B$. Thus, $x \in A$. So, $(A \cap B) \subseteq A$.
($\Leftarrow$ direction)
The set $A \cap B := \{x:(x \in A)\land(x \in B)\}.$
If $x \in A$, then both the propositions $(x \in A)$ and $(x \in B)$ hold, since additionally $(x \in A) \implies (x \in B)$ when $A$ is a subset of $B$. So, $A \subseteq (A \cap B).$
$\therefore$ $A \cap B = A$.
(c) $3 \iff 1.$
I am not exactly sure how to proceed, so any hint would help. I was wondering if assuming a that $A$ contains elements which are not in $B$ leads me to a contradiction.
Best Answer
1 implies 2: Assume 1. To show that $A \cup B \subseteq B$, let $x \in A \cup B$. If $x \in B$ we're done. If $x \in A$ then $x \in B$ by 1. So always $x \in B$ and 2. has been shown, as the other inclusion $B \subseteq A \cup B$ is trivial.
2 implies 3: Assume 2. To see 3. we only need to show $A \subseteq A \cap B$, as the other inclusion is again trivial. So let $x \in A$. This means $x \in A \cup B=B$ by 2, so $x \in B$ too and $x \in A \cap B$.
3 implies 1: Assume 3. Let $x \in A$. Then by 3. $x \in A \cap B$ so $x \in B$ in particular. This shows 1.
Going in circles for such equivalences is more efficient.