2
$\begingroup$

I have an exercise in my course, which asks to prove $A \cup B = B \iff A \subseteq B$.

My proof is: Let $A \nsubseteq B$, that is, $\exists a \in A : a \notin B$. Then from the definition follows $a \in A \cup B = B$, in contradiction to the initial assertion. $\square$

Usually I see that it's much more rigorous to prove $\implies$, then $\impliedby$, but I'm not sure, if that's only an option or a strict rule — and specifically if my proof does the job in both directions or there are some gaps that I don't recognize. My script suggests a really long 10+ lines proof using the 'both directions style', but I myself don't really see this necessity at least here.

This being said, is it always a must to prove the 'iff' in both directions?

$\endgroup$
  • 5
    $\begingroup$ You may prove an iff statement by proving each direction individually or in a single step by only using implications which are themselves also biconditional. Your proof however is not formed using biconditional statements and so only succeeds in proving the forward implication. The reverse implication has yet to be proven. $\endgroup$ – JMoravitz Jul 30 '18 at 19:05
  • $\begingroup$ @JMoravitz I think your comment answers what was intended better than the existing answer, so it might be worth posting it (or similar) as an answer. $\endgroup$ – Mark S. Jul 30 '18 at 19:07
  • $\begingroup$ Thanks! So what does exactly fail to show the reverse direction here? I've been thinking of the "then", of course, but this surely can't be only because of the word usage, can it? $\endgroup$ – WTEDST Jul 30 '18 at 19:08
  • $\begingroup$ I'm not sure what what I see here succeeds in proving either direction. As far as I can see it assumes $A\not\subseteq B$ and somehow arrives at a contradiction. If the "somehow" checks out, that would prove $A\subseteq B$ in general, but it doesn't seem to connect it to the other side of the biimplication. $\endgroup$ – hmakholm left over Monica Jul 30 '18 at 19:12
  • 2
    $\begingroup$ @HenningMakholm is succeeds in proving $A\cup B=B\implies A\subseteq B$ via contradition by showing that if $A\not\subseteq B$ while at the same time as tacitly assuming $A\cup B=B$ it follows that there is some $a\in A\setminus B$ which is simultaneously in and not in $B$. $\endgroup$ – JMoravitz Jul 30 '18 at 19:14
3
$\begingroup$

It appears that you're trying (without making it completely clear) to prove $A\cup B=B \Leftrightarrow A\subseteq B$ by showing that $A\cup B=B$ together with $A\not\subseteq B$ leads to a contradiction.

If you think that is a complete proof, how about this one, by the same principle:

Claim: For any integer $n>2$, $$ n\text{ is prime} \iff n\text{ is odd} $$

Proof: Assume that $n$ is prime and that $n$ is not odd. Then $n$ is even, so $n=2k$ for some $k$. But then $2$ divides $n$, which is a contradiction with $n$ being prime, since $n>2$. $\Box$

This seems to follow exactly the same logic as your proof -- namely, considering $P\Leftrightarrow Q$ to be proved because I have shown that $\neg Q$ and $P$ together lead to a contradiction.

But there are odd numbers that are not prime -- such as $9$ -- so the claim is not actually true.

$\endgroup$
  • 1
    $\begingroup$ This is a nice example. $\endgroup$ – Mark Bennet Jul 30 '18 at 19:26
3
$\begingroup$

"iff" means it is true both ways. If you only prove one way, you haven't shown "iff".


You are supposing the right hand side false, and show that if this is so the left-hand side must be false also, giving a contradiction. So if the left-hand side is true, the right-hand side can't be false, so must be true. You have shown the forward implication.

But now you have also to show the reverse implication. Note that with sets, to prove equality you also have to prove two things - so to show $A\cup B=B$ observe that if $a\in B$ then $a\in A\cup B$ by definition of union, whence $B\subseteq A\cup B$

Suppose $A\subseteq B$ and $a\in A$ then $a\in B$ by the definition of a subset. And if $a\in B$ then $a\in B$. Now if $a\in A\cup B$ then in either case $a\in A$ or $a\in B$ then $a\in B$. So $A\cup B\subseteq B$.

Since each side of the proposed equality is contained in the other, they are indeed equal.

I wrote this out in detail because of the hidden two-way implication concealed within $=$.

$\endgroup$
0
$\begingroup$

Left to right. A $\subseteq$ A $\cup$ B = B.
Right to left. A squeeze proof.
B $\subseteq$ A $\cup$ B $\subseteq$ B $\cup$ B = B.

Yes, iff, if and only if, means prove both directions.

$\endgroup$

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.