Direct proof

From Wikipedia, the free encyclopedia

In mathematics and logic, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems, without making any further assumptions. Logical deduction is employed to reason from assumptions to conclusion. The type of logic employed is almost invariably first order logic, employing the quantifiers for all and there exists. The most common proof rule used is modus ponens, the second most common modus tollens. Transposition and disjunctive syllogism are also very useful.

In contrast, an indirect proof begins with certain hypothetical scenarios and then proceed to eliminate the uncertainties in each of these scenarios until an inescapable conclusion is forced. Instead of showing directly p → q, one proves the logically equivalent transpositive ~q → ~p (one assumes ~q and shows that it leads to ~p). Since p → q and ~q → ~p are equivalent, one has indirectly proved p → q.

In order to directly prove a conditional statement of the form "If p, then q", it is only necessary to consider situations where the statement p is true.

[edit] Example

What follows is a simple, direct proof that the sum of two even integers is always even.

Consider two even integers x and y. Since they are even, they can be written as x = 2a and y = 2b respectively for smaller integers a and b. Then the sum x + y = 2a + 2b = 2(a + b). From this it is clear that 2 is a factor of x + y, so the sum of two even integers is always even.