Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

B A rather simple question

  1. Dec 13, 2017 #1
    Does a proof by counterexample belong to direct or indirect type of proof?
  2. jcsd
  3. Dec 13, 2017 #2
    With an indirect proof, you show that there can be no counter examples.
  4. Dec 13, 2017 #3
    That is what I was thinking. So basically, if we say, for example, show that something doesn't hold universally, our task is to disprove an universal statement, that is to prove the negation of the statement by giving an example. However, this still has some connection to the original statement which says that something holds universally, so I was also thinking that in some way this was indirect. However, if our theorem is (that is, if we look at the negation as the starting statement) to disprove something universal, then we are giving a direct proof by posing an example. It's a little bit confusing. I am still inclining towards the direct whatsoever.
  5. Dec 13, 2017 #4


    User Avatar
    2017 Award

    Staff: Mentor

    Keep in mind that these categories don't have a deeper meaning and the classification is somewhat arbitrary.
    You can always say a proof of X (a direct proof) is showing "(not X) is wrong" and therefore proving X (which would make that an indirect proof) or vice versa.
  6. Dec 13, 2017 #5


    User Avatar
    Science Advisor
    Gold Member

    Something less abstract may help.

    Suppose you're a great mathematician at the end of the 1800s and you show any polynomial with a single variable and real nonnegative coefficients can be written as a sum of squares. You conjecture, what about said polynomial except 2 variables or 3 or ... i.e. is it true that multivariate non-negative polynomial can always be written as a sum of squares?

    Hilbert answered this as definitively "no" in 1888 using a lot of powerful analytical machinery but bit he didn't give an example.

    About 80 years later Motzkin gave the first (very simple) example of a 2 variable non-negative polynomial that can't be written as a sum of squares. (The proof merely needs ##GM \leq AM##.) People would generally say he directly showed the conjecture to be false by a single example, whereas Hilbert's approach was indirect.

    Put differently:
    Hilbert showed that these 'rule breaker' polynomials must exist. (Indirect.)

    Motzkin directly proved they do exist with a simple example. (Direct.)
  7. Dec 14, 2017 #6
    Wow, an excellent answer! Thank you...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted