Thread: 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

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?


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...

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?

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.

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.

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.