# Cannot find a mistake in an incorrect proof.

I am reading an introductory book on proof-writing techniques. One of the exercises asks to demonstrate why the proof is incorrect. I spent quite a while thinking about it and still feel puzzled.

$\textbf{Incorrect theorem:}$ Suppose $F$ and $G$ are families of sets. If $\cup F$ and $\cup G$ are disjoint, then so are $F$ and $G$.

$\textbf{Proof:}$ (by contradiction) Suppose $\cup F$ and $\cup G$ are disjoint. Suppose $F$ and $G$ are not disjoint. Then we can choose some set $A$ such that $A \in F$ and $A \in G$. Since $A \in F$, then $A \subset \cup F$ (this result is true and was proven by me before as an exercise, so I just use it here). Similarly, since $A \in G$, every element of $A$ is in $\cup G$. But then every element of $A$ is in both $\cup F$ and $\cup G$, and this is impossible since $\cup F$ and $\cup G$ are disjoint. Thus, we have reached a contradiction, so $F$ and $G$ must be disjoint. QED.

$\textbf{Note:}$ So far I have been able to come up with the following counterexample. Consider $F = \left\lbrace \emptyset, \left\lbrace 1 \right\rbrace, \left\lbrace 2 \right\rbrace, \left\lbrace 3 \right\rbrace \right\rbrace$ and $G = \left\lbrace \emptyset, \left\lbrace 4 \right\rbrace, \left\lbrace 5 \right\rbrace, \left\lbrace 6 \right\rbrace \right\rbrace$. Then $\cup F = \left\lbrace 1,2,3 \right\rbrace$ and $\cup G = \left\lbrace 4,5,6 \right\rbrace$. We see from here that $\cup F \cap \cup G = \emptyset$ but $F \cap G = \left\lbrace \emptyset \right\rbrace$ which clearly demonstrates that the fore mentioned theorem is not correct. So the proof must be erroneous as well.

But still, I cannot understand from here why the proof of the theorem is not valid. Everything seems fine to me, so it is clear that I am missing something.

If we look at the proof and choose $A = \emptyset$ then the statement in the end of the theorem states that every element of $A$ is in both $\cup F$ and $\cup G$. But since $A$ has no elements, then the statement $\forall x (x \in A \rightarrow (x \in \cup F \wedge x \in \cup G))$ is true, isn't it?

-

You're almost there.

But then every element of $A$ is in both $\bigcup F$ and $\bigcup G$

is a correct conclusion from the premises, but is no contradiction; it just shows that $A=\emptyset$, because no element can belong to it.

The correct version of the theorem is

Let $F$ and $G$ be families of set such that $\bigcup F$ and $\bigcup G$ are disjoint. Then either $F$ and $G$ are disjoint or $F\cap G=\{\emptyset\}$.

-
Shouldn't that last expression be $F\cap G = \{\emptyset\}$? We already know that $\bigcup F$ and $\bigcup G$ are disjoint, and so $(\bigcup F)\cap(\bigcup G)$ must be $\emptyset$. –  jwodder Sep 5 '14 at 16:41
@jwodder You're right, fixed. –  egreg Sep 5 '14 at 17:36
At the risk of loosing some readability, the final conclusion could be written "Then $F\cap G\subseteq\{\emptyset\}$". –  Marc van Leeuwen Sep 5 '14 at 17:39
@MarcvanLeeuwen In a Bourbaki-style book it would be so written, not in mine. ;-) –  egreg Sep 5 '14 at 17:46
@egreg: Yeah, that why I said "could" rather than "should". –  Marc van Leeuwen Sep 5 '14 at 17:54