Finding flaw in proof

766 Views Asked by At

This is one of the problem I have been working on Velleman's How to prove book:

Incorrect Theorem. Suppose $\mathcal F$ and $\mathcal G$ are families of sets. If $\bigcup\mathcal F$ and $\bigcup\mathcal G$ are disjoint, then so are $\mathcal F$ and $\mathcal G$. $(a)$ What’s wrong with the following proof of the theorem?

Proof. Suppose $\bigcup\mathcal F$ and $\bigcup\mathcal G$ are disjoint. Suppose $\mathcal F$ and $\mathcal G$ are not disjoint. Then we can choose some set $A$ such that $A \in\mathcal F$ and $A \in\mathcal G$. Since $A \in\mathcal F$, by exercise $8$, $A\subseteq\bigcup\mathcal F$, so every element of $A$ is in $\bigcup\mathcal F$. Similarly, since $A \in\mathcal G$, every element of $A$ is in $\bigcup\mathcal G$. But then every element of $A$ is in both $\bigcup\mathcal F$ and $\bigcup\mathcal G$, and this is impossible since $\bigcup\mathcal F$ and $\bigcup\mathcal G$ are disjoint. Thus, we have reached a contradiction, so $\mathcal F$ and $\mathcal G$ must be disjoint.

Even though, I have found an counterexample for the proof ($\mathcal F = \{\{1\},\emptyset\}$ and $\mathcal G=\{\{2\}, \emptyset\}$), I'm not able to find any flaw with this proof (it seems so convincing). Can anybody point me to what I'm missing?

2

There are 2 best solutions below

3
On BEST ANSWER

A good strategy is to to run through the proof with your counter-example. The issue is that while it is also true for $A = \emptyset$ that every element of $A$ is in both $\cup F$ and $\cup G$ this does not contradict the assertion that the sets are disjoint. Only if there is an element in $A$, there is a contradiction.

Note that this also shows the the only set that can be common to both $F$ and $G$ is the empty set.

0
On

Your counterexample reveals a flawed implicit assumption in the proof. The contradiction the proof uses is based the fact that $A\subseteq\cup F$ and $A\subseteq\cup G$. It claims, based on this, that $\cup F$ and $\cup G$ are not disjoint. However, if $A=\emptyset$, then $A\subseteq S$ for any set $S$.