Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$$

share|improve this question
5  
It's true, which will be a problem. –  Chris Eagle Jan 31 '13 at 0:14
1  
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. –  Maesumi Jan 31 '13 at 0:17

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
So to prove it's true we would let a = n? –  user60334 Jan 31 '13 at 0:21
    
exactly!! you got it! For every $n$, put $a = n$ –  amWhy Jan 31 '13 at 0:26
    
I'd think that the simplest counterexample is $n=1$. :-) –  Asaf Karagila Jan 31 '13 at 0:26
    
I agree with @Asaf. –  Babak S. Jan 31 '13 at 6:53

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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