Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Constructive proof
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Examples== ===Non-constructive proofs=== First consider the theorem that there are an infinitude of [[prime number]]s. [[Euclid]]'s [[Euclid's theorem|proof]] is constructive. But a common way of simplifying Euclid's proof postulates that, contrary to the assertion in the theorem, there are only a finite number of them, in which case there is a largest one, denoted ''n''. Then consider the number ''n''! + 1 (1 + the product of the first ''n'' numbers). Either this number is prime, or all of its prime factors are greater than ''n''. Without establishing a specific prime number, this proves that one exists that is greater than ''n'', contrary to the original postulate. Now consider the theorem "there exist [[irrational number]]s <math>a</math> and <math>b</math> such that <math>a^b</math> is [[rational number|rational]]." This theorem can be proven by using both a constructive proof, and a non-constructive proof. The following 1953 proof by Dov Jarden has been widely used as an example of a non-constructive proof since at least 1970:<ref>[[J. Roger Hindley]], "The Root-2 Proof as an Example of Non-constructivity", unpublished paper, September 2014, [http://www.users.waitrose.com/~hindley/Root2Proof2014.pdf full text] {{webarchive|url=https://web.archive.org/web/20141023060917/http://www.users.waitrose.com/~hindley/Root2Proof2014.pdf |date=2014-10-23 }}</ref><ref>Dov Jarden, "A simple proof that a power of an irrational number to an irrational exponent may be rational", ''Curiosa'' No. 339 in ''[[Scripta Mathematica]]'' '''19''':229 (1953)</ref> <blockquote> '''CURIOSA'''<br> '''339.''' ''A Simple Proof That a Power of an Irrational Number to an Irrational Exponent May Be Rational.''<br> <math>\sqrt{2}^{\sqrt{2}}</math> is either rational or irrational. If it is rational, our statement is proved. If it is irrational, <math>(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = 2</math> proves our statement.<br> Dov Jarden Jerusalem </blockquote> In a bit more detail: *Recall that <math>\sqrt{2}</math> [[Square root of 2#Proofs of irrationality|is irrational]], and 2 is rational. Consider the number <math>q = \sqrt{2}^{\sqrt2}</math>. Either it is rational or it is irrational. *If <math>q</math> is rational, then the theorem is true, with <math>a</math> and <math>b</math> both being <math>\sqrt{2}</math>. *If <math>q</math> is irrational, then the theorem is true, with <math>a</math> being <math>\sqrt{2}^{\sqrt2}</math> and <math>b</math> being <math>\sqrt{2}</math>, since :<math>\left (\sqrt{2}^{\sqrt2}\right )^{\sqrt2} = \sqrt{2}^{(\sqrt{2} \cdot \sqrt{2})} = \sqrt{2}^2 = 2.</math> At its core, this proof is non-constructive because it relies on the statement "Either ''q'' is rational or it is irrational"—an instance of the [[law of excluded middle]], which is not valid within a constructive proof. The non-constructive proof does not construct an example ''a'' and ''b''; it merely gives a number of possibilities (in this case, two mutually exclusive possibilities) and shows that one of them—but does not show ''which'' one—must yield the desired example. As it turns out, <math>\sqrt{2}^{\sqrt2}</math> is irrational because of the [[Gelfond–Schneider theorem]], but this fact is irrelevant to the correctness of the non-constructive proof. ===Constructive proofs=== A ''constructive'' proof of the theorem that a power of an irrational number to an irrational exponent may be rational gives an actual example, such as: :<math>a = \sqrt{2}\, , \quad b = \log_2 9\, , \quad a^b = 3\, .</math> The [[square root of 2]] is irrational, and 3 is rational. <math>\log_2 9</math> is also irrational: if it were equal to <math>m \over n</math>, then, by the properties of [[logarithms]], 9<sup>''n''</sup> would be equal to 2<sup>''m''</sup>, but the former is odd, and the latter is even. A more substantial example is the [[graph minor theorem]]. A consequence of this theorem is that a [[graph (discrete mathematics)|graph]] can be drawn on the [[torus]] if, and only if, none of its [[minor (graph theory)|minors]] belong to a certain finite set of "[[forbidden minors]]". However, the proof of the existence of this finite set is not constructive, and the forbidden minors are not actually specified.<ref>{{Cite journal|last1=Fellows|first1=Michael R.|last2=Langston|first2=Michael A.|date=1988-06-01|title=Nonconstructive tools for proving polynomial-time decidability|url=http://www.mrfellows.net/papers/FL88_NonconstructiveTools.pdf|journal=Journal of the ACM|volume=35|issue=3|pages=727–739|doi=10.1145/44483.44491|s2cid=16587284}}</ref> They are still unknown.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)