[x] Close ad

MATHEMATICAL PROOF

In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true.

A proof is a logical argument, not an empirical one. That is, one must demonstrate that a proposition is true in all cases before it is considered a theorem of mathematics. An unproven proposition for which there is some sort of empirical evidence is known as a conjecture.

In virtually all branches of mathematics, the assumed axioms are ZFC, unless indicated otherwise. ZFC formalizes mathematical intuition about set theory, and set theory suffices to describe contemporary algebra and analysis.

Proofs employ logic but usually include some amount of natural language which usually admits some ambiguity. In fact, the vast majority of proofs in written mathematics can be considered as applications of informal logic. Purely formal proofs are considered in proof theory. The distinction between formal and informal proofs 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 statement were false, a logical contradiction occurs, hence the statement must be true.
  • Proof by construction: (also known as proof by example) 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.

An existence or nonconstructive proof is one that establishes that a certain mathematical object must exist (e.g. "Some X satisfies f(X)"), without explaining how such an object can be found. Often, this takes the form of a proof by contradiction in which the nonexistence of the object is proven to be impossible. In contrast, a constructive proof establishes that a particular object exists by providing a method of finding it.

There is a class of mathematical formulae for which neither a proof nor disproof exists, using only the standard ZFC axioms. This result is known as Gödel's (first) incompleteness theorem and examples include the continuum hypothesis. Whether a particular unproven proposition can be proved using a standard set of axioms is not always obvious, and can be extremely technical to determine.

End of a proof

Main article: Q.E.D.

Sometimes, the abbreviation "Q.E.D." is written to indicate the end of a proof. This abbreviation stands for "Quod Erat Demonstrandum", which is Latin for "that which was to be demonstrated". An alternative is to use a small rectangle with its shorter side horizontal (∎), known as a tombstone.

See also

External links