# Proof

1,078pages on
this wiki

A proof is a mathematical argument used to verify the truth of a statement. This usually takes the form of a formal proof, which is an orderly series of statements based upon axioms, theorems, and statements derived using rules of inference. When a statement has been proven true, it is considered to be a theorem.

Proofs generally use an implication as the statement to prove. The goal of a proof is to show that for all values of a given number, object, etc., that if a given condition is met, the conclusion will be true. For example, the implication, "for all natural numbers n, if n is a prime greater than 2, then n is odd" gives the domain of the implication (n is a natural number), a condition or hypothesis (n is a prime greater than 2) and the conclusion (n is odd).

## Methods of proof

There are many ways to go about proving any one statement. However, some statements are more conducive to a particular method.

### Direct proof

A direct proof of an implication proceeds in an orderly fashion from the hypothesis, using logical arguments to get directly from the hypothesis to the conclusion.

Proof by contradiction assumes a true hypothesis and false conclusion and shows how this presents a contradiction.

### Indirect proof

An indirect proof follows the same method as the direct proof, but it uses the contrapositive of the implication (if the conclusion is false, then the hypothesis is false).

### Mathematical induction

Main article: Mathematical induction

Mathematical induction seeks to show by implication that if a value is true for a given natural number, it is true for all natural numbers greater than that number. Induction is generally only applied to the natural numbers. The induction principle proceeds as follows:

Let P be a predicate with the natural numbers as its domain. Suppose that P has these two properties:
• $P(1)$ is true (or $P(0)$, if zero is included as a natural number)
• For all natural numbers $k$, if $P(k)$ is true, then $P(k + 1)$ is true.
Then $P(n)$ is true for all natural numbers $n$.

### Complete induction

Complete induction is similar to mathematical induction, except that the hypothesis of the implication in the second property of implication is not only for P(n), but for all values less than or equal to n.

## Visual proofs

Visual proofs are a proof of a statement that uses diagrams rather than some text. However, they are not as rigorous as a formal proof.

## List of proofs

Please see our list of proofs.

## Etymology

The word Proof comes from the Latin probare meaning "to test". Related modern words are the English "probe", "proboscis”, "probation", and "probability", the Spanish "probar" (to smell or taste, or (lesser use) touch or test),[1] and the German "probieren" (to try). The early use of "probity" was in the presentation of legal evidence. A person of authority, such as a nobleman, was said to have probity, whereby the evidence was by his relative authority, which outweighed empirical testimony.[2]

## History

Plausibility arguments using heuristic devices such as pictures and analogies preceded strict mathematical proof.[3] It is probable that the idea of demonstrating a conclusion first arose in connection with geometry, which originally meant the same as "land measurement".[4] In particular, the ancient Egyptians had empirically discovered some truths of geometry, such as the formula for a truncated pyramid.[5] The Phoenician philosopher Thales (624–546 BCE) proved some theorems in geometry. In the Greek tradition of mathematics, Eudoxus (408–355 BCE) and Theaetetus (417–369 BCE) formulated theorems but did not prove them. Aristotle (384–322 BCE) said definitions should describe the concept being defined in terms of other concepts already known. In Hellenistic Egypt, Euclid (300 BCE) began with undefined terms and axioms (propositions regarding the undefined terms assumed to be self-evidently true, from the Greek “axios” meaning “something worthy”) and used these to prove theorems using deductive logic.

Further advances took place in medieval Islamic mathematics. While earlier Greek proofs were largely geometric demonstrations, the development of arithmetic and algebra by Islamic mathematicians allowed more general proofs that no longer depended on geometry. In the 10th century CE, the Iraqi mathematician Al-Hashimi provided general proofs for numbers (rather than geometric demonstrations) as he considered multiplication, division, etc. for ”lines.” He used this method to provide the first proof for irrational numbers.[6] The earliest inductive proof for arithmetic sequences was introduced in the Al-Fakhri (1000) by Al-Karaji, who used it to prove the binomial theorem, Pascal's triangle, and the sum formula for integral cubes, a particular case of what is referred to as Waring's Problem.[7] His proof was the first to make use of the two basic components of an inductive proof: first, he notes the truth of the statement for n = 1; and secondly, he derives the truth for n = k from that of nk − 1.[8][9] Alhazen (965-1039) used an inductive proof to prove the sum of fourth powers, and by extension, the sum of any integral powers.[10][11] Alhazen also developed the method of proof by contradiction, as the first attempt at proving the Euclidean parallel postulate.[12]

Modern proof theory treats proofs as inductively defined data structures. There is no longer an assumption that axioms are "true" in any sense; this allows for parallel mathematical theories built on alternate sets of axioms (see Axiomatic set theory and Non-Euclidean geometry for examples).

## References

1. New Shorter Oxford English Dictionary, 1993, OUP, Oxford.
2. The Emergence of Probability, Ian Hacking
3. The History and Concept of Mathematical Proof, Steven G. Krantz. 1. February 5, 2007
4. Kneale, p. 2
5. Kneale p. 3
6. Matvievskaya, Galina (1987), "The Theory of Quadratic Irrationals in Medieval Oriental Mathematics", Annals of the New York Academy of Sciences 500: 253–277 [260], doi:10.1111/j.1749-6632.1987.tb37206.x
7. Katz (1998), p. 255:
"Another important idea introduced by al-Karaji and continued by al-Samaw'al and others was that of an inductive argument for dealing with certain arithmetic sequences. Thus al-Karaji used such an argument to prove the result on the sums of integral cubes already known to Aryabhata [...] Al-Karaji did not, however, state a general result for arbitrary n. He stated his theorem for the particular integer 10 [...] His proof, nevertheless, was clearly designed to be extendable to any other integer.
8. Katz (1998), p. 255:
"Al-Karaji's argumen includes in essence the two basic components of a modern argument by induction, namely the truth of the statement for n = 1 (1 = 13) and the deriving of the truth for n = k from that of n = k − 1. Of course, this second component is not explicit since, in some sense, al-Karaji's argument is in reverse; this is, he starts from n = 10 and goes down to 1 rather than proceeding upward. Nevertheless, his argument in al-Fakhri is the earliest extant proof of the sum formula for integral cubes."
9. Victor J. Katz (1995), p. 165–169.
"The central idea in ibn al-Haytham's proof of the sum formulas was the derivation of the equation [...] Naturally, he did not state this result in general form. He only stated it for particular integers, [...] but his proof for each of those k is by induction on n and is immediately generalizable to any value of k."
10. Katz (1998), pp. 255–259.
11. Eder, Michelle (2000), Views of Euclid's Parallel Postulate in Ancient Greece and in Medieval Islam, Rutgers University, retrieved 2008-01-23