4

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.

Martin Sleziak
  • 53,687
Conor O'Brien
  • 1,636

3 Answers3

4

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 $$

Aaron Maroja
  • 17,571
3

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$

Daniel W. Farlow
  • 22,531
1

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$.

SWilliams
  • 639
  • 1
    I would appreciate hearing about suggestions for improvements to the statement of my proof. Thx. – SWilliams Apr 11 '15 at 00:23
  • 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. – Daniel W. Farlow Apr 12 '15 at 14:51