0
$\begingroup$

This question already has an answer here:

I am working through Velleman's How To Prove It on my own and I am having trouble figuring out exactly why this proof is incorrect in a formal manner:

I have this intuitive feeling that makes sense to me that it should NOT follow that $\forall x\in A(x \in B)$ since you can't ensure that all elements of $A$ are also in $B$. I can even come up with a simple counterexample. But I don't know which formal step taken in the proof is incorrect.

Following Velleman's methods, if I have the goals $\forall x \in A(x \in B)$ or $\forall x \in A(x \in C)$, I can assume that $x$ is an arbitrary element of $A$. Then all I need to prove are the goals $x \in B$ or $x \in C$. I believe everything is correct up to this point.

Then the proof deduces from $A \subseteq B\space\cup C$ that $x \in B$ or $x \in C$. Assuming either one of them proves one of the goals true and the theorem is proven. I know one of these steps in here is incorrect but I was wondering of someone can point me to what exactly went wrong.

Thanks!

$\endgroup$

marked as duplicate by Community Jul 3 '17 at 2:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ For a counterexample, let $B=\{1\}$, $C=\{2\}$, $A =\,??$. $\endgroup$ – quasi Jul 3 '17 at 2:20
  • $\begingroup$ I know that A={1,2} is a counterexample but I am wondering where in the proof the incorrect step lies. $\endgroup$ – Vasting Jul 3 '17 at 2:21
  • $\begingroup$ Follow the counterexample to the logical error. $\endgroup$ – quasi Jul 3 '17 at 2:21
  • 3
    $\begingroup$ When the proof said, suppose $x \in B$, $x$ is no longer an arbitrary element of $A$. $\endgroup$ – quasi Jul 3 '17 at 2:24
  • $\begingroup$ A={1,2,3,4},B={2,4},C={1,3}. Go through the proof. Pick an arbitrary x. Okay 2. 3 is either in B or C. Yep, it's in B. Since x was arbitrary it follows that all x are in B. No it doesn't! Being in B is a specific event that needn't happen. Once we declare something specific about x we can't claim x was arbitrary after all. $\endgroup$ – fleablood Jul 3 '17 at 6:53
4
$\begingroup$

As @quasi states, you should first try to find a counterexample if you think it's false, and you mention that yourself.

I don't fully know what Vellerman's methods are, but your ability to make generalizations goes away once you start making conditions in your proof. The error in this proof is that you are NOT allowed to say "Since $x$ was an arbitrary element . . ." in the sub-clause of the proof.

To put it a little more formally, if $P$ and $Q$ are conditions on $x$, then you are leveraging the false statement $\forall x (P(X) \vee Q(x)) \to (\forall x P(x)) \vee (\forall x Q(x))$ in your proof.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.