I'm self-studying How to Prove It, by Daniel Velleman. The indicated exercise asks us to criticize an incorrect proof of the following incorrect theorem, and to provide a counterexample. I'd like to verify my answer. Thanks in advance for your help.

Incorrect Theorem: Suppose $\mathcal F$ and $\mathcal G$ are families of sets. If $\cup\mathcal F$ and $\cup\mathcal G$ are disjoint, then so are $\mathcal F$ and $\mathcal G$.

The incorrect proof goes like this (paraphrasing): Suppose $\cup\mathcal F$ and $\cup\mathcal G$ are disjoint and suppose $\mathcal F$ and $\mathcal G$ are not. We can choose a set $A$ which belongs to both $\mathcal F$ and $\mathcal G$. Now $A\in \mathcal F$ implies $A\subseteq\cup\mathcal F$ and $A\in \mathcal G$ implies $A\subseteq\cup\mathcal G$. But this contradicts the supposition that $\cup\mathcal F$ and $\cup\mathcal G$ are disjoint. So $\mathcal F$ and $\mathcal G$ must be disjoint. $\square$

The only flaw I can spot is on the sentence "But this contradicts..." because it tacitly supposes that $A\neq \emptyset$. My counterexample is $\mathcal F=\{\emptyset,\{1\}\}$ and $\mathcal G=\{\emptyset,\{2\}\}$, so that: $\mathcal F\cap \mathcal G=\{\emptyset\}$, $\cup\mathcal F=\{1\}$, $\cup\mathcal G=\{2\}$ and $\cup\mathcal F\cap\cup\mathcal G=\emptyset$.

Do you agree or I'm way off mark here?


Yes, I agree. You are entirely right. In fact, you spotted the only problem with that proof. If we add that $\emptyset\notin\mathcal{F}$ or $\emptyset\notin\mathcal{G}$, then the proof will be correct (and the statement will be true then, of course).

  • $\begingroup$ Muito obrigado pela resposta rápida! $\endgroup$ – fameros Jan 8 '18 at 11:52

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.