Let A, B be two sets. Prove that $A \subset B \iff A \cup B = B$
I'm thinking of using disjunctive syllogism by showing that $\neg \forall Y(Y \in A).$ However, I'm not sure how the proving steps should proceed such that it leads me to that premise.
Edit: Thanks for the input. FYI, I need to prove this using predicate logic.
$\endgroup$ 35 Answers
$\begingroup$Taking the "longer" road. Let us review the definitions:
- $A\subseteq B$ if and only if for every $x\in A$, $x\in B$.
- $x\in A\cup B$ if and only if $x\in A$ or $x\in B$.
- $A=B$ if and only if $A\subseteq B$ and $B\subseteq A$.
- $P\iff Q$ means that if we assume that $P$ holds, then $Q$ must hold; and vice versa.
Now assume $A\subseteq B$. This means that for every $x\in A$ we have $x\in B$. We want to show that $A\cup B=B$.
- So we take $x\in B$, then $x\in A$ or $x\in B$, and therefore $x\in A\cup B$.
Now take $x\in A\cup B$, we want to show that $x\in B$. By definition either $x\in A$ or $x\in B$.
- If $x\in B$ we are done.
- If $x\in A$ then by the assumption that $A\subseteq B$ we have that $x\in B$.
Either way we have that $x\in B$.
We have shown that if $A\subseteq B$ then $A\cup B\subseteq B$ and $B\subseteq A\cup B$, which is by fact number $3$ to say $A\cup B=B$.
Now we need to assume that $A\cup B=B$, and deduce that $A\subseteq B$. So we need to show that if $x\in A$ then $x\in B$.
Take $x\in A$ to be an arbitrary element. Because $x\in A$ we have that $x\in A$ or $x\in B$, and therefore $x\in A\cup B$. The assumption was, however, that $A\cup B=B$ and therefore we have that $x\in B$ as wanted.
$\endgroup$ 2 $\begingroup$Let $A\subset B$. Since $B\subset B$, we have $A\cup B\subset B$. Clearly, $B\subset A\cup B$. Hence $A\cup B=B$.
Let $A\not\subset B$. Then there is some $x\in A$ with $x\not\in B$. Clearly, $x\in A\cup B$. Hence $A\cup B\neq B$.
$\endgroup$ 2 $\begingroup$Here are the (very straightforward) first steps you should have thought of beginning with:
In one direction, suppose $A\subseteq B$: then $A\cup B\subseteq B\cup B\dots$
In the other direction, suppose $A\cup B=B$: then $A\subseteq A\cup B\subseteq\dots$
$\endgroup$ $\begingroup$For the first implication a draw can help us:
and now it is obvious.
Now conversely, we have:
$A \cup B =B \Rightarrow$ $A \cup B \subset B \tag{1}$ and $B \subset A \cup B\tag{2}.$ We need only the relation $(1)$ which help us to conclude that: $A \subset B.$
$\endgroup$ $\begingroup$Let $A\subseteq B$.
Claim: We need to prove $A\cup B\subseteq B$ and $B\subseteq A\cup B$
Let $x\in A\cup B$. Then $x\in A$ or $x\in B$. But $A\subseteq B$. Hence $x\in B$. Therefore $A\cup B\subseteq B$.
Now conversely $x\in B$. Then $x\in A\cup B$. Therefore $B\subseteq A\cup B$. Thus $A\cup B=B$.
Consider $A\cup B=B$.
Claim: $A\subseteq B$Let $x\in A$. Then $x\in A\cup B=B$. Therefore $A\subseteq B$.
