4
$\begingroup$

I need to prove that $$A\subseteq B \implies A\cup B=B$$ I defined the subset relation as the statement $x\in A\Rightarrow x\in B$. I tried to convert the claim into a logic statement, then proceeded to simplify the statement $$(x\in A\Rightarrow x\in B)\Rightarrow(x\in A\vee x\in B),$$ and I simplified it to $x\in A\vee x\in B$. Only after I did this did I realize that this didn't really prove anything.

This fact seems to be taken axiomatically—I haven't been able to find any proofs for it.

I found that it is proposed under Wikipedia's Proposition 8 under ‘Algebra of Sets’ that this is true, and equivalent to the subset relation. A proof of this, however, escapes me.

I also realize that it would be sufficient to be able to convert the antecedent to the consequent or vice versa (which would result in the tautology $p\Rightarrow p$ and thus prove the statement), though I do not know how to do this.

$\endgroup$
3
$\begingroup$

If you really want to do an element-chasing proof, then this is how you might go about it:

Start by supposing that $A\subseteq B$ (i.e., $x\in A\to x\in B$).

Suppose $x\in A\cup B$. Then $x\in A$ or $x\in B$. If $x\in A$, then $x\in B$ because $A\subseteq B$. If $x\in B$, then obviously $x\in B$. In either case, we must conclude $x\in A\cup B\to x\in B$. Thus, $A\cup B\subseteq B$.

Suppose $x\in B$. Then we clearly must have $x\in A\cup B$. That is, $x\in B\to x\in A\cup B$. Thus, $B\subseteq A\cup B$.

By mutual subset inclusion, we have that $A\subseteq B\to A\cup B=B$. $\blacksquare$

$\endgroup$
4
$\begingroup$

Notice that

$$B \subseteq B \implies B \subseteq B \cup A = A \cup B \implies B \subseteq A \cup B$$

and $$ A \subseteq B \implies A \cup B \subseteq B\cup B = B \implies A \cup B \subseteq B $$

$\endgroup$
  • 1
    $\begingroup$ Downvoter, do you mind to explain why? $\endgroup$ – Aaron Maroja Apr 10 '15 at 22:50
1
$\begingroup$

A proof by contradiction.

Given $A \subseteq B $ assume $A \cup B \not= B$. Then there is $x \in A\cup B$ and $x \notin B$ or $x \in B$ and $x \notin A \cup B$. Clearly the later contradicts the definition of set union.

If its the former then $x \in A\cup B \implies x \in A$ since $x \notin B$. But $A \subseteq B \implies x \in B$ which makes the former impossible by contradiction as well.

Since there is no $x$ in $A\cup B$ that is not in $B$ and vice versa we must conclude that $A \cup B = B$.

$\endgroup$
  • 1
    $\begingroup$ I would appreciate hearing about suggestions for improvements to the statement of my proof. Thx. $\endgroup$ – SWilliams Apr 11 '15 at 0:23
  • $\begingroup$ Since you asked for it, usually a proof by contradiction is used when a direct proof is either very difficult or unnatural. Using a proof by contradiction here doesn't seem natural at all. I don't have any quibbles about the actual content of your proof though. $\endgroup$ – Daniel W. Farlow Apr 12 '15 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.