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.

I am working through a suggested exercise

"If $n$ is an integer, $\frac{n}{n+1}$ is not an integer" - I can prove this is false, and I can prove the converse is false, and I can prove the contrapositive is false.

Now the question asks to show the negation and prove it true or false. Since the original is false by counter example $n=0$, I'm assuming the negation should prove true.

The negation of $p \implies q$ is $p \wedge ¬q$, so the negation in this case should be

"$n$ is an integer and $\frac{n}{n+1}$ is an integer" right?

This can be true ($n=0$) or false ($n=1$). So is the statement true or not? I assume not, so then the original is false AND the negation is false? getting very confused

share|improve this question
5  
The formula "If $n$ is an integer, [then] $n/n+1$ is not an integer" is actually of the form $\forall n\ (p(n) \to q(n))$; its negation is of the form $\exists n\ (p(n) \wedge\neg q(n))$. –  Yury Sep 9 '12 at 14:06
    
@Yury "For all n, if n is an integer, then n/n+1 is an integer" so negation is "There exists an integer n such that n/n+1 is not an integer", which is easily shown with n=1. So the negation is true, and my issue was forgetting quantifiers. Am I following you? Right now I find English slightly easier than the math notation. –  Henry Sep 9 '12 at 14:12
    
You're correct, Henry. We're using quantifiers, here, instead of (rather than in addition to) implications. –  Cameron Buie Sep 9 '12 at 14:53
    
For n = -2, n/n+1 = (-2 / -1) = 1, which is a well-known integer. –  Aric TenEyck Sep 9 '12 at 19:28

3 Answers 3

up vote 11 down vote accepted

The statement

If $n$ is an integer, then $\frac{n}{n+1}$ is not an integer.

is strictly speaking neither true nor false before $n$ is given a concrete value. When you say you proved it to be false, I think what you really proved false is

For all $n$, if $n$ is an integer, then $\frac{n}{n+1}$ is not an integer.

If you want a negation of this that you can prove true, you will have to negate the entire unfolded claim, giving:

There exists an $n$ such that $n$ is an integer and $\frac{n}{n+1}$ is an integer.


Alternatively you can choose to work with statements containing free variables, but then you have to group them into three classes:

A. Those that are always true.

B. Those that are sometimes true and sometimes false.

C. Those that are always false.

Then both of

  • If $n$ is an integer, then $\frac{n}{n+1}$ is not an integer.

  • $n$ is an integer and $\frac{n}{n+1}$ is an integer.

(which are negations of each other) belong in group B. When you proved that the first one "is false", what you really proved was just that it is not in group A.

share|improve this answer
    
Everybody gave me the prod I needed to sort it out, but this is the most complete and illuminating answer. Thanks Henning. –  Henry Sep 9 '12 at 14:15
    
Is there a typo there though? In the statements containing free variables, are those two statements really negations of each other? –  Henry Sep 9 '12 at 14:18
    
@Henry: Oops, there was a "not" missing. Fixed. –  Henning Makholm Sep 9 '12 at 14:21
    
I hereby grant the drive-by downvoter proactive amnesty and pledge that I will not take it personally if he explains what he finds lacking about the answer. –  Henning Makholm Sep 9 '12 at 19:03

Your confusion lies with implicit quantifiers. If you take $P(n)$ to mean $\forall n:P(n)$ then its negation is $\exists n:\lnot P(n)$. You cannot just take the negation under the (implicit) $\forall$ quantifier.

share|improve this answer

Except in the case when $n=0$ the statement is always false.
I suppose the most simple proof is:

If $n>0$, we know the following is true $0 < \frac{n}{n+1} < \frac{n+1}{n+1}=1$. On the other hand the integers are Defined as $\mathbb{Z}=\{0,±1,±2,...\}$ So if the statement were true then $\mathbb{Z} = \{...,-1,0, \frac{n}{n+1}, 1, ...\}$ but this isn't the definition of the integers, therefore $\frac{n}{n+1}$ is not an integer unless $n=0$.

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.