I am working on one of How To Prove It by Velleman's exercise:

"Is the following proof of the theorem correct? Suppose A, B, and C are sets and $A\subseteq B \cup C $. Then either $A\subseteq B$ or $A\subseteq C $.

Proof: Let $x$ be an arbitrary element of $A$. Since $A\subseteq B \cup C$, it follows that either $x \in B$ or $x\in C$.

Case 1. $x\in b$. Since x was an arbitrary element of A, it follows that $\forall x \in A (x\in B)$, which means that $A \subseteq B$.

Case 2. Similar step to case 1.

Thus, either $A \subseteq B$ or $A\subseteq C$."

Apparently it's incorrect, and a counterexample to the theorem is A={1,2}, B={1}, C={2}.

The counter example makes sense, but while I know that one counter example is enough to invalidate this proof, I don't really understand what went wrong in the proof; furthermore even if the proof is wrong I don't know why is the theorem incorrect. I drew up the logical form of this theorem: $$ \forall x((x\in A\to x \in B \lor x\in C) \to (x \in A \to x \in B) \lor (x \in A \to x \in C)) $$ Where the antecedent corresponds to the supposition of the proof as given. I managed to derive a contradiction with an indirect proof. So the only logical conclusion is that either my logical form or indirect proof is wrong (otherwise how could the theorem possibly be incorrect?), but I don't understand how is my logical form wrong either.

Would anyone mind giving me a hand please? Thank you so much!

$--------------------------------------$ Edit:The following is how my indirect proof with the logical form went. $$ \forall x((x\in A\to x \in B \lor x\in C) \to (x \in A \to x \in B) \lor (x \in A \to x \in C)) $$ 1. Let x be an arbitrary element, so that we have $(x\in A\to x \in B \lor x\in C) \to (x \in A \to x \in B) \lor (x \in A \to x \in C)$ to prove.

  1. Assume $(x\in A\to x \in B \lor x\in C)$, and try to prove the consequence of the conditional $(x \in A \to x \in B) \lor (x \in A \to x \in C)$

  2. Indirect proof: so let's assume the negated form of the consequence, which by DeMorgan's law becomes: $\sim(x \in A \to x \in B) \land \sim(x \in A \to x \in C) $

  3. The left side of the conjuction, by negated conditional, becomes $x\in A \land \sim x \in B $. Likewise for the right side, $x\in A \land \sim x \in C $

  4. We isolate $ x\in A$ from either of the conjunctions from 4, and by modus ponens onto the assumption of 2, we get $x \in B \lor x\in C$

  5. We isolate $ \sim x\in B $ and $ \sim x \in C$ from 4, and by disjunctive syllogism onto 5 we get $x \in B$ and $x \in C$ - contradiction.

  • 1
    $\begingroup$ As I said in one of my comments, your logical form is almost correct. It should be $$ (\forall x (x\in A\to x \in B \lor x\in C)) \to (\forall x(x \in A \to x \in B) \lor \forall x(x \in A \to x \in C)) $$ or, in order to make it clearer: $$ (\forall x (x\in A\to x \in B \lor x\in C)) \to (\forall y(y \in A \to y \in B) \lor \forall z(z \in A \to z \in C)) $$ Then I think that your proof doesn't work on this statement, even if it could work on your statement (because it was only almost correct). $\endgroup$ – Watson Feb 21 '16 at 12:16
  • $\begingroup$ Thank you! This question really bugged me big time so I am grateful for your help! $\endgroup$ – Daniel Mak Feb 22 '16 at 14:44

You are right to notice that $$\forall x \in A\quad x \in B \cup C$$ is not the same as $$\forall x \in A\quad x \in B \qquad\text{ or }\qquad \forall x \in A\quad x \in C$$

For instance, you can surely say "all the days, I'm happy or I'm unhappy", but maybe you can't say "all the days, I'm happy, or all the days I'm unhappy". (Take $A=$ set of all the people, $B=$ set of happy people, $C=$ set of unhappy people).

The problem here is that they take $x \in A$, and then sometimes $x \in B$ (case 1), and sometimes $x \in C$ (case 2). These cases depend on $x \in A$. But when you want to prove $A \subset B$, you must show that any $x \in A$ lies in $B$, you can't have $2$ cases depending on $x$.

More precisely, when they say in Case 1 : "$x\in B$. Since $x$ was an arbitrary element of A, it follows that $\forall x \in A (x\in B)$, which means that $A \subseteq B$.", the wrong part is $$"\forall x \in A (x\in B)".$$ To see what this is wrong, consider the statement $$"\forall y \in A (y \in B)"$$

I just changed the $x$ into a $y$. It was confusing before because they used $x$ in the formula "$\forall x \in A (x\in B)$", but we already had a $x \in B$ at the beginning.

Then it is clearer that, just assuming that $x \in B$, won't suffice to prove that $"\forall y \in A (y \in B)"$. Pick $y \in A$. Well, you only know that $y \in B \cup C$. It is not possible to prove that $y \in B$, even if you picked an element $x \in A$ that lies in $B$. This is precisely what happens in the given counterexample.

  • $\begingroup$ Do you mean that, the suppositions of case 1 and 2 are not valid, because the supposition given is that A⊆B∪C, not x∈B or x∈C? Would you mind also commenting on my logical form of the theorem please? This is actually where I am really confused; I am pretty sure my indirect proof is correct, so if there is anything wrong it's likely to be in how I translated the logical form of the theorem, but I don't know where the mistake is. $\endgroup$ – Daniel Mak Feb 21 '16 at 10:59
  • 1
    $\begingroup$ I will edit my answer to explain precisely what is wrong in this 2 cases. Your translation into a logical form is (almost) correct, but this doesn't mean that the theorem itself is correct. The exact formulation should be $$ (\forall x (x\in A\to x \in B \lor x\in C)) \to (\forall x(x \in A \to x \in B) \lor \forall x(x \in A \to x \in C)) $$ For instance, the translation of the (wrong) statement "if $A \subset B$ then $B \subset A$" is $$ \forall x(x\in A \to x \in B) \to \forall x(x \in B \to x \in A) $$ but this doesn't mean that the statement is true. $\endgroup$ – Watson Feb 21 '16 at 11:06
  • $\begingroup$ I am focusing on the logical form because I also did an indirect proof on it myself, and I managed to get a contradiction out of it. If the logical form is correct, then there must be something wrong with my proof - otherwise I just don't see how is the theorem wrong. Let me show it in my edit. $\endgroup$ – Daniel Mak Feb 21 '16 at 11:12

Logically, when we want to prove $A\subset B$, we need to prove that every element of $A$ is in $B$. for this, we choose an arbitrary element of A and fix it. Then we prove that this fixed element is in $B$.

Let $x$ be an arbitrary element of $A$. So hereafter we fix this $x$. Since $A\subseteq B \cup C$, it follows that either $x \in B$ or $x\in C$. It means that the fixed $x$ is in $B$ or in $C$; not every $x$.
In your example the $x$ is $1$ or is $2$. if it is $1$ then it is in $B$ and if it is $2$ then it is in $C$.


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.