5
$\begingroup$

I found this phrase in the page 60 of the book "A Transition to Advanced Mathematics, 8th Edition, written by Smith/Eggen/St. Andre."

"Proving that ∼(∃x) P (x), is false is equivalent to proving that (∀x )∼P (x) is true."

It seems incorrect to me, but as I am a student, I guess that I am wrong.

My reasoning is that if we work with the equation of the right side:

(∀x)∼P(x) is true, we can see it as

("(∀x)∼P (x) = true") and this would be equal to

("∼ ((∀x)∼P (x)) = ∼(true)")=

(∃x)P(x) = false.

then (∃x)P(x) is false.

That is the opposite of our goal.

Am I wrong?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ The book is wrong, in fact those two statements are the 'opposite' of each other. $\endgroup$ – Git Gud Jan 31 '15 at 22:52
  • 1
    $\begingroup$ I took the liberty of adding a shot of the relevant excerpt of the book to the question. However this was taken from the seventh edition and might not coincide with what you have (please check it). If the text is the same, then you misinterpreted what was said, the book is not wrong. $\endgroup$ – Git Gud Jan 31 '15 at 23:03
  • 1
    $\begingroup$ @GitGud: $\neg\exists{x}:{P(x)}$ is in fact equivalent to $\forall{x}:\neg{P(x)}$. So the only problem with that statement at the title is the is false, which looks more like a typo. $\endgroup$ – barak manos Jan 31 '15 at 23:06
  • 2
    $\begingroup$ @GitGud I checked the amazon preview of the 8th edition. (amazon.com/Transition-Advanced-Mathematics-Douglas-Smith/dp/…). Sentence appears in the book as in the title of OP. Although the page preview of that page does not work, so I could only see a small excerpt. $\endgroup$ – Loreno Heer Jan 31 '15 at 23:08
  • 2
    $\begingroup$ @sanjab Thanks. WTF is up with the price of that book? What a travesty. $\endgroup$ – Git Gud Jan 31 '15 at 23:11
2
$\begingroup$

See page 56 of seventh edition :

There are times when we will want to prove a quantified statement is false. We know that $(\forall x)P(x)$ is false precisely when $\lnot (\forall x)P(x)$ is true and $\lnot (\forall x)P(x)$ is equivalent to $(\exists x) \lnot P(x)$. Therefore, one way to prove $(\forall x)P(x)$ is false is to prove $(\exists x) \lnot P(x)$ is true.

Thus, if $\lnot (\exists x) P(x)$ is false, its negation : $(\exists x) P(x)$ must be true; but $(\exists x) P(x)$ is equivalent to $\lnot (\forall x) \lnot P(x)$.

In conclusion, you are right; alternatively, we can say that :

Proving that $\lnot (∃x)P(x)$, is false is equivalent to proving that $\lnot (∀x) \lnot P(x)$ is true.

As per comments above, the statement in the 2014 edition must be a typo.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Beginner - see my edied answer; I do not agree ... it must be a typo. $\endgroup$ – Mauro ALLEGRANZA Feb 1 '15 at 21:49
  • $\begingroup$ Thanks, I was crazy trying to understand the phrase! $\endgroup$ – Beginner Feb 2 '15 at 4:18

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.