Proof
this wiki
A proof is a mathematical argument used to verify the truth of a statement. This usually takes the form of an orderly series of statements based upon axioms. 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
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:
- is true (or , if zero is included as a natural number)
- For all natural numbers , if is true, then is true.
- Then is true for all natural numbers .
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.
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 n = k − 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).
See also
- Automated theorem proving
- Invalid proof
- Nonconstructive proof
- List of mathematical proofs
- Proof by intimidation
- Proofs wiki
References
- ↑ New Shorter Oxford English Dictionary, 1993, OUP, Oxford.
- ↑ The Emergence of Probability, Ian Hacking
- ↑ The History and Concept of Mathematical Proof, Steven G. Krantz. 1. February 5, 2007
- ↑ Kneale, p. 2
- ↑ Kneale p. 3
- ↑ 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
- ↑ 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.
- ↑ 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 = 1^{3}) 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."
- ↑ O'Connor, John J.; Robertson, Edmund F., "Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji", MacTutor History of Mathematics archive, University of St Andrews, http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Karaji.html.
- ↑ 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."
- ↑ Katz (1998), pp. 255–259.
- ↑ Eder, Michelle (2000), Views of Euclid's Parallel Postulate in Ancient Greece and in Medieval Islam, Rutgers University, http://www.math.rutgers.edu/~cherlin/History/Papers2000/eder.html, retrieved 2008-01-23
Sources
- Polya, G. Mathematics and Plausible Reasoning. Princeton University Press, 1954.
- Fallis, Don (2002) “What Do Mathematicians Want? Probabilistic Proofs and the Epistemic Goals of Mathematicians.” Logique et Analyse 45:373-88.
- Franklin, J. and Daoud, A. Proof in Mathematics: An Introduction. Quakers Hill Press, 1996. ISBN 1-876192-00-3
- Solow, D. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2004. ISBN 0-471-68058-3
- Velleman, D. How to Prove It: A Structured Approach. Cambridge University Press, 2006. ISBN 0-521-67599-5
External links
Look up proof in Wiktionary, the free dictionary. |
- What are mathematical proofs and why they are important?
- 2πix.com: Logic Part of a series of articles covering mathematics and logic.
- How To Write Proofs by Larry W. Cusick
- How to Write a Proof by Leslie Lamport, and the motivation of proposing such a hierarchical proof style.
- Proofs in Mathematics: Simple, Charming and Fallacious
- The Seventeen Provers of the World, ed. by Freek Wiedijk, foreword by Dana S. Scott, Lecture Notes in Computer Science 3600, Springer, 2006, ISBN 3-540-30704-4. Contains formalized versions of the proof that is irrational in several automated proof systems.
- What is Proof? Thoughts on proofs and proving.
- ProofWiki.org An online compendium of mathematical proofs.
- planetmath.org A wiki style encyclopedia of proofs
- A lesson about proofs, in a course from Wikiversity
- The role and function of proof by Michael de Villiers
- Developing understanding of different roles of proof by Michael de Villiers