How to do you show the statement is false and prove its negation is true?
$$\forall n \in\mathbb Z^+ \exists a \in\mathbb Z^+ \text{ such that } a|n\text{ and }\frac na\text{ is odd}$$
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ It's true, which will be a problem. $\endgroup$– Chris EagleJan 31, 2013 at 0:14
-
1$\begingroup$ To show a statement being false you need to find an example, it called a counter-example. In this case there is none because you could take $n=a$ when $n/a=1$ an odd number. $\endgroup$– MaesumiJan 31, 2013 at 0:17
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
The statement, as it reads, is true: $\forall n \in \mathbb{Z}^+, \exists a = n \in \mathbb{Z}^+$, such that $a\mid n$, and $\dfrac na = \dfrac nn = 1$ is odd.
IF it is also required that $a \neq n$, then one counterexample suffices to prove the statement is false: for $n = 4$, exists $a=1$ or $a = 2$ or $a = 4$ $\implies \dfrac {n}{a}$ is even. Since $3\not\mid 4,$ and no $a>4$ divides 4.
Hence, the statement, with this modification, is false. And you have thus proved that the negation of the statement is therefore true.
-
$\begingroup$ So to prove it's true we would let a = n? $\endgroup$ Jan 31, 2013 at 0:21
-
$\begingroup$ exactly!! you got it! For every $n$, put $a = n$ $\endgroup$– amWhyJan 31, 2013 at 0:26
-
$\begingroup$ I'd think that the simplest counterexample is $n=1$. :-) $\endgroup$– Asaf Karagila ♦Jan 31, 2013 at 0:26
-
$\begingroup$
$\endgroup$
Hint: Consider the case where $n=a$.
Generally a statement $\forall x\varphi(x)$ is true if and only if for every $u$ in our universe, the formula $\varphi$ is true when we assign $x$ the value $u$. In this case it means that the sentence is true if and only if for every $n\in\mathbb Z^+$ the formula $\exists a(a|n\land 2\nmid\frac na)$ is true.
Similarly a statement $\exists x\varphi(x)$ is true if and only if there exists some $u$ in our universe for which $\varphi$ is true when we assign $x=u$. In the case above it means that there exists some $a\in\mathbb Z^+$ such that $a|n$ and $\frac na$ is odd.
If so the negation of $\forall x\varphi$ would be a counterexample, and the negation of $\exists x\varphi$ would be to show that there is no such example. Combining the two we have that proving something of the form $\forall x\exists y\varphi(x,y)$ is false we need to show that there is some $u$ such that for all $v$, $\varphi(u,v)$ does not hold.
In our case it would mean to show that there is some positive integer that either have no divisors, or that every way we divide the number results in an even integer.
As remarked above this is impossible because the statement is true, simply because $n|n$ and $\frac nn$ is odd. But if we allowed $n=0$ (i.e. $\forall n\in\mathbb N$ instead of $\mathbb Z^+$) it could have served as the proper counterexample. Every way we divide zero we get zero.
answered Jan 31, 2013 at 0:16