# Discrete math proof-verification of divisibility. Case with both truth and a counterexample

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?

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.”

• "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? – SeesSound Dec 11 '16 at 19:35
• @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. – Matthew Leingang Dec 11 '16 at 21:35
• 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$ – SeesSound Dec 11 '16 at 21:54
• 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? – SeesSound Dec 11 '16 at 21:59
• @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. – Matthew Leingang Dec 12 '16 at 14:28