Proof

A proof is a logical argument demonstrating that a specific statement, proposition, or mathematical formula is true. It consists of a set of assumptions, or premises, which are combined according to logical rules, to establish a valid conclusion. This validation can be achieved by direct proof that verifies the conclusion is true, or by indirect proof that establishes that it cannot be false.

The term proof is derived from the Latin probare, meaning to test. The Greek philosopher and mathematician Thales is said to have introduced the first proofs into mathematics about 600 B.C. A more complete mathematical system of testing, or proving, the truth of statements was set forth by the Greek mathematician Euclid in his geometry text, Elements, published around 300 B.C. As proposed by Euclid, a proof is a valid argument from true premises to arrive at a conclusion. It consists of a set of assumptions (called axioms) linked by statements of deductive reasoning (known as an argument) to derive the proposition that is being proved (the conclusion). If the initial statement is agreed to be true, the final statement in the proof sequence establishes the truth of the theorem.

Each proof begins with one or more axioms, which are statements that are accepted as facts. Also known as postulates, these facts may be well known mathematical formulae for which proofs have already been established. They are followed by a sequence of true statements known as an argument. The argument is said to be valid if the conclusion is a logical consequence of the conjunction of its statements. If the argument does not support the conclusion, it is said to be a fallacy. These arguments may take several forms. One frequently used form can be generally stated as follows: If a statement of the form "if p then q" is assumed to be true, and if p is known to be true, then q must be true. This form follows the rule of detachment; in logic, it is called affirming the antecedent; and the Latin term modus ponens can also be used. However, just because the conclusion is known to be true does not necessarily mean the argument is valid. For example, a math student may attempt a problem, make mistakes or leave out steps, and still get the right answer. Even though the conclusion is true, the argument may not be valid.

The two fundamental types of proofs are direct and indirect. Direct proofs begin with a basic axiom and reach their conclusion through a sequence of statements (arguments) such that each statement is a logical consequence of the preceding statements. In other words, the conclusion is proved through a step by step process based on a key set of initial statements that are known or assumed to be true. For example, given the true statement that "either John eats a pizza or John gets hungry" and that "John did not get hungry," it may be proved that John ate a pizza. In this example, let p and q denote the propositions:

p: John eats a pizza.

q: John gets hungry.

Using the symbols / for "intersection" and ~ for "not," the premise can be written as follows: p/q: Either John eats a pizza or John gets hungry. and ~q: John did not get hungry. (Where ~q denotes the opposite of q).

One of the fundamental laws of traditional logic, the law of contradiction, tells us that a statement must be true if its opposite is false. In this case, we are given ~q: John did not get hungry. Therefore, its opposite (q: John did get hungry) must be false. But the first axiom tells us that either p or q is true; therefore, if q is false, p must be true: John did eat a pizza.

In contrast, a statement may also be proven indirectly by invalidating its negation. This method is known as indirect proof, or proof by contradiction. This type of proof aims to directly validate a statement; instead, the premise is proven by showing that it cannot be false. Thus, by proving that the statement ~p is false, we indirectly prove that p is true. For example, by invalidating the statement "cats do not meow," we indirectly prove the statement "cats meow." Proof by contradiction is also known as reductio ad absurdum. A famous example of reductio ad absurdum is the proof, attributed to Pythagoras, that the square root of 2 is an irrational number.

Other methods of formal proof include proof by exhaustion (in which the conclusion is established by testing all possible cases). For example, if experience tells us that cats meow, we will conclude that all cats meow. This is an example of inductive inference, whereby a conclusion exceeds the information presented in the premises (we have no way of studying every individual cat). Inductive reasoning is widely used in science. Deductive reasoning, which is prominent in mathematical logic, is concerned with the formal relation between individual statements, and not with their content. In other words, the actual content of a statement is irrelevant. If the statement" if p then q" is true, q would be true if p is true, even if p and q stood for, respectively, "The Moon is a philosopher" and "Triangles never snore."