4793:
994:
791:
1181:. 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 "
60:
More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved. In this general sense, proof by contradiction is also known as
595:
1538:
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.
2509:
is based on proof by contradiction. That is, in order to show that a given statement is entailed by given hypotheses, the automated prover assumes the hypotheses and the negation of the statement, and attempts to derive a contradiction.
2379:, but this notation is rarely used today. A graphical symbol sometimes used for contradictions is a downwards zigzag arrow "lightning" symbol (U+21AF: ↯), for example in Davey and Priestley. Others sometimes used include a pair of
876:
Formally these are not the same, as refutation by contradiction applies only when the proposition to be proved is negated, whereas proof by contradiction may be applied to any proposition whatsoever. In classical logic, where
1952:
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
1152:. 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
2321:
Such a proof is 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
2587:
230:
1058:
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.
333:
2359:, 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.
1464:
1725:
2063:
965:. It posits that a proposition and its negation cannot both be true, or equivalently, that a proposition cannot be both true and false. Formally the law of non-contradiction is written as
135:
by contradiction: in order to demonstrate that an object with a given property exists, we derive a contradiction from the assumption that all objects satisfy the negation of the property.
1146:
2429:
2405:
786:{\displaystyle {\cfrac {{\cfrac {{\cfrac {\ }{\Gamma ,P\vdash P,\Delta }}\;(I)}{\Gamma ,\vdash \lnot P,P,\Delta }}\;({\lnot }R)}{\Gamma ,\lnot \lnot P\vdash P,\Delta }}\;({\lnot }L)}
2476:
969:
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.
2004:
1673:
1513:
1392:
1330:
2449:
3172:
1179:
1101:(which is intuitionistically valid). If proof by contradiction were intuitionistically valid, we would obtain an algorithm for deciding whether an arbitrary Turing machine
1061:
384:
259:
2281:
1932:
The following examples are commonly referred to as proofs by contradiction, but formally employ refutation by contradiction (and therefore are intuitionistically valid).
921:
3847:
426:
356:
1903:
1871:
1804:
1757:
2225:
2139:
2113:
2245:
2199:
2179:
2159:
2083:
1923:
1844:
1824:
1777:
1627:
1603:
1583:
1560:
1239:
1219:
1199:
895:
404:
279:
3930:
3071:
923:
may be freely interchanged, the distinction is largely obscured. Thus in mathematical practice, both principles are referred to as "proof by contradiction".
2931:
4827:
1015:
4244:
4402:
3008:
2968:
2672:
3190:
4257:
3580:
1066:
if there is no method for establishing that a proposition is false, then there is a method for establishing that the proposition is true.
1905:, 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
3842:
4262:
4252:
3989:
3195:
2869:
3740:
3186:
4398:
2923:
2575:
1041:
4495:
4239:
3064:
3800:
3493:
3234:
2161:
is not in the given list of primes. Suppose to the contrary that it were (an application of refutation by contradiction). Then
178:
4756:
4458:
4221:
4216:
4041:
3462:
3146:
1019:
2887:
294:
4751:
4534:
4451:
4164:
4095:
3972:
3214:
3822:
2489:
described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any
4817:
4676:
4502:
4188:
3421:
3024:
2994:
2915:
1279:
3827:
4159:
3898:
3156:
3057:
1397:
4554:
4549:
1678:
1004:
2009:
4483:
4073:
3467:
3435:
3126:
516:
3200:
2686:
1023:
1008:
4822:
4773:
4722:
4619:
4117:
4078:
3555:
2534:
2502:
2307:
50:
4614:
3229:
1119:
4544:
4083:
3935:
3918:
3641:
3121:
2410:
2386:
1262:
If in a triangle two angles equal one another, then the sides opposite the equal angles also equal one another.
2928:
4446:
4423:
4384:
4270:
4211:
3857:
3777:
3621:
3565:
3178:
2899:
2524:
2454:
1098:
958:
551:
113:
2317:
Demonstrate that an even smaller object with the desired property exists, thereby deriving a contradiction.
4736:
4463:
4441:
4408:
4301:
4147:
4132:
4105:
4056:
3940:
3875:
3700:
3666:
3661:
3535:
3366:
3343:
2519:
2493:: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."
938:
932:
578:. It turns out that, conversely, proof by contradiction can be used to derive the law of excluded middle.
563:
1963:
1632:
1472:
1351:
1289:
4666:
4519:
4311:
4029:
3765:
3671:
3530:
3515:
3396:
3371:
2743:
144:
54:
4792:
2434:
2310:
is a method of proof whereby a smallest object with desired property is shown not to exist as follows:
4639:
4601:
4478:
4282:
4122:
4046:
4024:
3852:
3810:
3709:
3676:
3540:
3328:
3239:
2544:
2356:
1527:
1255:
1055:
104:
implies falsehood. This is typically accomplished by deriving two mutually contradictory assertions,
3031:
4768:
4659:
4644:
4624:
4581:
4468:
4418:
4344:
4289:
4226:
4019:
4014:
3962:
3730:
3719:
3391:
3291:
3219:
3210:
3206:
3141:
3136:
2529:
1954:
1941:
1523:
1266:
The proof proceeds by assuming that the opposite sides are not equal, and derives a contradiction.
1155:
363:
238:
2773:
2264:
4797:
4566:
4529:
4514:
4507:
4490:
4276:
4142:
4068:
4051:
4004:
3817:
3726:
3560:
3545:
3505:
3457:
3442:
3430:
3386:
3361:
3131:
3080:
3018:
2506:
1779:
is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say
1345:
900:
30:
4294:
3750:
2737:
1609:
exists (an application of proof by contradiction). Then all primes are smaller than or equal to
2711:
4732:
4539:
4349:
4339:
4231:
4112:
3947:
3923:
3704:
3688:
3593:
3570:
3447:
3416:
3381:
3276:
3111:
3004:
2964:
2919:
2668:
2571:
449:
170:
166:
411:
341:
4746:
4741:
4634:
4591:
4413:
4374:
4369:
4354:
4180:
4137:
4034:
3832:
3782:
3356:
3318:
2956:
2807:
2752:
2637:
2256:
586:
582:
285:
38:
1876:
1849:
1782:
1730:
4727:
4717:
4671:
4654:
4609:
4571:
4473:
4393:
4200:
4127:
4100:
4088:
3994:
3908:
3882:
3837:
3805:
3606:
3408:
3351:
3301:
3266:
3224:
2935:
2006:, it will be shown that at least one additional prime number not in this list exists. Let
1106:
1075:
437:
132:
3035:
2888:
https://web.archive.org/web/20110607061046/http://people.umass.edu/gmhwww/511/pdf/c02.pdf
2854:
2204:
2118:
2092:
2612:
2451:), a stylized form of hash (such as U+2A33: ⨳), or the "reference mark" (U+203B: ※), or
1105:
halts, thereby violating the (intuitionistically valid) proof of non-solvability of the
4712:
4691:
4649:
4629:
4524:
4379:
3977:
3967:
3957:
3952:
3886:
3760:
3636:
3525:
3520:
3498:
3099:
2230:
2184:
2164:
2144:
2068:
1908:
1829:
1809:
1762:
1612:
1588:
1568:
1545:
1341:
1224:
1204:
1184:
1083:
880:
389:
264:
4811:
4686:
4364:
3871:
3656:
3646:
3616:
3601:
3271:
2960:
2732:
2539:
1275:
46:
2948:
2663:
1562:
there is a prime bigger than it, then we employ proof by contradiction, as follows.
972:
The laws of excluded middle and non-contradiction together mean that exactly one of
4586:
4433:
4334:
4326:
4206:
4154:
4063:
3999:
3982:
3913:
3772:
3631:
3333:
3116:
2380:
2368:
2086:
78:
A mathematical proof employing proof by contradiction usually proceeds as follows:
1064:
of proof by contradiction gives the following intuitionistic validity condition:
4696:
4576:
3755:
3745:
3692:
3376:
3296:
3281:
3161:
3106:
2998:
2910:
2486:
1542:
If we formally express Euclid's theorem as saying that for every natural number
993:
441:
42:
3626:
3481:
3452:
3258:
1333:
4778:
4681:
3734:
3651:
3611:
3575:
3511:
3323:
3313:
3286:
2828:
1469:
Hilbert proved the statement by assuming that there are no such polynomials
1071:
962:
942:
2259:
is a refutation by contradiction. Indeed, we set out to prove the negation
1074:, then the condition is not acceptable, as it would allow us to solve the
4763:
4561:
4009:
3714:
3308:
2900:
http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf
811:
2812:
2795:
4359:
3151:
2756:
2367:
Proofs by contradiction sometimes end with the word "Contradiction!".
3049:
2490:
2376:
49:. Although it is quite freely used in mathematical proofs, not every
1948:
Prime numbers are more than any assigned multitude of prime numbers.
1534:
Prime numbers are more than any assigned multitude of prime numbers.
3040:
2299:
whose ratio is the square root of two, and derive a contradiction.
3903:
3249:
3094:
34:
22:
2873:, Cambridge University Press, 2002; see "Notation Index", p. 286.
2314:
Assume that there is a smallest object with the desired property.
945:, which states that either an assertion or its negation is true,
45:
by showing that assuming the proposition to be false leads to a
3053:
2247:. This gives a contradiction, since no prime number divides 1.
1254:
An early occurrence of proof by contradiction can be found in
987:
515:
Another way to justify the principle is to derive it from the
1957:
applies refutation by contradiction at one step, as follows.
123:
to be false leads to a contradiction, it is concluded that
847:
In contrast, proof by contradiction proceeds as follows:
440:
the principle may be justified by the examination of the
225:{\displaystyle {\cfrac {\vdash \lnot \lnot P}{\vdash P}}}
1097:
neither halts nor does not halt", which is false by the
731:
675:
630:
618:
610:
602:
206:
185:
734:
678:
633:
621:
613:
605:
209:
188:
2457:
2437:
2413:
2389:
2267:
2233:
2207:
2187:
2167:
2147:
2121:
2095:
2071:
2012:
1966:
1911:
1879:
1852:
1832:
1812:
1785:
1765:
1733:
1681:
1635:
1615:
1591:
1585:, we seek to prove that there is a prime larger than
1571:
1548:
1475:
1400:
1354:
1292:
1227:
1207:
1187:
1158:
1122:
903:
883:
598:
414:
392:
366:
344:
328:{\displaystyle \Gamma ,\lnot \lnot P\vdash P,\Delta }
297:
267:
241:
181:
4705:
4600:
4432:
4325:
4177:
3870:
3793:
3687:
3591:
3480:
3407:
3342:
3257:
3248:
3170:
3087:
3043:
2796:"Five stages of accepting constructive mathematics"
2768:
2766:
1274:An influential proof by contradiction was given by
2736:
2470:
2443:
2423:
2399:
2275:
2239:
2219:
2193:
2173:
2153:
2133:
2107:
2077:
2057:
1998:
1917:
1897:
1865:
1838:
1818:
1798:
1771:
1751:
1719:
1667:
1621:
1597:
1577:
1554:
1530:the theorem is stated in Book IX, Proposition 20:
1507:
1458:
1386:
1324:
1233:
1213:
1193:
1173:
1140:
915:
889:
785:
420:
398:
378:
350:
327:
273:
253:
224:
2464:
2463:
2462:
2461:
2417:
2393:
1526:states that there are infinitely many primes. In
1459:{\displaystyle f_{1}g_{1}+\ldots +f_{k}g_{k}=1.}
961:was first stated as a metaphysical principle by
550:holds, then we derive falsehood by applying the
2835:. Department of Mathematics, University of Utah
1720:{\displaystyle P=p_{1}\cdot \ldots \cdot p_{k}}
143:The principle may be formally expressed as the
2898:The Comprehensive LaTeX Symbol List, pg. 20.
2687:"Proof of negation and proof by contradiction"
2058:{\displaystyle P=p_{1}\cdot p_{2}\cdots p_{n}}
984:Proof by contradiction in intuitionistic logic
3065:
2800:Bulletin of the American Mathematical Society
2326:and derive a contradiction by observing that
2291:by assuming that there exist natural numbers
2257:proof that the square root of 2 is irrational
585:proof by contradiction is derivable from the
8:
2371:and Baermann used the notation Q.E.A., for "
2227:, therefore also their difference, which is
2065:be the product of all the listed primes and
937:Proof by contradiction is equivalent to the
2774:"Euclid's Elements, Book 9, Proposition 20"
1344:coefficients, which have no common complex
1022:. Unsourced material may be challenged and
3891:
3486:
3254:
3072:
3058:
3050:
2712:"Euclid's Elements, Book 6, Proposition 1"
2375:" ("which is absurd"), along the lines of
1141:{\displaystyle \lnot \lnot P\Rightarrow P}
768:
712:
661:
288:the principle is expressed by the sequent
2829:"Why is the square root of 2 irrational?"
2811:
2456:
2436:
2424:{\displaystyle \Rightarrow \!\Leftarrow }
2412:
2400:{\displaystyle \rightarrow \!\leftarrow }
2388:
2269:
2268:
2266:
2232:
2206:
2186:
2166:
2146:
2120:
2094:
2070:
2049:
2036:
2023:
2011:
1990:
1971:
1965:
1910:
1878:
1857:
1851:
1831:
1811:
1790:
1784:
1764:
1732:
1711:
1692:
1680:
1659:
1640:
1634:
1614:
1590:
1570:
1547:
1499:
1480:
1474:
1444:
1434:
1415:
1405:
1399:
1378:
1359:
1353:
1316:
1297:
1291:
1226:
1206:
1186:
1157:
1121:
1062:Brouwer–Heyting–Kolmogorov interpretation
1042:Learn how and when to remove this message
902:
882:
772:
735:
716:
679:
634:
622:
615:
614:
607:
606:
599:
597:
413:
391:
365:
343:
296:
266:
240:
210:
189:
182:
180:
2955:, The MIT Press, pp. 93–120, 1994,
2833:Understanding Mathematics, a study guide
1928:Examples of refutations by contradiction
797:Relationship with other proof techniques
454:
2559:
1960:Given any finite list of prime numbers
1605:. Suppose to the contrary that no such
16:Proving that the negation is impossible
3016:
2471:{\displaystyle \times \!\!\!\!\times }
1089:halts or does not halt". Its negation
3000:Proof in Mathematics: An Introduction
2738:"Ueber die vollen Invariantensysteme"
2251:Irrationality of the square root of 2
1078:. To see how, consider the statement
806:Proof by contradiction is similar to
7:
2918:; Cambridge University Press, 1992.
2568:Foundations of Constructive Analysis
1020:adding citations to reliable sources
169:the principle takes the form of the
158:to be false implies falsehood, then
1999:{\displaystyle p_{1},\ldots ,p_{n}}
1668:{\displaystyle p_{1},\ldots ,p_{k}}
1508:{\displaystyle g_{1},\ldots ,g_{k}}
1387:{\displaystyle g_{1},\ldots ,g_{k}}
1325:{\displaystyle f_{1},\ldots ,f_{k}}
1245:Examples of proofs by contradiction
2988:Further reading and external links
2870:Introduction to Lattices and Order
1165:
1126:
1123:
907:
904:
773:
760:
745:
742:
736:
717:
704:
689:
680:
653:
635:
415:
370:
367:
345:
322:
307:
304:
298:
245:
242:
196:
193:
14:
2444:{\displaystyle \nleftrightarrow }
1727:be the product of all primes and
131:An important special case is the
4791:
2827:Alfeld, Peter (16 August 1996).
992:
851:The proposition to be proved is
822:The proposition to be proved is
527:. By the law of excluded middle
448:, which demonstrates it to be a
82:The proposition to be proved is
4828:Theorems in propositional logic
2953:From Logic to Logic Programming
2685:Bauer, Andrej (29 March 2010).
1873:, hence so is their difference
1269:
574:In either case, we established
2961:10.7551/mitpress/3133.003.0007
2613:"Reductio ad absurdum | logic"
2418:
2414:
2394:
2390:
1132:
780:
769:
724:
713:
668:
662:
67:proof by assuming the opposite
51:school of mathematical thought
1:
4752:History of mathematical logic
2867:B. Davey and H.A. Priestley,
1940:Let us take a second look at
1515:and derived a contradiction.
1348:, then there are polynomials
1174:{\displaystyle P\lor \lnot P}
583:classical sequent calculus LK
531:either holds or it does not:
379:{\displaystyle \lnot \lnot P}
254:{\displaystyle \lnot \lnot P}
93:to be false, i.e., we assume
4677:Primitive recursive function
2675:; see "Chapter 9: Disproof".
2570:, New York: Academic Press.
2276:{\displaystyle \mathbb {N} }
1070:If we take "method" to mean
154:, which reads: "If assuming
2884:Introduction to Modal Logic
2691:Mathematics and Computation
1944:– Book IX, Proposition 20:
1629:, and we may form the list
916:{\displaystyle \neg \neg P}
808:refutation by contradiction
802:Refutation by contradiction
4844:
3741:Schröder–Bernstein theorem
3468:Monadic predicate calculus
3127:Foundations of mathematics
939:law of the excluded middle
930:
927:Law of the excluded middle
517:law of the excluded middle
4787:
4774:Philosophy of mathematics
4723:Automated theorem proving
3894:
3848:Von Neumann–Bernays–Gödel
3489:
2916:A Mathematician's Apology
2535:Proof by infinite descent
2503:automated theorem proving
2497:Automated theorem proving
2308:Proof by infinite descent
2303:Proof by infinite descent
1270:Hilbert's Nullstellensatz
1258:, Book 1, Proposition 6:
338:which reads: "Hypotheses
3023:: CS1 maint: location (
2997:; Daoud, Albert (2011).
2886:, Chapter 2, pg. II–2.
2855:"Math Forum Discussions"
2638:"Proof by contradiction"
2588:"Proof By Contradiction"
1249:
953:Law of non-contradiction
519:, as follows. We assume
4424:Self-verifying theories
4245:Tarski's axiomatization
3196:Tarski's undefinability
3191:incompleteness theorems
3034:from Larry W. Cusick's
2617:Encyclopedia Britannica
2525:Law of noncontradiction
2351:
1099:law of noncontradiction
959:law of noncontradiction
552:law of noncontradiction
421:{\displaystyle \Delta }
351:{\displaystyle \Gamma }
114:law of noncontradiction
112:, and appealing to the
72:reductio ad impossibile
4798:Mathematics portal
4409:Proof of impossibility
4057:propositional variable
3367:Propositional calculus
3032:Proof by Contradiction
2794:Bauer, Andrej (2017).
2566:Bishop, Errett 1967.
2520:Law of excluded middle
2472:
2445:
2431:), struck-out arrows (
2425:
2401:
2277:
2241:
2221:
2195:
2175:
2155:
2141:itself. We claim that
2135:
2109:
2079:
2059:
2000:
1919:
1899:
1867:
1840:
1820:
1800:
1773:
1753:
1721:
1669:
1623:
1599:
1579:
1556:
1509:
1460:
1388:
1326:
1235:
1215:
1195:
1175:
1142:
941:, first formulated by
933:Law of excluded middle
917:
891:
818:is proved as follows:
787:
566:allows us to conclude
564:principle of explosion
539:holds, then of course
422:
400:
386:entail the conclusion
380:
352:
329:
275:
255:
226:
100:It is then shown that
57:as universally valid.
27:proof by contradiction
4667:Kolmogorov complexity
4620:Computably enumerable
4520:Model complete theory
4312:Principia Mathematica
3372:Propositional formula
3201:Banach–Tarski paradox
2744:Mathematische Annalen
2667:, 3rd edition, 2022,
2473:
2446:
2426:
2402:
2344:is even smaller than
2278:
2242:
2222:
2196:
2176:
2156:
2136:
2110:
2080:
2060:
2001:
1920:
1900:
1898:{\displaystyle Q-P=1}
1868:
1866:{\displaystyle p_{i}}
1841:
1821:
1801:
1799:{\displaystyle p_{i}}
1774:
1754:
1752:{\displaystyle Q=P+1}
1722:
1670:
1624:
1600:
1580:
1557:
1510:
1461:
1389:
1327:
1236:
1216:
1196:
1176:
1150:¬¬-stable proposition
1143:
918:
892:
788:
423:
401:
381:
353:
330:
276:
256:
227:
145:propositional formula
55:nonconstructive proof
53:accepts this kind of
33:that establishes the
4615:Church–Turing thesis
4602:Computability theory
3811:continuum hypothesis
3329:Square of opposition
3187:Gödel's completeness
3041:Reductio ad Absurdum
2545:Reductio ad absurdum
2481:
2455:
2435:
2411:
2387:
2348:and still positive.
2265:
2231:
2205:
2185:
2165:
2145:
2119:
2093:
2069:
2010:
1964:
1936:Infinitude of primes
1909:
1877:
1850:
1830:
1810:
1783:
1763:
1731:
1679:
1633:
1613:
1589:
1569:
1546:
1519:Infinitude of primes
1473:
1398:
1352:
1340:indeterminates with
1290:
1225:
1205:
1185:
1156:
1120:
1056:intuitionistic logic
1016:improve this section
901:
881:
814:, which states that
596:
412:
390:
364:
342:
295:
265:
239:
179:
4818:Mathematical proofs
4769:Mathematical object
4660:P versus NP problem
4625:Computable function
4419:Reverse mathematics
4345:Logical consequence
4222:primitive recursive
4217:elementary function
3990:Free/bound variable
3843:Tarski–Grothendieck
3362:Logical connectives
3292:Logical equivalence
3142:Logical consequence
3036:How To Write Proofs
2949:"Linear Resolution"
2530:Proof by exhaustion
2220:{\displaystyle P+1}
2134:{\displaystyle P+1}
2108:{\displaystyle P+1}
733:
677:
632:
620:
612:
604:
444:of the proposition
281:may be concluded."
208:
187:
4567:Transfer principle
4530:Semantics of logic
4515:Categorical theory
4491:Non-standard model
4005:Logical connective
3132:Information theory
3081:Mathematical logic
3003:. chapter 6: Kew.
2934:2021-02-16 at the
2757:10.1007/BF01444162
2468:
2441:
2421:
2397:
2273:
2237:
2217:
2191:
2181:would divide both
2171:
2151:
2131:
2105:
2075:
2055:
1996:
1915:
1895:
1863:
1836:
1816:
1796:
1769:
1749:
1717:
1665:
1619:
1595:
1575:
1552:
1505:
1456:
1384:
1322:
1231:
1211:
1191:
1171:
1138:
913:
887:
783:
764:
728:
708:
672:
657:
627:
562:, after which the
523:and seek to prove
418:
396:
376:
348:
325:
271:
251:
222:
218:
203:
4805:
4804:
4737:Abstract category
4540:Theories of truth
4350:Rule of inference
4340:Natural deduction
4321:
4320:
3866:
3865:
3571:Cartesian product
3476:
3475:
3382:Many-valued logic
3357:Boolean functions
3240:Russell's paradox
3215:diagonal argument
3112:First-order logic
3010:978-0-646-54509-7
2970:978-0-262-28847-7
2813:10.1090/bull/1556
2673:978-0-9894721-2-8
2661:Richard Hammack,
2373:quod est absurdum
2357:Russell's paradox
2352:Russell's paradox
2240:{\displaystyle 1}
2194:{\displaystyle P}
2174:{\displaystyle p}
2154:{\displaystyle p}
2078:{\displaystyle p}
1918:{\displaystyle n}
1846:are divisible by
1839:{\displaystyle Q}
1819:{\displaystyle P}
1772:{\displaystyle Q}
1675:of them all. Let
1622:{\displaystyle n}
1598:{\displaystyle n}
1578:{\displaystyle n}
1565:Given any number
1555:{\displaystyle n}
1528:Euclid's Elements
1256:Euclid's Elements
1250:Euclid's Elements
1234:{\displaystyle b}
1214:{\displaystyle a}
1194:{\displaystyle n}
1052:
1051:
1044:
890:{\displaystyle P}
865:Derive falsehood.
836:Derive falsehood.
812:proof of negation
766:
732:
710:
676:
659:
631:
625:
619:
611:
603:
513:
512:
399:{\displaystyle P}
274:{\displaystyle P}
235:which reads: "If
220:
207:
186:
171:rule of inference
167:natural deduction
4835:
4823:Methods of proof
4796:
4795:
4747:History of logic
4742:Category of sets
4635:Decision problem
4414:Ordinal analysis
4355:Sequent calculus
4253:Boolean algebras
4193:
4192:
4167:
4138:logical/constant
3892:
3878:
3801:Zermelo–Fraenkel
3552:Set operations:
3487:
3424:
3255:
3235:Löwenheim–Skolem
3122:Formal semantics
3074:
3067:
3060:
3051:
3028:
3022:
3014:
2981:
2980:
2979:
2977:
2945:
2939:
2908:
2902:
2896:
2890:
2882:Gary Hardegree,
2880:
2874:
2865:
2859:
2858:
2851:
2845:
2844:
2842:
2840:
2824:
2818:
2817:
2815:
2791:
2785:
2784:
2782:
2780:
2770:
2761:
2760:
2740:
2729:
2723:
2722:
2720:
2718:
2708:
2702:
2701:
2699:
2697:
2682:
2676:
2659:
2653:
2652:
2650:
2648:
2634:
2628:
2627:
2625:
2623:
2609:
2603:
2602:
2600:
2598:
2584:
2578:
2564:
2477:
2475:
2474:
2469:
2450:
2448:
2447:
2442:
2430:
2428:
2427:
2422:
2406:
2404:
2403:
2398:
2343:
2341:
2340:
2337:
2334:
2289:
2288:
2282:
2280:
2279:
2274:
2272:
2246:
2244:
2243:
2238:
2226:
2224:
2223:
2218:
2200:
2198:
2197:
2192:
2180:
2178:
2177:
2172:
2160:
2158:
2157:
2152:
2140:
2138:
2137:
2132:
2114:
2112:
2111:
2106:
2084:
2082:
2081:
2076:
2064:
2062:
2061:
2056:
2054:
2053:
2041:
2040:
2028:
2027:
2005:
2003:
2002:
1997:
1995:
1994:
1976:
1975:
1942:Euclid's theorem
1924:
1922:
1921:
1916:
1904:
1902:
1901:
1896:
1872:
1870:
1869:
1864:
1862:
1861:
1845:
1843:
1842:
1837:
1825:
1823:
1822:
1817:
1805:
1803:
1802:
1797:
1795:
1794:
1778:
1776:
1775:
1770:
1758:
1756:
1755:
1750:
1726:
1724:
1723:
1718:
1716:
1715:
1697:
1696:
1674:
1672:
1671:
1666:
1664:
1663:
1645:
1644:
1628:
1626:
1625:
1620:
1604:
1602:
1601:
1596:
1584:
1582:
1581:
1576:
1561:
1559:
1558:
1553:
1524:Euclid's theorem
1514:
1512:
1511:
1506:
1504:
1503:
1485:
1484:
1465:
1463:
1462:
1457:
1449:
1448:
1439:
1438:
1420:
1419:
1410:
1409:
1393:
1391:
1390:
1385:
1383:
1382:
1364:
1363:
1339:
1331:
1329:
1328:
1323:
1321:
1320:
1302:
1301:
1240:
1238:
1237:
1232:
1220:
1218:
1217:
1212:
1200:
1198:
1197:
1192:
1180:
1178:
1177:
1172:
1147:
1145:
1144:
1139:
1116:which satisfies
1067:
1047:
1040:
1036:
1033:
1027:
996:
988:
922:
920:
919:
914:
896:
894:
893:
888:
810:, also known as
792:
790:
789:
784:
776:
767:
765:
763:
729:
727:
720:
711:
709:
707:
673:
671:
660:
658:
656:
628:
626:
623:
616:
608:
600:
481:
474:
467:
455:
427:
425:
424:
419:
405:
403:
402:
397:
385:
383:
382:
377:
357:
355:
354:
349:
334:
332:
331:
326:
286:sequent calculus
280:
278:
277:
272:
261:is proved, then
260:
258:
257:
252:
231:
229:
228:
223:
221:
219:
217:
204:
202:
183:
127:is in fact true.
4843:
4842:
4838:
4837:
4836:
4834:
4833:
4832:
4808:
4807:
4806:
4801:
4790:
4783:
4728:Category theory
4718:Algebraic logic
4701:
4672:Lambda calculus
4610:Church encoding
4596:
4572:Truth predicate
4428:
4394:Complete theory
4317:
4186:
4182:
4178:
4173:
4165:
3885: and
3881:
3876:
3862:
3838:New Foundations
3806:axiom of choice
3789:
3751:Gödel numbering
3691: and
3683:
3587:
3472:
3422:
3403:
3352:Boolean algebra
3338:
3302:Equiconsistency
3267:Classical logic
3244:
3225:Halting problem
3213: and
3189: and
3177: and
3176:
3171:Theorems (
3166:
3083:
3078:
3047:
3015:
3011:
2995:Franklin, James
2993:
2990:
2985:
2984:
2975:
2973:
2971:
2947:
2946:
2942:
2936:Wayback Machine
2909:
2905:
2897:
2893:
2881:
2877:
2866:
2862:
2853:
2852:
2848:
2838:
2836:
2826:
2825:
2821:
2793:
2792:
2788:
2778:
2776:
2772:
2771:
2764:
2731:
2730:
2726:
2716:
2714:
2710:
2709:
2705:
2695:
2693:
2684:
2683:
2679:
2660:
2656:
2646:
2644:
2636:
2635:
2631:
2621:
2619:
2611:
2610:
2606:
2596:
2594:
2586:
2585:
2581:
2565:
2561:
2556:
2550:
2516:
2499:
2484:
2453:
2452:
2433:
2432:
2409:
2408:
2385:
2384:
2381:opposing arrows
2365:
2354:
2338:
2335:
2330:
2329:
2327:
2305:
2286:
2284:
2263:
2262:
2253:
2229:
2228:
2203:
2202:
2183:
2182:
2163:
2162:
2143:
2142:
2117:
2116:
2091:
2090:
2067:
2066:
2045:
2032:
2019:
2008:
2007:
1986:
1967:
1962:
1961:
1938:
1930:
1907:
1906:
1875:
1874:
1853:
1848:
1847:
1828:
1827:
1808:
1807:
1786:
1781:
1780:
1761:
1760:
1729:
1728:
1707:
1688:
1677:
1676:
1655:
1636:
1631:
1630:
1611:
1610:
1587:
1586:
1567:
1566:
1544:
1543:
1521:
1495:
1476:
1471:
1470:
1440:
1430:
1411:
1401:
1396:
1395:
1374:
1355:
1350:
1349:
1337:
1312:
1293:
1288:
1287:
1280:Nullstellensatz
1272:
1252:
1247:
1223:
1222:
1203:
1202:
1183:
1182:
1154:
1153:
1118:
1117:
1107:Halting problem
1076:Halting problem
1065:
1048:
1037:
1031:
1028:
1013:
997:
986:
955:
935:
929:
899:
898:
879:
878:
804:
799:
730:
674:
629:
617:
609:
601:
594:
593:
587:inference rules
477:
470:
463:
438:classical logic
434:
410:
409:
388:
387:
362:
361:
340:
339:
293:
292:
263:
262:
237:
236:
205:
184:
177:
176:
150:, equivalently
141:
133:existence proof
119:Since assuming
17:
12:
11:
5:
4841:
4839:
4831:
4830:
4825:
4820:
4810:
4809:
4803:
4802:
4788:
4785:
4784:
4782:
4781:
4776:
4771:
4766:
4761:
4760:
4759:
4749:
4744:
4739:
4730:
4725:
4720:
4715:
4713:Abstract logic
4709:
4707:
4703:
4702:
4700:
4699:
4694:
4692:Turing machine
4689:
4684:
4679:
4674:
4669:
4664:
4663:
4662:
4657:
4652:
4647:
4642:
4632:
4630:Computable set
4627:
4622:
4617:
4612:
4606:
4604:
4598:
4597:
4595:
4594:
4589:
4584:
4579:
4574:
4569:
4564:
4559:
4558:
4557:
4552:
4547:
4537:
4532:
4527:
4525:Satisfiability
4522:
4517:
4512:
4511:
4510:
4500:
4499:
4498:
4488:
4487:
4486:
4481:
4476:
4471:
4466:
4456:
4455:
4454:
4449:
4442:Interpretation
4438:
4436:
4430:
4429:
4427:
4426:
4421:
4416:
4411:
4406:
4396:
4391:
4390:
4389:
4388:
4387:
4377:
4372:
4362:
4357:
4352:
4347:
4342:
4337:
4331:
4329:
4323:
4322:
4319:
4318:
4316:
4315:
4307:
4306:
4305:
4304:
4299:
4298:
4297:
4292:
4287:
4267:
4266:
4265:
4263:minimal axioms
4260:
4249:
4248:
4247:
4236:
4235:
4234:
4229:
4224:
4219:
4214:
4209:
4196:
4194:
4175:
4174:
4172:
4171:
4170:
4169:
4157:
4152:
4151:
4150:
4145:
4140:
4135:
4125:
4120:
4115:
4110:
4109:
4108:
4103:
4093:
4092:
4091:
4086:
4081:
4076:
4066:
4061:
4060:
4059:
4054:
4049:
4039:
4038:
4037:
4032:
4027:
4022:
4017:
4012:
4002:
3997:
3992:
3987:
3986:
3985:
3980:
3975:
3970:
3960:
3955:
3953:Formation rule
3950:
3945:
3944:
3943:
3938:
3928:
3927:
3926:
3916:
3911:
3906:
3901:
3895:
3889:
3872:Formal systems
3868:
3867:
3864:
3863:
3861:
3860:
3855:
3850:
3845:
3840:
3835:
3830:
3825:
3820:
3815:
3814:
3813:
3808:
3797:
3795:
3791:
3790:
3788:
3787:
3786:
3785:
3775:
3770:
3769:
3768:
3761:Large cardinal
3758:
3753:
3748:
3743:
3738:
3724:
3723:
3722:
3717:
3712:
3697:
3695:
3685:
3684:
3682:
3681:
3680:
3679:
3674:
3669:
3659:
3654:
3649:
3644:
3639:
3634:
3629:
3624:
3619:
3614:
3609:
3604:
3598:
3596:
3589:
3588:
3586:
3585:
3584:
3583:
3578:
3573:
3568:
3563:
3558:
3550:
3549:
3548:
3543:
3533:
3528:
3526:Extensionality
3523:
3521:Ordinal number
3518:
3508:
3503:
3502:
3501:
3490:
3484:
3478:
3477:
3474:
3473:
3471:
3470:
3465:
3460:
3455:
3450:
3445:
3440:
3439:
3438:
3428:
3427:
3426:
3413:
3411:
3405:
3404:
3402:
3401:
3400:
3399:
3394:
3389:
3379:
3374:
3369:
3364:
3359:
3354:
3348:
3346:
3340:
3339:
3337:
3336:
3331:
3326:
3321:
3316:
3311:
3306:
3305:
3304:
3294:
3289:
3284:
3279:
3274:
3269:
3263:
3261:
3252:
3246:
3245:
3243:
3242:
3237:
3232:
3227:
3222:
3217:
3205:Cantor's
3203:
3198:
3193:
3183:
3181:
3168:
3167:
3165:
3164:
3159:
3154:
3149:
3144:
3139:
3134:
3129:
3124:
3119:
3114:
3109:
3104:
3103:
3102:
3091:
3089:
3085:
3084:
3079:
3077:
3076:
3069:
3062:
3054:
3045:
3044:
3038:
3029:
3009:
2989:
2986:
2983:
2982:
2969:
2940:
2903:
2891:
2875:
2860:
2846:
2819:
2806:(3): 481–498.
2786:
2762:
2751:(3): 313–373.
2733:Hilbert, David
2724:
2703:
2677:
2654:
2629:
2604:
2579:
2558:
2557:
2555:
2552:
2548:
2547:
2542:
2537:
2532:
2527:
2522:
2515:
2512:
2505:the method of
2498:
2495:
2483:
2480:
2467:
2460:
2440:
2420:
2416:
2396:
2392:
2364:
2361:
2353:
2350:
2319:
2318:
2315:
2304:
2301:
2271:
2252:
2249:
2236:
2216:
2213:
2210:
2190:
2170:
2150:
2130:
2127:
2124:
2104:
2101:
2098:
2074:
2052:
2048:
2044:
2039:
2035:
2031:
2026:
2022:
2018:
2015:
1993:
1989:
1985:
1982:
1979:
1974:
1970:
1955:Euclid's proof
1950:
1949:
1937:
1934:
1929:
1926:
1914:
1894:
1891:
1888:
1885:
1882:
1860:
1856:
1835:
1815:
1793:
1789:
1768:
1748:
1745:
1742:
1739:
1736:
1714:
1710:
1706:
1703:
1700:
1695:
1691:
1687:
1684:
1662:
1658:
1654:
1651:
1648:
1643:
1639:
1618:
1594:
1574:
1551:
1536:
1535:
1520:
1517:
1502:
1498:
1494:
1491:
1488:
1483:
1479:
1467:
1466:
1455:
1452:
1447:
1443:
1437:
1433:
1429:
1426:
1423:
1418:
1414:
1408:
1404:
1381:
1377:
1373:
1370:
1367:
1362:
1358:
1319:
1315:
1311:
1308:
1305:
1300:
1296:
1271:
1268:
1264:
1263:
1251:
1248:
1246:
1243:
1230:
1210:
1201:is prime" or "
1190:
1170:
1167:
1164:
1161:
1148:is known as a
1137:
1134:
1131:
1128:
1125:
1112:A proposition
1084:Turing machine
1050:
1049:
1000:
998:
991:
985:
982:
954:
951:
931:Main article:
928:
925:
912:
909:
906:
886:
874:
873:
866:
863:
856:
845:
844:
837:
834:
827:
803:
800:
798:
795:
794:
793:
782:
779:
775:
771:
762:
759:
756:
753:
750:
747:
744:
741:
738:
726:
723:
719:
715:
706:
703:
700:
697:
694:
691:
688:
685:
682:
670:
667:
664:
655:
652:
649:
646:
643:
640:
637:
589:for negation:
572:
571:
544:
511:
510:
507:
504:
501:
497:
496:
493:
490:
487:
483:
482:
475:
468:
461:
433:
430:
417:
395:
375:
372:
369:
347:
336:
335:
324:
321:
318:
315:
312:
309:
306:
303:
300:
270:
250:
247:
244:
233:
232:
216:
213:
201:
198:
195:
192:
140:
137:
129:
128:
117:
98:
87:
63:indirect proof
15:
13:
10:
9:
6:
4:
3:
2:
4840:
4829:
4826:
4824:
4821:
4819:
4816:
4815:
4813:
4800:
4799:
4794:
4786:
4780:
4777:
4775:
4772:
4770:
4767:
4765:
4762:
4758:
4755:
4754:
4753:
4750:
4748:
4745:
4743:
4740:
4738:
4734:
4731:
4729:
4726:
4724:
4721:
4719:
4716:
4714:
4711:
4710:
4708:
4704:
4698:
4695:
4693:
4690:
4688:
4687:Recursive set
4685:
4683:
4680:
4678:
4675:
4673:
4670:
4668:
4665:
4661:
4658:
4656:
4653:
4651:
4648:
4646:
4643:
4641:
4638:
4637:
4636:
4633:
4631:
4628:
4626:
4623:
4621:
4618:
4616:
4613:
4611:
4608:
4607:
4605:
4603:
4599:
4593:
4590:
4588:
4585:
4583:
4580:
4578:
4575:
4573:
4570:
4568:
4565:
4563:
4560:
4556:
4553:
4551:
4548:
4546:
4543:
4542:
4541:
4538:
4536:
4533:
4531:
4528:
4526:
4523:
4521:
4518:
4516:
4513:
4509:
4506:
4505:
4504:
4501:
4497:
4496:of arithmetic
4494:
4493:
4492:
4489:
4485:
4482:
4480:
4477:
4475:
4472:
4470:
4467:
4465:
4462:
4461:
4460:
4457:
4453:
4450:
4448:
4445:
4444:
4443:
4440:
4439:
4437:
4435:
4431:
4425:
4422:
4420:
4417:
4415:
4412:
4410:
4407:
4404:
4403:from ZFC
4400:
4397:
4395:
4392:
4386:
4383:
4382:
4381:
4378:
4376:
4373:
4371:
4368:
4367:
4366:
4363:
4361:
4358:
4356:
4353:
4351:
4348:
4346:
4343:
4341:
4338:
4336:
4333:
4332:
4330:
4328:
4324:
4314:
4313:
4309:
4308:
4303:
4302:non-Euclidean
4300:
4296:
4293:
4291:
4288:
4286:
4285:
4281:
4280:
4278:
4275:
4274:
4272:
4268:
4264:
4261:
4259:
4256:
4255:
4254:
4250:
4246:
4243:
4242:
4241:
4237:
4233:
4230:
4228:
4225:
4223:
4220:
4218:
4215:
4213:
4210:
4208:
4205:
4204:
4202:
4198:
4197:
4195:
4190:
4184:
4179:Example
4176:
4168:
4163:
4162:
4161:
4158:
4156:
4153:
4149:
4146:
4144:
4141:
4139:
4136:
4134:
4131:
4130:
4129:
4126:
4124:
4121:
4119:
4116:
4114:
4111:
4107:
4104:
4102:
4099:
4098:
4097:
4094:
4090:
4087:
4085:
4082:
4080:
4077:
4075:
4072:
4071:
4070:
4067:
4065:
4062:
4058:
4055:
4053:
4050:
4048:
4045:
4044:
4043:
4040:
4036:
4033:
4031:
4028:
4026:
4023:
4021:
4018:
4016:
4013:
4011:
4008:
4007:
4006:
4003:
4001:
3998:
3996:
3993:
3991:
3988:
3984:
3981:
3979:
3976:
3974:
3971:
3969:
3966:
3965:
3964:
3961:
3959:
3956:
3954:
3951:
3949:
3946:
3942:
3939:
3937:
3936:by definition
3934:
3933:
3932:
3929:
3925:
3922:
3921:
3920:
3917:
3915:
3912:
3910:
3907:
3905:
3902:
3900:
3897:
3896:
3893:
3890:
3888:
3884:
3879:
3873:
3869:
3859:
3856:
3854:
3851:
3849:
3846:
3844:
3841:
3839:
3836:
3834:
3831:
3829:
3826:
3824:
3823:Kripke–Platek
3821:
3819:
3816:
3812:
3809:
3807:
3804:
3803:
3802:
3799:
3798:
3796:
3792:
3784:
3781:
3780:
3779:
3776:
3774:
3771:
3767:
3764:
3763:
3762:
3759:
3757:
3754:
3752:
3749:
3747:
3744:
3742:
3739:
3736:
3732:
3728:
3725:
3721:
3718:
3716:
3713:
3711:
3708:
3707:
3706:
3702:
3699:
3698:
3696:
3694:
3690:
3686:
3678:
3675:
3673:
3670:
3668:
3667:constructible
3665:
3664:
3663:
3660:
3658:
3655:
3653:
3650:
3648:
3645:
3643:
3640:
3638:
3635:
3633:
3630:
3628:
3625:
3623:
3620:
3618:
3615:
3613:
3610:
3608:
3605:
3603:
3600:
3599:
3597:
3595:
3590:
3582:
3579:
3577:
3574:
3572:
3569:
3567:
3564:
3562:
3559:
3557:
3554:
3553:
3551:
3547:
3544:
3542:
3539:
3538:
3537:
3534:
3532:
3529:
3527:
3524:
3522:
3519:
3517:
3513:
3509:
3507:
3504:
3500:
3497:
3496:
3495:
3492:
3491:
3488:
3485:
3483:
3479:
3469:
3466:
3464:
3461:
3459:
3456:
3454:
3451:
3449:
3446:
3444:
3441:
3437:
3434:
3433:
3432:
3429:
3425:
3420:
3419:
3418:
3415:
3414:
3412:
3410:
3406:
3398:
3395:
3393:
3390:
3388:
3385:
3384:
3383:
3380:
3378:
3375:
3373:
3370:
3368:
3365:
3363:
3360:
3358:
3355:
3353:
3350:
3349:
3347:
3345:
3344:Propositional
3341:
3335:
3332:
3330:
3327:
3325:
3322:
3320:
3317:
3315:
3312:
3310:
3307:
3303:
3300:
3299:
3298:
3295:
3293:
3290:
3288:
3285:
3283:
3280:
3278:
3275:
3273:
3272:Logical truth
3270:
3268:
3265:
3264:
3262:
3260:
3256:
3253:
3251:
3247:
3241:
3238:
3236:
3233:
3231:
3228:
3226:
3223:
3221:
3218:
3216:
3212:
3208:
3204:
3202:
3199:
3197:
3194:
3192:
3188:
3185:
3184:
3182:
3180:
3174:
3169:
3163:
3160:
3158:
3155:
3153:
3150:
3148:
3145:
3143:
3140:
3138:
3135:
3133:
3130:
3128:
3125:
3123:
3120:
3118:
3115:
3113:
3110:
3108:
3105:
3101:
3098:
3097:
3096:
3093:
3092:
3090:
3086:
3082:
3075:
3070:
3068:
3063:
3061:
3056:
3055:
3052:
3048:
3042:
3039:
3037:
3033:
3030:
3026:
3020:
3012:
3006:
3002:
3001:
2996:
2992:
2991:
2987:
2972:
2966:
2962:
2958:
2954:
2950:
2944:
2941:
2937:
2933:
2930:
2927:
2925:
2924:9780521427067
2921:
2917:
2912:
2907:
2904:
2901:
2895:
2892:
2889:
2885:
2879:
2876:
2872:
2871:
2864:
2861:
2856:
2850:
2847:
2834:
2830:
2823:
2820:
2814:
2809:
2805:
2801:
2797:
2790:
2787:
2775:
2769:
2767:
2763:
2758:
2754:
2750:
2746:
2745:
2739:
2734:
2728:
2725:
2713:
2707:
2704:
2692:
2688:
2681:
2678:
2674:
2670:
2666:
2665:
2664:Book of Proof
2658:
2655:
2643:
2639:
2633:
2630:
2618:
2614:
2608:
2605:
2593:
2589:
2583:
2580:
2577:
2576:4-87187-714-0
2573:
2569:
2563:
2560:
2553:
2551:
2546:
2543:
2541:
2540:Modus tollens
2538:
2536:
2533:
2531:
2528:
2526:
2523:
2521:
2518:
2517:
2513:
2511:
2508:
2504:
2496:
2494:
2492:
2488:
2479:
2465:
2458:
2438:
2382:
2378:
2374:
2370:
2362:
2360:
2358:
2349:
2347:
2333:
2325:
2316:
2313:
2312:
2311:
2309:
2302:
2300:
2298:
2294:
2290:
2258:
2250:
2248:
2234:
2214:
2211:
2208:
2188:
2168:
2148:
2128:
2125:
2122:
2102:
2099:
2096:
2088:
2072:
2050:
2046:
2042:
2037:
2033:
2029:
2024:
2020:
2016:
2013:
1991:
1987:
1983:
1980:
1977:
1972:
1968:
1958:
1956:
1947:
1946:
1945:
1943:
1935:
1933:
1927:
1925:
1912:
1892:
1889:
1886:
1883:
1880:
1858:
1854:
1833:
1813:
1791:
1787:
1766:
1746:
1743:
1740:
1737:
1734:
1712:
1708:
1704:
1701:
1698:
1693:
1689:
1685:
1682:
1660:
1656:
1652:
1649:
1646:
1641:
1637:
1616:
1608:
1592:
1572:
1563:
1549:
1540:
1533:
1532:
1531:
1529:
1525:
1518:
1516:
1500:
1496:
1492:
1489:
1486:
1481:
1477:
1453:
1450:
1445:
1441:
1435:
1431:
1427:
1424:
1421:
1416:
1412:
1406:
1402:
1379:
1375:
1371:
1368:
1365:
1360:
1356:
1347:
1343:
1335:
1317:
1313:
1309:
1306:
1303:
1298:
1294:
1285:
1284:
1283:
1281:
1277:
1276:David Hilbert
1267:
1261:
1260:
1259:
1257:
1244:
1242:
1228:
1208:
1188:
1168:
1162:
1159:
1151:
1135:
1129:
1115:
1110:
1108:
1104:
1100:
1096:
1093:states that "
1092:
1088:
1085:
1081:
1077:
1073:
1068:
1063:
1059:
1057:
1046:
1043:
1035:
1025:
1021:
1017:
1011:
1010:
1006:
1001:This section
999:
995:
990:
989:
983:
981:
979:
975:
970:
968:
964:
960:
952:
950:
948:
944:
940:
934:
926:
924:
910:
884:
871:
867:
864:
861:
857:
854:
850:
849:
848:
842:
838:
835:
832:
828:
825:
821:
820:
819:
817:
813:
809:
801:
796:
777:
757:
754:
751:
748:
739:
721:
701:
698:
695:
692:
686:
683:
665:
650:
647:
644:
641:
638:
592:
591:
590:
588:
584:
579:
577:
569:
565:
561:
557:
553:
549:
545:
542:
538:
534:
533:
532:
530:
526:
522:
518:
508:
505:
502:
499:
498:
494:
491:
488:
485:
484:
480:
476:
473:
469:
466:
462:
460:
457:
456:
453:
451:
447:
443:
439:
432:Justification
431:
429:
408:
393:
373:
360:
319:
316:
313:
310:
301:
291:
290:
289:
287:
282:
268:
248:
214:
211:
199:
190:
175:
174:
173:
172:
168:
163:
161:
157:
153:
149:
146:
139:Formalization
138:
136:
134:
126:
122:
118:
115:
111:
107:
103:
99:
96:
92:
88:
85:
81:
80:
79:
76:
74:
73:
68:
64:
58:
56:
52:
48:
47:contradiction
44:
40:
36:
32:
29:is a form of
28:
24:
19:
4789:
4587:Ultraproduct
4434:Model theory
4399:Independence
4335:Formal proof
4327:Proof theory
4310:
4283:
4240:real numbers
4212:second-order
4123:Substitution
4000:Metalanguage
3941:conservative
3914:Axiom schema
3858:Constructive
3828:Morse–Kelley
3794:Set theories
3773:Aleph number
3766:inaccessible
3672:Grothendieck
3556:intersection
3443:Higher-order
3431:Second-order
3377:Truth tables
3334:Venn diagram
3117:Formal proof
3046:
2999:
2974:, retrieved
2952:
2943:
2914:
2906:
2894:
2883:
2878:
2868:
2863:
2849:
2837:. Retrieved
2832:
2822:
2803:
2799:
2789:
2777:. Retrieved
2748:
2742:
2727:
2715:. Retrieved
2706:
2694:. Retrieved
2690:
2680:
2662:
2657:
2645:. Retrieved
2641:
2632:
2620:. Retrieved
2616:
2607:
2595:. Retrieved
2592:www2.edc.org
2591:
2582:
2567:
2562:
2549:
2500:
2491:chess gambit
2485:
2482:Hardy's view
2372:
2369:Isaac Barrow
2366:
2355:
2345:
2331:
2323:
2320:
2306:
2296:
2292:
2260:
2255:The classic
2254:
2087:prime factor
1959:
1951:
1939:
1931:
1606:
1564:
1541:
1537:
1522:
1468:
1273:
1265:
1253:
1149:
1113:
1111:
1102:
1094:
1090:
1086:
1079:
1069:
1060:
1053:
1038:
1029:
1014:Please help
1002:
977:
973:
971:
966:
956:
946:
936:
875:
869:
859:
852:
846:
840:
830:
823:
815:
807:
805:
580:
575:
573:
567:
559:
555:
547:
540:
536:
528:
524:
520:
514:
478:
471:
464:
458:
445:
435:
406:
358:
337:
283:
234:
164:
159:
155:
152:(¬P ⇒ ⊥) ⇒ P
151:
147:
142:
130:
124:
120:
109:
105:
101:
94:
90:
83:
77:
71:
70:
66:
62:
59:
26:
20:
18:
4697:Type theory
4645:undecidable
4577:Truth value
4464:equivalence
4143:non-logical
3756:Enumeration
3746:Isomorphism
3693:cardinality
3677:Von Neumann
3642:Ultrafilter
3607:Uncountable
3541:equivalence
3458:Quantifiers
3448:Fixed-point
3417:First-order
3297:Consistency
3282:Proposition
3259:Traditional
3230:Lindström's
3220:Compactness
3162:Type theory
3107:Cardinality
2976:21 December
2911:G. H. Hardy
2487:G. H. Hardy
2261:¬ ∃ a, b ∈
2115:, possibly
1806:. Now both
1334:polynomials
442:truth table
43:proposition
4812:Categories
4508:elementary
4201:arithmetic
4069:Quantifier
4047:functional
3919:Expression
3637:Transitive
3581:identities
3566:complement
3499:hereditary
3482:Set theory
2839:6 February
2696:26 October
2622:25 October
2554:References
2507:resolution
1759:. Because
1394:such that
162:is true."
89:We assume
4779:Supertask
4682:Recursion
4640:decidable
4474:saturated
4452:of models
4375:deductive
4370:axiomatic
4290:Hilbert's
4277:Euclidean
4258:canonical
4181:axiomatic
4113:Signature
4042:Predicate
3931:Extension
3853:Ackermann
3778:Operation
3657:Universal
3647:Recursive
3622:Singleton
3617:Inhabited
3602:Countable
3592:Types of
3576:power set
3546:partition
3463:Predicate
3409:Predicate
3324:Syllogism
3314:Soundness
3287:Inference
3277:Tautology
3179:paradoxes
3019:cite book
2779:2 October
2717:2 October
2647:7 October
2466:×
2459:×
2439:↮
2419:⇐
2415:⇒
2395:←
2391:→
2043:⋯
2030:⋅
1981:…
1884:−
1705:⋅
1702:…
1699:⋅
1650:…
1490:…
1425:…
1369:…
1307:…
1166:¬
1163:∨
1133:⇒
1127:¬
1124:¬
1082:stating "
1072:algorithm
1003:does not
980:is true.
967:¬(P ∧ ¬P)
963:Aristotle
943:Aristotle
908:¬
905:¬
868:Conclude
839:Conclude
774:¬
761:Δ
752:⊢
746:¬
743:¬
737:Γ
718:¬
705:Δ
690:¬
687:⊢
681:Γ
654:Δ
645:⊢
636:Γ
450:tautology
416:Δ
371:¬
368:¬
346:Γ
323:Δ
314:⊢
308:¬
305:¬
299:Γ
246:¬
243:¬
212:⊢
197:¬
194:¬
191:⊢
4764:Logicism
4757:timeline
4733:Concrete
4592:Validity
4562:T-schema
4555:Kripke's
4550:Tarski's
4545:semantic
4535:Strength
4484:submodel
4479:spectrum
4447:function
4295:Tarski's
4284:Elements
4271:geometry
4227:Robinson
4148:variable
4133:function
4106:spectrum
4096:Sentence
4052:variable
3995:Language
3948:Relation
3909:Automata
3899:Alphabet
3883:language
3737:-jection
3715:codomain
3701:Function
3662:Universe
3632:Infinite
3536:Relation
3319:Validity
3309:Argument
3207:theorem,
2932:Archived
2929:PDF p.19
2735:(1893).
2514:See also
2363:Notation
2283:. a/b =
1282:states:
1221:divides
1032:May 2024
39:validity
4706:Related
4503:Diagram
4401: (
4380:Hilbert
4365:Systems
4360:Theorem
4238:of the
4183:systems
3963:Formula
3958:Grammar
3874: (
3818:General
3531:Forcing
3516:Element
3436:Monadic
3211:paradox
3152:Theorem
3088:General
2597:12 June
2342:
2328:
2285:√
1342:complex
1024:removed
1009:sources
858:Assume
829:Assume
479:¬¬p ⇒ p
446:¬¬P ⇒ P
148:¬¬P ⇒ P
37:or the
4469:finite
4232:Skolem
4185:
4160:Theory
4128:Symbol
4118:String
4101:atomic
3978:ground
3973:closed
3968:atomic
3924:ground
3887:syntax
3783:binary
3710:domain
3627:Finite
3392:finite
3250:Logics
3209:
3157:Theory
3007:
2967:
2922:
2671:
2574:
2377:Q.E.D.
1278:. His
947:P ∨ ¬P
624:
543:holds.
69:, and
4459:Model
4207:Peano
4064:Proof
3904:Arity
3833:Naive
3720:image
3652:Fuzzy
3612:Empty
3561:union
3506:Class
3147:Model
3137:Lemma
3095:Axiom
2201:and
1346:zeros
1091:¬H(M)
41:of a
35:truth
31:proof
23:logic
4582:Type
4385:list
4189:list
4166:list
4155:Term
4089:rank
3983:open
3877:list
3689:Maps
3594:sets
3453:Free
3423:list
3173:list
3100:list
3025:link
3005:ISBN
2978:2023
2965:ISBN
2920:ISBN
2841:2013
2781:2022
2719:2022
2698:2021
2669:ISBN
2649:2022
2642:nLab
2624:2019
2599:2023
2572:ISBN
2383:(as
2295:and
1826:and
1332:are
1080:H(M)
1007:any
1005:cite
976:and
957:The
897:and
558:and
108:and
4269:of
4251:of
4199:of
3731:Sur
3705:Map
3512:Ur-
3494:Set
2957:doi
2926:.
2913:,
2808:doi
2753:doi
2501:In
2407:or
2089:of
1336:in
1286:If
1241:".
1054:In
1018:by
581:In
560:¬¬P
554:to
546:if
535:if
521:¬¬P
472:¬¬p
436:In
428:."
359:and
284:In
165:In
21:In
4814::
4655:NP
4279::
4273::
4203::
3880:),
3735:Bi
3727:In
3021:}}
3017:{{
2963:,
2951:,
2831:.
2804:54
2802:.
2798:.
2765:^
2749:42
2747:.
2741:.
2689:.
2640:.
2615:.
2590:.
2478:.
2085:a
1454:1.
1109:.
978:¬P
949:.
860:¬P
841:¬P
824:¬P
816:¬P
556:¬P
548:¬P
509:T
506:F
503:T
500:F
495:T
492:T
489:F
486:T
465:¬p
452::
407:or
110:¬Q
102:¬P
95:¬P
75:.
65:,
25:,
4735:/
4650:P
4405:)
4191:)
4187:(
4084:∀
4079:!
4074:∃
4035:=
4030:↔
4025:→
4020:∧
4015:∨
4010:¬
3733:/
3729:/
3703:/
3514:)
3510:(
3397:∞
3387:3
3175:)
3073:e
3066:t
3059:v
3027:)
3013:.
2959::
2938:.
2857:.
2843:.
2816:.
2810::
2783:.
2759:.
2755::
2721:.
2700:.
2651:.
2626:.
2601:.
2346:q
2339:2
2336:/
2332:q
2324:q
2297:b
2293:a
2287:2
2270:N
2235:1
2215:1
2212:+
2209:P
2189:P
2169:p
2149:p
2129:1
2126:+
2123:P
2103:1
2100:+
2097:P
2073:p
2051:n
2047:p
2038:2
2034:p
2025:1
2021:p
2017:=
2014:P
1992:n
1988:p
1984:,
1978:,
1973:1
1969:p
1913:n
1893:1
1890:=
1887:P
1881:Q
1859:i
1855:p
1834:Q
1814:P
1792:i
1788:p
1767:Q
1747:1
1744:+
1741:P
1738:=
1735:Q
1713:k
1709:p
1694:1
1690:p
1686:=
1683:P
1661:k
1657:p
1653:,
1647:,
1642:1
1638:p
1617:n
1607:p
1593:n
1573:n
1550:n
1501:k
1497:g
1493:,
1487:,
1482:1
1478:g
1451:=
1446:k
1442:g
1436:k
1432:f
1428:+
1422:+
1417:1
1413:g
1407:1
1403:f
1380:k
1376:g
1372:,
1366:,
1361:1
1357:g
1338:n
1318:k
1314:f
1310:,
1304:,
1299:1
1295:f
1229:b
1209:a
1189:n
1169:P
1160:P
1136:P
1130:P
1114:P
1103:M
1095:M
1087:M
1045:)
1039:(
1034:)
1030:(
1026:.
1012:.
974:P
911:P
885:P
872:.
870:P
862:.
855:.
853:P
843:.
833:.
831:P
826:.
781:)
778:L
770:(
758:,
755:P
749:P
740:,
725:)
722:R
714:(
702:,
699:P
696:,
693:P
684:,
669:)
666:I
663:(
651:,
648:P
642:P
639:,
576:P
570:.
568:P
541:P
537:P
529:P
525:P
459:p
394:P
374:P
320:,
317:P
311:P
302:,
269:P
249:P
215:P
200:P
160:P
156:P
125:P
121:P
116:.
106:Q
97:.
91:P
86:.
84:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
