Meta tags:

Headings (most frequently used words):

constructive, proofs, proof, contents, historical, example, examples, brouwerian, counterexamples, see, also, references, further, reading, external, links, non,

Text of the page (most frequently used words):
the (108), #constructive (50), proof (39), that (35), displaystyle (29), and (24), mathematics (22), sqrt (22), this (21), non (18), number (17), irrational (16), statement (15), theorem (15), not (14), edit (13), example (13), rational (12), proofs (11), for (11), existence (11), such (11), which (11), are (11), may (9), with (9), counterexamples (9), also (9), wikipedia (7), numbers (7), can (7), there (7), then (7), one (7), some (7), weak (6), however (6), counterexample (6), even (6), two (6), log (6), search (5), page (5), links (5), from (5), constructivism (5), philosophy (5), mathematical (5), brouwerian (5), constructively (5), goldbach (5), conjecture (5), case (5), known (5), they (5), natural (5), than (5), sum (5), primes (5), mbox (5), law (5), excluded (5), middle (5), ldots (5), contents (4), view (4), use (4), stanford (4), encyclopedia (4), isbn (4), theory (4), doi (4), tools (4), hilbert (4), its (4), method (4), real (4), proved (4), because (4), have (4), main (4), shows (4), least (4), principle (4), show (4), interval (4), axiom (4), finite (4), but (4), either (4), consider (4), first (4), prime (4), object (4), hide (4), move (4), sidebar (4), toggle (3), about (3), terms (3), was (3), different (3), mark (3), van (3), university (3), further (3), s2cid (3), nonconstructive (3), dov (3), jarden (3), simple (3), power (3), exponent (3), der (3), algorithm (3), meaning (3), would (3), former (3), quoted (3), must (3), present (3), does (3), well (3), problem (3), sequence (3), only (3), every (3), follows (3), particular (3), systems (3), since (3), choice (3), implies (3), set (3), minors (3), them (3), true (3), being (3), proves (3), has (3), all (3), examples (3), stronger (3), languages (2), table (2), contact (2), privacy (2), policy (2), text (2), using (2), categories (2), wayback (2), german (2), short (2), description (2), wikidata (2), retrieved (2), atten (2), external (2), 1988 (2), troelstra (2), press (2), introduction (2), reading (2), principles (2), intuitionism (2), 2689939 (2), 0025 (2), issn (2), michael (2), pdf (2), time (2), 339 (2), 1953 (2), curiosa (2), root (2), 2014 (2), full (2), hermann (2), grete (2), princeton (2), 9781400842681 (2), theology (2), 2018 (2), references (2), pure (2), see (2), false (2), latter (2), possible (2), whether (2), unknown (2), shown (2), sort (2), related (2), brouwer (2), provided (2), cases (2), end (2), type (2), idea (2), various (2), classical (2), provable (2), more (2), certain (2), forbidden (2), specified (2), graph (2), gives (2), were (2), equal (2), quad (2), valid (2), possibilities (2), both (2), our (2), been (2), used (2), exist (2), common (2), euclid (2), contrary (2), greater (2), without (2), solving (2), coefficients (2), she (2), nullstellensatz (2), complex (2), polynomials (2), constructions (2), historical (2), proposition (2), contradiction (2), concept (2), creating (2), providing (2), appearance (2), upload (2), file (2), changes (2), history (2), read (2), english (2), article (2), create (2), account (2), donate (2), menu (2), add, topic, mobile, cookie, statistics, developers, code, conduct, legal, safety, contacts, disclaimers, available, under, additional, apply, site, you, agree, registered, trademark, profit, organization, wikimedia, foundation, inc, creative, commons, attribution, sharealike, license, rendered, parsoid, last, edited, october, 2026, utc, hidden, webarchive, template, cs1, language, sources, articles, https, org, index, php, title, constructive_proof, oldid, 1377902422, volume, elsevier, science, 978, 444, 70506, dirk, dalen, anne, sjerp, 1979, fifth, edition, oxford, 853171, wright, hardy, daoud, 2011, kew, books, 646, 54509, franklin, 2015, lecture, notes, 1969, 102, mandelkern, 1989, jstor, 570x, 2307, magazine, fellows, langston, 739, 16587284, 1145, 44483, 44491, 727, journal, acm, proving, polynomial, decidability, 229, scripta, mathematica, constructivity, unpublished, paper, september, machine, archived, roger, hindley, 1926, die, frage, endlich, vielen, schritte, theorie, polynomideale, unter, benutzung, nachgelassener, sätze, von, hentzelt, 788, 115897210, 5831, 1007, bf01206635, 736, mathematische, annalen, mclarty, colin, april, 2008, 170826113, 775873004, oclc, 1515, 105, mazur, barry, doxiadēs, apostolos, circles, disturbed, interplay, narrative, chapter, discontents, origin, myth, modern, bridges, douglas, palmgren, erik, zalta, edward, summer, metaphysics, research, lab, 2019, probabilistic, results, author, book, foundations, analysis, errett, bishop, several, facts, based, words, mean, entirely, know, albeit, practical, identify, hardness, just, hard, prove, often, limited, omniscience, each, value, determined, exhaustive, defined, moreover, fixed, rate, convergence, converges, according, usual, treatment, cauchy, disprove, begins, taking, unsolved, asks, larger, define, begin, imply, field, develops, classifying, how, showing, equivalent, fragments, reverse, diaconescu, disproved, giving, give, itself, cannot, substantial, consequence, drawn, none, belong, actually, still, torus, minor, actual, properties, odd, logarithms, over, square, turns, out, fact, irrelevant, correctness, gelfond, schneider, core, relies, instance, within, construct, merely, mutually, exclusive, yield, desired, left, right, cdot, recall, bit, detail, jerusalem, following, widely, 1970, now, proven, infinitude, way, simplifying, postulates, assertion, largest, denoted, product, factors, establishing, specific, exists, original, postulate, provides, reduced, considering, unknowns, system, linear, equations, twenty, five, years, later, computing, strong, sense, result, found, degrees, less, surprise, mathematicians, wrote, paul, gordan, stated, indeterminates, zeros, previously, considered, problems, seems, philosophical, point, especially, interesting, implying, basis, until, 19th, century, essentially, appeared, formal, definition, infinite, sets, georg, cantor, seen, defining, certified, explored, between, programs, logical, calculus, gérard, huet, thierry, coquand, intuitionistic, per, martin, löf, curry, howard, correspondence, logic, heyting, kolmogorov, interpretation, algorithms, ensues, consequently, accepted, varieties, including, falso, quodlibet, explosion, refer, rejects, methods, involve, objects, explicitly, built, excludes, induces, terminology, term, infinity, demonstrates, contrast, kind, avoiding, confusion, sometimes, called, effective, redirected, free, item, wikibooks, other, projects, printable, version, download, print, export, switch, legacy, parser, get, shortened, url, cite, information, permanent, link, what, here, general, actions, talk, українська, русский, português, nederlands, 한국어, 日本語, français, español, deutsch, cymraeg, subsection, top, personal, special, pages, recent, community, portal, learn, help, contribute, random, current, events, navigation, jump, content,

Text of the page (random words):
constructive proof wikipedia jump to content main menu main menu move to sidebar hide navigation main page contents current events random article about wikipedia contact us contribute help learn to edit community portal recent changes upload file special pages search search appearance donate create account log in personal tools donate create account log in contents move to sidebar hide top 1 a historical example 2 examples toggle examples subsection 2 1 non constructive proofs 2 2 constructive proofs 3 brouwerian counterexamples 4 see also 5 references 6 further reading 7 external links toggle the table of contents constructive proof 13 languages cymraeg deutsch español français 日本語 한국어 nederlands português русский simple english українська 粵語 中文 edit links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikibooks wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia redirected from nonconstructive method of proof in mathematics in mathematics a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object this is in contrast to a non constructive proof also known as an existence proof or pure existence theorem which proves the existence of a particular kind of object without providing an example for avoiding confusion with the stronger concept that follows such a constructive proof is sometimes called an effective proof a constructive proof may also refer to the stronger concept of a proof that is valid in constructive mathematics constructivism is a mathematical philosophy that rejects all proof methods that involve the existence of objects that are not explicitly built this excludes in particular the use of the law of the excluded middle the axiom of infinity and the axiom of choice constructivism also induces a different meaning for some terminology for example the term or has a stronger meaning in constructive mathematics than in classical 1 some non constructive proofs show that if a certain proposition is false a contradiction ensues consequently the proposition must be true proof by contradiction however the principle of explosion ex falso quodlibet has been accepted in some varieties of constructive mathematics including intuitionism constructive proofs can be seen as defining certified mathematical algorithms this idea is explored in the brouwer heyting kolmogorov interpretation of constructive logic the curry howard correspondence between proofs and programs and such logical systems as per martin löf s intuitionistic type theory and thierry coquand and gérard huet s calculus of constructions a historical example edit until the end of 19th century all mathematical proofs were essentially constructive the first non constructive constructions appeared with georg cantor s theory of infinite sets and the formal definition of real numbers the first use of non constructive proofs for solving previously considered problems seems to be hilbert s nullstellensatz and hilbert s basis theorem from a philosophical point of view the former is especially interesting as implying the existence of a well specified object the nullstellensatz may be stated as follows if f 1 f k displaystyle f_ 1 ldots f_ k are polynomials in n indeterminates with complex coefficients which have no common complex zeros then there are polynomials g 1 g k displaystyle g_ 1 ldots g_ k such that f 1 g 1 f k g k 1 displaystyle f_ 1 g_ 1 ldots f_ k g_ k 1 such a non constructive existence theorem was such a surprise for mathematicians of that time that one of them paul gordan wrote this is not mathematics it is theology 2 twenty five years later grete hermann provided an algorithm for computing g 1 g k displaystyle g_ 1 ldots g_ k which is not a constructive proof in the strong sense as she used hilbert s result she proved that if g 1 g k displaystyle g_ 1 ldots g_ k exist they can be found with degrees less than 2 2 n displaystyle 2 2 n 3 this provides an algorithm as the problem is reduced to solving a system of linear equations by considering as unknowns the finite number of coefficients of the g i displaystyle g_ i examples edit non constructive proofs edit first consider the theorem that there are an infinitude of prime numbers euclid s 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 numbers a displaystyle a and b displaystyle b such that a b displaystyle a b is 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 4 5 curiosa 339 a simple proof that a power of an irrational number to an irrational exponent may be rational 2 2 displaystyle sqrt 2 sqrt 2 is either rational or irrational if it is rational our statement is proved if it is irrational 2 2 2 2 displaystyle sqrt 2 sqrt 2 sqrt 2 2 proves our statement dov jarden jerusalem in a bit more detail recall that 2 displaystyle sqrt 2 is irrational and 2 is rational consider the number q 2 2 displaystyle q sqrt 2 sqrt 2 either it is rational or it is irrational if q displaystyle q is rational then the theorem is true with a displaystyle a and b displaystyle b both being 2 displaystyle sqrt 2 if q displaystyle q is irrational then the theorem is true with a displaystyle a being 2 2 displaystyle sqrt 2 sqrt 2 and b displaystyle b being 2 displaystyle sqrt 2 since 2 2 2 2 2 2 2 2 2 displaystyle left sqrt 2 sqrt 2 right sqrt 2 sqrt 2 sqrt 2 cdot sqrt 2 sqrt 2 2 2 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 2 2 displaystyle sqrt 2 sqrt 2 is irrational because of the gelfond schneider theorem but this fact is irrelevant to the correctness of the non constructive proof constructive proofs edit 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 a 2 b log 2 9 a b 3 displaystyle a sqrt 2 quad b log _ 2 9 quad a b 3 the square root of 2 is irrational and 3 is rational log 2 9 displaystyle log _ 2 9 is also irrational if it were equal to m n displaystyle m over n then by the properties of logarithms 9 n would be equal to 2 m 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 can be drawn on the torus if and only if none of its 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 6 they are still unknown brouwerian counterexamples edit in constructive mathematics a statement may be disproved by giving a counterexample as in classical mathematics however it is also possible to give a brouwerian counterexample to show that the statement is non constructive 7 this sort of counterexample shows that the statement implies some principle that is known to be non constructive if it can be proved constructively that the statement implies some principle that is not constructively provable then the statement itself cannot be constructively provable for example a particular statement may be shown to imply the law of the excluded middle an example of a brouwerian counterexample of this type is diaconescu s theorem which shows that the full axiom of choice is non constructive in systems of constructive set theory since the axiom of choice implies the law of excluded middle in such systems the field of constructive reverse mathematics develops this idea further by classifying various principles in terms of how nonconstructive they are by showing they are equivalent to various fragments of the law of the excluded middle brouwer also provided weak counterexamples 8 such counterexamples do not disprove a statement however they only show that at present no constructive proof of the statement is known one weak counterexample begins by taking some unsolved problem of mathematics such as goldbach s conjecture which asks whether every even natural number larger than 4 is the sum of two primes define a sequence a n of rational numbers as follows 9 a n 1 2 n if every even natural number in the interval 4 n is the sum of two primes 1 2 k if k is the least even natural number in the interval 4 n which is not the sum of two primes displaystyle a n begin cases 1 2 n mbox if every even natural number in the interval 4 n mbox is the sum of two primes 1 2 k mbox if k mbox is the least even natural number in the interval 4 n mbox which is not the sum of two primes end cases for each n the value of a n can be determined by exhaustive search and so a is a well defined sequence constructively moreover because a is a cauchy sequence with a fixed rate of convergence a converges to some real number α according to the usual treatment of real numbers in constructive mathematics several facts about the real number α can be proved constructively however based on the different meaning of the words in constructive mathematics if there is a constructive proof that α 0 or α 0 then this would mean that there is a constructive proof of goldbach s conjecture in the former case or a constructive proof that goldbach s conjecture is false in the latter case because no such proof is known the quoted statement must also not have a known constructive proof however it is entirely possible that goldbach s conjecture may have a constructive proof as we do not know at present whether it does in which case the quoted statement would have a constructive proof as well albeit one that is unknown at present the main practical use of weak counterexamples is to identify the hardness of a problem for example the counterexample just shown shows that the quoted statement is at least as hard to prove as goldbach s conjecture weak counterexamples of this sort are often related to the limited principle of omniscience see also edit constructivism philosophy of mathematics errett bishop author of the book foundations of constructive analysis existence theorem pure existence results non constructive algorithm existence proofs probabilistic method references edit bridges douglas palmgren erik 2018 constructive mathematics in zalta edward n ed the stanford encyclopedia of philosophy summer 2018 ed metaphysics research lab stanford university retrieved 2019 10 25 mclarty colin april 15 2008 circles disturbed the interplay of mathematics and narrative chapter 4 hilbert on theology and its discontents the origin myth of modern mathematics doxiadēs apostolos k mazur barry princeton princeton university press doi 10 1515 9781400842681 105 isbn 9781400842681 oclc 775873004 s2cid 170826113 hermann grete 1926 die frage der endlich vielen schritte in der theorie der polynomideale unter benutzung nachgelassener sätze von k hentzelt mathematische annalen in german 95 1 736 788 doi 10 1007 bf01206635 issn 0025 5831 s2cid 115897210 j roger hindley the root 2 proof as an example of non constructivity unpublished paper september 2014 full text archived 2014 10 23 at the wayback machine 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 fellows michael r langston michael a 1988 06 01 nonconstructive tools for proving polynomial time decidability pdf journal of the acm 35 3 727 739 doi 10 1145 44483 44491 s2cid 16587284 mandelkern mark 1989 brouwerian counterexamples mathematics magazine 62 1 3 27 doi 10 2307 2689939 issn 0025 570x jstor 2689939 a s troelstra principles of intuitionism lecture notes in mathematics 95 1969 p 102 mark van atten 2015 weak counterexamples stanford encyclopedia of mathematics further reading edit j franklin and a daoud 2011 proof in mathematics an introduction kew books isbn 0 646 54509 4 ch 4 hardy g h wright e m 1979 an introduction to the theory of numbers fifth edition oxford university press isbn 0 19 853171 0 anne sjerp troelstra and dirk van dalen 1988 constructivism in mathematics volume 1 elsevier science isbn 978 0 444 70506 8 external links edit weak counterexamples by mark van atten stanford encyclopedia of philosophy retrieved from https en wikipedia org w index php title constructive_proof oldid 1377902422 categories mathematical proofs constructivism philosophy of mathematics hidden categories articles with short description short description is different from wikidata cs1 german language sources de webarchive template wayback links this page was last edited on 1 october 2026 at 21 28 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a registered trademark of the wikimedia foundation inc a non profit organization privacy policy about wikipedia disclaimers contact wikipedia legal safety contacts code of conduct developers statistics cookie statement mobile view search search toggle the table of contents constructive proof 13 languages add topic