Meta tags:

Headings (most frequently used words):

edit, of, by, contradiction, proof, other, in, examples, navigation, law, the, infinitude, primes, tools, contents, formalization, justification, relationship, with, techniques, intuitionistic, logic, proofs, refutations, notation, hardy, view, see, also, references, further, reading, and, external, links, menu, refutation, non, excluded, middle, euclid, elements, hilbert, nullstellensatz, irrationality, square, root, infinite, descent, russell, paradox, personal, namespaces, views, search, contribute, print, export, projects, languages,

Text of the page (most frequently used words):
the (107), proof (69), #contradiction (69), displaystyle (51), and (40), that (36), proposition (26), edit (24), not (23), prime (21), law (19), logic (17), with (16), lnot (16), list (15), are (15), then (15), which (14), there (14), #refutation (14), theory (13), this (12), euclid (12), set (11), principle (11), primes (11), elements (10), from (10), mathematical (10), mathematics (10), number (10), excluded (10), middle (10), than (10), non (9), october (9), 2022 (9), retrieved (9), logical (9), numbers (9), for (9), assume (9), wikipedia (8), may (8), theorem (8), negation (8), one (8), such (8), derive (8), follows (8), valid (8), false (8), true (8), statement (7), all (7), proofs (7), truth (7), hilbert (7), order (7), book (7), noncontradiction (7), any (7), citation (7), needed (7), assuming (7), ldots (7), states (7), proved (7), propositional (6), object (6), calculus (6), tarski (6), square (6), paradox (6), also (6), but (6), used (6), both (6), can (6), vdash (6), page (5), pdf (5), articles (5), org (5), function (5), problem (5), predicate (5), model (5), finite (5), formal (5), example (5), infinite (5), see (5), notation (5), root (5), form (5), either (5), case (5), intuitionistically (5), equal (5), intuitionistic (5), falsehood (5), gamma (5), delta (5), view (4), links (4), unsourced (4), statements (4), turing (4), machine (4), recursive (4), decidable (4), validity (4), sequent (4), inference (4), natural (4), variable (4), symbol (4), first (4), russell (4), reductio (4), absurdum (4), how (4), hardy (4), web (4), descent (4), smallest (4), property (4), exists (4), method (4), given (4), because (4), divides (4), another (4), infinitude (4), they (4), examples (4), formally (4), opposite (4), cfrac (4), holds (4), about (3), was (3), other (3), article (3), navigation (3), more (3), history (3), read (3), 2021 (3), theorems (3), https (3), category (3), sets (3), type (3), theories (3), equivalence (3), rule (3), boolean (3), second (3), free (3), formula (3), axiom (3), gödel (3), product (3), classical (3), halting (3), encyclopedia (3), introduction (3), university (3), mathematician (3), http (3), archive (3), saying (3), even (3), sometimes (3), out (3), rightarrow (3), whose (3), positive (3), smaller (3), desired (3), shown (3), prove (3), two (3), would (3), let (3), cdot (3), every (3), refutations (3), hence (3), divisible (3), cannot (3), polynomials (3), nullstellensatz (3), proceeds (3), angles (3), stable (3), implies (3), halts (3), does (3), its (3), equivalent (3), conclude (3), reads (3), contact (2), privacy (2), policy (2), additional (2), terms (2), wikidata (2), cite (2), information (2), link (2), special (2), upload (2), file (2), related (2), changes (2), here (2), tools (2), portal (2), contents (2), main (2), search (2), talk (2), categories (2), cs1 (2), maint (2), location (2), short (2), description (2), index (2), proof_by_contradiction (2), philosophy (2), abstract (2), primitive (2), kolmogorov (2), computable (2), church (2), schema (2), kripke (2), semantics (2), complete (2), elementary (2), diagram (2), arithmetic (2), interpretation (2), ordinal (2), systems (2), axiomatic (2), consequence (2), deduction (2), euclidean (2), skolem (2), atomic (2), ground (2), language (2), relation (2), constructive (2), von (2), neumann (2), grothendieck (2), foundations (2), general (2), cardinality (2), pair (2), monadic (2), many (2), argument (2), tautology (2), write (2), chapter (2), isbn (2), has (2), further (2), reading (2), external (2), cambridge (2), press (2), comprehensive (2), symbols (2), davey (2), priestley (2), math (2), irrational (2), bauer (2), andrej (2), 2017 (2), david (2), computation (2), references (2), gambit (2), chess (2), arrows (2), times (2), leftarrow (2), stated (2), negated (2), usual (2), typical (2), rational (2), demonstrate (2), thereby (2), deriving (2), exist (2), indeed (2), irrationality (2), suppose (2), contrary (2), were (2), application (2), their (2), difference (2), gives (2), since (2), thus (2), consider (2), applies (2), assigned (2), multitude (2), take (2), frequently (2), following (2), seek (2), larger (2), them (2), have (2), bigger (2), above (2), takes (2), derived (2), complex (2), known (2), universally (2), only (2), applied (2), satisfying (2), condition (2), halt (2), neither (2), nor (2), algorithm (2), establishing (2), although (2), contrast (2), aristotle (2), equivalently (2), similar (2), relationship (2), techniques (2), justification (2), expressed (2), concluded (2), formalization (2), existence (2), leads (2), showing (2), jump (2), cookie, statistics, developers, mobile, disclaimers, text, available, under, apply, using, site, you, agree, registered, trademark, profit, organization, wikimedia, foundation, inc, use, creative, commons, attribution, sharealike, license, last, edited, utc, tiếng, việt, українська, தமிழ், svenska, српски, srpski, slovenščina, slovenčina, русский, português, polski, 日本語, nederlands, magyar, latviešu, עברית, íslenska, bahasa, indonesia, 한국어, فارسی, esperanto, español, ελληνικά, eesti, dansk, cymraeg, čeština, bân, lâm, العربية, languages, wikibooks, projects, printable, version, download, print, export, item, permanent, pages, what, recent, community, learn, help, contribute, donate, random, current, events, views, english, namespaces, log, create, account, contributions, logged, personal, menu, hidden, june, different, methods, php, title, oldid, 1118847036, supertask, logicism, timeline, concrete, recursion, lambda, complexity, versus, undecidable, decision, computably, enumerable, thesis, encoding, computability, ultraproduct, value, transfer, semantic, strength, satisfiability, categorical, standard, substructure, saturated, self, verifying, reverse, analysis, impossibility, zfc, independence, deductive, principia, mathematica, geometry, minimal, axioms, canonical, algebras, axiomatization, real, robinson, peano, term, constant, substitution, string, signature, sentence, rank, quantifier, functional, connective, metalanguage, bound, open, closed, formation, system, grammar, extension, expression, automata, arity, alphabet, syntax, bernays, new, naive, morse, kelley, platek, continuum, hypothesis, choice, zermelo, fraenkel, binary, operation, aleph, inaccessible, large, cardinal, enumeration, numbering, isomorphism, schröder, bernstein, jection, sur, image, codomain, domain, map, maps, constructible, universe, universal, fuzzy, ultrafilter, transitive, singleton, inhabited, empty, uncountable, countable, types, operations, identities, power, cartesian, complement, union, intersection, partition, forcing, extensionality, equality, subset, ordered, element, class, hereditary, quantifiers, higher, valued, tables, connectives, functions, algebra, venn, opposition, syllogism, soundness, equiconsistency, consistency, traditional, logics, löwenheim, lindström, compactness, cantor, diagonal, banach, undefinability, incompleteness, completeness, paradoxes, internet, issn, 2161, 0002, larry, cusick, daoud, albert, 2011, kew, 978, 646, 54509, franklin, james, wikibook, topic, 1992, 9780521427067, apology, latex, www, ctan, tex, info, gary, hardegree, 20110607061046, people, umass, edu, gmhwww, 511, c02, modal, 2002, 286, lattices, forum, discussions, alfeld, peter, august, 1996, department, utah, 2013, february, understanding, study, guide, why, bull, amer, soc, 481, 498, five, stages, accepting, 1893, 313, 373, 1007, bf01444162, doi, mathematische, annalen, ueber, die, vollen, invariantensysteme, march, 2010, nlab, 2019, britannica, modus, tollens, exhaustion, described, finest, weapons, far, finer, player, offer, sacrifice, pawn, piece, offers, game, end, word, baermann, absurd, along, lines, rarely, today, graphical, contradictions, downwards, zigzag, arrow, lightning, 21af, others, include, struck, stylized, hash, 2a33, reference, mark, 203b, nleftrightarrow, opposing, quod, est, isaac, barrow, theoretically, precisely, those, contain, themselves, once, again, observing, still, whereby, classic, ratio, mathbb, claim, divide, factor, itself, greater, will, least, cdots, arguably, closer, same, spirit, original, formulation, step, look, conflated, often, erroneously, claimed, really, therefore, must, say, now, express, employ, depending, present, former, below, done, infinitely, indeterminates, coefficients, common, zeros, influential, his, derives, triangle, sides, early, occurrence, found, satisfies, propositions, instance, repurposed, show, checked, direct, lor, mean, acceptable, allow, solve, stating, obtain, deciding, whether, arbitrary, violating, solvability, brouwer, heyting, generally, some, particular, instances, formulated, assertion, combined, means, exactly, implied, formalized, metaphysical, written, confusingly, practice, referred, proceed, manner, however, unless, become, when, whereas, whatsoever, confused, looking, derivable, rules, established, turns, conversely, applying, after, allows, explosion, course, way, justify, justified, examination, demonstrates, table, hypotheses, entail, conclusion, important, quite, freely, accepts, kind, nonconstructive, school, thought, fact, typically, accomplished, mutually, contradictory, assertions, appealing, employing, usually, establishes, weaker, impossibile, indirect, impossible, wayback, 20221029130207, wiki, timestamps, capture, fail, success, 2023, nov, oct, sep, jun, 2004, jul, 2026, 463, captures,

Text of the page (random words):
by contradiction edit proof by contradiction is frequently confused with the similar looking refutation by contradiction 2 a k a proof of negation citation needed which states that p is proved as follows the proposition to be proved is p assume p derive falsehood conclude p in contrast proof by contradiction proceeds as follows the proposition to be proved is p assume p derive falsehood conclude p refutation by contradiction applies only when the proposition to be proved is negated whereas proof by contradiction may be applied to any proposition whatsoever confusingly in mathematical practice both proof by contradiction and refutation by contradiction are referred to as proof by contradiction as they proceed in a similar manner 3 however they are not equivalent unless we assume the law of excluded middle in which case they become equivalent law of non contradiction edit the law of noncontradiction was first formalized as a metaphysical principle by aristotle it states that a proposition and its negation cannot both be true equivalently it states that a proposition cannot be both true and false formally the law of non contradiction is written as q q and read as it is not the case that a proposition is both true and false the law of non contradiction neither follows nor is implied by the principle of proof by contradiction law of the excluded middle edit main article law of excluded middle proof by contradiction is equivalent to the law of the excluded middle also first formulated by aristotle which states that either an assertion or its negation is true p p combined with the principle of noncontradiction this means that exactly one of p and p is true proof by contradiction in intuitionistic logic edit in intuitionistic logic proof by contradiction is not generally valid although some particular instances can be derived in contrast proof of negation and principle of noncontradiction are both intuitionistically valid brouwer heyting kolmogorov interpretation of proof by contradiction gives the following intuitionistic validity condition if there is no method for establishing that a proposition is false then there is a method for establishing that the proposition is true if we take method to mean algorithm then the condition is not acceptable as it would allow us to solve the halting problem to see how consider the statement h m stating turing machine m halts or does not halt its negation h m states that m neither halts nor does not halt which is false by the law of noncontradiction which is intuitionistically valid if proof by contradiction were intuitionistically valid we would obtain an algorithm for deciding whether an arbitrary turing machine m halts thereby violating the intuitionistically valid proof of non solvability of the halting problem a proposition p which satisfies p p displaystyle lnot lnot p rightarrow p is known as a stable proposition thus in intuitionistic logic proof by contradiction is not universally valid but can only be applied to the stable propositions an instance of such a proposition is a decidable one i e satisfying p p displaystyle p lor lnot p indeed the above proof that the law of excluded middle implies proof by contradiction can be repurposed to show that a decidable proposition is stable a typical example of a decidable proposition is a statement that can be checked by direct computation such as n displaystyle n is prime or a displaystyle a divides b displaystyle b examples of proofs by contradiction edit euclid s elements edit an early occurrence of proof by contradiction can be found in euclid s elements book 1 proposition 6 4 if in a triangle two angles equal one another then the sides opposite the equal angles also equal one another the proof proceeds by assuming that the opposite angles are not equal and derives a contradiction hilbert s nullstellensatz edit an influential proof by contradiction was given by david hilbert his nullstellensatz states 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 hilbert proved the statement by assuming that there are no such polynomials g 1 g k displaystyle g_ 1 ldots g_ k and derived a contradiction 5 infinitude of primes edit euclid s theorem states that there are infinitely many primes in euclid s elements the theorem is stated in book ix proposition 20 6 prime numbers are more than any assigned multitude of prime numbers depending on how we formally write the above statement the usual proof takes either the form of a proof by contradiction or a refutation by contradiction we present here the former see below how the proof is done as refutation by contradiction if we formally express euclid s theorem as saying that for every natural number n displaystyle n there is a prime bigger than it then we employ proof by contradiction as follows given any number n displaystyle n we seek to prove that there is a prime larger than n displaystyle n suppose to the contrary that no such p exists an application of proof by contradiction then all primes are smaller than or equal to n displaystyle n and we may form the list p 1 p k displaystyle p_ 1 ldots p_ k of them all let p p 1 p k displaystyle p p_ 1 cdot ldots cdot p_ k be the product of all primes and q p 1 displaystyle q p 1 because q displaystyle q is larger than all prime numbers it is not prime hence it must be divisible by one of them say p i displaystyle p_ i now both p displaystyle p and q displaystyle q are divisible by p i displaystyle p_ i hence so is their difference q p 1 displaystyle q p 1 but this cannot be because 1 is not divisible by any primes hence we have a contradiction and so there is a prime number bigger than n displaystyle n examples of refutations by contradiction edit because proof by contradiction is frequently conflated with refutation by contradiction the following are often erroneously claimed to be proofs by contradiction but they really are refutations by contradiction and therefore intuitionistically valid 7 infinitude of primes edit let us take a second look at euclid s theorem book ix proposition 20 8 prime numbers are more than any assigned multitude of prime numbers we may read the statement as saying that for every finite list of primes there is another prime not on that list which is arguably closer to and in the same spirit as euclid s original formulation in this case euclid s proof applies refutation by contradiction at one step as follows consider any finite list of prime numbers p 1 p n displaystyle p_ 1 ldots p_ n it will be shown that at least one additional prime number not in this list exists let p p 1 p 2 p n displaystyle p p_ 1 cdot p_ 2 cdots p_ n be the product of all the prime numbers in the list and q p 1 displaystyle q p 1 then q displaystyle q is either prime or not if q displaystyle q is prime then q displaystyle q itself is a prime not in the list as it is greater than all primes in the list if q displaystyle q is not prime then it has a prime factor p displaystyle p we claim that p displaystyle p is not in the given list of primes suppose to the contrary that it were an application of refutation by contradiction then p displaystyle p would divide p displaystyle p and because it also divides q displaystyle q it divides their difference q p 1 displaystyle q p 1 this gives a contradiction since no prime number divides 1 thus p displaystyle p is a prime number not in the list irrationality of the square root of 2 edit the classic proof that the square root of 2 is irrational is a refutation by contradiction 9 indeed we set out to prove the negation a b n displaystyle mathbb n a b 2 by assuming that there exist natural numbers a and b whose ratio is the square root of two and derive a contradiction proof by infinite descent edit proof by infinite descent is a method of proof whereby a smallest object with desired property is shown not to exist as follows assume that there is a smallest object with the desired property demonstrate that an even smaller object with the desired property exists thereby deriving a contradiction such a proof is not a proof by contradiction but once again a refutation by contradiction a typical example is the proof of the proposition there is no smallest positive rational number assume there is a smallest positive rational number q and derive a contradiction by observing that q 2 is even smaller than q and still positive russell s paradox edit russell s paradox stated set theoretically as there is no set whose elements are precisely those sets that do not contain themselves is a negated statement whose usual proof is a refutation by contradiction notation edit proofs by contradiction sometimes end with the word contradiction isaac barrow and baermann used the notation q e a for quod est absurdum which is absurd along the lines of q e d but this notation is rarely used today 10 a graphical symbol sometimes used for contradictions is a downwards zigzag arrow lightning symbol u 21af for example in davey and priestley 11 others sometimes used include a pair of opposing arrows as displaystyle rightarrow leftarrow citation needed or displaystyle rightarrow leftarrow citation needed struck out arrows displaystyle nleftrightarrow citation needed a stylized form of hash such as u 2a33 citation needed or the reference mark u 203b citation needed or displaystyle times times 12 13 hardy s view edit g h hardy described proof by contradiction as one of a mathematician s finest weapons saying it is a far finer gambit than any chess gambit a chess player may offer the sacrifice of a pawn or even a piece but a mathematician offers the game 14 see also edit law of excluded middle law of noncontradiction proof by exhaustion proof by infinite descent modus tollens references edit reductio ad absurdum logic encyclopedia britannica retrieved 2019 10 25 proof by contradiction nlab retrieved 7 october 2022 bauer andrej 29 march 2010 proof of negation and proof by contradiction mathematics and computation retrieved 26 october 2021 euclid s elements book 6 proposition 1 retrieved 2 october 2022 hilbert david 1893 ueber die vollen invariantensysteme mathematische annalen 42 3 313 373 doi 10 1007 bf01444162 euclid s elements book 9 proposition 20 retrieved 2 october 2022 bauer andrej 2017 five stages of accepting constructive mathematics bull amer math soc 54 2017 481 498 retrieved 2 october 2022 euclid s elements book 9 proposition 20 retrieved 2 october 2022 alfeld peter 16 august 1996 why is the square root of 2 irrational understanding mathematics a study guide department of mathematics university of utah retrieved 6 february 2013 math forum discussions b davey and h a priestley introduction to lattices and order cambridge university press 2002 see notation index p 286 gary hardegree introduction to modal logic chapter 2 pg ii 2 https web archive org web 20110607061046 http people umass edu gmhwww 511 pdf c02 pdf the comprehensive latex symbol list pg 20 http www ctan org tex archive info symbols comprehensive symbols a4 pdf g h hardy a mathematician s apology cambridge university press 1992 isbn 9780521427067 pdf p 19 further reading and external links edit the wikibook mathematical proof has a page on the topic of proof by contradiction franklin james daoud albert 2011 proof in mathematics an introduction chapter 6 kew isbn 978 0 646 54509 7 cite book cs1 maint location link proof by contradiction from larry w cusick s how to write proofs reductio ad absurdum internet encyclopedia of philosophy issn 2161 0002 v t e mathematical logic general axiom list cardinality first order logic formal proof formal semantics foundations of mathematics information theory logical consequence model set theorem theory type theory theorems list paradoxes gödel s completeness and incompleteness theorems tarski s undefinability banach tarski paradox cantor s theorem paradox and diagonal argument compactness halting problem lindström s löwenheim skolem russell s paradox logics traditional classical logic logical truth tautology proposition inference logical equivalence consistency equiconsistency argument soundness validity syllogism square of opposition venn diagram propositional boolean algebra boolean functions logical connectives propositional calculus propositional formula truth tables many valued logic 3 finite predicate first order second order monadic higher order free quantifiers predicate monadic predicate calculus set theory set hereditary class ur element ordered pair ordinal number subset equality extensionality forcing relation equivalence partition set operations intersection union complement cartesian product power set identities types of sets countable uncountable empty inhabited singleton finite infinite transitive ultrafilter recursive fuzzy universal universe constructible grothendieck von neumann maps cardinality function map domain codomain image in sur bi jection schröder bernstein theorem isomorphism gödel numbering enumeration large cardinal inaccessible aleph number operation binary set theories zermelo fraenkel axiom of choice continuum hypothesis general kripke platek morse kelley naive new foundations tarski grothendieck von neumann bernays gödel constructive syntax language alphabet arity automata axiom schema expression ground extension relation formal grammar language proof system theory formation rule formula atomic closed ground open free bound variable metalanguage logical connective predicate functional variable propositional variable quantifier rank sentence atomic signature string substitution symbol function logical constant non logical variable term example axiomatic systems list of arithmetic peano second order elementary function primitive recursive robinson skolem of the real numbers tarski s axiomatization of boolean algebras canonical minimal axioms of geometry euclidean elements hilbert s non euclidean tarski s principia mathematica proof theory formal proof natural deduction logical consequence rule of inference sequent calculus theorem systems formal axiomatic deductive hilbert list complete theory independence from zfc proof of impossibility ordinal analysis reverse mathematics self verifying theories model theory interpretation model equivalence finite saturated substructure non standard model of arithmetic diagram elementary categorical theory model complete theory satisfiability semantics of logic strength theories of truth semantic tarski s kripke s t schema transfer principle truth predicate truth value type ultraproduct validity computability theory church encoding church turing thesis computably enumerable computable function computable set decision problem decidable undecidable p np p versus np problem kolmogorov complexity lambda calculus primitive recursive function recursion recursive s...