Sajun.org
In
mathematics, a '''proof''' is a demonstration that, given certain
axioms, some statement of interest is necessarily true.
Proofs employ
logic but usually include some amount of
natural language which of course admits some ambiguity. In fact, the vast majority of proofs in written mathematics can be considered as applications of
informal logic. In the context of
proof theory, where purely formal proofs are considered, such not entirely formal demonstrations in mathematics are often called "social proofs". The distinction has led to much examination of current and historical
mathematical practice,
quasi-empiricism in mathematics, and so-called
folk mathematics (in both senses of that term). The
philosophy of mathematics is concerned with the role of language and logic in proofs, and
mathematics as a language.
Regardless of one's attitude to formalism, the result that is proved to be true is a
theorem; in a completely formal proof it would be the final line, and the complete proof shows how it follows from the axioms alone. Once a theorem is proved, it can be used as the basis to prove further statements. The so-called
foundations of mathematics are those statements one cannot, or need not, prove. These were once the primary study of philosophers of mathematics. Today focus is more on
practice, i.e. acceptable techniques.
Some common proof techniques are:
* ''
Direct proof'': where the conclusion is established by logically combining the axioms, definitions and earlier theorems
* ''
Proof by induction'': where a ''base case'' is proved, and an ''induction rule'' used to prove an (often
infinite) series of other cases
* ''
Proof by contradiction'' (also known as ''reductio ad absurdum''): where it is shown that if some property were true, a logical contradiction occurs, hence the property must be false.
* ''
Proof by construction'': constructing a concrete example with a property to show that something having that property exists.
* ''
Proof by exhaustion'': where the conclusion is established by dividing it into a finite number of cases and proving each one separately
A ''
probabilistic proof'' should mean a proof in which an example is shown to exist by methods of
probability theory - not an argument that a theorem is 'probably' true. The latter type of reasoning can be called a 'plausibility argument'; in the case of the
Collatz conjecture it is clear how far that is from a genuine proof. Probabilistic proof is one of many ways to show
existence theorems, '''''other than''''' proof by construction.
A ''
combinatorial proof'' establishes the equivalence of different expressions by showing that they count the same object in different ways.
Usually a
one-to-one correspondence is used to show that the two interpretations give the same result.
If we are trying to prove, for example, "Some X satisfies f(X)", an ''existence'' or ''
nonconstructive'' proof will prove that there is a X that satisfies f(X), but does '''not''' tell you how such an X will be obtained. A ''constructive'' proof, conversely, will do so.
A statement which is thought to be true but hasn't been proven yet is known as a
conjecture.
Sometimes it is possible to prove that a certain statement cannot possibly be proven from a given set of axioms; see for instance the
continuum hypothesis. In most axiom systems, there are statements which can neither be proven nor disproven; see
Gödel's incompleteness theorem.
==See also==
*
proof theory
*
model theory
*
automated theorem proving
*
invalid proof
*
nonconstructive proof
*
list of mathematical proofs
*
Q.E.D.
fr:Dmonstration he:הוכחה nl:Wiskundig bewijs pl:Dowód_(matematyka) tr:Matematiksel tanıt
