In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and logic

Logic

In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

, a direct proof is a way of showing the truth

Truth

Truth has a variety of meanings, such as the state of being in accord with fact or reality. It can also mean having fidelity to an original or to a standard or ideal. In a common usage, it also means constancy or sincerity in action or character...

 or falsehood of a given statement by a straightforward combination of established facts, usually existing lemma

Lemma (mathematics)

In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...

s and theorem

Theorem

In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...

s, without making any further assumptions. In order to directly prove a conditional

Material conditional

The material conditional, also known as material implication, is a binary truth function, such that the compound sentence p→q is logically equivalent to the negative compound: not . A material conditional compound itself is often simply called a conditional...

 statement of the form "If p, then q", it suffices to consider the situations in which the statement p is true. Logical deduction is employed to reason from assumptions to conclusion. The type of logic employed is almost invariably first-order logic

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

, employing the quantifiers for all and there exists. Common proof rules used are modus ponens

Modus ponens

In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments...

 and universal instantiation

Universal instantiation

In logic universal instantiation is an inference from a truth about each member of a class of individuals to the truth about a particular individual of that class. It is generally given as a quantification rule for the universal quantifier but it can also be encoded in an axiom...

.

In contrast, an indirect proof may begin with certain hypothetical scenarios and then proceed to eliminate the uncertainties in each of these scenarios until an inescapable conclusion is forced. For example instead of showing directly p ⇒ q, one proves its contrapositive ~q ⇒ ~p (one assumes ~q and shows that it leads to ~p). Since p ⇒ q and ~q ⇒ ~p are equivalent by the principle of transposition

Transposition (logic)

In the methods of deductive reasoning in classical logic, transposition is the rule of inference that permits one to infer from the truth of "A implies B" the truth of "Not-B implies not-A", and conversely. Its symbolic expression is:...

 (see law of excluded middle

Law of excluded middle

In logic, the law of excluded middle is the third of the so-called three classic laws of thought. It states that for any proposition, either that proposition is true, or its negation is....

), p ⇒ q is indirectly proved. Proof methods that are not direct include proof by contradiction. Direct proof methods include proof by exhaustion

Proof by exhaustion

Proof by exhaustion, also known as proof by cases, perfect induction, or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases and each case is checked to see if the proposition in question holds...

, proof by infinite descent, and proof by induction.

Example

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

Even and odd numbers

In mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...

integers is itself an even number.

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