Results 1 to 5 of 5

Math Help - Proof methods

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    7

    Question Proof methods

    Hello

    1. Sometimes to prove a statement false, we negate it and prove the negation is true. Is it also possible to prove a true statement by proving its negation is false with a counter example?

    2. Could you explain proof by reduction?


    Thanks in advance
    Kardash
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,831
    Thanks
    1602

    Re: Proof methods

    Quote Originally Posted by kardash View Post
    Hello

    1. Sometimes to prove a statement false, we negate it and prove the negation is true. Is it also possible to prove a true statement by proving its negation is false with a counter example?

    2. Could you explain proof by reduction?


    Thanks in advance
    Kardash
    1. Yes. But the more common practice is to prove the negation is false by going through a series of logical steps to arrive at a contradiction.

    2. No...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Proof methods

    Quote Originally Posted by kardash View Post
    1. Sometimes to prove a statement false, we negate it and prove the negation is true. Is it also possible to prove a true statement by proving its negation is false with a counter example?
    Quote Originally Posted by Prove It View Post
    1. Yes. But the more common practice is to prove the negation is false by going through a series of logical steps to arrive at a contradiction.
    Yes. A counterexample is given to a statement of the form "For all x, P(x)." If this is a negation, the original statement must be "There exists an x such that not P(x)." A counterexample to "For all x, P(x)" is some x0 such that P(x0) is false. But if you have a counterexample like this, you can prove the original existential statement directly.

    More often, one derives a contradiction from the negation "For all x, P(x)" without exhibiting a counterexample explicitly. Sometimes this counterexample is still hidden in the proof, so it can be extracted and used to prove the original existential statement directly. Other times, extracting a counterexample cannot be done in principle.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,427
    Thanks
    1857

    Re: Proof methods

    No, in general a counterexample to the negation will not prove the statement. Mathematica theorems are typically of the form "for all x, P(x)". You could disprove that by giving a single counter-example, denying the "all x" part. But the negation of that is "for some x, not P(x)". A single counterexample, one value of x such that P(x) is true, does not disprove that.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Proof methods

    Quote Originally Posted by HallsofIvy View Post
    No, in general a counterexample to the negation will not prove the statement. Mathematica theorems are typically of the form "for all x, P(x)".
    We all agree that counterexamples can be given only to universal statements ("for all x, P(x)"). Therefore, I was talking about existential theorems, which have universal negations, and whose negations therefore can be disproved with a counterexample. I agree that theorems are typically universal, but many have the form "for all x there exists an y..." After fixing an x, the existential statement can be proved either by constructing a witness or by contradiction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 2 Methods
    Posted in the Algebra Forum
    Replies: 6
    Last Post: September 16th 2011, 12:58 PM
  2. Numerical Methods
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: September 10th 2010, 09:27 PM
  3. Counting Methods ???
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 10th 2008, 06:55 PM
  4. algebraic methods; please help me!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 25th 2008, 12:48 PM
  5. Calculus proof methods...
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 20th 2008, 02:32 PM

Search Tags


/mathhelpforum @mathhelpforum