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$
14
  • 1
    $\begingroup$ The book is wrong, in fact those two statements are the 'opposite' of each other. $\endgroup$
    – Git Gud
    Jan 31, 2015 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, 2015 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$ Jan 31, 2015 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$ Jan 31, 2015 at 23:08
  • 2
    $\begingroup$ @sanjab Thanks. WTF is up with the price of that book? What a travesty. $\endgroup$
    – Git Gud
    Jan 31, 2015 at 23:11

1 Answer 1

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.

$\endgroup$
2
  • $\begingroup$ @Beginner - see my edied answer; I do not agree ... it must be a typo. $\endgroup$ Feb 1, 2015 at 21:49
  • $\begingroup$ Thanks, I was crazy trying to understand the phrase! $\endgroup$
    – Beginner
    Feb 2, 2015 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.