If you need me to expand or write the proof more formally please let me know.

I am confused by the following question, where it seems I have found both a universal value that makes the question true, but then I have also found a counterexample. Where did I go wrong in my proof? Is the statement true or false?

enter image description here


Your negation of the statement is not correct. The original statement is

$$\forall a \ \exists b\ (3 \mid a+b)$$

Its negation is

$$\exists a\ \forall b (3 \not\mid a+b)\tag{1}$$

What you showed is

$$\forall b\ \exists a\ (3 \not\mid a+b)\tag{2}$$

Interchanging those two quantifiers is a big deal. In (2), $a$ can depend on $b$. Indeed, this is what you did to show the statement is true. But in (1), $a$ comes first and $b$ is arbitrary.

Your proof of truth of the original statement is valid. To make it clear that you are using the quantifiers correctly, you should add words to your proof. “Given $a$, let $b=-a$. Then $b+a = 0$, and $3 \mid 0$.” The use of “given” refers to the “for all” quantifier, and the use of “let” refers to “there exists.”

  • $\begingroup$ "Interchanging those two quantifiers is a big deal. In (2), aa can depend on bb. " . But in this case DOES it matter? Because the end of the statement is just an addition statement (a+b), so if you are doing for all A or for all B how does it change anything and why would it matter in this case which quantifier came first?....What I am looking at is the (1-b) that I wrote. Does it not solve your (1), since the A that exists is (1-b) and that (1-b) makes 3 'not divide' A+B for all B? $\endgroup$ – SeesSound Dec 11 '16 at 19:35
  • $\begingroup$ @SajSeesSound: The "end" of the statement matters less than the beginning. Try with these two: "For all $y>0$ there exists an $x>0$ such that $y=x^2$." and "There exists an $x>0$ such that for all $y>0$, $y=x^2$." Only one of those is true. $\endgroup$ – Matthew Leingang Dec 11 '16 at 21:35
  • $\begingroup$ Yeah but those are seperated by an equal sign. If it was x+y, then x+y and y+x are the same thing... Still dont get it... I am trying to use your logic here, but I dont see why (2) is not proving the statement even though it makes sense to write: Given $b$ let $a=1-b$ Then $3 | 1-b+b=1$ $\endgroup$ – SeesSound Dec 11 '16 at 21:54
  • $\begingroup$ I think I may have grasped it. Please let me know if the following is correct. SO in your $(2)$ What I was basically doing was giving a value to $a ->$ $(a=1-b)$ before I stated $for all b$. So the proof I was writing was not working or being written for $a+b$ it was in fact working/being written for $1-b+b$. Is that right? $\endgroup$ – SeesSound Dec 11 '16 at 21:59
  • $\begingroup$ @SajSeesSound When you say "let $a=1-b$", then $a$ depends on $b$. This means $a$ can't come before $b$ as a quantified variable. The fact that the statement starts with $\exists a$ means that $a$ must be a constant. $\endgroup$ – Matthew Leingang Dec 12 '16 at 14:28

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.