Proof methods

• Sep 16th 2011, 07:51 PM
kardash
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?

Kardash
• Sep 16th 2011, 09:22 PM
Prove It
Re: Proof methods
Quote:

Originally Posted by kardash
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?

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...
• Sep 17th 2011, 05:04 AM
emakarov
Re: Proof methods
Quote:

Originally Posted by kardash
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
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.
• Sep 17th 2011, 05:56 AM
HallsofIvy
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.
• Sep 17th 2011, 08:15 AM
emakarov
Re: Proof methods
Quote:

Originally Posted by HallsofIvy
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.