1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Disproving Existential

  1. Oct 3, 2015 #1
    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. jcsd
  3. Oct 3, 2015 #2

    Krylov

    User Avatar
    Science Advisor
    Education Advisor

    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.
     
  4. Oct 3, 2015 #3
    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?
     
  5. Oct 3, 2015 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Can you give us an example where proving the original statement is false is different than proving the negation is true?
     
  6. Oct 3, 2015 #5
    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?
     
  7. Oct 3, 2015 #6

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    By "extra step," do you mean explicitly writing down the negation of the original statement?
     
  8. Oct 3, 2015 #7
    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?
     
  9. Oct 3, 2015 #8

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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.
     
  10. Oct 3, 2015 #9
    So for the approach I took, was that a proof by contradiction?
     
  11. Oct 3, 2015 #10

    Krylov

    User Avatar
    Science Advisor
    Education Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Disproving Existential
Loading...