Disproving Existential

1. Oct 3, 2015

Joseph1739

1. The problem statement, all variables and given/known data
Disprove: There is a positive integer n such that n2+3n+2 is prime.

2. Relevant equations
Disprove existential statements by proving that the negation is true.

3. The attempt at a solution
So my book goes over how to disprove this by proving the negation is true:
For all positive integer n, n2+3n+2 is composite.
n2+3n+2 = (n+1)(n+2) which must be composite, because n>1, so the original statement is false.

Isn't proving that the negation true useless in this situation? Wouldn't proving the original false also be valid? For example:
n2+3n+2 = (n+1)(n+2)
(n+1) and (n+2) will always be greater than 1, so there doesn't exist an integer n such that n2+3n+2 is prime.

2. Oct 3, 2015

Krylov

I think this should be $n \ge 1$.

To answer your question, I don't see what you are doing differently from the book. You both prove that the negation of the original statement is true by showing that $n^2 + 3n + 2$ is composite, thereby proving that the original statement itself is false.

3. Oct 3, 2015

Joseph1739

Sorry, I mean't n≥1.

My book makes it seem like the only way to disprove an existential is to first negate the original statement, then prove the negation is true. I just don't understand the purpose of negating it. Why not just prove the original is false?

4. Oct 3, 2015

vela

Staff Emeritus
Can you give us an example where proving the original statement is false is different than proving the negation is true?

5. Oct 3, 2015

Joseph1739

Sorry if I'm not very clear. I'm certain that proving the negation true is equivalent to proving the original statement false. I guess what I'm confused about is whether proving the original false is a correct way to do a proof. Every time I search for "Disproving an existential statement" I get something along the lines of: To prove an existential statement false, prove that its negation is true, but it just seems proving the negation true is adding an extra useless step. Is there any situation when using the negation is actually beneficial?

6. Oct 3, 2015

vela

Staff Emeritus
By "extra step," do you mean explicitly writing down the negation of the original statement?

7. Oct 3, 2015

Joseph1739

Yes.

(1) There exists a positive integer n, such that n2+3n+2 is prime.
(2) For all positive integers n, n2+3n+2 is composite.

Proving that (1) is false is equivalent to proving that (2) is true. If these will always yield the same answer, what is the point of negating it first? Is there a situation when proving a universal statement is easier than an existential statement?

8. Oct 3, 2015

vela

Staff Emeritus
I suppose, pedagogically, it may be useful to have students first write down the negation explicitly, so they know what they have to show.

Still, when writing a proof, you should explain what you're doing clearly rather than relying on the reader to read your mind. You'll end up essentially writing down the negation if that's the route you're going to take, e.g., we'll show that this statement is false by showing there is no n for which $n^2+3n+2$ is prime.

You can prove a statement is false by assuming it's true and showing that this assumption leads to a contradiction. So, no, you don't always have to use the negation.

9. Oct 3, 2015

Joseph1739

So for the approach I took, was that a proof by contradiction?

10. Oct 3, 2015

Krylov

Also, it may be worthwhile to point out that in order to disprove an existential statement, you need to prove a universal (here: "for all $n$...") statement. However, in order to disprove a universal statement, you need to prove an existential statement, and the latter is typically done by giving an example. Such an example is then often called a counterexample to the original universal statement that you were supposed to disprove.