The statement is: $\forall n \in \mathbb Z^+ \exists a \in \mathbb Z^+$ so that a|n and n/a is even
The statement is false because there is a counterexample n= 1, a=1 correct?
So its negation would be:
$\exists n\in \mathbb Z^+ $~($\exists a \in \mathbb Z^+$so that a|n and n/a is even)
which is: $\exists n\in\mathbb Z^+$ such that $\forall a\in \mathbb Z^+ a \not|n \lor n/a$ is odd.
Is this correct? Now how can I prove the negation is true?

  • $\begingroup$ The counterexample you have in mind should be $n=1$, no mention of $a$. The $a$'s come in when you are doing the (easy!) proof that $n=1$ is a counterexample. $\endgroup$ Jan 31 '13 at 1:37
  • $\begingroup$ I actually answered this in my answer to your previous question. $\endgroup$
    – Asaf Karagila
    Jan 31 '13 at 1:44

Your negated statement is indeed true.

But to disprove a statement, it is enough to show prove by counterexample: the nice one happens to be when $n = 1$: there is no positive integer $a$ such that $a | n$, except for $a = 1$ in which case $1/a = 1/1 = 1\;$ which is odd.

You have to show the non-existence of any $a$ such that ($a \mid n$ and $n/a$ is even). This must fail for all positive integers $a$, not just $1$. It fails for $a=1$, and it fails for all positive integers greater than 1, since no integer $a>1$ divides $1$.

  • $\begingroup$ This proves the original statement is false, but I am actually asked to prove the negation is true which is what i am confused about. How is it possible to prove that for some positive integer n, all positive integers a either don't divide into n or n/a is odd. $\endgroup$
    – user60334
    Jan 31 '13 at 1:52
  • $\begingroup$ You have already proved the negation is true by proving the original statement is false. If p is the original claim, then the negation of p, which you wrote correctly, is $\lnot p$. Since you proved that p is false, it follows that $\lnot p$ must be true. That is also the case with your earlier problem. $\endgroup$
    – amWhy
    Jan 31 '13 at 1:55
  • $\begingroup$ Another correction needed +1 :-) $\endgroup$
    – Amzoti
    May 3 '13 at 2:29
  • $\begingroup$ Thanks, Amzoti...logic questions sometimes get low visibility, especially when "check my work"...Just seems to be the norm... $\endgroup$
    – amWhy
    May 3 '13 at 2:32

This is the correct negation. To show that the negation is true you simply have to provide an example which shows the existence. You did this already $n = 1$. (There are many others though, infinitely many actually since all primes but $2$ are counterexamples)

Note: The counter example doesn't involve taking $a = 1$, you can't pick a specific $a$. What you need to say is the only $a$ which divides $1$ is $1$ and $\frac{1}{1} = 1$ is odd.


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.