# Proof by contradiction. Statement negation

This should be an easy question. Yet, the provided solution confuses me.
The question comes from "Understanding analysis" by S. Abbot, 2nd edition (Exercise 1.2.11).

Negate the statement. Make an intuitive guess as to whether the claim or its negation is the true statement.

(b) There exists a real number $$x > 0$$ such that $$x < 1/n\;\;\forall n \in \mathbb{N}$$.

The provided solution says:

The solution seems correct, apart from: shouldn't the negation be with $$\exists n \in \mathbb{N}$$, i.e.: $$\forall x >0 \;\; \exists n \in \mathbb{N}: x \geq 1/n$$ ?

• The statement given is false, so it cannot be proved, not by contradiction nor by any other method. Your negation of the statement is correct, and is therefore a true statement. – Simon Oct 21 '18 at 12:24
• I suspect that you have made a mistake in transcribing the problem from the book, or else that it is a typo in the book. – Simon Oct 21 '18 at 12:26
• The statement has been correctly transcribed from the book. – Sandu Ursu Oct 21 '18 at 12:28
• The solution that you quote is a flawed attempt at a proof of a true statement, that is not the same as the true statement that you correctly give as the negation of the statement given in the question. The flaw in the purported proof is that "for all n" should be "there exists n". – Simon Oct 21 '18 at 12:58
• You are welcome ! The statement given in the question is false, and therefore it implies ANY statement, whether the latter is true or false (implication is false only when the hypothesis is true and the conclusion false). The negation of the statement given in the question is true, and can be used to prove the other true statement (the one in the solution), as follows: By the hypothesis, there exists m in N such that 1/m <= 1/n. Let x=1/(2m). Then x < 1/n. About your last sentence - in general, the contrapositive of a true implication need not be true. I'm not an expert in logic though ! – Simon Oct 21 '18 at 13:28

Regarding Ex.1.2.11 (b) :

Form the logical negation of [...] there exists a real number $$x > 0$$ such that $$x < \dfrac 1 n$$ for all $$n \in \mathbb N$$,

the formula to be negated is :

$$\exists x > 0 \ \forall n \in \mathbb N \ (x < \dfrac 1 n)$$.

Thus, tou are right. The correct negation will be :

$$\forall x > 0 \ \exists n \in \mathbb N \ (x \ge \dfrac 1 n)$$.

But in the solution provided, the author exhibits a proof of the statement; from this, we have to assume that the formula above is not what the author alludes to.

We have instead to transalte the semi-formal statement with :

$$\forall n \in \mathbb N \ \exists x > 0 \ (x < \dfrac 1 n)$$

which is true.

Its negation will then be : $$\exists n \in \mathbb N \ \forall x > 0 \ (x \ge \dfrac 1 n)$$.

• Is this in the 2nd edition of the book? (I've just edited my description to mention that) – Sandu Ursu Oct 21 '18 at 12:34
• Exercise 1.2.11 here – Sandu Ursu Oct 21 '18 at 12:40

This is why putting quantifiers at the end of a formula is a bad practice. It creates ambiguity. The statements

1. $$(\forall n \in \mathbb{N})(\exists x > 0)(x < \frac{1}{n})$$
2. $$(\exists x > 0)(\forall n \in \mathbb{N})(x < \frac{1}{n})$$

are not equivalent. The second one is obviously false, however it's more likely to interpret your formulation as the second statement. Undoubtedly, the first statement is what's actually meant. For proving by contradiction, we need its negation which goes as follows: $$(\exists n \in \mathbb{N})(\forall x > 0)\left(x \ge \frac{1}{n}\right)$$

• The second statement (which is the one from the question) implies the first one (which is the one from the provided solution). – Sandu Ursu Oct 21 '18 at 12:51
• Only because the second statement is false, and a false statement implies any statement. – Simon Oct 21 '18 at 13:34
• If (2) were true it would still imply (1), no? – Sandu Ursu Oct 21 '18 at 13:56
• @SanduUrsu Think of the second statement. Can you really find a real number $x>0$ that is larger than every possible $1/n$? – BioPhysicist Oct 21 '18 at 18:20
• @AaronStevens I suppose you mean lower. (2) is false, yes. But I meant in general, statements of the form $\exists x \;\forall y \;P(x,y)$ imply $\forall y \;\exists x \; P(x,y)$. – Sandu Ursu Oct 21 '18 at 18:25

There exists a real number $$x > 0$$ such that $$x < 1/n\;\;\forall n \in \mathbb{N}$$.

Is this statement really valid? Let's check.

$$nx<1 \;\;\forall n\in\mathbb{N}$$ is valid only for $$x\leq 0$$.

(Because $$n$$ becomes very large, and if $$x\gt 0$$ then $$nx$$ diverges to infinity)

So there is no such $$x$$ exist.

• @AaronStevens yes absolutely. See the last line of my answer. – Avinash N Oct 21 '18 at 17:31
• @AaronStevens is $x$ exist? How long $x$ close to $0$? – Avinash N Oct 21 '18 at 17:39
• You should note that carefully..... We are working on For all n in N – Avinash N Oct 21 '18 at 17:43
• @AaronStevens Here $n$ is not fixed. We are going to find a positive $x$ which is strictly less than $1/n$ for every $n$. – Avinash N Oct 21 '18 at 17:46
• ${1,1/2,1/3,1/4,...}$. What is the infimum of this collection? – Avinash N Oct 21 '18 at 17:49