# When would I NOT use a double implication when proving equalities between sets?

I am currently studying how to prove set equalities.

For this, there is an example in my book which goes this way:

Prove the following: $A-(B\cup C) = (A-B)\cap (A-C)$

We need to prove the following two propositions: $$A-(B\cup C)\subseteq (A-B)\cap (A-C)$$ and also $$(A-B)\cap (A-C) \subseteq A-(B\cup C)$$

To do so, we'll do both with one single equivalence: $$a\in A - (B\cup C) \leftrightarrow a \in A \land a \notin (B\cup C)$$ $$\leftrightarrow a \in A \land a \notin B \land a \notin C$$ $$\leftrightarrow (a \in A \land a \notin B) \land (a \in A \land a \notin C)$$ $$\leftrightarrow a \in (A-B) \land a \in (A-C)$$ $$\leftrightarrow a \in (A-B) \cap (A-C)$$

The following example in the book does the same thing (proving both statements with one single equivalence) to prove $\overline{A \cap B} = \overline{A} \cup \overline{B}$

Okay, great. If I ever have to prove this kind of equality, I'll do the same thing (not even sure why). Is there ever a case I need to do both of them separately?

To show that two sets $A$ and $B$ are equal, you need to show that each is a subset of the other; that is, $A\subseteq B$ and $B\subseteq A$. In the examples you have given, it just happens that each of the implications in the steps is bidirectional so that the proof is considerably shortened.

In general, many proofs don't work like this and one has to do them separately. Also, if one is required to prove say $A=B=C$, one way is to do this in a cyclic manner; that is, showing that $A\subseteq B\subseteq C\subseteq A$.

• @Istvan: In more than a handful of places, $\subset$ indicates improper inclusion, much like $\subseteq$ does in other places. Please don't enforce your notational conventions on other posts. A comment about the use of $\subset$ and $\subseteq$ would have sufficed here. – Asaf Karagila May 1 '14 at 15:58
• @AsafKaragila Apologies; I honestly didn't realize that there existed different conventions. Thank you for educating me! – Lily Chung May 1 '14 at 18:19

$\newcommand{\cl}{\operatorname{cl}}$There are simpler examples than the one that I’m about to give, but the ones that I can think of at the moment all require some mathematical background that you may not have.

Say that a set $A\subseteq\Bbb Z^+$ is closed under addition if $a+b\in A$ whenever $a,b\in A$. For $A\subseteq\Bbb N$ define the closure of $A$ to be

$$\cl A=\bigcap\{C\subseteq\Bbb Z^+:A\subseteq C\text{ and }C\text{ is closed under addition}\}\;,$$

the intersection of all supersets of $A$ that are closed under addition.

Now let $A=\{n\in\Bbb Z^+:n\text{ is even}\}$, and show that $A=\cl A$.

Let $\mathscr{C}=\{C\subseteq\Bbb Z^+:A\subseteq C\text{ and }C\text{ is closed under addition}\}$. Clearly $A\in\mathscr{C}$, so $\cl A=\bigcap\mathscr{C}\subseteq A$. On the other hand, $A\subseteq C$ for all $C\in\mathscr{C}$, so $A\subseteq\bigcap\mathscr{C}=\cl A$. Putting the pieces together, we have $A=\cl A$.

I think that you’ll find it hard to come up with a proof that uses a chain of double implications.

Or show that $\cl\{2\}=A$.

Let $\mathscr{C}=\{C\subseteq\Bbb Z^+:2\in C\text{ and }C\text{ is closed under addition}\}$, so that $\cl\{2\}=\bigcap\mathscr{C}$. Clearly $A\in\mathscr{C}$, so $\cl\{2\}\subseteq A$. To show that $A\subseteq\cl\{2\}$, suppose not. Then $A\setminus\cl\{2\}\ne\varnothing$, so let $m=\min(A\setminus\cl\{2\})$. Clearly $m\ne 2$, since $2\in\{2\}\subseteq\cl\{2\}$, so $m\ge 4$, and $m-2\in A$. Moreover, $m$ is the smallest member of $A$ that is not in $\cl\{2\}$, so $m-2\in\cl\{2\}$, and therefore $m-2\in C$ for every $C\in\mathscr{C}$. But we also have $2\in C$ for every $C\in\mathscr{C}$, and each $C\in\mathscr{C}$ is closed under addition, so $2+(m-2)=m\in C$ for every $C\in\mathscr{C}$. But then $m\in\bigcap\mathscr{C}=\cl\{2\}$, contradicting the choice of $m$. This contradiction shows that $A\setminus\cl\{2\}$ must actually be empty, i.e., that $A\subseteq\cl\{2\}$. Putting the pieces together, we have $A=\cl\{2\}$, as desired.

Here it’s even harder to come up with a proof that uses a chain of double implications.

It's surprisingly tough to prove that $\left|\Bbb{Q}\right| = \left|\Bbb{N}\right| (=\aleph_0)$ by exhibiting an explicit bijection between the two. Instead it's much easier to use the fact that $\Bbb{N}\subseteq\Bbb{Q}$ (trivially) and then find a correspondence $\Bbb{Q}\leftrightarrow S\subset\Bbb{N}$ for some set $S$ of natural numbers. For instance, the classic way is to take the 'simplest form' of a fraction $\frac{p}{q}\in\Bbb{Q}$ and map that to the usual number $\frac{(p+q)(p+q+1)}{2}+q$; see http://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function . This approach doesn't provide a direct bijection because, for instance, the number $8 = \langle 1,2\rangle = \frac{(1+2)(1+2+1)}{2}+2$ and the number $25=\langle 2,4\rangle = \frac{(2+4)(2+4+1)}{2}+4$ both correspond to the fraction $\frac{1}{2}$ so a form of the theorem you quote (the so-called Cantor-Bernstein Theorem) is needed to prove that the two sets are actually in bijection.

• This doesn’t really address the OP’s question, since one isn’t trying to prove that $\Bbb Q=\Bbb N$. – Brian M. Scott Dec 4 '12 at 0:27
• @BrianM.Scott Not directly, but I felt that the arguments used were similar enough that seeing a canonical example for Cantor-Bernstein might help with the OP's understanding of why there isn't always an easy equality. – Steven Stadnicki Dec 4 '12 at 0:29
• It still seems to me that it’s a rather different issue at a rather higher level. Note too that the OP did not quote the Schröder-Bernstein theorem. – Brian M. Scott Dec 4 '12 at 0:32