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