Editing Mathematical proof (section)

=={{Anchor|Types of proof}}Methods of proof==

===Direct proof===
{{Main|Direct proof}}

In direct proof, the conclusion is established by logically combining the axioms, definitions, and earlier theorems.<ref>Cupillari, p. 20.</ref> For example, direct proof can be used to prove that the sum of two [[parity (mathematics)|even]] [[integer]]s is always even:

:Consider two even integers ''x'' and ''y''. Since they are even, they can be written as ''x''&nbsp;=&nbsp;2''a'' and ''y''&nbsp;=&nbsp;2''b'', respectively, for some integers ''a'' and ''b''. Then the sum is ''x''&nbsp;+&nbsp;''y''&nbsp;= 2''a''&nbsp;+&nbsp;2''b''&nbsp;= 2(''a''+''b''). Therefore ''x''+''y'' has 2 as a [[divisor|factor]] and, by definition, is even. Hence, the sum of any two even integers is even.

This proof uses the definition of even integers, the integer properties of [[Closure (mathematics)|closure]] under addition and multiplication, and the [[distributive property]].

===Proof by mathematical induction===
{{Main|Mathematical induction}}
Despite its name, mathematical induction is a method of [[Deductive reasoning|deduction]], not a form of [[inductive reasoning]]. In proof by mathematical induction, a single "base case" is proved, and an "induction rule" is proved that establishes that any arbitrary case [[Material conditional|implies]] the next case. Since in principle the induction rule can be applied repeatedly (starting from the proved base case), it follows that all (usually [[Infinite set|infinitely]] many) cases are provable.<ref>Cupillari, p. 46.</ref> This avoids having to prove each case individually. A variant of mathematical induction is [[proof by infinite descent]], which can be used, for example, to prove the [[Square root of 2#Proofs of irrationality|irrationality of the square root of two]].

A common application of proof by mathematical induction is to prove that a property known to hold for one number holds for all [[natural number]]s:<ref>[http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html Examples of simple proofs by mathematical induction for all natural numbers]</ref>
Let {{math|1='''N''' = {1, 2, 3, 4, ...}}} be the set of natural numbers, and let {{math|''P''(''n'')}} be a mathematical statement involving the natural number {{math|''n''}} belonging to {{math|'''N'''}} such that
* '''(i)''' {{math|''P''(1)}} is true, i.e., {{math|''P''(''n'')}} is true for {{math|1=''n'' = 1}}.
* '''(ii)''' {{math|''P''(''n''+1)}} is true whenever {{math|''P''(''n'')}} is true, i.e., {{math|''P''(''n'')}} is true implies that {{math|''P''(''n''+1)}} is true.
* '''Then {{math|''P''(''n'')}} is true for all natural numbers {{math|''n''}}.'''

For example, we can prove by induction that all positive integers of the form {{math|2''n''&nbsp;−&nbsp;1}} are [[parity (mathematics)|odd]].  Let {{math|''P''(''n'')}} represent "{{math|2''n''&nbsp;−&nbsp;1}} is odd":
:'''(i)''' For {{math|1=''n'' = 1}}, {{math|1=2''n''&nbsp;−&nbsp;1&nbsp;=&nbsp;2(1)&nbsp;−&nbsp;1&nbsp;=&nbsp;1}}, and {{math|1}} is odd, since it leaves a remainder of {{math|1}} when divided by {{math|2}}. Thus {{math|''P''(1)}} is true.
:'''(ii)''' For any {{math|''n''}}, if {{math|2''n''&nbsp;−&nbsp;1}} is odd ({{math|''P''(''n'')}}), then {{math|(2''n''&nbsp;−&nbsp;1)&nbsp;+&nbsp;2}} must also be odd, because adding {{math|2}} to an odd number results in an odd number.  But {{math|1=(2''n''&nbsp;−&nbsp;1)&nbsp;+&nbsp;2&nbsp;=&nbsp;2''n''&nbsp;+&nbsp;1&nbsp;=&nbsp;2(''n''+1)&nbsp;−&nbsp;1}}, so {{math|1=2(''n''+1)&nbsp;−&nbsp;1}} is odd ({{math|''P''(''n''+1)}}).  So {{math|''P''(''n'')}} implies {{math|''P''(''n''+1)}}.
:'''Thus''' {{math|2''n''&nbsp;−&nbsp;1}} is odd, for all positive integers {{math|''n''}}.

The shorter phrase "proof by induction" is often used instead of "proof by mathematical induction".<ref>[http://www.warwick.ac.uk/AEAhelp/glossary/glossaryParser.php?glossaryFile=Proof%20by%20induction.htm Proof by induction] {{Webarchive|url=https://web.archive.org/web/20120218033011/http://www.warwick.ac.uk/AEAhelp/glossary/glossaryParser.php?glossaryFile=Proof%20by%20induction.htm |date=February 18, 2012 }}, University of Warwick Glossary of Mathematical Terminology</ref>

===Proof by contraposition===
{{Main|Contraposition}}
[[Proof by contrapositive|Proof by contraposition]] [[Rule of inference|infers]] the statement "if ''p'' then ''q''" by establishing the [[logically equivalent]] [[contrapositive|contrapositive statement]]: "if ''not q'' then ''not p''".

For example, contraposition can be used to establish that, given an integer <math>x</math>, if <math> x^2 </math> is even, then <math>x</math> is even:

: Suppose <math>x</math> is not even. Then <math>x</math> is odd. The product of two odd numbers is odd, hence <math> x^2  = x\cdot x </math> is odd. Thus <math> x^2 </math> is not even. Thus, if <math> x^2 </math> ''is'' even, the supposition must be false, so <math> x </math> has to be even.

===Proof by contradiction===
{{Main|Proof by contradiction}}
In proof by contradiction, also known by the Latin phrase ''[[reductio ad absurdum]]'' (by reduction to the absurd), it is shown that if some statement is assumed true, a [[contradiction|logical contradiction]] occurs, hence the statement must be false.  A famous example involves the proof that <math>\sqrt{2}</math> is an [[irrational number]]:

:Suppose that <math>\sqrt{2}</math> were a rational number. Then it could be written in lowest terms as <math>\sqrt{2} = {a\over b}</math> where ''a'' and ''b'' are non-zero integers with [[coprime|no common factor]]. Thus, <math>b\sqrt{2} = a</math>. Squaring both sides yields 2''b''<sup>2</sup> = ''a''<sup>2</sup>. Since the expression on the left is an integer multiple of 2, the right expression is by definition divisible by 2. That is, ''a''<sup>2</sup> is even, which implies that ''a'' must also be even, as seen in the proposition above (in [[#Proof by contraposition]]). So we can write ''a'' = 2''c'', where ''c'' is also an integer. Substitution into the original equation yields 2''b''<sup>2</sup> = (2''c'')<sup>2</sup> = 4''c''<sup>2</sup>. Dividing both sides by 2 yields ''b''<sup>2</sup> = 2''c''<sup>2</sup>. But then, by the same argument as before, 2 divides ''b''<sup>2</sup>, so ''b'' must be even. However, if ''a'' and ''b'' are both even, they have 2 as a common factor. This contradicts our previous statement that ''a'' and ''b'' have no common factor, so we must conclude that <math>\sqrt{2}</math> is an irrational number.

To paraphrase: if one could write <math>\sqrt{2}</math> as a [[fraction]], this fraction could never be written in lowest terms, since 2 could always be factored from numerator and denominator.

===Proof by construction===
{{Main|Proof by construction}}
Proof by construction, or proof by example, is the construction of a concrete example with a property to show that something having that property exists. [[Joseph Liouville]], for instance, proved the existence of [[transcendental number]]s by constructing an [[Liouville number|explicit example]].  It can also be used to construct a [[counterexample]] to disprove a proposition that all elements have a certain property.

===Proof by exhaustion===
{{Main|Proof by exhaustion}}
In proof by exhaustion, the conclusion is established by dividing it into a finite number of cases and proving each one separately. The number of cases sometimes can become very large. For example, the first proof of the [[four color theorem]] was a proof by exhaustion with 1,936 cases. This proof was controversial because the majority of the cases were checked by a computer program, not by hand.<ref>See [[Four color theorem#Simplification and verification]].</ref>

=== Closed chain inference ===
{{Main|Closed chain inference}}

A closed chain inference shows that a collection of statements are pairwise equivalent.

In order to prove that the statements <math>\varphi_1,\ldots,\varphi_n</math> are each pairwise equivalent, proofs are given for the implications <math>\varphi_1\Rightarrow\varphi_2</math>, <math>\varphi_2\Rightarrow\varphi_3</math>, <math>\dots</math>, <math>\varphi_{n-1}\Rightarrow\varphi_n</math> and <math>\varphi_{n}\Rightarrow\varphi_1</math>.<ref>{{Cite book |last1=Plaue |first1=Matthias |url=https://books.google.com/books?id=-WCHDwAAQBAJ |title=Mathematik für das Bachelorstudium I: Grundlagen und Grundzüge der linearen Algebra und Analysis |last2=Scherfner |first2=Mike |date=2019-02-11 |publisher=Springer-Verlag |isbn=978-3-662-58352-4 |pages=26 |language=de |trans-title=Mathematics for the Bachelor's degree I: Fundamentals and basics of linear algebra and analysis}}</ref><ref>{{Cite book |last1=Struckmann |first1=Werner |url=https://books.google.com/books?id=1epNDQAAQBAJ |title=Mathematik für Informatiker: Grundlagen und Anwendungen |last2=Wätjen |first2=Dietmar |date=2016-10-20 |publisher=Springer-Verlag |isbn=978-3-662-49870-5 |pages=28 |language=de |trans-title=Mathematics for Computer Scientists: Fundamentals and Applications}}</ref>

The pairwise equivalence of the statements then results from the [[Transitive relation|transitivity]] of the [[material conditional]].

===Probabilistic proof===
{{Main|Probabilistic method}}
A probabilistic proof is one in which an example is shown to exist, with certainty, by using methods of [[probability theory]]. Probabilistic proof, like proof by construction, is one of many ways to prove [[existence theorem]]s.

In the probabilistic method, one seeks an object having a given property, starting with a large set of candidates. One assigns a certain probability for each candidate to be chosen, and then proves that there is a non-zero probability that a chosen candidate will have the desired property. This does not specify which candidates have the property, but the probability could not be positive without at least one.

A probabilistic proof is not to be confused with an argument that a theorem is 'probably' true, a 'plausibility argument'. The work toward the [[Collatz conjecture]] shows how far plausibility is from genuine proof, as does the disproof of the [[Mertens conjecture]]. While most mathematicians do not think that probabilistic evidence for the properties of a given object counts as a genuine mathematical proof, a few mathematicians and philosophers have argued that at least some types of probabilistic evidence (such as Rabin's [[probabilistic algorithm]] for [[primality test|testing primality]]) are as good as genuine mathematical proofs.<ref>Davis, Philip J. (1972), "Fidelity in Mathematical Discourse: Is One and One Really Two?" ''American Mathematical Monthly'' 79:252–63.</ref><ref>Fallis, Don (1997), "The Epistemic Status of Probabilistic Proof." ''Journal of Philosophy'' 94:165–86.</ref>

===Combinatorial proof===
{{Main|Combinatorial proof}}
A combinatorial proof establishes the equivalence of different expressions by showing that they count the same object in different ways. Often a [[bijection]] between two [[set (mathematics)|sets]] is used to show that the expressions for their two sizes are equal. Alternatively, a [[double counting (proof technique)|double counting argument]] provides two different expressions for the size of a single set, again showing that the two expressions are equal.

===Nonconstructive proof===
{{Main|Nonconstructive proof}}
A nonconstructive proof establishes that a [[mathematical object]] with a certain property exists—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 proved to be impossible. In contrast, a constructive proof establishes that a particular object exists by providing a method of finding it. The following famous example of a nonconstructive proof shows that there exist two [[irrational number]]s ''a'' and ''b'' such that <math>a^b</math> is a [[rational number]]. This proof uses that <math>\sqrt{2}</math> is irrational (an easy proof is known since [[Euclid]]), but not that <math>\sqrt{2}^{\sqrt{2}}</math> is irrational (this is true, but the proof is not elementary).
:Either <math>\sqrt{2}^{\sqrt{2}}</math> is a rational number and we are done (take <math>a=b=\sqrt{2}</math>), or <math>\sqrt{2}^{\sqrt{2}}</math> is irrational so we can write <math>a=\sqrt{2}^{\sqrt{2}}</math> and <math>b=\sqrt{2}</math>. This then gives <math>\left (\sqrt{2}^{\sqrt{2}}\right )^{\sqrt{2}}=\sqrt{2}^{2}=2</math>, which is thus a rational number of the form <math>a^b.</math>

===Statistical proofs in pure mathematics===
{{Main| Statistical proof}}
The expression "statistical proof" may be used technically or colloquially in areas of [[pure mathematics]], such as involving [[cryptography]], [[chaotic series]], and [[probabilistic|probabilistic number theory]] or [[analytic number theory]].<ref>"in number theory and commutative algebra... in particular the statistical proof of the lemma." [https://www.jstor.org/pss/2686395]</ref><ref>"Whether constant π (i.e., pi) is normal is a confusing problem without any strict theoretical demonstration except for some ''statistical'' proof"" (Derogatory use.)[https://doi.org/10.1007%2F978-3-540-74282-1_78]</ref><ref>"these observations suggest a statistical proof of Goldbach's conjecture with very quickly vanishing probability of failure for large E" [http://people.web.psi.ch/gassmann/eneseminare/abstracts/Goldbach1.pdf]</ref> It is less commonly used to refer to a mathematical proof in the branch of mathematics known as [[mathematical statistics]].  See also the "[[#Colloquial use, Statistical proof using data|Statistical proof using data]]" section below.

===Computer-assisted proofs===
{{Main|Computer-assisted proof }}
Until the twentieth century it was assumed that any proof could, in principle, be checked by a competent mathematician to confirm its validity.<ref name="Krantz">[http://www.math.wustl.edu/~sk/eolss.pdf The History and Concept of Mathematical Proof], Steven G. Krantz. 1. February 5, 2007</ref> However, computers are now used both to prove theorems and to carry out calculations that are too long for any human or team of humans to check; the first proof of the [[four color theorem]] is an example of a computer-assisted proof. Some mathematicians are concerned that the possibility of an error in a computer program or a run-time error in its calculations calls the validity of such computer-assisted proofs into question. In practice, the chances of an error invalidating a computer-assisted proof can be reduced by incorporating redundancy and self-checks into calculations, and by developing multiple independent approaches and programs. Errors can never be completely ruled out in case of verification of a proof by humans either, especially if the proof contains natural language and requires deep mathematical insight to uncover the potential hidden assumptions and fallacies involved.