3419:
2914:
3533:
12011:
3414:{\displaystyle {\begin{aligned}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(angle addition)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(triangle inequality)}}\\&=\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\right|&&{\text{(induction hypothesis}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}}
9275:, p. 197: 'The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.'
8662:
29:
1919:
9061:
It is mistakenly printed in several books and sources that the well-ordering principle is equivalent to the induction axiom. In the context of the other Peano axioms, this is not the case, but in the context of other axioms, they are equivalent; specifically, the well-ordering principle implies the
8218:
7929:
6850:
558:
Another important idea introduced by al-Karaji and continued by al-Samaw'al and others was that of an inductive argument for dealing with certain arithmetic sequences. Thus al-Karaji used such an argument to prove the result on the sums of integral cubes already known to
179: all hold. This is done by first proving a simple case, then also showing that if we assume the claim is true for a given case, then the next case is also true. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:
8223:
may be read as a set representing a proposition, and containing natural numbers, for which the proposition holds. This is not an axiom, but a theorem, given that natural numbers are defined in the language of ZFC set theory by axioms, analogous to Peano's. See
1686:
567:. He stated his theorem for the particular integer 10 His proof, nevertheless, was clearly designed to be extendable to any other integer. Al-Karaji's argument includes in essence the two basic components of a modern argument by induction, namely the
4514:
4658:
8099:
6619:
7789:
4565:
Predecessor induction can trivially simulate prefix induction on the same statement. Prefix induction can simulate predecessor induction, but only at the cost of making the statement more syntactically complex (adding a
8795:
6710:
5803:
7313:. However, proving the validity of the statement for no single number suffices to establish the base case; instead, one needs to prove the statement for an infinite subset of the natural numbers. For example,
2040:
1676:
2730:
9057:
Peano's axioms with the induction principle uniquely model the natural numbers. Replacing the induction principle with the well-ordering principle allows for more exotic models that fulfill all the axioms.
938:
2628:
2509:
2261:
2151:
5283:
Complete induction is equivalent to ordinary mathematical induction as described above, in the sense that a proof by one method can be transformed into a proof by the other. Suppose there is a proof of
4435:
1342:
1247:
484:, in which the examination of many cases results in a probable conclusion. The mathematical method examines infinitely many cases to prove a general statement, but it does so by a finite chain of
6715:
5890:
2919:
1691:
618:
None of these ancient mathematicians, however, explicitly stated the induction hypothesis. Another similar case (contrary to what Vacca has written, as
Freudenthal carefully showed) was that of
1557:
5946:
4440:
7081:
7577:
7318:
7262:
4587:
4547:. In fact, it is called "prefix induction" because each step proves something about a number from something about the "prefix" of that number â as formed by truncating the low bit of its
1132:
7517:
4320:
1062:
177:
1424:
8532:
It can then be proved that induction, given the above-listed axioms, implies the well-ordering principle. The following proof uses complete induction and the first and fourth axioms.
998:
2337:
6057:
5735:
Complete induction is most useful when several instances of the inductive hypothesis are required for each induction step. For example, complete induction can be used to show that
8038:
The axiom of structural induction for the natural numbers was first formulated by Peano, who used it to specify the natural numbers together with the following four other axioms:
7463:
2820:
9002:
8889:
6085:
5513:
2445:
2417:
1168:
3988:
3597:
In practice, proofs by induction are often structured differently, depending on the exact nature of the property to be proven. All variants of induction are special cases of
7766:
7738:
6965:
6705:
5421:
4852:. The name "strong induction" does not mean that this method can prove more than "weak induction", but merely refers to the stronger hypothesis used in the induction step.
8974:
8861:
6528:
6393:
1914:{\displaystyle {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}.\end{aligned}}}
5992:
2872:
6884:
5048:
432:
7678:
7116:
6330:
6304:
5696:
5485:
5269:
5243:
5188:
4855:
In fact, it can be shown that the two methods are actually equivalent, as explained below. In this form of complete induction, one still has to prove the base case,
4742:
3456:
7710:
7029:
6487:
6460:
5830:
4941:
308:
7251:
6994:
6913:
6661:
6151:
6118:
5725:
5661:
5632:
5600:
5571:
5542:
5450:
5369:
5340:
5311:
5217:
5136:
5107:
5002:
4973:
4911:
4882:
4850:
4771:
3491:
2901:
2759:
2564:
74:
7652:
7623:
7407:
7291:
7142:
6204:
5162:
5078:
4821:
2291:
406:
380:
354:
272:
238:
6178:
3514:
7597:
7381:
7311:
7222:
7202:
7182:
7162:
6933:
6507:
6433:
6413:
6350:
6262:
5389:
5022:
4795:
2840:
2648:
2535:
2381:
2357:
2194:
2174:
509:
328:
97:
6230:
5738:
527:
may have contained traces of an early example of an implicit inductive proof, however, the earliest implicit proof by mathematical induction was written by
813:
Authors who prefer to define natural numbers to begin at 0 use that value in the base case; those who define natural numbers to begin at 1 use that value.
10390:
9919:
8801:. Moreover, except for the induction axiom, it satisfies all Peano axioms, where Peano's constant 0 is interpreted as the pair (0, 0), and Peano's
9555:
1926:
1562:
844:
9144:
4041:
942:
This states a general formula for the sum of the natural numbers less than or equal to a given number; in fact an infinite sequence of statements:
9497:
8710:
8213:{\displaystyle \forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}}
4346:. This could be called "predecessor induction" because each step proves something about a number from something about that number's predecessor.
11065:
3562:
4124:
The validity of this method can be verified from the usual principle of mathematical induction. Using mathematical induction on the statement
10197:
5313:
by complete induction. Then, this proof can be transformed into an ordinary induction proof by assuming a stronger inductive hypothesis. Let
4356:
3744:
Assume an infinite supply of 4- and 5-dollar coins. Induction can be used to prove that any whole amount of dollars greater than or equal to
11148:
10289:
9468:
9199:
1491:
591:- 1. Of course, this second component is not explicit since, in some sense, al-Karaji's argument is in reverse; this is, he starts from
2659:
183:
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the
7924:{\displaystyle \forall P\,{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n\,{\bigl (}P(n){\bigr )}{\Bigr )},}
4562:-step loop. Because of that, proofs using prefix induction are "more feasibly constructive" than proofs using predecessor induction.
6845:{\displaystyle {\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}}
6623:
However, there will be slight differences in the structure and the assumptions of the proof, starting with the extended base case.
2569:
2450:
2202:
2092:
5054:
as described below, although it is no longer equivalent to ordinary induction. In this form the base case is subsumed by the case
11462:
4262:
3702:. This form of mathematical induction is actually a special case of the previous form, because if the statement to be proved is
6273:
511:, which can take infinitely many values. The result is a rigorous proof of the statement, not an assertion of its probability.
9251:"The earliest implicit proof by mathematical induction was given around 1000 in a work by the Persian mathematician Al-Karaji"
4102:. Because there are no infinite decreasing sequences of natural numbers, this situation would be impossible, thereby showing (
11620:
10050:
9796:
9768:
9739:
9658:
10408:
7343:. To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by mathematical induction that
4012:, the second case in the induction step (replacing three 5- by four 4-dollar coins) will not work; let alone for even lower
11475:
10798:
10108:
Shields, Paul (1997). "Peirce's
Axiomatization of Arithmetic". In Houser, Nathan; Roberts, Don D.; Evra, James Van (eds.).
7599:
horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all
1268:
1173:
676:, and from then on it became well known. The modern formal treatment of the principle came only in the 19th century, with
9348:
is the next greater integer. Hence the theorem is true universally. ⊠This species of argument may be termed a continued
5843:
3881:
must be a multiple of 5 and so at least 15; but then we can replace three 5-dollar coins by four 4-dollar coins to make
11480:
11470:
11207:
11060:
10413:
9699:
9416:
9182:
10404:
4577:
computation depend on excluding unbounded quantifiers entirely, and limiting the alternation of bounded universal and
11616:
10121:
10098:
9948:
9869:
9835:
9371:
7034:
6277:
5899:
3584:
10958:
3555:
11713:
11457:
10282:
8269:
Applied to a well-founded set, transfinite induction can be formulated as a single step. To prove that a statement
2904:
8096:, quantification over predicates is not allowed, but one can still express induction by quantification over sets:
7522:
2059:
Since both the base case and the induction step have been proved as true, by mathematical induction the statement
1067:
12035:
11018:
10711:
9967:
9729:
8019:
rather than over individual numbers. This is a second-order quantifier, which means that this axiom is stated in
10452:
9324:
which it involves shall be an integer or whole number and the method of proof is usually of the following kind.
7468:
4551:. It can also be viewed as an application of traditional induction on the length of that binary representation.
1003:
102:
11974:
11676:
11439:
11434:
11259:
10680:
10364:
9437:
1373:
470:
5190:, making the proof simpler and more elegant. In this method, however, it is vital to ensure that the proof of
945:
11969:
11752:
11669:
11382:
11313:
11190:
10432:
9679:
9550:
8250:
One variation of the principle of complete induction can be generalized for statements about elements of any
8233:
7344:
7334:
9669:
11894:
11720:
11406:
11040:
10639:
9898:
9644:
5997:
4946:
Although the form just described requires one to prove the base case, this is unnecessary if one can prove
2296:
12040:
11772:
11767:
11377:
11116:
11045:
10374:
10275:
9674:
9141:
7412:
5634:
had been proven by ordinary induction, the proof would already effectively be one by complete induction:
4509:{\displaystyle \forall k\,\left(P\!\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)}
4046:
2773:
10228:
Yadegari, Mohammad (1978). "The Use of
Mathematical Induction by AbĆ« KÄmil ShujÄ' Ibn Aslam (850-930)".
9088:
is a unique and well-defined natural number, a property which is not implied by the other Peano axioms.
8225:
11701:
11291:
10685:
10653:
10344:
8979:
8866:
6062:
5490:
2422:
2394:
1145:
8391:
Strictly speaking, it is not necessary in transfinite induction to prove a base case, because it is a
5698:
is proved in the induction step, in which one may assume all earlier cases but need only use the case
4653:{\displaystyle \forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)}
12045:
11991:
11940:
11837:
11335:
11296:
10773:
10418:
10093:. Boston Studies in the Philosophy of Science. Vol. 156. Springer Science & Business Media.
8259:
4709:), makes the induction step easier to prove by using a stronger hypothesis: one proves the statement
3937:
3545:
600:
10447:
4259:
The most common form of proof by mathematical induction requires proving in the induction step that
11832:
11762:
11301:
11153:
11136:
10859:
10339:
8703:. Numbers refer to the second component of pairs; the first can be obtained from color or location.
8456:
6938:
6666:
6352:
is prime then it is certainly a product of primes, and if not, then by definition it is a product:
5394:
4350:
3549:
3541:
2086:
8941:
8828:
7743:
7715:
6355:
5138:
assumed; this case may need to be handled separately, but sometimes the same argument applies for
11664:
11641:
11602:
11488:
11429:
11075:
10995:
10839:
10783:
10396:
9562:
Paris. The proof of the inequality of arithmetic and geometric means can be found on pages 457ff.
9128:
8448:
8431:
that could serve as counterexamples. So the special cases are special cases of the general case.
4032:, by iterating the induction process. That is, one proves a base case and an induction step for
704:
The simplest and most common form of mathematical induction infers that a statement involving a
11954:
11681:
11659:
11626:
11519:
11365:
11350:
11323:
11274:
11158:
11093:
10918:
10884:
10879:
10753:
10584:
10561:
9958:
5958:
4578:
4103:
3566:
2845:
685:
544:
532:
489:
10140:
9248:
9174:
32:
Mathematical induction can be informally illustrated by reference to the sequential effect of
11884:
11737:
11529:
11247:
10983:
10889:
10748:
10733:
10614:
10589:
10088:
9359:
9320:"It is sometimes required to prove a theorem which shall be true whenever a certain quantity
9203:
8334:
8245:
7314:
6863:
5027:
4685:. This form of induction has been used, analogously, to study log-time parallel computation.
4548:
3598:
524:
411:
7657:
7086:
6309:
6283:
5666:
5455:
5248:
5222:
5167:
4712:
3426:
2908:
11857:
11819:
11696:
11500:
11340:
11264:
11242:
11070:
11028:
10927:
10894:
10758:
10546:
10457:
10220:
10131:
10071:
10029:
9996:
9717:
7683:
7002:
6465:
6438:
5949:
5808:
4919:
4570:
630:
540:
481:
446:
281:
197:
7227:
6970:
6889:
6637:
5701:
5637:
5608:
5576:
5547:
5518:
5426:
5345:
5316:
5287:
5193:
5112:
5083:
4978:
4949:
4887:
4858:
4826:
4747:
4353:
is "prefix induction", in which one proves the following statement in the induction step:
4064:
The method of infinite descent is a variation of mathematical induction which was used by
3613:
If one wishes to prove a statement, not for all natural numbers, but only for all numbers
3467:
2877:
2735:
2540:
50:
8:
11986:
11877:
11862:
11842:
11799:
11686:
11636:
11562:
11507:
11444:
11237:
11232:
11180:
10948:
10937:
10609:
10509:
10437:
10428:
10424:
10359:
10354:
9102:
8798:
8076:
7631:
7602:
7386:
7270:
7121:
6183:
6123:
6090:
5141:
5057:
4800:
2768:
2270:
619:
485:
477:
385:
359:
333:
251:
217:
20:
3870:
dollars that includes at least one 4-dollar coin, replace it by a 5-dollar coin to make
3496:
12015:
11784:
11747:
11732:
11725:
11708:
11512:
11494:
11360:
11286:
11269:
11222:
11035:
10944:
10778:
10763:
10723:
10675:
10660:
10648:
10604:
10579:
10349:
10298:
10255:
10247:
10075:
10033:
9984:
9886:
9852:
9821:
9813:
9758:
9473:
9167:
9153:
9122:
8329:
8255:
8020:
7778:
7582:
7366:
7296:
7207:
7187:
7167:
7147:
6918:
6509:
is a product of products of primes, and hence by extension a product of primes itself.
6492:
6418:
6398:
6335:
6247:
6156:
5374:
5007:
4780:
4567:
2825:
2633:
2520:
2366:
2342:
2179:
2159:
681:
653:(1288â1344). The first explicit formulation of the principle of induction was given by
494:
450:
313:
82:
44:
10968:
12010:
11950:
11757:
11567:
11557:
11449:
11330:
11165:
11141:
10922:
10906:
10811:
10788:
10665:
10634:
10599:
10494:
10329:
10259:
10117:
10110:
10094:
10079:
10037:
10005:
9944:
9825:
9764:
9750:
9735:
9705:
9695:
9654:
9552:
Cours d'analyse de l'Ăcole Royale
Polytechnique, premiÚre partie, Analyse algébrique,
9525:
9433:
9412:
9367:
9178:
9097:
8229:
8089:
8024:
6614:{\displaystyle S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b}
6240:
Another proof by complete induction uses the hypothesis that the statement holds for
6209:
612:
595:= 10 and goes down to 1 rather than proceeding upward. Nevertheless, his argument in
442:
10211:
10192:
772:. In other words, assume that the statement holds for some arbitrary natural number
11964:
11959:
11852:
11809:
11631:
11592:
11587:
11572:
11398:
11355:
11252:
11050:
11000:
10574:
10536:
10239:
10206:
10059:
10017:
9976:
9914:
9878:
9844:
9805:
9614:
8251:
5837:
4914:
4519:
4065:
4059:
693:
666:
662:
536:
454:
3423:
The inequality between the extreme left-hand and right-hand quantities shows that
646:
11945:
11935:
11889:
11872:
11827:
11789:
11691:
11611:
11418:
11345:
11318:
11306:
11212:
11126:
11100:
11055:
11023:
10824:
10626:
10569:
10519:
10484:
10442:
10216:
10127:
10067:
10025:
9992:
9962:
9713:
9559:
9148:
5423:"âthis becomes the inductive hypothesis for ordinary induction. We can then show
4574:
4050:. More complicated arguments involving three or more counters are also possible.
3763:
dollars can be formed by a combination of 4- and 5-dollar coins". The proof that
673:
33:
9648:
7267:
Sometimes, it is more convenient to deduce backwards, proving the statement for
787:
The hypothesis in the induction step, that the statement holds for a particular
11930:
11909:
11867:
11847:
11742:
11597:
11195:
11185:
11175:
11170:
11104:
10978:
10854:
10743:
10738:
10716:
10317:
10230:
10175:
10159:
9940:
9932:
9901:(1994). "Could the Greeks Have Used Mathematical Induction? Did They Use It?".
9864:
9619:
9602:
8891:. As an example for the violation of the induction axiom, define the predicate
8324:
This form of induction, when applied to a set of ordinal numbers (which form a
8263:
8092:
7947:
6280:. For proving the induction step, the induction hypothesis is that for a given
6265:
705:
689:
462:
77:
6180:. To complete the proof, the identity must be verified in the two base cases:
4024:
It is sometimes desirable to prove a statement involving two natural numbers,
608:
310:. These two steps establish that the statement holds for every natural number
12029:
11904:
11582:
11089:
10874:
10864:
10834:
10819:
10489:
10193:"Maurolycus, the First Discoverer of the Principle of Mathematical Induction"
10045:
9709:
9350:
8392:
8384:
654:
10008:(1970). "Rabbi Levi Ben Gershon and the origins of mathematical induction".
11804:
11651:
11552:
11544:
11424:
11372:
11281:
11217:
11200:
11131:
10990:
10849:
10551:
10334:
9754:
9725:
8790:{\displaystyle \{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}}
8444:
8032:
8028:
6269:
5893:
677:
466:
438:
9809:
8368:
has a direct predecessor, i.e. the set of elements which are smaller than
4554:
If traditional predecessor induction is interpreted computationally as an
11914:
11794:
10973:
10963:
10910:
10594:
10514:
10499:
10379:
10324:
9687:
8666:
7322:
2154:
10087:
Rashed, R. (1994). "Mathematical induction: al-Karajī and al-Samawʟal".
9817:
9062:
induction axiom in the context of the first two above listed axioms and
7325:, and then used backwards induction to show it for all natural numbers.
6395:, where neither of the factors is equal to 1; hence neither is equal to
4705:(in contrast to which the basic form of induction is sometimes known as
799:. To prove the induction step, one assumes the induction hypothesis for
10844:
10699:
10670:
10476:
10063:
10021:
9988:
9890:
9856:
8339:
8325:
5953:
650:
10251:
5798:{\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}}
3990:, the above proof cannot be modified to replace the minimum amount of
457:. Mathematical induction in this extended sense is closely related to
11996:
11899:
10952:
10869:
10829:
10793:
10729:
10541:
10531:
10504:
10267:
10090:
The
Development of Arabic Mathematics: Between Arithmetic and Algebra
8661:
8539:
8069:
8031:
containing a separate axiom for each possible predicate. The article
560:
528:
458:
9980:
9882:
9848:
7680:. However, the argument used in the induction step is incorrect for
4913:
before the general argument applies, as in the example below of the
4036:, and in each of those proves a base case and an induction step for
1923:
Equating the extreme left hand and right hand sides, we deduce that:
826:
Mathematical induction can be used to prove the following statement
803:
and then uses this assumption to prove that the statement holds for
607:
In India, early implicit proofs by mathematical induction appear in
476:
Despite its name, mathematical induction differs fundamentally from
240:
without assuming any knowledge of other cases. The second case, the
11981:
11779:
11227:
10932:
10526:
10243:
9787:
8349:
Proofs by transfinite induction typically distinguish three cases:
8343:
2035:{\displaystyle 0+1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.}
1671:{\displaystyle (0+1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1).}
626:(1575), who used the technique to prove that the sum of the first
437:
The method can be extended to prove statements about more general
408:, establishing the truth of the statement for all natural numbers
11577:
10369:
9731:
The Art of
Computer Programming, Volume 1: Fundamental Algorithms
8451:
in the context of the other Peano axioms. Suppose the following:
7712:, because the statement that "the two sets overlap" is false for
4884:, and it may even be necessary to prove extra-base cases such as
2725:{\displaystyle \left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|}
1680:
633:
563:
Al-Karaji did not, however, state a general result for arbitrary
9526:"Forward-Backward Induction | Brilliant Math & Science Wiki"
8439:
The principle of mathematical induction is usually stated as an
8421:. It is vacuously true precisely because there are no values of
7997:. The axiom of induction asserts the validity of inferring that
3713:
then proving it with these two rules is equivalent with proving
543:. Whilst the original work was lost, it was later referenced by
6087:, the identity above can be verified by direct calculation for
2075:
933:{\displaystyle P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.}
187:) and that from each rung we can climb up to the next one (the
28:
9833:
Bussey, W. H. (1917). "The Origin of
Mathematical Induction".
9572:
Cohen, Joel E. (1961). "On the nature of mathematical proof".
9364:
George Boole: Selected
Manuscripts on Logic and its Philosophy
8434:
7960:
and the induction step (namely, that the induction hypothesis
7938:
is a variable for predicates involving one natural number and
1354:
Show that the statement holds for the smallest natural number
11121:
10467:
10312:
8572:
is true, for if it were false then 0 is the least element of
8440:
7783:
6518:
2623:{\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}
2504:{\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}
2256:{\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}
2146:{\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}
568:
520:
10048:(1972). "L'induction mathématique: al-Karajī, as-Samaw'al".
9081:
A common mistake in many erroneous proofs is to assume that
8357:
is a minimal element, i.e. there is no element smaller than
8266:
is well-founded, the set of natural numbers is one of them.
4558:-step loop, then prefix induction would correspond to a log-
3638:
Showing that if the statement holds for an arbitrary number
2199:
At first glance, it may appear that a more general version,
7654:
is trivial, and the induction step is correct in all cases
4573:), so the interesting results relating prefix induction to
3739:
665:, made ample use of a related principle: indirect proof by
2359:. This suggests we examine the statement specifically for
8639:
is true. Therefore, by the complete induction principle,
7328:
4098:, it also holds for some strictly smaller natural number
3621:, then the proof by induction consists of the following:
10162:(1991). "Greek Mathematics and Mathematical Induction".
9746:(Section 1.2.1: Mathematical Induction, pp. 11â21.)
9469:"Proof:Strong induction is equivalent to weak induction"
7383:
horses, there is only one color. Now look at any set of
672:
The induction hypothesis was also employed by the Swiss
9867:(1918). "Origin of the Name "Mathematical Induction"".
9302:
4430:{\displaystyle \forall k\,(P(k)\to P(2k)\land P(2k+1))}
9917:(1953). "Zur Geschichte der vollstÀndigen Induction".
9230:
7746:
7718:
7525:
7471:
7363:
assume as induction hypothesis that within any set of
6212:
6159:
6126:
6093:
5902:
5846:
5663:
is proved in the base case, using no assumptions, and
5278:
3940:
2299:
1463:
Assume the induction hypothesis that for a particular
1384:
1303:
1208:
1090:
1020:
956:
9775:(Section 3.8: Transfinite induction, pp. 28â29.)
9249:
Mathematical
Knowledge and the Interplay of Practices
8982:
8944:
8869:
8831:
8713:
8102:
7792:
7686:
7660:
7634:
7605:
7585:
7415:
7389:
7369:
7299:
7273:
7230:
7210:
7190:
7170:
7150:
7124:
7118:
holds, by the inductive hypothesis. That is, the sum
7089:
7037:
7005:
6973:
6941:
6921:
6892:
6866:
6713:
6669:
6640:
6531:
6495:
6468:
6441:
6421:
6401:
6358:
6338:
6312:
6286:
6250:
6186:
6065:
6000:
5961:
5811:
5741:
5704:
5669:
5640:
5611:
5579:
5550:
5521:
5493:
5458:
5429:
5397:
5377:
5348:
5319:
5290:
5251:
5225:
5196:
5170:
5144:
5115:
5086:
5060:
5030:
5010:
4981:
4952:
4922:
4890:
4861:
4829:
4803:
4783:
4750:
4715:
4590:
4584:
One can take the idea a step further: one must prove
4443:
4359:
4265:
4019:
3877:
dollars. Otherwise, if only 5-dollar coins are used,
3499:
3470:
3429:
2917:
2880:
2848:
2842:. Assume the induction hypothesis: for a given value
2828:
2776:
2738:
2662:
2636:
2572:
2543:
2523:
2453:
2425:
2397:
2369:
2345:
2273:
2205:
2182:
2162:
2095:
1929:
1689:
1565:
1494:
1376:
1337:{\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}
1271:
1242:{\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}
1176:
1148:
1070:
1006:
948:
847:
821:
497:
414:
388:
362:
336:
316:
284:
254:
220:
105:
85:
53:
9290:
9278:
9011:
is trivially true, and so is the induction step: if
8546:, of natural numbers that has no least element. Let
7339:
The induction step must be proved for all values of
7317:
first used forward (regular) induction to prove the
6512:
6264:
more thoroughly. Consider the statement that "every
4198:
holds for all natural numbers less than or equal to
9763:. Silverman, R. A. (trans., ed.). New York: Dover.
9389:
5885:{\textstyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}
4083:. Its traditional form consists of showing that if
10109:
9582:(R. L. Weber, ed.), Crane, Russak & Co., 1973.
9377:
9268:
9266:
9166:
8996:
8968:
8883:
8855:
8789:
8212:
7923:
7760:
7732:
7704:
7672:
7646:
7617:
7591:
7571:
7511:
7457:
7401:
7375:
7305:
7285:
7245:
7216:
7196:
7176:
7156:
7136:
7110:
7075:
7023:
6988:
6959:
6927:
6907:
6878:
6844:
6699:
6655:
6613:
6501:
6481:
6454:
6427:
6415:, and so both are greater than 1 and smaller than
6407:
6387:
6344:
6324:
6298:
6256:
6224:
6198:
6172:
6145:
6112:
6079:
6051:
5986:
5940:
5884:
5824:
5797:
5719:
5690:
5655:
5626:
5594:
5565:
5536:
5507:
5479:
5444:
5415:
5383:
5363:
5334:
5305:
5263:
5237:
5211:
5182:
5156:
5130:
5101:
5072:
5042:
5016:
4996:
4967:
4935:
4905:
4876:
4844:
4815:
4789:
4765:
4736:
4652:
4508:
4429:
4314:
3982:
3748:can be formed by a combination of such coins. Let
3508:
3485:
3450:
3413:
2895:
2866:
2834:
2814:
2753:
2724:
2642:
2622:
2558:
2529:
2503:
2439:
2411:
2375:
2351:
2331:
2293:, could be proven without induction; but the case
2285:
2255:
2188:
2168:
2145:
2053:also holds true, establishing the induction step.
2034:
1913:
1670:
1552:{\displaystyle 0+1+\cdots +k={\frac {k(k+1)}{2}}.}
1551:
1418:
1336:
1241:
1162:
1126:
1056:
992:
932:
503:
426:
400:
374:
348:
322:
302:
266:
232:
171:
91:
68:
10141:"The Mathematics of Levi ben Gershon, the Ralbag"
10001:Reprinted (CP 3.252â288), (W 4:299â309)
9218:
8205:
8111:
7913:
7802:
4606:
4459:
4187:
860:
12027:
9920:Archives Internationales d'Histoire des Sciences
9340:. It is proved that if the theorem is true when
8049:of every natural number yields a natural number
5941:{\textstyle \psi ={\frac {1}{2}}(1-{\sqrt {5}})}
3554:but its sources remain unclear because it lacks
2339:shows it may be false for non-integer values of
330:. The base case does not necessarily begin with
9749:
9263:
8797:, shown in the picture, is well-ordered by the
7204:dollar coin to that combination yields the sum
7076:{\displaystyle 15<j\implies 12\leq j-4<j}
6235:
4667:applications of this inference in getting from
4529:applications of this inference in getting from
3677:In this way, one can prove that some statement
8015:The first quantifier in the axiom ranges over
6120:if one assumes that it already holds for both
4688:
4660:whereupon the induction principle "automates"
4324:whereupon the induction principle "automates"
3608:
738:): prove that the statement holds for 0, or 1.
575:= 1 (1 = 1) and the deriving of the truth for
10283:
10198:Bulletin of the American Mathematical Society
9643:
9603:"Are Induction and Well-Ordering Equivalent?"
9356:Elementary Treatise on Logic not mathematical
8184:
8144:
7906:
7887:
7870:
7830:
7572:{\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}
7256:
6268:greater than 1 is a product of (one or more)
5730:
4208:satisfies the following conditions suffices:
3458:is true, which completes the induction step.
2080:
549:al-Bahir fi'l-jabr (The Brilliant in Algebra)
382:, and possibly with any fixed natural number
10116:. Indiana University Press. pp. 43â52.
9596:
9594:
9592:
9590:
9588:
9344:is a given whole number, it will be true if
9047:is not true for all pairs in the set, since
8963:
8951:
8850:
8838:
8784:
8752:
8746:
8714:
7319:inequality of arithmetic and geometric means
3977:
3947:
3659:This can be used, for example, to show that
1127:{\displaystyle 0+1+2={\tfrac {(2)(2+1)}{2}}}
10004:
9913:
9308:
9173:. New York: John Wiley & Sons. p.
8435:Relationship to the well-ordering principle
8035:contains further discussion of this issue.
8012:from the base case and the induction step.
7512:{\textstyle \left\{1,2,3,\dotsc ,n\right\}}
6517:We shall look to prove the same example as
6489:, so each one is a product of primes. Thus
4823:; by contrast, the basic form only assumes
4315:{\displaystyle \forall k\,(P(k)\to P(k+1))}
10475:
10290:
10276:
7051:
7047:
6562:
6558:
6435:. The induction hypothesis now applies to
5051:
4328:applications of this step in getting from
3902:Therefore, by the principle of induction,
3617:greater than or equal to a certain number
3602:
2793:
2789:
1057:{\displaystyle 0+1={\tfrac {(1)(1+1)}{2}}}
172:{\displaystyle P(0),P(1),P(2),P(3),\dots }
99:, that is, that the infinitely many cases
10210:
10112:Studies in the Logic of Charles S. Peirce
9792:149a7-c3. A Proof by Complete Induction?"
9618:
9585:
8990:
8877:
8780:
8742:
8193:
8138:
7884:
7799:
6589:
6588:
6581:
6567:
6563:
6548:
6547:
6073:
5501:
4597:
4518:The induction principle then "automates"
4450:
4366:
4272:
4068:. It is used to show that some statement
3648:, then the same statement also holds for
3585:Learn how and when to remove this message
3084:
2433:
2405:
2319:
1419:{\displaystyle 0={\tfrac {0(0+1)}{2}}\,.}
1412:
1156:
776:, and prove that the statement holds for
10227:
10138:
9430:A Beginner's Guide to Mathematical Logic
9427:
9296:
9164:
8660:
8395:special case of the proposition that if
8338:. It is an important proof technique in
8239:
3740:Example: forming dollar amounts by coins
993:{\displaystyle 0={\tfrac {(0)(0+1)}{2}}}
554:Katz says in his history of mathematics
27:
10107:
9937:History of Mathematics: An Introduction
9446:
9395:
8023:. Axiomatizing arithmetic induction in
4192:If one wishes to prove that a property
4005:, the base case is actually false; for
248:the statement holds for any given case
12028:
10297:
10174:
10158:
10086:
10044:
9957:
9897:
9863:
9832:
9785:
9686:
9383:
9284:
9272:
9236:
9224:
7329:Example of error in the induction step
5245:, e.g. by saying "choose an arbitrary
4581:quantifiers allowed in the statement.
3809:is simple: take three 4-dollar coins.
3625:Showing that the statement holds when
2383:, and induction is the readiest tool.
2332:{\textstyle n={\frac {1}{2}},\,x=\pi }
210:consists of two cases. The first, the
10271:
10190:
10051:Archive for History of Exact Sciences
10010:Archive for History of Exact Sciences
9797:Archive for History of Exact Sciences
9724:
9650:Proof in Mathematics: An Introduction
9600:
9571:
9488:
7144:can be formed by some combination of
6052:{\displaystyle F_{n+2}=F_{n+1}+F_{n}}
3781:can then be achieved by induction on
1683:, the right hand side simplifies as:
10139:Simonson, Charles G. (Winter 2000).
9931:
9498:"Strong Induction and Well-Ordering"
9452:
9066:Every natural number is either 0 or
8528:No natural number is less than zero.
7184:dollar coins. Then, simply adding a
6306:the statement holds for all smaller
3526:
278:it must also hold for the next case
10178:(1994). "Fowling after Induction".
9694:. Hochschultext. London: Springer.
9495:
9328:. The theorem is proved to be true
8447:. It is strictly stronger than the
8226:construction of the natural numbers
7458:{\displaystyle 1,2,3,\dotsc ,n,n+1}
5279:Equivalence with ordinary induction
4254:
4053:
2815:{\displaystyle P(k)\implies P(k+1)}
722:. The proof consists of two steps:
13:
10154:. Bar-Ilan University Press: 5â21.
9692:Introduction to Mathematical Logic
8658:is empty, a contradiction. Q.E.D.
8624:, thus being a minimal element in
8128:
8103:
7878:
7822:
7793:
6564:
6525:. The statement remains the same:
4591:
4444:
4360:
4266:
4180:is false for every natural number
4020:Induction on more than one counter
822:Sum of consecutive natural numbers
601:the sum formula for integral cubes
531:around 1000 AD, who applied it to
14:
12057:
9870:The American Mathematical Monthly
9836:The American Mathematical Monthly
9601:Ăhman, LarsâDaniel (6 May 2019).
9202:. Earlham College. Archived from
9197:
8997:{\displaystyle m\in \mathbb {N} }
8884:{\displaystyle n\in \mathbb {N} }
8580:be a natural number, and suppose
6513:Example: dollar amounts revisited
6278:fundamental theorem of arithmetic
6080:{\displaystyle n\in \mathbb {N} }
5508:{\displaystyle n\in \mathbb {N} }
4146:is false for all natural numbers
4079:is false for all natural numbers
2440:{\displaystyle n\in \mathbb {N} }
2412:{\displaystyle x\in \mathbb {R} }
2085:Induction is often used to prove
1163:{\displaystyle n\in \mathbb {N} }
12009:
9734:(3rd ed.). Addison-Wesley.
8805:function is defined on pairs by
8591:is true for all natural numbers
8379:has no direct predecessor, i.e.
7771:
7357:horse, there is only one color.
7345:all horses are of the same color
5271:", or by assuming that a set of
5219:does not implicitly assume that
4094:is true for some natural number
3983:{\textstyle k\in \{4,5,8,9,10\}}
3531:
1344:We give a proof by induction on
599:is the earliest extant proof of
469:, and is the foundation of most
445:; this generalization, known as
10212:10.1090/S0002-9904-1909-01860-9
9968:American Journal of Mathematics
9637:
9565:
9549:Cauchy, Augustin-Louis (1821).
9543:
9518:
9461:
9421:
9401:
9314:
8459:axiom: For any natural numbers
8280:holds for each ordinal number:
2089:. As an example, we prove that
2070:holds for every natural number
659:Traité du triangle arithmétique
461:. Mathematical induction is an
9607:The Mathematical Intelligencer
9254:
9242:
9191:
9158:
9133:
9115:
8767:
8755:
8729:
8717:
8650:holds for all natural numbers
8284:Show, for each ordinal number
8189:
8173:
8161:
8158:
7901:
7895:
7875:
7865:
7853:
7847:
7844:
7838:
7816:
7810:
7240:
7234:
7105:
7093:
7048:
6983:
6977:
6902:
6896:
6650:
6644:
6559:
6541:
6535:
5935:
5919:
5879:
5863:
5714:
5708:
5685:
5673:
5650:
5644:
5621:
5615:
5589:
5583:
5560:
5554:
5531:
5525:
5474:
5462:
5439:
5433:
5358:
5352:
5329:
5323:
5300:
5294:
5206:
5200:
5125:
5119:
5096:
5090:
4991:
4985:
4962:
4956:
4900:
4894:
4871:
4865:
4839:
4833:
4760:
4754:
4731:
4719:
4642:
4636:
4630:
4498:
4492:
4486:
4424:
4421:
4406:
4397:
4388:
4382:
4379:
4373:
4367:
4309:
4306:
4294:
4288:
4285:
4279:
4273:
4188:Limited mathematical induction
3493:holds for all natural numbers
3480:
3474:
3445:
3433:
3382:
3370:
3357:
3292:
3264:
2945:
2933:
2890:
2884:
2809:
2797:
2790:
2786:
2780:
2748:
2742:
2553:
2547:
2020:
2011:
1999:
1996:
1993:
1981:
1972:
1960:
1895:
1886:
1874:
1871:
1868:
1856:
1834:
1822:
1819:
1807:
1785:
1773:
1764:
1752:
1736:
1724:
1712:
1700:
1662:
1650:
1638:
1626:
1614:
1602:
1596:
1566:
1537:
1525:
1402:
1390:
1321:
1309:
1226:
1214:
1114:
1102:
1099:
1093:
1044:
1032:
1029:
1023:
980:
968:
965:
959:
918:
906:
857:
851:
718:or 1) holds for all values of
699:
473:proofs for computer programs.
160:
154:
145:
139:
130:
124:
115:
109:
63:
57:
1:
11970:History of mathematical logic
9786:Acerbi, Fabio (August 2000).
9631:
9366:, BirkhÀuser Verlag, Berlin,
8234:axiom schema of specification
8008:holds for any natural number
7761:{\textstyle \left\{2\right\}}
7733:{\textstyle \left\{1\right\}}
7335:All horses are the same color
6960:{\displaystyle 12\leq m<j}
6700:{\displaystyle k=12,13,14,15}
5416:{\displaystyle 0\leq m\leq n}
3920:, and the proof is complete.
3866:. If there is a solution for
2517:Fix an arbitrary real number
761:, if the statement holds for
11895:Primitive recursive function
9779:
9165:Anderson, Robert B. (1979).
8969:{\displaystyle y\in \{0,1\}}
8856:{\displaystyle x\in \{0,1\}}
8443:of the natural numbers; see
8262:. Every set representing an
6388:{\displaystyle m=n_{1}n_{2}}
6236:Example: prime factorization
5050:. This is a special case of
3732:with an induction base case
7:
9675:Encyclopedia of Mathematics
9362:and Bornet, GĂ©rard (1997),
9091:
8707:On the other hand, the set
4689:Complete (strong) induction
4047:addition of natural numbers
3859:is true for some arbitrary
3609:Base case other than 0 or 1
3522:
816:
661:(1665). Another Frenchman,
214:, proves the statement for
10:
12062:
10959:SchröderâBernstein theorem
10686:Monadic predicate calculus
10345:Foundations of mathematics
9760:Introductory Real Analysis
9620:10.1007/s00283-019-09898-4
9428:Smullyan, Raymond (2014).
8260:infinite descending chains
8243:
8068:The successor function is
7786:of induction" as follows:
7782:, one can write down the "
7332:
7263:Forward-backward induction
7260:
7257:Forward-backward induction
5731:Example: Fibonacci numbers
4744:under the assumption that
4699:course of values induction
4057:
3994:dollar to any lower value
3923:In this example, although
2081:A trigonometric inequality
514:
18:
16:Form of mathematical proof
12005:
11992:Philosophy of mathematics
11941:Automated theorem proving
11923:
11818:
11650:
11543:
11395:
11112:
11088:
11066:Von NeumannâBernaysâGödel
11011:
10905:
10809:
10707:
10698:
10625:
10560:
10466:
10388:
10305:
9411:, p. 190, Pearson, 2006,
8471:is less than or equal to
8254:, that is, a set with an
7293:, given its validity for
5994:. By using the fact that
5987:{\displaystyle x^{2}-x-1}
5275:elements has an element.
4349:A variant of interest in
2867:{\displaystyle n=k\geq 0}
9963:"On the Logic of Number"
9670:"Mathematical induction"
9580:A Random Walk in Science
9200:"Mathematical Induction"
9169:Proving Programs Correct
9108:
9073:for some natural number
8628:, a contradiction. Thus
7953:In words, the base case
7579:. Each is a set of only
5109:is proved with no other
4693:Another variant, called
4351:computational complexity
4040:. See, for example, the
3826:holds for some value of
3728:for all natural numbers
3540:This section includes a
837:for all natural numbers
757:): prove that for every
649:use of induction was by
624:Arithmeticorum libri duo
19:Not to be confused with
11642:Self-verifying theories
11463:Tarski's axiomatization
10414:Tarski's undefinability
10409:incompleteness theorems
10148:Bekhol Derakhekha Daehu
9959:Peirce, Charles Sanders
9558:14 October 2017 at the
9358:pp. 40â41 reprinted in
9129:Simon Fraser University
8538:Suppose there exists a
8511:, no natural number is
8507:For any natural number
8486:For any natural number
8449:well-ordering principle
8328:and hence well-founded
8045:The successor function
7993:for any natural number
6879:{\displaystyle j>15}
5605:If, on the other hand,
5043:{\displaystyle m\geq 0}
4220:For any natural number
4117:cannot be true for any
3888:dollars. In each case,
3569:more precise citations.
2822:for any natural number
2042:That is, the statement
427:{\displaystyle n\geq N}
12036:Mathematical induction
12016:Mathematics portal
11627:Proof of impossibility
11275:propositional variable
10585:Propositional calculus
10006:Rabinovitch, Nachum L.
9457:. Naples: Bibliopolis.
9409:Mathematical Reasoning
9360:Grattan-Guinness, Ivor
9142:Mathematical Induction
9124:Mathematical Induction
8998:
8970:
8885:
8857:
8791:
8704:
8557:be the assertion that
8372:has a largest element;
8258:< that contains no
8214:
8042:0 is a natural number.
7982:) together imply that
7925:
7762:
7734:
7706:
7674:
7673:{\displaystyle n>1}
7648:
7619:
7593:
7573:
7513:
7459:
7403:
7377:
7307:
7287:
7247:
7218:
7198:
7178:
7158:
7138:
7112:
7111:{\displaystyle S(j-4)}
7077:
7025:
6990:
6961:
6929:
6909:
6880:
6846:
6701:
6657:
6615:
6503:
6483:
6456:
6429:
6409:
6389:
6346:
6326:
6325:{\displaystyle n>1}
6300:
6299:{\displaystyle n>1}
6258:
6226:
6200:
6174:
6147:
6114:
6081:
6053:
5988:
5942:
5886:
5826:
5799:
5721:
5692:
5691:{\displaystyle P(n+1)}
5657:
5628:
5596:
5567:
5538:
5509:
5481:
5480:{\displaystyle Q(n+1)}
5446:
5417:
5385:
5365:
5336:
5307:
5265:
5264:{\displaystyle n<m}
5239:
5238:{\displaystyle m>0}
5213:
5184:
5183:{\displaystyle m>0}
5158:
5132:
5103:
5074:
5044:
5018:
4998:
4969:
4937:
4907:
4878:
4846:
4817:
4791:
4767:
4738:
4737:{\displaystyle P(m+1)}
4654:
4510:
4431:
4316:
4150:less than or equal to
4042:proof of commutativity
3984:
3759:denote the statement "
3510:
3487:
3452:
3451:{\displaystyle P(k+1)}
3415:
2905:angle addition formula
2897:
2868:
2836:
2816:
2755:
2726:
2644:
2624:
2560:
2531:
2505:
2441:
2413:
2377:
2353:
2333:
2287:
2257:
2190:
2170:
2147:
2036:
1915:
1672:
1553:
1420:
1338:
1243:
1164:
1128:
1058:
994:
934:
686:Charles Sanders Peirce
605:
545:Al-Samawal al-Maghribi
505:
428:
402:
376:
350:
324:
304:
268:
234:
204:
173:
93:
70:
41:Mathematical induction
37:
11885:Kolmogorov complexity
11838:Computably enumerable
11738:Model complete theory
11530:Principia Mathematica
10590:Propositional formula
10419:BanachâTarski paradox
9810:10.1007/s004070000020
9751:Kolmogorov, Andrey N.
9653:. Sydney: Kew Books.
9453:Buss, Samuel (1986).
9432:. Dover. p. 41.
9004:. Then the base case
8999:
8971:
8886:
8858:
8792:
8664:
8335:transfinite induction
8246:Transfinite induction
8240:Transfinite induction
8215:
7926:
7763:
7735:
7707:
7705:{\displaystyle n+1=2}
7675:
7649:
7620:
7594:
7574:
7514:
7460:
7409:horses. Number them:
7404:
7378:
7315:Augustin Louis Cauchy
7308:
7288:
7248:
7219:
7199:
7179:
7159:
7139:
7113:
7078:
7031:, and observing that
7026:
7024:{\displaystyle m=j-4}
6991:
6962:
6930:
6910:
6881:
6854:The base case holds.
6847:
6702:
6658:
6616:
6504:
6484:
6482:{\displaystyle n_{2}}
6457:
6455:{\displaystyle n_{1}}
6430:
6410:
6390:
6347:
6327:
6301:
6259:
6227:
6201:
6175:
6148:
6115:
6082:
6054:
5989:
5943:
5887:
5827:
5825:{\displaystyle F_{n}}
5800:
5722:
5693:
5658:
5629:
5597:
5568:
5539:
5510:
5482:
5447:
5418:
5386:
5366:
5337:
5308:
5266:
5240:
5214:
5185:
5159:
5133:
5104:
5075:
5052:transfinite induction
5045:
5019:
4999:
4970:
4938:
4936:{\displaystyle F_{n}}
4908:
4879:
4847:
4818:
4792:
4768:
4739:
4655:
4549:binary representation
4511:
4432:
4317:
3985:
3599:transfinite induction
3511:
3488:
3453:
3416:
3354:(induction hypothesis
3107:(triangle inequality)
2898:
2869:
2837:
2817:
2756:
2727:
2645:
2625:
2561:
2532:
2506:
2442:
2414:
2378:
2354:
2334:
2288:
2258:
2191:
2171:
2148:
2037:
1916:
1673:
1554:
1421:
1339:
1244:
1165:
1129:
1059:
995:
935:
711:(that is, an integer
571:of the statement for
556:
506:
429:
403:
377:
351:
325:
305:
303:{\displaystyle n=k+1}
269:
235:
181:
174:
94:
71:
31:
11833:ChurchâTuring thesis
11820:Computability theory
11029:continuum hypothesis
10547:Square of opposition
10405:Gödel's completeness
9647:; Daoud, A. (2011).
8980:
8942:
8867:
8829:
8711:
8256:irreflexive relation
8100:
7790:
7744:
7716:
7684:
7658:
7632:
7603:
7583:
7523:
7469:
7465:. Consider the sets
7413:
7387:
7367:
7297:
7271:
7246:{\displaystyle S(j)}
7228:
7208:
7188:
7168:
7148:
7122:
7087:
7035:
7003:
6989:{\displaystyle S(j)}
6971:
6939:
6919:
6908:{\displaystyle S(m)}
6890:
6864:
6711:
6667:
6656:{\displaystyle S(k)}
6638:
6529:
6493:
6466:
6439:
6419:
6399:
6356:
6336:
6310:
6284:
6248:
6210:
6184:
6157:
6146:{\textstyle F_{n+1}}
6124:
6113:{\textstyle F_{n+2}}
6091:
6063:
5998:
5959:
5900:
5844:
5809:
5739:
5720:{\displaystyle P(n)}
5702:
5667:
5656:{\displaystyle P(0)}
5638:
5627:{\displaystyle P(n)}
5609:
5595:{\displaystyle P(n)}
5577:
5566:{\displaystyle Q(n)}
5548:
5537:{\displaystyle Q(n)}
5519:
5491:
5456:
5445:{\displaystyle Q(0)}
5427:
5395:
5375:
5364:{\displaystyle P(m)}
5346:
5335:{\displaystyle Q(n)}
5317:
5306:{\displaystyle P(n)}
5288:
5249:
5223:
5212:{\displaystyle P(m)}
5194:
5168:
5142:
5131:{\displaystyle P(n)}
5113:
5102:{\displaystyle P(0)}
5084:
5058:
5028:
5008:
4997:{\displaystyle P(n)}
4979:
4968:{\displaystyle P(m)}
4950:
4920:
4906:{\displaystyle P(1)}
4888:
4877:{\displaystyle P(0)}
4859:
4845:{\displaystyle P(m)}
4827:
4801:
4781:
4766:{\displaystyle P(n)}
4748:
4713:
4588:
4571:universal quantifier
4441:
4357:
4263:
3938:
3835:induction hypothesis
3497:
3486:{\displaystyle P(n)}
3468:
3427:
2915:
2896:{\displaystyle P(k)}
2878:
2846:
2826:
2774:
2754:{\displaystyle P(0)}
2736:
2660:
2634:
2570:
2559:{\displaystyle P(n)}
2541:
2521:
2451:
2423:
2395:
2367:
2343:
2297:
2271:
2203:
2180:
2160:
2093:
1927:
1687:
1563:
1492:
1431:Show that for every
1374:
1269:
1174:
1146:
1068:
1004:
946:
845:
797:inductive hypothesis
793:induction hypothesis
765:, then it holds for
533:arithmetic sequences
495:
447:structural induction
441:structures, such as
412:
386:
360:
334:
314:
282:
252:
218:
198:Concrete Mathematics
103:
83:
69:{\displaystyle P(n)}
51:
11987:Mathematical object
11878:P versus NP problem
11843:Computable function
11637:Reverse mathematics
11563:Logical consequence
11440:primitive recursive
11435:elementary function
11208:Free/bound variable
11061:TarskiâGrothendieck
10580:Logical connectives
10510:Logical equivalence
10360:Logical consequence
9496:Shafiei, Niloufar.
9260:Katz (1998), p. 255
9103:Proof by exhaustion
8799:lexicographic order
8576:. Furthermore, let
7647:{\displaystyle n=1}
7618:{\displaystyle n+1}
7402:{\displaystyle n+1}
7286:{\displaystyle n-1}
7137:{\displaystyle j-4}
6199:{\displaystyle n=0}
5157:{\displaystyle m=0}
5073:{\displaystyle m=0}
4816:{\displaystyle m+1}
4169:, which means that
4154:", it follows that
3848:holds, too. Assume
2909:triangle inequality
2903:is true. Using the
2286:{\displaystyle n,x}
2176:and natural number
620:Francesco Maurolico
551:in around 1150 AD.
486:deductive reasoning
478:inductive reasoning
401:{\displaystyle n=N}
375:{\displaystyle n=1}
349:{\displaystyle n=0}
267:{\displaystyle n=k}
233:{\displaystyle n=0}
21:inductive reasoning
12041:Mathematical logic
11785:Transfer principle
11748:Semantics of logic
11733:Categorical theory
11709:Non-standard model
11223:Logical connective
10350:Information theory
10299:Mathematical logic
10191:Vacca, G. (1909).
10064:10.1007/BF00348537
10022:10.1007/BF00327237
9474:Cornell University
9455:Bounded Arithmetic
9154:Harvard University
9147:2 May 2013 at the
9139:Gerardo con Diaz,
8994:
8966:
8881:
8853:
8787:
8705:
8346:and other fields.
8210:
8021:second-order logic
7946:are variables for
7921:
7779:second-order logic
7758:
7730:
7702:
7670:
7644:
7615:
7589:
7569:
7509:
7455:
7399:
7373:
7303:
7283:
7243:
7214:
7194:
7174:
7154:
7134:
7108:
7073:
7021:
6986:
6957:
6925:
6905:
6876:
6842:
6840:
6697:
6653:
6611:
6499:
6479:
6452:
6425:
6405:
6385:
6342:
6322:
6296:
6254:
6222:
6196:
6173:{\textstyle F_{n}}
6170:
6143:
6110:
6077:
6049:
5984:
5938:
5882:
5822:
5795:
5717:
5688:
5653:
5624:
5592:
5563:
5534:
5505:
5477:
5442:
5413:
5381:
5361:
5342:be the statement "
5332:
5303:
5261:
5235:
5209:
5180:
5154:
5128:
5099:
5070:
5040:
5014:
4994:
4965:
4933:
4903:
4874:
4842:
4813:
4787:
4763:
4734:
4695:complete induction
4650:
4506:
4427:
4312:
3980:
3695:, or even for all
3542:list of references
3509:{\displaystyle n.}
3506:
3483:
3448:
3411:
3409:
2893:
2874:, the single case
2864:
2832:
2812:
2751:
2722:
2640:
2620:
2556:
2527:
2501:
2437:
2409:
2373:
2349:
2329:
2283:
2253:
2186:
2166:
2143:
2032:
1911:
1909:
1668:
1549:
1467:, the single case
1416:
1410:
1334:
1329:
1239:
1234:
1160:
1124:
1122:
1054:
1052:
990:
988:
930:
682:Augustus De Morgan
539:and properties of
501:
482:used in philosophy
451:mathematical logic
424:
398:
372:
346:
320:
300:
264:
230:
208:proof by induction
169:
89:
76:is true for every
66:
38:
12023:
12022:
11955:Abstract category
11758:Theories of truth
11568:Rule of inference
11558:Natural deduction
11539:
11538:
11084:
11083:
10789:Cartesian product
10694:
10693:
10600:Many-valued logic
10575:Boolean functions
10458:Russell's paradox
10433:diagonal argument
10330:First-order logic
9915:Freudenthal, Hans
9770:978-0-486-61226-3
9741:978-0-201-89683-1
9660:978-0-646-54509-7
9354:" (Boole c. 1849
9239:, pp. 62â84.
9098:Induction puzzles
8479:is not less than
8230:axiom of infinity
8025:first-order logic
7592:{\displaystyle n}
7376:{\displaystyle n}
7353:in a set of only
7306:{\displaystyle n}
7217:{\displaystyle j}
7197:{\displaystyle 4}
7177:{\displaystyle 5}
7157:{\displaystyle 4}
6928:{\displaystyle m}
6521:, this time with
6502:{\displaystyle m}
6428:{\displaystyle m}
6408:{\displaystyle m}
6345:{\displaystyle m}
6272:", which is the "
6257:{\displaystyle n}
5933:
5917:
5877:
5861:
5793:
5384:{\displaystyle m}
5017:{\displaystyle n}
4790:{\displaystyle n}
4620:
4476:
3595:
3594:
3587:
3355:
3108:
3024:
2835:{\displaystyle k}
2643:{\displaystyle n}
2566:be the statement
2530:{\displaystyle x}
2376:{\displaystyle n}
2352:{\displaystyle n}
2314:
2189:{\displaystyle n}
2169:{\displaystyle x}
2027:
1902:
1841:
1792:
1719:
1645:
1559:It follows that:
1544:
1409:
1370:is clearly true:
1328:
1265:be the statement
1233:
1121:
1051:
987:
925:
869:
866:
541:Pascal's triangle
504:{\displaystyle n}
356:, but often with
323:{\displaystyle n}
201:, page 3 margins.
92:{\displaystyle n}
47:that a statement
12053:
12046:Methods of proof
12014:
12013:
11965:History of logic
11960:Category of sets
11853:Decision problem
11632:Ordinal analysis
11573:Sequent calculus
11471:Boolean algebras
11411:
11410:
11385:
11356:logical/constant
11110:
11109:
11096:
11019:ZermeloâFraenkel
10770:Set operations:
10705:
10704:
10642:
10473:
10472:
10453:LöwenheimâSkolem
10340:Formal semantics
10292:
10285:
10278:
10269:
10268:
10263:
10224:
10214:
10187:
10171:
10155:
10145:
10135:
10115:
10104:
10083:
10041:
10000:
9954:
9928:
9910:
9894:
9860:
9829:
9774:
9755:Fomin, Sergei V.
9745:
9726:Knuth, Donald E.
9721:
9683:
9664:
9625:
9624:
9622:
9598:
9583:
9577:
9569:
9563:
9547:
9541:
9540:
9538:
9536:
9522:
9516:
9515:
9513:
9511:
9502:
9492:
9486:
9485:
9483:
9481:
9465:
9459:
9458:
9450:
9444:
9443:
9425:
9419:
9405:
9399:
9393:
9387:
9381:
9375:
9335:
9318:
9312:
9309:Rabinovitch 1970
9306:
9300:
9294:
9288:
9282:
9276:
9270:
9261:
9258:
9252:
9246:
9240:
9234:
9228:
9222:
9216:
9215:
9213:
9211:
9195:
9189:
9188:
9172:
9162:
9156:
9137:
9131:
9119:
9087:
9076:
9072:
9053:
9046:
9040:
9025:
9010:
9003:
9001:
9000:
8995:
8993:
8975:
8973:
8972:
8967:
8937:
8917:
8905:
8890:
8888:
8887:
8882:
8880:
8862:
8860:
8859:
8854:
8824:
8796:
8794:
8793:
8788:
8783:
8745:
8702:
8701:
8685:
8657:
8653:
8649:
8638:
8627:
8623:
8619:
8612:
8601:
8594:
8590:
8579:
8575:
8571:
8564:
8560:
8556:
8545:
8524:
8517:
8510:
8503:
8496:
8489:
8482:
8478:
8474:
8470:
8466:
8462:
8430:
8420:
8416:
8410:
8400:
8382:
8378:
8371:
8367:
8360:
8356:
8319:
8308:
8298:
8287:
8279:
8252:well-founded set
8222:
8219:
8217:
8216:
8211:
8209:
8208:
8196:
8188:
8187:
8148:
8147:
8141:
8115:
8114:
8082:
8075:0 is not in the
8064:
8048:
8011:
8007:
7996:
7992:
7981:
7970:
7959:
7945:
7941:
7937:
7930:
7928:
7927:
7922:
7917:
7916:
7910:
7909:
7891:
7890:
7874:
7873:
7834:
7833:
7806:
7805:
7767:
7765:
7764:
7759:
7757:
7739:
7737:
7736:
7731:
7729:
7711:
7709:
7708:
7703:
7679:
7677:
7676:
7671:
7653:
7651:
7650:
7645:
7624:
7622:
7621:
7616:
7598:
7596:
7595:
7590:
7578:
7576:
7575:
7570:
7568:
7564:
7518:
7516:
7515:
7510:
7508:
7504:
7464:
7462:
7461:
7456:
7408:
7406:
7405:
7400:
7382:
7380:
7379:
7374:
7342:
7312:
7310:
7309:
7304:
7292:
7290:
7289:
7284:
7252:
7250:
7249:
7244:
7223:
7221:
7220:
7215:
7203:
7201:
7200:
7195:
7183:
7181:
7180:
7175:
7163:
7161:
7160:
7155:
7143:
7141:
7140:
7135:
7117:
7115:
7114:
7109:
7082:
7080:
7079:
7074:
7030:
7028:
7027:
7022:
6995:
6993:
6992:
6987:
6966:
6964:
6963:
6958:
6934:
6932:
6931:
6926:
6914:
6912:
6911:
6906:
6885:
6883:
6882:
6877:
6851:
6849:
6848:
6843:
6841:
6706:
6704:
6703:
6698:
6662:
6660:
6659:
6654:
6620:
6618:
6617:
6612:
6584:
6523:strong induction
6508:
6506:
6505:
6500:
6488:
6486:
6485:
6480:
6478:
6477:
6461:
6459:
6458:
6453:
6451:
6450:
6434:
6432:
6431:
6426:
6414:
6412:
6411:
6406:
6394:
6392:
6391:
6386:
6384:
6383:
6374:
6373:
6351:
6349:
6348:
6343:
6331:
6329:
6328:
6323:
6305:
6303:
6302:
6297:
6263:
6261:
6260:
6255:
6231:
6229:
6228:
6225:{\textstyle n=1}
6223:
6205:
6203:
6202:
6197:
6179:
6177:
6176:
6171:
6169:
6168:
6152:
6150:
6149:
6144:
6142:
6141:
6119:
6117:
6116:
6111:
6109:
6108:
6086:
6084:
6083:
6078:
6076:
6058:
6056:
6055:
6050:
6048:
6047:
6035:
6034:
6016:
6015:
5993:
5991:
5990:
5985:
5971:
5970:
5947:
5945:
5944:
5939:
5934:
5929:
5918:
5910:
5891:
5889:
5888:
5883:
5878:
5873:
5862:
5854:
5838:Fibonacci number
5835:
5831:
5829:
5828:
5823:
5821:
5820:
5804:
5802:
5801:
5796:
5794:
5792:
5781:
5780:
5779:
5767:
5766:
5756:
5751:
5750:
5726:
5724:
5723:
5718:
5697:
5695:
5694:
5689:
5662:
5660:
5659:
5654:
5633:
5631:
5630:
5625:
5601:
5599:
5598:
5593:
5572:
5570:
5569:
5564:
5543:
5541:
5540:
5535:
5514:
5512:
5511:
5506:
5504:
5486:
5484:
5483:
5478:
5451:
5449:
5448:
5443:
5422:
5420:
5419:
5414:
5390:
5388:
5387:
5382:
5370:
5368:
5367:
5362:
5341:
5339:
5338:
5333:
5312:
5310:
5309:
5304:
5274:
5270:
5268:
5267:
5262:
5244:
5242:
5241:
5236:
5218:
5216:
5215:
5210:
5189:
5187:
5186:
5181:
5163:
5161:
5160:
5155:
5137:
5135:
5134:
5129:
5108:
5106:
5105:
5100:
5079:
5077:
5076:
5071:
5049:
5047:
5046:
5041:
5023:
5021:
5020:
5015:
5003:
5001:
5000:
4995:
4974:
4972:
4971:
4966:
4942:
4940:
4939:
4934:
4932:
4931:
4915:Fibonacci number
4912:
4910:
4909:
4904:
4883:
4881:
4880:
4875:
4851:
4849:
4848:
4843:
4822:
4820:
4819:
4814:
4796:
4794:
4793:
4788:
4777:natural numbers
4772:
4770:
4769:
4764:
4743:
4741:
4740:
4735:
4703:strong induction
4684:
4673:
4666:
4659:
4657:
4656:
4651:
4649:
4645:
4629:
4625:
4621:
4616:
4561:
4557:
4546:
4535:
4515:
4513:
4512:
4507:
4505:
4501:
4485:
4481:
4477:
4469:
4437:or equivalently
4436:
4434:
4433:
4428:
4345:
4334:
4327:
4321:
4319:
4318:
4313:
4255:Prefix induction
4250:
4243:
4237:
4233:
4227:
4223:
4216:
4207:
4201:
4197:
4183:
4179:
4168:
4164:
4153:
4149:
4145:
4134:
4120:
4116:
4104:by contradiction
4101:
4097:
4093:
4082:
4078:
4066:Pierre de Fermat
4060:Infinite descent
4054:Infinite descent
4039:
4035:
4031:
4027:
4015:
4011:
4004:
3997:
3993:
3989:
3987:
3986:
3981:
3933:
3919:
3912:
3898:
3887:
3880:
3876:
3869:
3865:
3858:
3847:
3832:
3825:
3808:
3801:
3784:
3780:
3774:is true for all
3773:
3762:
3758:
3747:
3735:
3731:
3727:
3712:
3701:
3694:
3687:
3673:
3666:
3654:
3647:
3634:
3620:
3616:
3590:
3583:
3579:
3576:
3570:
3565:this section by
3556:inline citations
3535:
3534:
3527:
3518:
3515:
3513:
3512:
3507:
3492:
3490:
3489:
3484:
3464:The proposition
3457:
3455:
3454:
3449:
3420:
3418:
3417:
3412:
3410:
3403:
3399:
3363:
3356:
3353:
3350:
3348:
3344:
3326:
3322:
3298:
3285:
3281:
3260:
3258:
3254:
3236:
3232:
3208:
3204:
3200:
3182:
3178:
3160:
3156:
3141:
3137:
3113:
3109:
3106:
3103:
3101:
3097:
3066:
3062:
3029:
3025:
3023:(angle addition)
3022:
3019:
3017:
3013:
2955:
2951:
2902:
2900:
2899:
2894:
2873:
2871:
2870:
2865:
2841:
2839:
2838:
2833:
2821:
2819:
2818:
2813:
2760:
2758:
2757:
2752:
2731:
2729:
2728:
2723:
2721:
2717:
2684:
2680:
2656:The calculation
2649:
2647:
2646:
2641:
2629:
2627:
2626:
2621:
2619:
2615:
2594:
2590:
2565:
2563:
2562:
2557:
2536:
2534:
2533:
2528:
2510:
2508:
2507:
2502:
2500:
2496:
2475:
2471:
2446:
2444:
2443:
2438:
2436:
2418:
2416:
2415:
2410:
2408:
2382:
2380:
2379:
2374:
2358:
2356:
2355:
2350:
2338:
2336:
2335:
2330:
2315:
2307:
2292:
2290:
2289:
2284:
2262:
2260:
2259:
2254:
2252:
2248:
2227:
2223:
2195:
2193:
2192:
2187:
2175:
2173:
2172:
2167:
2152:
2150:
2149:
2144:
2142:
2138:
2117:
2113:
2073:
2069:
2052:
2041:
2039:
2038:
2033:
2028:
2023:
1979:
1920:
1918:
1917:
1912:
1910:
1903:
1898:
1854:
1846:
1842:
1837:
1805:
1797:
1793:
1788:
1747:
1720:
1715:
1695:
1677:
1675:
1674:
1669:
1646:
1641:
1621:
1558:
1556:
1555:
1550:
1545:
1540:
1520:
1487:
1476:
1466:
1459:
1448:
1437:
1425:
1423:
1422:
1417:
1411:
1405:
1385:
1369:
1360:
1347:
1343:
1341:
1340:
1335:
1330:
1324:
1304:
1264:
1248:
1246:
1245:
1240:
1235:
1229:
1209:
1169:
1167:
1166:
1161:
1159:
1133:
1131:
1130:
1125:
1123:
1117:
1091:
1063:
1061:
1060:
1055:
1053:
1047:
1021:
999:
997:
996:
991:
989:
983:
957:
939:
937:
936:
931:
926:
921:
901:
867:
864:
840:
836:
809:
802:
791:, is called the
790:
782:
775:
771:
764:
760:
747:
746:
732:
731:
721:
717:
710:
694:Richard Dedekind
667:infinite descent
641:
629:
547:in his treatise
537:binomial theorem
510:
508:
507:
502:
455:computer science
433:
431:
430:
425:
407:
405:
404:
399:
381:
379:
378:
373:
355:
353:
352:
347:
329:
327:
326:
321:
309:
307:
306:
301:
273:
271:
270:
265:
239:
237:
236:
231:
202:
178:
176:
175:
170:
98:
96:
95:
90:
75:
73:
72:
67:
43:is a method for
34:falling dominoes
12061:
12060:
12056:
12055:
12054:
12052:
12051:
12050:
12026:
12025:
12024:
12019:
12008:
12001:
11946:Category theory
11936:Algebraic logic
11919:
11890:Lambda calculus
11828:Church encoding
11814:
11790:Truth predicate
11646:
11612:Complete theory
11535:
11404:
11400:
11396:
11391:
11383:
11103: and
11099:
11094:
11080:
11056:New Foundations
11024:axiom of choice
11007:
10969:Gödel numbering
10909: and
10901:
10805:
10690:
10640:
10621:
10570:Boolean algebra
10556:
10520:Equiconsistency
10485:Classical logic
10462:
10443:Halting problem
10431: and
10407: and
10395: and
10394:
10389:Theorems (
10384:
10301:
10296:
10266:
10143:
10124:
10101:
9981:10.2307/2369151
9951:
9933:Katz, Victor J.
9883:10.2307/2972638
9865:Cajori, Florian
9849:10.2307/2974308
9782:
9771:
9742:
9702:
9668:
9661:
9640:
9634:
9629:
9628:
9599:
9586:
9578:. Reprinted in
9570:
9566:
9560:Wayback Machine
9548:
9544:
9534:
9532:
9524:
9523:
9519:
9509:
9507:
9505:York University
9500:
9493:
9489:
9479:
9477:
9467:
9466:
9462:
9451:
9447:
9440:
9426:
9422:
9407:Ted Sundstrom,
9406:
9402:
9394:
9390:
9382:
9378:
9329:
9319:
9315:
9307:
9303:
9295:
9291:
9283:
9279:
9271:
9264:
9259:
9255:
9247:
9243:
9235:
9231:
9223:
9219:
9209:
9207:
9196:
9192:
9185:
9163:
9159:
9149:Wayback Machine
9138:
9134:
9120:
9116:
9111:
9094:
9082:
9074:
9067:
9048:
9042:
9027:
9012:
9005:
8989:
8981:
8978:
8977:
8943:
8940:
8939:
8919:
8907:
8892:
8876:
8868:
8865:
8864:
8830:
8827:
8826:
8806:
8779:
8741:
8712:
8709:
8708:
8687:
8671:
8670:
8655:
8651:
8640:
8629:
8625:
8621:
8614:
8603:
8596:
8592:
8581:
8577:
8573:
8566:
8562:
8558:
8547:
8543:
8519:
8512:
8508:
8498:
8491:
8487:
8480:
8476:
8475:if and only if
8472:
8468:
8464:
8460:
8437:
8422:
8418:
8412:
8402:
8401:is true of all
8396:
8383:is a so-called
8380:
8376:
8369:
8365:
8358:
8354:
8310:
8300:
8289:
8285:
8270:
8248:
8242:
8220:
8204:
8203:
8192:
8183:
8182:
8143:
8142:
8137:
8110:
8109:
8101:
8098:
8097:
8080:
8050:
8046:
8009:
7998:
7994:
7983:
7972:
7961:
7954:
7948:natural numbers
7943:
7939:
7932:
7912:
7911:
7905:
7904:
7886:
7885:
7869:
7868:
7829:
7828:
7801:
7800:
7791:
7788:
7787:
7774:
7747:
7745:
7742:
7741:
7719:
7717:
7714:
7713:
7685:
7682:
7681:
7659:
7656:
7655:
7633:
7630:
7629:
7604:
7601:
7600:
7584:
7581:
7580:
7530:
7526:
7524:
7521:
7520:
7476:
7472:
7470:
7467:
7466:
7414:
7411:
7410:
7388:
7385:
7384:
7368:
7365:
7364:
7361:Induction step:
7340:
7337:
7331:
7298:
7295:
7294:
7272:
7269:
7268:
7265:
7259:
7229:
7226:
7225:
7209:
7206:
7205:
7189:
7186:
7185:
7169:
7166:
7165:
7149:
7146:
7145:
7123:
7120:
7119:
7088:
7085:
7084:
7036:
7033:
7032:
7004:
7001:
7000:
6972:
6969:
6968:
6940:
6937:
6936:
6920:
6917:
6916:
6891:
6888:
6887:
6865:
6862:
6861:
6858:Induction step:
6839:
6838:
6808:
6807:
6777:
6776:
6746:
6745:
6714:
6712:
6709:
6708:
6668:
6665:
6664:
6639:
6636:
6635:
6580:
6530:
6527:
6526:
6515:
6494:
6491:
6490:
6473:
6469:
6467:
6464:
6463:
6446:
6442:
6440:
6437:
6436:
6420:
6417:
6416:
6400:
6397:
6396:
6379:
6375:
6369:
6365:
6357:
6354:
6353:
6337:
6334:
6333:
6311:
6308:
6307:
6285:
6282:
6281:
6249:
6246:
6245:
6238:
6211:
6208:
6207:
6185:
6182:
6181:
6164:
6160:
6158:
6155:
6154:
6131:
6127:
6125:
6122:
6121:
6098:
6094:
6092:
6089:
6088:
6072:
6064:
6061:
6060:
6043:
6039:
6024:
6020:
6005:
6001:
5999:
5996:
5995:
5966:
5962:
5960:
5957:
5956:
5928:
5909:
5901:
5898:
5897:
5872:
5853:
5845:
5842:
5841:
5833:
5816:
5812:
5810:
5807:
5806:
5782:
5775:
5771:
5762:
5758:
5757:
5755:
5746:
5742:
5740:
5737:
5736:
5733:
5703:
5700:
5699:
5668:
5665:
5664:
5639:
5636:
5635:
5610:
5607:
5606:
5578:
5575:
5574:
5549:
5546:
5545:
5520:
5517:
5516:
5500:
5492:
5489:
5488:
5457:
5454:
5453:
5428:
5425:
5424:
5396:
5393:
5392:
5376:
5373:
5372:
5347:
5344:
5343:
5318:
5315:
5314:
5289:
5286:
5285:
5281:
5272:
5250:
5247:
5246:
5224:
5221:
5220:
5195:
5192:
5191:
5169:
5166:
5165:
5143:
5140:
5139:
5114:
5111:
5110:
5085:
5082:
5081:
5059:
5056:
5055:
5029:
5026:
5025:
5009:
5006:
5005:
4980:
4977:
4976:
4951:
4948:
4947:
4927:
4923:
4921:
4918:
4917:
4889:
4886:
4885:
4860:
4857:
4856:
4828:
4825:
4824:
4802:
4799:
4798:
4782:
4779:
4778:
4749:
4746:
4745:
4714:
4711:
4710:
4691:
4675:
4668:
4661:
4615:
4611:
4607:
4602:
4598:
4589:
4586:
4585:
4575:polynomial-time
4559:
4555:
4537:
4530:
4523:
4468:
4464:
4460:
4455:
4451:
4442:
4439:
4438:
4358:
4355:
4354:
4336:
4329:
4325:
4264:
4261:
4260:
4257:
4245:
4239:
4235:
4229:
4225:
4221:
4212:
4203:
4199:
4193:
4190:
4181:
4170:
4166:
4155:
4151:
4147:
4136:
4125:
4118:
4107:
4099:
4095:
4084:
4080:
4069:
4062:
4056:
4037:
4033:
4029:
4025:
4022:
4013:
4006:
3999:
3995:
3991:
3939:
3936:
3935:
3934:also holds for
3924:
3914:
3903:
3889:
3882:
3878:
3871:
3867:
3860:
3849:
3838:
3827:
3816:
3813:Induction step:
3803:
3792:
3782:
3775:
3764:
3760:
3749:
3745:
3742:
3733:
3729:
3714:
3703:
3696:
3689:
3678:
3668:
3660:
3649:
3639:
3626:
3618:
3614:
3611:
3591:
3580:
3574:
3571:
3560:
3546:related reading
3536:
3532:
3525:
3516:
3498:
3495:
3494:
3469:
3466:
3465:
3428:
3425:
3424:
3408:
3407:
3389:
3385:
3361:
3360:
3352:
3349:
3334:
3330:
3312:
3308:
3296:
3295:
3271:
3267:
3259:
3244:
3240:
3219:
3215:
3206:
3205:
3187:
3183:
3168:
3164:
3146:
3142:
3124:
3120:
3111:
3110:
3105:
3102:
3074:
3070:
3040:
3036:
3027:
3026:
3021:
3018:
2967:
2963:
2956:
2926:
2922:
2918:
2916:
2913:
2912:
2879:
2876:
2875:
2847:
2844:
2843:
2827:
2824:
2823:
2775:
2772:
2771:
2765:Induction step:
2737:
2734:
2733:
2707:
2703:
2667:
2663:
2661:
2658:
2657:
2635:
2632:
2631:
2630:. We induce on
2605:
2601:
2577:
2573:
2571:
2568:
2567:
2542:
2539:
2538:
2522:
2519:
2518:
2486:
2482:
2458:
2454:
2452:
2449:
2448:
2432:
2424:
2421:
2420:
2404:
2396:
2393:
2392:
2368:
2365:
2364:
2344:
2341:
2340:
2306:
2298:
2295:
2294:
2272:
2269:
2268:
2238:
2234:
2210:
2206:
2204:
2201:
2200:
2181:
2178:
2177:
2161:
2158:
2157:
2128:
2124:
2100:
2096:
2094:
2091:
2090:
2083:
2071:
2060:
2043:
1980:
1978:
1928:
1925:
1924:
1908:
1907:
1855:
1853:
1844:
1843:
1806:
1804:
1795:
1794:
1748:
1746:
1739:
1696:
1694:
1690:
1688:
1685:
1684:
1622:
1620:
1564:
1561:
1560:
1521:
1519:
1493:
1490:
1489:
1478:
1477:holds, meaning
1468:
1464:
1450:
1439:
1432:
1429:Induction step:
1386:
1383:
1375:
1372:
1371:
1364:
1355:
1345:
1305:
1302:
1270:
1267:
1266:
1255:
1210:
1207:
1175:
1172:
1171:
1155:
1147:
1144:
1143:
1092:
1089:
1069:
1066:
1065:
1022:
1019:
1005:
1002:
1001:
958:
955:
947:
944:
943:
902:
900:
846:
843:
842:
838:
827:
824:
819:
804:
800:
788:
777:
773:
766:
762:
758:
744:
743:
729:
728:
719:
712:
708:
702:
674:Jakob Bernoulli
637:
627:
517:
496:
493:
492:
413:
410:
409:
387:
384:
383:
361:
358:
357:
335:
332:
331:
315:
312:
311:
283:
280:
279:
253:
250:
249:
219:
216:
215:
203:
195:
104:
101:
100:
84:
81:
80:
52:
49:
48:
24:
17:
12:
11:
5:
12059:
12049:
12048:
12043:
12038:
12021:
12020:
12006:
12003:
12002:
12000:
11999:
11994:
11989:
11984:
11979:
11978:
11977:
11967:
11962:
11957:
11948:
11943:
11938:
11933:
11931:Abstract logic
11927:
11925:
11921:
11920:
11918:
11917:
11912:
11910:Turing machine
11907:
11902:
11897:
11892:
11887:
11882:
11881:
11880:
11875:
11870:
11865:
11860:
11850:
11848:Computable set
11845:
11840:
11835:
11830:
11824:
11822:
11816:
11815:
11813:
11812:
11807:
11802:
11797:
11792:
11787:
11782:
11777:
11776:
11775:
11770:
11765:
11755:
11750:
11745:
11743:Satisfiability
11740:
11735:
11730:
11729:
11728:
11718:
11717:
11716:
11706:
11705:
11704:
11699:
11694:
11689:
11684:
11674:
11673:
11672:
11667:
11660:Interpretation
11656:
11654:
11648:
11647:
11645:
11644:
11639:
11634:
11629:
11624:
11614:
11609:
11608:
11607:
11606:
11605:
11595:
11590:
11580:
11575:
11570:
11565:
11560:
11555:
11549:
11547:
11541:
11540:
11537:
11536:
11534:
11533:
11525:
11524:
11523:
11522:
11517:
11516:
11515:
11510:
11505:
11485:
11484:
11483:
11481:minimal axioms
11478:
11467:
11466:
11465:
11454:
11453:
11452:
11447:
11442:
11437:
11432:
11427:
11414:
11412:
11393:
11392:
11390:
11389:
11388:
11387:
11375:
11370:
11369:
11368:
11363:
11358:
11353:
11343:
11338:
11333:
11328:
11327:
11326:
11321:
11311:
11310:
11309:
11304:
11299:
11294:
11284:
11279:
11278:
11277:
11272:
11267:
11257:
11256:
11255:
11250:
11245:
11240:
11235:
11230:
11220:
11215:
11210:
11205:
11204:
11203:
11198:
11193:
11188:
11178:
11173:
11171:Formation rule
11168:
11163:
11162:
11161:
11156:
11146:
11145:
11144:
11134:
11129:
11124:
11119:
11113:
11107:
11090:Formal systems
11086:
11085:
11082:
11081:
11079:
11078:
11073:
11068:
11063:
11058:
11053:
11048:
11043:
11038:
11033:
11032:
11031:
11026:
11015:
11013:
11009:
11008:
11006:
11005:
11004:
11003:
10993:
10988:
10987:
10986:
10979:Large cardinal
10976:
10971:
10966:
10961:
10956:
10942:
10941:
10940:
10935:
10930:
10915:
10913:
10903:
10902:
10900:
10899:
10898:
10897:
10892:
10887:
10877:
10872:
10867:
10862:
10857:
10852:
10847:
10842:
10837:
10832:
10827:
10822:
10816:
10814:
10807:
10806:
10804:
10803:
10802:
10801:
10796:
10791:
10786:
10781:
10776:
10768:
10767:
10766:
10761:
10751:
10746:
10744:Extensionality
10741:
10739:Ordinal number
10736:
10726:
10721:
10720:
10719:
10708:
10702:
10696:
10695:
10692:
10691:
10689:
10688:
10683:
10678:
10673:
10668:
10663:
10658:
10657:
10656:
10646:
10645:
10644:
10631:
10629:
10623:
10622:
10620:
10619:
10618:
10617:
10612:
10607:
10597:
10592:
10587:
10582:
10577:
10572:
10566:
10564:
10558:
10557:
10555:
10554:
10549:
10544:
10539:
10534:
10529:
10524:
10523:
10522:
10512:
10507:
10502:
10497:
10492:
10487:
10481:
10479:
10470:
10464:
10463:
10461:
10460:
10455:
10450:
10445:
10440:
10435:
10423:Cantor's
10421:
10416:
10411:
10401:
10399:
10386:
10385:
10383:
10382:
10377:
10372:
10367:
10362:
10357:
10352:
10347:
10342:
10337:
10332:
10327:
10322:
10321:
10320:
10309:
10307:
10303:
10302:
10295:
10294:
10287:
10280:
10272:
10265:
10264:
10244:10.1086/352009
10238:(2): 259â262.
10225:
10188:
10172:
10156:
10136:
10122:
10105:
10099:
10084:
10046:Rashed, Roshdi
10042:
10016:(3): 237â248.
10002:
9975:(1â4): 85â95.
9955:
9949:
9941:Addison-Wesley
9929:
9911:
9895:
9877:(5): 197â201.
9861:
9843:(5): 199â207.
9830:
9781:
9778:
9777:
9776:
9769:
9747:
9740:
9722:
9701:978-3540058199
9700:
9684:
9666:
9659:
9639:
9636:
9635:
9633:
9630:
9627:
9626:
9584:
9564:
9542:
9517:
9487:
9460:
9445:
9438:
9420:
9417:978-0131877184
9400:
9388:
9376:
9313:
9301:
9289:
9277:
9262:
9253:
9241:
9229:
9217:
9206:on 24 May 2011
9198:Suber, Peter.
9190:
9184:978-0471033950
9183:
9157:
9132:
9113:
9112:
9110:
9107:
9106:
9105:
9100:
9093:
9090:
9079:
9078:
8992:
8988:
8985:
8965:
8962:
8959:
8956:
8953:
8950:
8947:
8879:
8875:
8872:
8852:
8849:
8846:
8843:
8840:
8837:
8834:
8786:
8782:
8778:
8775:
8772:
8769:
8766:
8763:
8760:
8757:
8754:
8751:
8748:
8744:
8740:
8737:
8734:
8731:
8728:
8725:
8722:
8719:
8716:
8669:" for the set
8530:
8529:
8526:
8505:
8484:
8436:
8433:
8389:
8388:
8373:
8362:
8322:
8321:
8299:holds for all
8264:ordinal number
8244:Main article:
8241:
8238:
8207:
8202:
8199:
8195:
8191:
8186:
8181:
8178:
8175:
8172:
8169:
8166:
8163:
8160:
8157:
8154:
8151:
8146:
8140:
8136:
8133:
8130:
8127:
8124:
8121:
8118:
8113:
8108:
8105:
8093:ZFC set theory
8085:
8084:
8073:
8066:
8043:
7920:
7915:
7908:
7903:
7900:
7897:
7894:
7889:
7883:
7880:
7877:
7872:
7867:
7864:
7861:
7858:
7855:
7852:
7849:
7846:
7843:
7840:
7837:
7832:
7827:
7824:
7821:
7818:
7815:
7812:
7809:
7804:
7798:
7795:
7773:
7772:Formalization
7770:
7756:
7753:
7750:
7728:
7725:
7722:
7701:
7698:
7695:
7692:
7689:
7669:
7666:
7663:
7643:
7640:
7637:
7628:The base case
7614:
7611:
7608:
7588:
7567:
7563:
7560:
7557:
7554:
7551:
7548:
7545:
7542:
7539:
7536:
7533:
7529:
7507:
7503:
7500:
7497:
7494:
7491:
7488:
7485:
7482:
7479:
7475:
7454:
7451:
7448:
7445:
7442:
7439:
7436:
7433:
7430:
7427:
7424:
7421:
7418:
7398:
7395:
7392:
7372:
7333:Main article:
7330:
7327:
7302:
7282:
7279:
7276:
7261:Main article:
7258:
7255:
7242:
7239:
7236:
7233:
7213:
7193:
7173:
7153:
7133:
7130:
7127:
7107:
7104:
7101:
7098:
7095:
7092:
7072:
7069:
7066:
7063:
7060:
7057:
7054:
7050:
7046:
7043:
7040:
7020:
7017:
7014:
7011:
7008:
6985:
6982:
6979:
6976:
6956:
6953:
6950:
6947:
6944:
6924:
6915:holds for all
6904:
6901:
6898:
6895:
6875:
6872:
6869:
6837:
6834:
6831:
6828:
6825:
6822:
6819:
6816:
6813:
6810:
6809:
6806:
6803:
6800:
6797:
6794:
6791:
6788:
6785:
6782:
6779:
6778:
6775:
6772:
6769:
6766:
6763:
6760:
6757:
6754:
6751:
6748:
6747:
6744:
6741:
6738:
6735:
6732:
6729:
6726:
6723:
6720:
6717:
6716:
6696:
6693:
6690:
6687:
6684:
6681:
6678:
6675:
6672:
6652:
6649:
6646:
6643:
6610:
6607:
6604:
6601:
6598:
6595:
6592:
6587:
6583:
6579:
6576:
6573:
6570:
6566:
6561:
6557:
6554:
6551:
6546:
6543:
6540:
6537:
6534:
6514:
6511:
6498:
6476:
6472:
6449:
6445:
6424:
6404:
6382:
6378:
6372:
6368:
6364:
6361:
6341:
6321:
6318:
6315:
6295:
6292:
6289:
6276:" part of the
6266:natural number
6253:
6237:
6234:
6221:
6218:
6215:
6195:
6192:
6189:
6167:
6163:
6140:
6137:
6134:
6130:
6107:
6104:
6101:
6097:
6075:
6071:
6068:
6046:
6042:
6038:
6033:
6030:
6027:
6023:
6019:
6014:
6011:
6008:
6004:
5983:
5980:
5977:
5974:
5969:
5965:
5937:
5932:
5927:
5924:
5921:
5916:
5913:
5908:
5905:
5881:
5876:
5871:
5868:
5865:
5860:
5857:
5852:
5849:
5819:
5815:
5791:
5788:
5785:
5778:
5774:
5770:
5765:
5761:
5754:
5749:
5745:
5732:
5729:
5716:
5713:
5710:
5707:
5687:
5684:
5681:
5678:
5675:
5672:
5652:
5649:
5646:
5643:
5623:
5620:
5617:
5614:
5591:
5588:
5585:
5582:
5562:
5559:
5556:
5553:
5544:and show that
5533:
5530:
5527:
5524:
5515:assuming only
5503:
5499:
5496:
5476:
5473:
5470:
5467:
5464:
5461:
5441:
5438:
5435:
5432:
5412:
5409:
5406:
5403:
5400:
5380:
5371:holds for all
5360:
5357:
5354:
5351:
5331:
5328:
5325:
5322:
5302:
5299:
5296:
5293:
5280:
5277:
5260:
5257:
5254:
5234:
5231:
5228:
5208:
5205:
5202:
5199:
5179:
5176:
5173:
5153:
5150:
5147:
5127:
5124:
5121:
5118:
5098:
5095:
5092:
5089:
5069:
5066:
5063:
5039:
5036:
5033:
5013:
5004:for all lower
4993:
4990:
4987:
4984:
4964:
4961:
4958:
4955:
4930:
4926:
4902:
4899:
4896:
4893:
4873:
4870:
4867:
4864:
4841:
4838:
4835:
4832:
4812:
4809:
4806:
4786:
4762:
4759:
4756:
4753:
4733:
4730:
4727:
4724:
4721:
4718:
4707:weak induction
4690:
4687:
4648:
4644:
4641:
4638:
4635:
4632:
4628:
4624:
4619:
4614:
4610:
4605:
4601:
4596:
4593:
4521:
4504:
4500:
4497:
4494:
4491:
4488:
4484:
4480:
4475:
4472:
4467:
4463:
4458:
4454:
4449:
4446:
4426:
4423:
4420:
4417:
4414:
4411:
4408:
4405:
4402:
4399:
4396:
4393:
4390:
4387:
4384:
4381:
4378:
4375:
4372:
4369:
4365:
4362:
4311:
4308:
4305:
4302:
4299:
4296:
4293:
4290:
4287:
4284:
4281:
4278:
4275:
4271:
4268:
4256:
4253:
4252:
4251:
4218:
4189:
4186:
4165:holds for all
4058:Main article:
4055:
4052:
4021:
4018:
3979:
3976:
3973:
3970:
3967:
3964:
3961:
3958:
3955:
3952:
3949:
3946:
3943:
3913:holds for all
3837:), prove that
3741:
3738:
3688:holds for all
3657:
3656:
3636:
3610:
3607:
3593:
3592:
3550:external links
3539:
3537:
3530:
3524:
3521:
3505:
3502:
3482:
3479:
3476:
3473:
3447:
3444:
3441:
3438:
3435:
3432:
3406:
3402:
3398:
3395:
3392:
3388:
3384:
3381:
3378:
3375:
3372:
3369:
3366:
3364:
3362:
3359:
3351:
3347:
3343:
3340:
3337:
3333:
3329:
3325:
3321:
3318:
3315:
3311:
3307:
3304:
3301:
3299:
3297:
3294:
3291:
3288:
3284:
3280:
3277:
3274:
3270:
3266:
3263:
3261:
3257:
3253:
3250:
3247:
3243:
3239:
3235:
3231:
3228:
3225:
3222:
3218:
3214:
3211:
3209:
3207:
3203:
3199:
3196:
3193:
3190:
3186:
3181:
3177:
3174:
3171:
3167:
3163:
3159:
3155:
3152:
3149:
3145:
3140:
3136:
3133:
3130:
3127:
3123:
3119:
3116:
3114:
3112:
3104:
3100:
3096:
3093:
3090:
3087:
3083:
3080:
3077:
3073:
3069:
3065:
3061:
3058:
3055:
3052:
3049:
3046:
3043:
3039:
3035:
3032:
3030:
3028:
3020:
3016:
3012:
3009:
3006:
3003:
3000:
2997:
2994:
2991:
2988:
2985:
2982:
2979:
2976:
2973:
2970:
2966:
2962:
2959:
2957:
2954:
2950:
2947:
2944:
2941:
2938:
2935:
2932:
2929:
2925:
2921:
2920:
2892:
2889:
2886:
2883:
2863:
2860:
2857:
2854:
2851:
2831:
2811:
2808:
2805:
2802:
2799:
2796:
2792:
2788:
2785:
2782:
2779:
2750:
2747:
2744:
2741:
2720:
2716:
2713:
2710:
2706:
2702:
2699:
2696:
2693:
2690:
2687:
2683:
2679:
2676:
2673:
2670:
2666:
2639:
2618:
2614:
2611:
2608:
2604:
2600:
2597:
2593:
2589:
2586:
2583:
2580:
2576:
2555:
2552:
2549:
2546:
2526:
2499:
2495:
2492:
2489:
2485:
2481:
2478:
2474:
2470:
2467:
2464:
2461:
2457:
2435:
2431:
2428:
2407:
2403:
2400:
2372:
2348:
2328:
2325:
2322:
2318:
2313:
2310:
2305:
2302:
2282:
2279:
2276:
2251:
2247:
2244:
2241:
2237:
2233:
2230:
2226:
2222:
2219:
2216:
2213:
2209:
2185:
2165:
2141:
2137:
2134:
2131:
2127:
2123:
2120:
2116:
2112:
2109:
2106:
2103:
2099:
2082:
2079:
2031:
2026:
2022:
2019:
2016:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1947:
1944:
1941:
1938:
1935:
1932:
1906:
1901:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1852:
1849:
1847:
1845:
1840:
1836:
1833:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1803:
1800:
1798:
1796:
1791:
1787:
1784:
1781:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1745:
1742:
1740:
1738:
1735:
1732:
1729:
1726:
1723:
1718:
1714:
1711:
1708:
1705:
1702:
1699:
1693:
1692:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1644:
1640:
1637:
1634:
1631:
1628:
1625:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1583:
1580:
1577:
1574:
1571:
1568:
1548:
1543:
1539:
1536:
1533:
1530:
1527:
1524:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1497:
1415:
1408:
1404:
1401:
1398:
1395:
1392:
1389:
1382:
1379:
1333:
1327:
1323:
1320:
1317:
1314:
1311:
1308:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1238:
1232:
1228:
1225:
1222:
1219:
1216:
1213:
1206:
1203:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1158:
1154:
1151:
1120:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1088:
1085:
1082:
1079:
1076:
1073:
1050:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1018:
1015:
1012:
1009:
986:
982:
979:
976:
973:
970:
967:
964:
961:
954:
951:
929:
924:
920:
917:
914:
911:
908:
905:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
863:
859:
856:
853:
850:
823:
820:
818:
815:
785:
784:
751:inductive step
745:induction step
739:
706:natural number
701:
698:
690:Giuseppe Peano
516:
513:
500:
488:involving the
463:inference rule
423:
420:
417:
397:
394:
391:
371:
368:
365:
345:
342:
339:
319:
299:
296:
293:
290:
287:
263:
260:
257:
244:, proves that
242:induction step
229:
226:
223:
193:
168:
165:
162:
159:
156:
153:
150:
147:
144:
141:
138:
135:
132:
129:
126:
123:
120:
117:
114:
111:
108:
88:
78:natural number
65:
62:
59:
56:
15:
9:
6:
4:
3:
2:
12058:
12047:
12044:
12042:
12039:
12037:
12034:
12033:
12031:
12018:
12017:
12012:
12004:
11998:
11995:
11993:
11990:
11988:
11985:
11983:
11980:
11976:
11973:
11972:
11971:
11968:
11966:
11963:
11961:
11958:
11956:
11952:
11949:
11947:
11944:
11942:
11939:
11937:
11934:
11932:
11929:
11928:
11926:
11922:
11916:
11913:
11911:
11908:
11906:
11905:Recursive set
11903:
11901:
11898:
11896:
11893:
11891:
11888:
11886:
11883:
11879:
11876:
11874:
11871:
11869:
11866:
11864:
11861:
11859:
11856:
11855:
11854:
11851:
11849:
11846:
11844:
11841:
11839:
11836:
11834:
11831:
11829:
11826:
11825:
11823:
11821:
11817:
11811:
11808:
11806:
11803:
11801:
11798:
11796:
11793:
11791:
11788:
11786:
11783:
11781:
11778:
11774:
11771:
11769:
11766:
11764:
11761:
11760:
11759:
11756:
11754:
11751:
11749:
11746:
11744:
11741:
11739:
11736:
11734:
11731:
11727:
11724:
11723:
11722:
11719:
11715:
11714:of arithmetic
11712:
11711:
11710:
11707:
11703:
11700:
11698:
11695:
11693:
11690:
11688:
11685:
11683:
11680:
11679:
11678:
11675:
11671:
11668:
11666:
11663:
11662:
11661:
11658:
11657:
11655:
11653:
11649:
11643:
11640:
11638:
11635:
11633:
11630:
11628:
11625:
11622:
11621:from ZFC
11618:
11615:
11613:
11610:
11604:
11601:
11600:
11599:
11596:
11594:
11591:
11589:
11586:
11585:
11584:
11581:
11579:
11576:
11574:
11571:
11569:
11566:
11564:
11561:
11559:
11556:
11554:
11551:
11550:
11548:
11546:
11542:
11532:
11531:
11527:
11526:
11521:
11520:non-Euclidean
11518:
11514:
11511:
11509:
11506:
11504:
11503:
11499:
11498:
11496:
11493:
11492:
11490:
11486:
11482:
11479:
11477:
11474:
11473:
11472:
11468:
11464:
11461:
11460:
11459:
11455:
11451:
11448:
11446:
11443:
11441:
11438:
11436:
11433:
11431:
11428:
11426:
11423:
11422:
11420:
11416:
11415:
11413:
11408:
11402:
11397:Example
11394:
11386:
11381:
11380:
11379:
11376:
11374:
11371:
11367:
11364:
11362:
11359:
11357:
11354:
11352:
11349:
11348:
11347:
11344:
11342:
11339:
11337:
11334:
11332:
11329:
11325:
11322:
11320:
11317:
11316:
11315:
11312:
11308:
11305:
11303:
11300:
11298:
11295:
11293:
11290:
11289:
11288:
11285:
11283:
11280:
11276:
11273:
11271:
11268:
11266:
11263:
11262:
11261:
11258:
11254:
11251:
11249:
11246:
11244:
11241:
11239:
11236:
11234:
11231:
11229:
11226:
11225:
11224:
11221:
11219:
11216:
11214:
11211:
11209:
11206:
11202:
11199:
11197:
11194:
11192:
11189:
11187:
11184:
11183:
11182:
11179:
11177:
11174:
11172:
11169:
11167:
11164:
11160:
11157:
11155:
11154:by definition
11152:
11151:
11150:
11147:
11143:
11140:
11139:
11138:
11135:
11133:
11130:
11128:
11125:
11123:
11120:
11118:
11115:
11114:
11111:
11108:
11106:
11102:
11097:
11091:
11087:
11077:
11074:
11072:
11069:
11067:
11064:
11062:
11059:
11057:
11054:
11052:
11049:
11047:
11044:
11042:
11041:KripkeâPlatek
11039:
11037:
11034:
11030:
11027:
11025:
11022:
11021:
11020:
11017:
11016:
11014:
11010:
11002:
10999:
10998:
10997:
10994:
10992:
10989:
10985:
10982:
10981:
10980:
10977:
10975:
10972:
10970:
10967:
10965:
10962:
10960:
10957:
10954:
10950:
10946:
10943:
10939:
10936:
10934:
10931:
10929:
10926:
10925:
10924:
10920:
10917:
10916:
10914:
10912:
10908:
10904:
10896:
10893:
10891:
10888:
10886:
10885:constructible
10883:
10882:
10881:
10878:
10876:
10873:
10871:
10868:
10866:
10863:
10861:
10858:
10856:
10853:
10851:
10848:
10846:
10843:
10841:
10838:
10836:
10833:
10831:
10828:
10826:
10823:
10821:
10818:
10817:
10815:
10813:
10808:
10800:
10797:
10795:
10792:
10790:
10787:
10785:
10782:
10780:
10777:
10775:
10772:
10771:
10769:
10765:
10762:
10760:
10757:
10756:
10755:
10752:
10750:
10747:
10745:
10742:
10740:
10737:
10735:
10731:
10727:
10725:
10722:
10718:
10715:
10714:
10713:
10710:
10709:
10706:
10703:
10701:
10697:
10687:
10684:
10682:
10679:
10677:
10674:
10672:
10669:
10667:
10664:
10662:
10659:
10655:
10652:
10651:
10650:
10647:
10643:
10638:
10637:
10636:
10633:
10632:
10630:
10628:
10624:
10616:
10613:
10611:
10608:
10606:
10603:
10602:
10601:
10598:
10596:
10593:
10591:
10588:
10586:
10583:
10581:
10578:
10576:
10573:
10571:
10568:
10567:
10565:
10563:
10562:Propositional
10559:
10553:
10550:
10548:
10545:
10543:
10540:
10538:
10535:
10533:
10530:
10528:
10525:
10521:
10518:
10517:
10516:
10513:
10511:
10508:
10506:
10503:
10501:
10498:
10496:
10493:
10491:
10490:Logical truth
10488:
10486:
10483:
10482:
10480:
10478:
10474:
10471:
10469:
10465:
10459:
10456:
10454:
10451:
10449:
10446:
10444:
10441:
10439:
10436:
10434:
10430:
10426:
10422:
10420:
10417:
10415:
10412:
10410:
10406:
10403:
10402:
10400:
10398:
10392:
10387:
10381:
10378:
10376:
10373:
10371:
10368:
10366:
10363:
10361:
10358:
10356:
10353:
10351:
10348:
10346:
10343:
10341:
10338:
10336:
10333:
10331:
10328:
10326:
10323:
10319:
10316:
10315:
10314:
10311:
10310:
10308:
10304:
10300:
10293:
10288:
10286:
10281:
10279:
10274:
10273:
10270:
10261:
10257:
10253:
10249:
10245:
10241:
10237:
10233:
10232:
10226:
10222:
10218:
10213:
10208:
10204:
10200:
10199:
10194:
10189:
10185:
10181:
10177:
10173:
10169:
10165:
10161:
10157:
10153:
10149:
10142:
10137:
10133:
10129:
10125:
10123:0-253-33020-3
10119:
10114:
10113:
10106:
10102:
10100:9780792325659
10096:
10092:
10091:
10085:
10081:
10077:
10073:
10069:
10065:
10061:
10057:
10054:(in French).
10053:
10052:
10047:
10043:
10039:
10035:
10031:
10027:
10023:
10019:
10015:
10011:
10007:
10003:
9998:
9994:
9990:
9986:
9982:
9978:
9974:
9970:
9969:
9964:
9960:
9956:
9952:
9950:0-321-01618-1
9946:
9942:
9938:
9934:
9930:
9926:
9922:
9921:
9916:
9912:
9908:
9904:
9900:
9896:
9892:
9888:
9884:
9880:
9876:
9872:
9871:
9866:
9862:
9858:
9854:
9850:
9846:
9842:
9838:
9837:
9831:
9827:
9823:
9819:
9815:
9811:
9807:
9803:
9799:
9798:
9793:
9791:
9784:
9783:
9772:
9766:
9762:
9761:
9756:
9752:
9748:
9743:
9737:
9733:
9732:
9727:
9723:
9719:
9715:
9711:
9707:
9703:
9697:
9693:
9689:
9685:
9681:
9677:
9676:
9671:
9667:
9662:
9656:
9652:
9651:
9646:
9642:
9641:
9621:
9616:
9612:
9608:
9604:
9597:
9595:
9593:
9591:
9589:
9581:
9575:
9568:
9561:
9557:
9554:
9553:
9546:
9531:
9530:brilliant.org
9527:
9521:
9506:
9499:
9491:
9476:
9475:
9470:
9464:
9456:
9449:
9441:
9435:
9431:
9424:
9418:
9414:
9410:
9404:
9397:
9392:
9385:
9380:
9373:
9372:3-7643-5456-9
9369:
9365:
9361:
9357:
9353:
9352:
9347:
9343:
9339:
9333:
9327:
9323:
9317:
9310:
9305:
9298:
9297:Simonson 2000
9293:
9287:, p. 62.
9286:
9281:
9274:
9273:Cajori (1918)
9269:
9267:
9257:
9250:
9245:
9238:
9233:
9226:
9221:
9205:
9201:
9194:
9186:
9180:
9176:
9171:
9170:
9161:
9155:
9151:
9150:
9146:
9143:
9136:
9130:
9126:
9125:
9118:
9114:
9104:
9101:
9099:
9096:
9095:
9089:
9085:
9070:
9065:
9064:
9063:
9059:
9055:
9051:
9045:
9038:
9034:
9030:
9023:
9019:
9015:
9008:
8986:
8983:
8960:
8957:
8954:
8948:
8945:
8935:
8931:
8927:
8923:
8915:
8911:
8903:
8899:
8895:
8873:
8870:
8847:
8844:
8841:
8835:
8832:
8822:
8818:
8814:
8810:
8804:
8800:
8776:
8773:
8770:
8764:
8761:
8758:
8749:
8738:
8735:
8732:
8726:
8723:
8720:
8699:
8695:
8691:
8683:
8679:
8675:
8668:
8663:
8659:
8647:
8643:
8636:
8632:
8617:
8610:
8606:
8599:
8588:
8584:
8569:
8554:
8550:
8541:
8537:
8533:
8527:
8522:
8516:
8506:
8502:
8494:
8485:
8458:
8454:
8453:
8452:
8450:
8446:
8442:
8432:
8429:
8425:
8415:
8409:
8405:
8399:
8394:
8386:
8385:limit ordinal
8374:
8363:
8352:
8351:
8350:
8347:
8345:
8341:
8337:
8336:
8332:), is called
8331:
8327:
8317:
8313:
8307:
8303:
8296:
8292:
8283:
8282:
8281:
8277:
8273:
8267:
8265:
8261:
8257:
8253:
8247:
8237:
8235:
8231:
8227:
8200:
8197:
8179:
8176:
8170:
8167:
8164:
8155:
8152:
8149:
8134:
8131:
8125:
8122:
8119:
8116:
8106:
8095:
8094:
8091:
8078:
8074:
8071:
8067:
8062:
8058:
8054:
8044:
8041:
8040:
8039:
8036:
8034:
8030:
8026:
8022:
8018:
8013:
8005:
8001:
7990:
7986:
7979:
7975:
7968:
7964:
7957:
7951:
7949:
7935:
7918:
7898:
7892:
7881:
7862:
7859:
7856:
7850:
7841:
7835:
7825:
7819:
7813:
7807:
7796:
7785:
7781:
7780:
7769:
7754:
7751:
7748:
7726:
7723:
7720:
7699:
7696:
7693:
7690:
7687:
7667:
7664:
7661:
7641:
7638:
7635:
7626:
7612:
7609:
7606:
7586:
7565:
7561:
7558:
7555:
7552:
7549:
7546:
7543:
7540:
7537:
7534:
7531:
7527:
7505:
7501:
7498:
7495:
7492:
7489:
7486:
7483:
7480:
7477:
7473:
7452:
7449:
7446:
7443:
7440:
7437:
7434:
7431:
7428:
7425:
7422:
7419:
7416:
7396:
7393:
7390:
7370:
7362:
7358:
7356:
7352:
7348:
7346:
7336:
7326:
7324:
7320:
7316:
7300:
7280:
7277:
7274:
7264:
7254:
7253:holds Q.E.D.
7237:
7231:
7211:
7191:
7171:
7151:
7131:
7128:
7125:
7102:
7099:
7096:
7090:
7070:
7067:
7064:
7061:
7058:
7055:
7052:
7044:
7041:
7038:
7018:
7015:
7012:
7009:
7006:
6997:
6980:
6974:
6967:. Prove that
6954:
6951:
6948:
6945:
6942:
6922:
6899:
6893:
6873:
6870:
6867:
6859:
6855:
6852:
6835:
6832:
6829:
6826:
6823:
6820:
6817:
6814:
6811:
6804:
6801:
6798:
6795:
6792:
6789:
6786:
6783:
6780:
6773:
6770:
6767:
6764:
6761:
6758:
6755:
6752:
6749:
6742:
6739:
6736:
6733:
6730:
6727:
6724:
6721:
6718:
6694:
6691:
6688:
6685:
6682:
6679:
6676:
6673:
6670:
6647:
6641:
6633:
6629:
6628:
6624:
6621:
6608:
6605:
6602:
6599:
6596:
6593:
6590:
6585:
6577:
6574:
6571:
6568:
6555:
6552:
6549:
6544:
6538:
6532:
6524:
6520:
6510:
6496:
6474:
6470:
6447:
6443:
6422:
6402:
6380:
6376:
6370:
6366:
6362:
6359:
6339:
6319:
6316:
6313:
6293:
6290:
6287:
6279:
6275:
6271:
6270:prime numbers
6267:
6251:
6243:
6233:
6219:
6216:
6213:
6193:
6190:
6187:
6165:
6161:
6138:
6135:
6132:
6128:
6105:
6102:
6099:
6095:
6069:
6066:
6044:
6040:
6036:
6031:
6028:
6025:
6021:
6017:
6012:
6009:
6006:
6002:
5981:
5978:
5975:
5972:
5967:
5963:
5955:
5951:
5930:
5925:
5922:
5914:
5911:
5906:
5903:
5895:
5874:
5869:
5866:
5858:
5855:
5850:
5847:
5839:
5817:
5813:
5789:
5786:
5783:
5776:
5772:
5768:
5763:
5759:
5752:
5747:
5743:
5728:
5711:
5705:
5682:
5679:
5676:
5670:
5647:
5641:
5618:
5612:
5603:
5586:
5580:
5557:
5551:
5528:
5522:
5497:
5494:
5471:
5468:
5465:
5459:
5436:
5430:
5410:
5407:
5404:
5401:
5398:
5378:
5355:
5349:
5326:
5320:
5297:
5291:
5276:
5258:
5255:
5252:
5232:
5229:
5226:
5203:
5197:
5177:
5174:
5171:
5151:
5148:
5145:
5122:
5116:
5093:
5087:
5067:
5064:
5061:
5053:
5037:
5034:
5031:
5011:
4988:
4982:
4959:
4953:
4944:
4928:
4924:
4916:
4897:
4891:
4868:
4862:
4853:
4836:
4830:
4810:
4807:
4804:
4784:
4776:
4757:
4751:
4728:
4725:
4722:
4716:
4708:
4704:
4700:
4696:
4686:
4682:
4678:
4671:
4665:
4646:
4639:
4633:
4626:
4622:
4617:
4612:
4608:
4603:
4599:
4594:
4582:
4580:
4576:
4572:
4569:
4563:
4552:
4550:
4544:
4540:
4533:
4528:
4524:
4516:
4502:
4495:
4489:
4482:
4478:
4473:
4470:
4465:
4461:
4456:
4452:
4447:
4418:
4415:
4412:
4409:
4403:
4400:
4394:
4391:
4385:
4376:
4370:
4363:
4352:
4347:
4343:
4339:
4332:
4322:
4303:
4300:
4297:
4291:
4282:
4276:
4269:
4248:
4242:
4232:
4219:
4215:
4211:
4210:
4209:
4206:
4196:
4185:
4177:
4173:
4162:
4158:
4143:
4139:
4132:
4128:
4122:
4114:
4110:
4105:
4091:
4087:
4076:
4072:
4067:
4061:
4051:
4049:
4048:
4044:accompanying
4043:
4017:
4009:
4002:
3974:
3971:
3968:
3965:
3962:
3959:
3956:
3953:
3950:
3944:
3941:
3931:
3927:
3921:
3917:
3910:
3906:
3900:
3896:
3892:
3885:
3874:
3863:
3856:
3852:
3845:
3841:
3836:
3830:
3823:
3819:
3814:
3810:
3806:
3799:
3795:
3791:Showing that
3790:
3786:
3778:
3771:
3767:
3756:
3752:
3737:
3725:
3721:
3717:
3710:
3706:
3699:
3692:
3685:
3681:
3675:
3671:
3664:
3652:
3646:
3642:
3637:
3633:
3629:
3624:
3623:
3622:
3606:
3604:
3600:
3589:
3586:
3578:
3568:
3564:
3558:
3557:
3551:
3547:
3543:
3538:
3529:
3528:
3520:
3503:
3500:
3477:
3471:
3463:
3459:
3442:
3439:
3436:
3430:
3421:
3404:
3400:
3396:
3393:
3390:
3386:
3379:
3376:
3373:
3367:
3365:
3345:
3341:
3338:
3335:
3331:
3327:
3323:
3319:
3316:
3313:
3309:
3305:
3302:
3300:
3289:
3286:
3282:
3278:
3275:
3272:
3268:
3262:
3255:
3251:
3248:
3245:
3241:
3237:
3233:
3229:
3226:
3223:
3220:
3216:
3212:
3210:
3201:
3197:
3194:
3191:
3188:
3184:
3179:
3175:
3172:
3169:
3165:
3161:
3157:
3153:
3150:
3147:
3143:
3138:
3134:
3131:
3128:
3125:
3121:
3117:
3115:
3098:
3094:
3091:
3088:
3085:
3081:
3078:
3075:
3071:
3067:
3063:
3059:
3056:
3053:
3050:
3047:
3044:
3041:
3037:
3033:
3031:
3014:
3010:
3007:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2974:
2971:
2968:
2964:
2960:
2958:
2952:
2948:
2942:
2939:
2936:
2930:
2927:
2923:
2911:, we deduce:
2910:
2906:
2887:
2881:
2861:
2858:
2855:
2852:
2849:
2829:
2806:
2803:
2800:
2794:
2783:
2777:
2770:
2766:
2762:
2745:
2739:
2718:
2714:
2711:
2708:
2704:
2700:
2697:
2694:
2691:
2688:
2685:
2681:
2677:
2674:
2671:
2668:
2664:
2655:
2651:
2637:
2616:
2612:
2609:
2606:
2602:
2598:
2595:
2591:
2587:
2584:
2581:
2578:
2574:
2550:
2544:
2524:
2516:
2512:
2497:
2493:
2490:
2487:
2483:
2479:
2476:
2472:
2468:
2465:
2462:
2459:
2455:
2429:
2426:
2401:
2398:
2390:
2389:
2384:
2370:
2362:
2346:
2326:
2323:
2320:
2316:
2311:
2308:
2303:
2300:
2280:
2277:
2274:
2266:
2249:
2245:
2242:
2239:
2235:
2231:
2228:
2224:
2220:
2217:
2214:
2211:
2207:
2197:
2183:
2163:
2156:
2139:
2135:
2132:
2129:
2125:
2121:
2118:
2114:
2110:
2107:
2104:
2101:
2097:
2088:
2078:
2077:
2067:
2063:
2058:
2054:
2050:
2046:
2029:
2024:
2017:
2014:
2008:
2005:
2002:
1990:
1987:
1984:
1975:
1969:
1966:
1963:
1957:
1954:
1951:
1948:
1945:
1942:
1939:
1936:
1933:
1930:
1921:
1904:
1899:
1892:
1889:
1883:
1880:
1877:
1865:
1862:
1859:
1850:
1848:
1838:
1831:
1828:
1825:
1816:
1813:
1810:
1801:
1799:
1789:
1782:
1779:
1776:
1770:
1767:
1761:
1758:
1755:
1749:
1743:
1741:
1733:
1730:
1727:
1721:
1716:
1709:
1706:
1703:
1697:
1682:
1681:Algebraically
1678:
1665:
1659:
1656:
1653:
1647:
1642:
1635:
1632:
1629:
1623:
1617:
1611:
1608:
1605:
1599:
1593:
1590:
1587:
1584:
1581:
1578:
1575:
1572:
1569:
1546:
1541:
1534:
1531:
1528:
1522:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1495:
1485:
1481:
1475:
1471:
1461:
1457:
1453:
1446:
1442:
1435:
1430:
1426:
1413:
1406:
1399:
1396:
1393:
1387:
1380:
1377:
1367:
1362:
1358:
1353:
1349:
1331:
1325:
1318:
1315:
1312:
1306:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1262:
1258:
1253:
1249:
1236:
1230:
1223:
1220:
1217:
1211:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1152:
1149:
1141:
1140:
1135:
1118:
1111:
1108:
1105:
1096:
1086:
1083:
1080:
1077:
1074:
1071:
1048:
1041:
1038:
1035:
1026:
1016:
1013:
1010:
1007:
984:
977:
974:
971:
962:
952:
949:
940:
927:
922:
915:
912:
909:
903:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
861:
854:
848:
834:
830:
814:
811:
807:
798:
794:
780:
769:
756:
752:
748:
740:
737:
733:
725:
724:
723:
715:
707:
697:
695:
691:
687:
683:
679:
675:
670:
668:
664:
660:
656:
652:
648:
645:The earliest
643:
640:
635:
632:
625:
621:
616:
614:
613:cyclic method
610:
604:
602:
598:
594:
590:
586:
583:from that of
582:
578:
574:
570:
566:
562:
555:
552:
550:
546:
542:
538:
535:to prove the
534:
530:
526:
522:
512:
498:
491:
487:
483:
479:
474:
472:
468:
467:formal proofs
464:
460:
456:
452:
449:, is used in
448:
444:
440:
435:
421:
418:
415:
395:
392:
389:
369:
366:
363:
343:
340:
337:
317:
297:
294:
291:
288:
285:
277:
261:
258:
255:
247:
243:
227:
224:
221:
213:
209:
200:
199:
192:
190:
186:
180:
166:
163:
157:
151:
148:
142:
136:
133:
127:
121:
118:
112:
106:
86:
79:
60:
54:
46:
42:
35:
30:
26:
22:
12007:
11805:Ultraproduct
11652:Model theory
11617:Independence
11553:Formal proof
11545:Proof theory
11528:
11501:
11458:real numbers
11430:second-order
11341:Substitution
11218:Metalanguage
11159:conservative
11132:Axiom schema
11076:Constructive
11046:MorseâKelley
11012:Set theories
10991:Aleph number
10984:inaccessible
10890:Grothendieck
10774:intersection
10661:Higher-order
10649:Second-order
10595:Truth tables
10552:Venn diagram
10335:Formal proof
10235:
10229:
10205:(2): 70â73.
10202:
10196:
10183:
10179:
10167:
10163:
10151:
10147:
10111:
10089:
10055:
10049:
10013:
10009:
9972:
9966:
9936:
9924:
9918:
9906:
9902:
9874:
9868:
9840:
9834:
9804:(1): 57â76.
9801:
9795:
9789:
9759:
9730:
9691:
9688:Hermes, Hans
9673:
9649:
9645:Franklin, J.
9638:Introduction
9613:(3): 33â40.
9610:
9606:
9579:
9573:
9567:
9551:
9545:
9533:. Retrieved
9529:
9520:
9508:. Retrieved
9504:
9490:
9478:. Retrieved
9472:
9463:
9454:
9448:
9429:
9423:
9408:
9403:
9396:Shields 1997
9391:
9379:
9363:
9355:
9349:
9345:
9341:
9337:
9331:
9325:
9321:
9316:
9304:
9292:
9280:
9256:
9244:
9232:
9220:
9208:. Retrieved
9204:the original
9193:
9168:
9160:
9140:
9135:
9123:
9121:Matt DeVos,
9117:
9083:
9080:
9068:
9060:
9056:
9049:
9043:
9036:
9032:
9028:
9021:
9017:
9013:
9009:(0, 0)
9006:
8933:
8929:
8925:
8921:
8913:
8909:
8901:
8897:
8893:
8820:
8816:
8812:
8808:
8802:
8706:
8697:
8693:
8689:
8681:
8677:
8673:
8645:
8641:
8634:
8630:
8615:
8608:
8604:
8597:
8586:
8582:
8567:
8552:
8548:
8535:
8534:
8531:
8520:
8514:
8500:
8492:
8445:Peano axioms
8438:
8427:
8423:
8413:
8407:
8403:
8397:
8390:
8348:
8333:
8326:well-ordered
8323:
8315:
8311:
8305:
8301:
8294:
8290:
8275:
8271:
8268:
8249:
8088:
8086:
8060:
8056:
8052:
8037:
8033:Peano axioms
8029:axiom schema
8027:requires an
8016:
8014:
8003:
7999:
7988:
7984:
7977:
7973:
7966:
7962:
7955:
7952:
7933:
7777:
7775:
7627:
7360:
7359:
7354:
7350:
7349:
7338:
7266:
6998:
6857:
6856:
6853:
6631:
6630:
6626:
6625:
6622:
6522:
6516:
6241:
6239:
5894:golden ratio
5734:
5604:
5282:
4945:
4854:
4774:
4706:
4702:
4698:
4694:
4692:
4680:
4676:
4669:
4663:
4583:
4564:
4553:
4542:
4538:
4531:
4526:
4517:
4348:
4341:
4337:
4330:
4323:
4258:
4246:
4240:
4230:
4217:holds for 0,
4213:
4204:
4194:
4191:
4175:
4171:
4160:
4156:
4141:
4137:
4135:defined as "
4130:
4126:
4123:
4112:
4108:
4089:
4085:
4074:
4070:
4063:
4045:
4023:
4007:
4000:
3929:
3925:
3922:
3915:
3908:
3904:
3901:
3894:
3890:
3883:
3872:
3861:
3854:
3850:
3843:
3839:
3834:
3828:
3821:
3817:
3812:
3811:
3804:
3797:
3793:
3788:
3787:
3785:as follows:
3776:
3769:
3765:
3754:
3750:
3743:
3723:
3719:
3715:
3708:
3704:
3697:
3690:
3683:
3679:
3676:
3669:
3662:
3658:
3650:
3644:
3640:
3631:
3627:
3612:
3596:
3581:
3572:
3561:Please help
3553:
3461:
3460:
3422:
2767:We show the
2764:
2763:
2653:
2652:
2514:
2513:
2388:Proposition.
2387:
2386:
2385:
2360:
2264:
2198:
2087:inequalities
2084:
2065:
2061:
2056:
2055:
2048:
2044:
1922:
1679:
1483:
1479:
1473:
1469:
1462:
1460:also holds.
1455:
1451:
1449:holds, then
1444:
1440:
1433:
1428:
1427:
1365:
1363:
1356:
1351:
1350:
1260:
1256:
1251:
1250:
1139:Proposition.
1138:
1137:
1136:
941:
832:
828:
825:
812:
805:
796:
792:
786:
778:
767:
754:
750:
742:
736:initial case
735:
727:
713:
703:
678:George Boole
671:
658:
644:
638:
623:
617:
606:
596:
592:
588:
584:
580:
576:
572:
564:
557:
553:
548:
518:
475:
439:well-founded
436:
275:
245:
241:
211:
207:
205:
196:
188:
184:
182:
40:
39:
25:
11915:Type theory
11863:undecidable
11795:Truth value
11682:equivalence
11361:non-logical
10974:Enumeration
10964:Isomorphism
10911:cardinality
10895:Von Neumann
10860:Ultrafilter
10825:Uncountable
10759:equivalence
10676:Quantifiers
10666:Fixed-point
10635:First-order
10515:Consistency
10500:Proposition
10477:Traditional
10448:Lindström's
10438:Compactness
10380:Type theory
10325:Cardinality
10058:(1): 1â21.
9384:Peirce 1881
9285:Rashed 1994
9237:Rashed 1994
9225:Acerbi 2000
9041:. However,
8667:Number line
8497:is greater
8417:is true of
8320:also holds.
8090:first-order
7323:powers of 2
7224:. That is,
7083:shows that
6860:Given some
4579:existential
3815:Given that
3567:introducing
3462:Conclusion:
2769:implication
2155:real number
2057:Conclusion:
700:Description
519:In 370 BC,
471:correctness
12030:Categories
11726:elementary
11419:arithmetic
11287:Quantifier
11265:functional
11137:Expression
10855:Transitive
10799:identities
10784:complement
10717:hereditary
10700:Set theory
10186:: 267â272.
10176:Unguru, S.
10170:: 273â289.
10160:Unguru, S.
9909:: 253â265.
9899:Fowler, D.
9790:Parmenides
9632:References
9535:23 October
9439:0486492370
9054:is false.
8916:) = (0, 0)
8823:+ 1)
8637:+ 1)
8611:+ 1)
8602:. Then if
8595:less than
8561:is not in
8457:trichotomy
8340:set theory
8288:, that if
8228:using the
8017:predicates
7980:+ 1)
7351:Base case:
6663:holds for
6634:Show that
6632:Base case:
5954:polynomial
5391:such that
5024:) for all
4975:(assuming
4797:less than
4773:holds for
4244:holds for
4234:holds for
4224:less than
4202:, proving
3897:+ 1)
3846:+ 1)
3802:holds for
3789:Base case:
2654:Base case:
2537:, and let
2363:values of
2051:+ 1)
1458:+ 1)
1352:Base case:
1142:For every
651:Gersonides
525:Parmenides
11997:Supertask
11900:Recursion
11858:decidable
11692:saturated
11670:of models
11593:deductive
11588:axiomatic
11508:Hilbert's
11495:Euclidean
11476:canonical
11399:axiomatic
11331:Signature
11260:Predicate
11149:Extension
11071:Ackermann
10996:Operation
10875:Universal
10865:Recursive
10840:Singleton
10835:Inhabited
10820:Countable
10810:Types of
10794:power set
10764:partition
10681:Predicate
10627:Predicate
10542:Syllogism
10532:Soundness
10505:Inference
10495:Tautology
10397:paradoxes
10260:144112534
10080:124040444
10038:119948133
9826:123045154
9710:1431-4657
9680:EMS Press
9086:â 1
9071:+ 1
8987:∈
8949:∈
8938:for some
8928:) = succ(
8874:∈
8836:∈
8803:successor
8777:∈
8750:∪
8739:∈
8618:+ 1
8613:is false
8600:+ 1
8540:non-empty
8523:+ 1
8495:+ 1
8198:⊆
8190:→
8177:∈
8159:→
8153:∈
8135:∈
8129:∀
8126:∧
8120:∈
8104:∀
8070:injective
7879:∀
7876:→
7848:→
7823:∀
7820:∧
7794:∀
7550:…
7496:…
7435:…
7278:−
7129:−
7100:−
7062:−
7056:≤
7049:⟹
7016:−
6999:Choosing
6946:≤
6886:, assume
6827:⋅
6815:⋅
6796:⋅
6784:⋅
6765:⋅
6753:⋅
6734:⋅
6722:⋅
6578:∈
6565:∃
6560:⟹
6553:≥
6274:existence
6070:∈
6059:for each
5979:−
5973:−
5926:−
5904:ψ
5848:φ
5790:ψ
5787:−
5784:φ
5773:ψ
5769:−
5760:φ
5498:∈
5408:≤
5402:≤
5035:≥
4631:→
4592:∀
4487:→
4445:∀
4401:∧
4383:→
4361:∀
4289:→
4267:∀
3945:∈
3899:is true.
3886:+ 1
3875:+ 1
3653:+ 1
3575:July 2013
3394:
3339:
3317:
3303:≤
3287:≤
3276:
3249:
3224:
3213:≤
3192:
3173:
3151:
3129:
3089:
3079:
3057:
3045:
3034:≤
3005:
2996:
2984:
2972:
2931:
2859:≥
2791:⟹
2732:verifies
2712:
2692:≤
2672:
2610:
2596:≤
2582:
2491:
2477:≤
2463:
2430:∈
2402:∈
2327:π
2243:
2229:≤
2215:
2133:
2119:≤
2105:
1949:⋯
1588:⋯
1508:⋯
1291:⋯
1196:⋯
1153:∈
889:⋯
808:+ 1
781:+ 1
770:+ 1
755:step case
730:base case
597:al-Fakhri
561:Aryabhata
529:al-Karaji
459:recursion
419:≥
212:base case
167:…
11982:Logicism
11975:timeline
11951:Concrete
11810:Validity
11780:T-schema
11773:Kripke's
11768:Tarski's
11763:semantic
11753:Strength
11702:submodel
11697:spectrum
11665:function
11513:Tarski's
11502:Elements
11489:geometry
11445:Robinson
11366:variable
11351:function
11324:spectrum
11314:Sentence
11270:variable
11213:Language
11166:Relation
11127:Automata
11117:Alphabet
11101:language
10955:-jection
10933:codomain
10919:Function
10880:Universe
10850:Infinite
10754:Relation
10537:Validity
10527:Argument
10425:theorem,
9961:(1881).
9935:(1998).
9927:: 17â37.
9818:41134098
9788:"Plato:
9757:(1975).
9728:(1997).
9690:(1973).
9682:. 2001 .
9665:(Ch. 8.)
9556:Archived
9210:26 March
9145:Archived
9092:See also
8825:for all
8513:between
8344:topology
7971:implies
7936:(·)
7625:horses.
7321:for all
6244:smaller
5948:are the
5573:implies
5080:, where
4662:log log
4623:⌋
4613:⌊
4479:⌋
4466:⌊
3523:Variants
2907:and the
2391:For any
2267:numbers
2263:for any
2153:for any
1488:is true:
817:Examples
647:rigorous
634:integers
609:Bhaskara
490:variable
465:used in
194:â
11924:Related
11721:Diagram
11619: (
11598:Hilbert
11583:Systems
11578:Theorem
11456:of the
11401:systems
11181:Formula
11176:Grammar
11092: (
11036:General
10749:Forcing
10734:Element
10654:Monadic
10429:paradox
10370:Theorem
10306:General
10221:1558845
10132:1720827
10072:1554160
10030:1554128
9997:1507856
9989:2369151
9891:2972638
9857:2974308
9780:History
9718:0345788
9351:sorites
9026:, then
8565:. Then
8411:, then
8393:vacuous
8309:, then
6996:holds.
5952:of the
5832:is the
4568:bounded
4525:
4238:, then
4106:) that
3563:improve
3519:Q.E.D.
2361:natural
1134:, etc.
657:in his
622:in his
515:History
45:proving
11687:finite
11450:Skolem
11403:
11378:Theory
11346:Symbol
11336:String
11319:atomic
11196:ground
11191:closed
11186:atomic
11142:ground
11105:syntax
11001:binary
10928:domain
10845:Finite
10610:finite
10468:Logics
10427:
10375:Theory
10258:
10252:230435
10250:
10219:
10180:Physis
10164:Physis
10130:
10120:
10097:
10078:
10070:
10036:
10028:
9995:
9987:
9947:
9903:Physis
9889:
9855:
9824:
9816:
9767:
9738:
9716:
9708:
9698:
9657:
9510:28 May
9436:
9415:
9370:
9181:
9031:(succ(
8620:is in
8536:Proof.
7931:where
6627:Proof.
5896:) and
5840:, and
5805:where
3998:. For
3601:; see
3517:
2515:Proof.
2076:Q.E.D.
1252:Proof.
868:
865:
692:, and
663:Fermat
655:Pascal
11677:Model
11425:Peano
11282:Proof
11122:Arity
11051:Naive
10938:image
10870:Fuzzy
10830:Empty
10779:union
10724:Class
10365:Model
10355:Lemma
10313:Axiom
10256:S2CID
10248:JSTOR
10144:(PDF)
10076:S2CID
10034:S2CID
9985:JSTOR
9887:JSTOR
9853:JSTOR
9822:S2CID
9814:JSTOR
9501:(PDF)
9480:4 May
9338:2ndly
9330:when
9109:Notes
9052:(1,0)
8815:) = (
8807:succ(
8688:{(1,
8672:{(0,
8654:; so
8542:set,
8499:than
8441:axiom
8426:<
8406:<
8375:when
8364:when
8353:when
8330:class
8304:<
8077:range
7784:axiom
6935:with
6519:above
6332:. If
5950:roots
5892:(the
4228:, if
3603:below
3548:, or
1438:, if
753:, or
569:truth
521:Plato
443:trees
185:basis
11800:Type
11603:list
11407:list
11384:list
11373:Term
11307:rank
11201:open
11095:list
10907:Maps
10812:sets
10671:Free
10641:list
10391:list
10318:list
10231:Isis
10118:ISBN
10095:ISBN
9945:ISBN
9765:ISBN
9736:ISBN
9706:ISSN
9696:ISBN
9655:ISBN
9574:Opus
9537:2019
9512:2023
9482:2023
9434:ISBN
9413:ISBN
9368:ISBN
9212:2011
9179:ISBN
8976:and
8863:and
8518:and
8463:and
8455:The
8232:and
8063:+ 1)
8059:) =
7942:and
7740:and
7665:>
7519:and
7164:and
7068:<
7042:<
6952:<
6871:>
6462:and
6317:>
6291:>
6206:and
6153:and
5836:-th
5487:for
5452:and
5256:<
5230:>
5175:>
5164:and
4028:and
4010:= 10
4003:= 11
3918:â„ 12
3864:â„ 12
3831:â„ 12
3807:= 12
3779:â„ 12
3700:â„ â5
3667:for
3661:2 â„
2419:and
2265:real
1254:Let
749:(or
741:The
734:(or
726:The
611:'s "
453:and
276:then
189:step
11487:of
11469:of
11417:of
10949:Sur
10923:Map
10730:Ur-
10712:Set
10240:doi
10207:doi
10060:doi
10018:doi
9977:doi
9879:doi
9845:doi
9806:doi
9615:doi
9334:= 1
9326:1st
8918:or
8906:as
8692:):
8676:):
8570:(0)
8087:In
8079:of
7958:(0)
7776:In
7355:one
6242:all
4775:all
4701:or
4674:to
4672:(0)
4536:to
4534:(0)
4520:log
4335:to
4333:(0)
4249:+ 1
3693:â„ 1
3672:â„ 3
3665:+ 5
3391:sin
3336:sin
3314:sin
3273:cos
3246:sin
3221:sin
3189:cos
3170:sin
3148:cos
3126:sin
3086:cos
3076:sin
3054:cos
3042:sin
3002:cos
2993:sin
2981:cos
2969:sin
2928:sin
2709:sin
2669:sin
2607:sin
2579:sin
2488:sin
2460:sin
2240:sin
2212:sin
2130:sin
2102:sin
1436:â„ 0
1368:(0)
1359:= 0
795:or
716:â„ 0
636:is
631:odd
615:".
523:'s
480:as
12032::
11873:NP
11497::
11491::
11421::
11098:),
10953:Bi
10945:In
10254:.
10246:.
10236:69
10234:.
10217:MR
10215:.
10203:16
10201:.
10195:.
10184:31
10182:.
10168:28
10166:.
10152:10
10150:.
10146:.
10128:MR
10126:.
10074:.
10068:MR
10066:.
10032:.
10026:MR
10024:.
10012:.
9993:MR
9991:.
9983:.
9971:.
9965:.
9943:.
9939:.
9923:.
9907:31
9905:.
9885:.
9875:25
9873:.
9851:.
9841:24
9839:.
9820:.
9812:.
9802:55
9800:.
9794:.
9753:;
9714:MR
9712:.
9704:.
9678:.
9672:.
9611:41
9609:.
9605:.
9587:^
9528:.
9503:.
9471:.
9336:.
9265:^
9177:.
9152:,
9127:,
9039:))
9035:,
9020:,
8932:,
8924:,
8912:,
8900:,
8819:,
8811:,
8696:â
8686:âȘ
8680:â
8490:,
8467:,
8342:,
8236:.
7950:.
7768:.
7347::
7053:12
7039:15
6943:12
6874:15
6836:15
6805:14
6774:13
6743:12
6707:.
6695:15
6689:14
6683:13
6677:12
6556:12
6232:.
5727:.
5602:.
4943:.
4697:,
4184:.
4121:.
4016:.
3992:12
3975:10
3746:12
3736:.
3722:+
3674:.
3643:â„
3630:=
3605:.
3552:,
3544:,
2761:.
2650:.
2511:.
2447:,
2196:.
2074:.
1472:=
1361:.
1348:.
1170:,
1064:,
1000:,
841:.
810:.
696:.
688:,
684:,
680:,
669:.
642:.
587:=
579:=
434:.
274:,
246:if
206:A
191:).
11953:/
11868:P
11623:)
11409:)
11405:(
11302:â
11297:!
11292:â
11253:=
11248:â
11243:â
11238:â§
11233:âš
11228:ÂŹ
10951:/
10947:/
10921:/
10732:)
10728:(
10615:â
10605:3
10393:)
10291:e
10284:t
10277:v
10262:.
10242::
10223:.
10209::
10134:.
10103:.
10082:.
10062::
10056:9
10040:.
10020::
10014:6
9999:.
9979::
9973:4
9953:.
9925:6
9893:.
9881::
9859:.
9847::
9828:.
9808::
9773:.
9744:.
9720:.
9663:.
9623:.
9617::
9576:.
9539:.
9514:.
9494:.
9484:.
9442:.
9398:.
9386:.
9374:)
9346:n
9342:n
9332:n
9322:n
9311:.
9299:.
9227:.
9214:.
9187:.
9175:1
9084:n
9077:.
9075:n
9069:n
9050:P
9044:P
9037:n
9033:x
9029:P
9024:)
9022:n
9018:x
9016:(
9014:P
9007:P
8991:N
8984:m
8964:}
8961:1
8958:,
8955:0
8952:{
8946:y
8936:)
8934:m
8930:y
8926:n
8922:x
8920:(
8914:n
8910:x
8908:(
8904:)
8902:n
8898:x
8896:(
8894:P
8878:N
8871:n
8851:}
8848:1
8845:,
8842:0
8839:{
8833:x
8821:n
8817:x
8813:n
8809:x
8785:}
8781:N
8774:n
8771::
8768:)
8765:n
8762:,
8759:1
8756:(
8753:{
8747:}
8743:N
8736:n
8733::
8730:)
8727:n
8724:,
8721:0
8718:(
8715:{
8700:}
8698:N
8694:n
8690:n
8684:}
8682:N
8678:n
8674:n
8665:"
8656:S
8652:n
8648:)
8646:n
8644:(
8642:P
8635:n
8633:(
8631:P
8626:S
8622:S
8616:n
8609:n
8607:(
8605:P
8598:n
8593:m
8589:)
8587:m
8585:(
8583:P
8578:n
8574:S
8568:P
8563:S
8559:n
8555:)
8553:n
8551:(
8549:P
8544:S
8525:.
8521:n
8515:n
8509:n
8504:.
8501:n
8493:n
8488:n
8483:.
8481:n
8477:m
8473:m
8469:n
8465:m
8461:n
8428:m
8424:n
8419:m
8414:P
8408:m
8404:n
8398:P
8387:.
8381:n
8377:n
8370:n
8366:n
8361:;
8359:n
8355:n
8318:)
8316:n
8314:(
8312:P
8306:n
8302:m
8297:)
8295:m
8293:(
8291:P
8286:n
8278:)
8276:n
8274:(
8272:P
8221:A
8206:)
8201:A
8194:N
8185:)
8180:A
8174:)
8171:1
8168:+
8165:k
8162:(
8156:A
8150:k
8145:(
8139:N
8132:k
8123:A
8117:0
8112:(
8107:A
8083:.
8081:s
8072:.
8065:.
8061:x
8057:x
8055:(
8053:s
8051:(
8047:s
8010:n
8006:)
8004:n
8002:(
8000:P
7995:n
7991:)
7989:n
7987:(
7985:P
7978:k
7976:(
7974:P
7969:)
7967:k
7965:(
7963:P
7956:P
7944:n
7940:k
7934:P
7919:,
7914:)
7907:)
7902:)
7899:n
7896:(
7893:P
7888:(
7882:n
7871:)
7866:)
7863:1
7860:+
7857:k
7854:(
7851:P
7845:)
7842:k
7839:(
7836:P
7831:(
7826:k
7817:)
7814:0
7811:(
7808:P
7803:(
7797:P
7755:}
7752:2
7749:{
7727:}
7724:1
7721:{
7700:2
7697:=
7694:1
7691:+
7688:n
7668:1
7662:n
7642:1
7639:=
7636:n
7613:1
7610:+
7607:n
7587:n
7566:}
7562:1
7559:+
7556:n
7553:,
7547:,
7544:4
7541:,
7538:3
7535:,
7532:2
7528:{
7506:}
7502:n
7499:,
7493:,
7490:3
7487:,
7484:2
7481:,
7478:1
7474:{
7453:1
7450:+
7447:n
7444:,
7441:n
7438:,
7432:,
7429:3
7426:,
7423:2
7420:,
7417:1
7397:1
7394:+
7391:n
7371:n
7341:n
7301:n
7281:1
7275:n
7241:)
7238:j
7235:(
7232:S
7212:j
7192:4
7172:5
7152:4
7132:4
7126:j
7106:)
7103:4
7097:j
7094:(
7091:S
7071:j
7065:4
7059:j
7045:j
7019:4
7013:j
7010:=
7007:m
6984:)
6981:j
6978:(
6975:S
6955:j
6949:m
6923:m
6903:)
6900:m
6897:(
6894:S
6868:j
6833:=
6830:3
6824:5
6821:+
6818:0
6812:4
6802:=
6799:2
6793:5
6790:+
6787:1
6781:4
6771:=
6768:1
6762:5
6759:+
6756:2
6750:4
6740:=
6737:0
6731:5
6728:+
6725:3
6719:4
6692:,
6686:,
6680:,
6674:=
6671:k
6651:)
6648:k
6645:(
6642:S
6609:b
6606:5
6603:+
6600:a
6597:4
6594:=
6591:n
6586:.
6582:N
6575:b
6572:,
6569:a
6550:n
6545::
6542:)
6539:n
6536:(
6533:S
6497:m
6475:2
6471:n
6448:1
6444:n
6423:m
6403:m
6381:2
6377:n
6371:1
6367:n
6363:=
6360:m
6340:m
6320:1
6314:n
6294:1
6288:n
6252:n
6220:1
6217:=
6214:n
6194:0
6191:=
6188:n
6166:n
6162:F
6139:1
6136:+
6133:n
6129:F
6106:2
6103:+
6100:n
6096:F
6074:N
6067:n
6045:n
6041:F
6037:+
6032:1
6029:+
6026:n
6022:F
6018:=
6013:2
6010:+
6007:n
6003:F
5982:1
5976:x
5968:2
5964:x
5936:)
5931:5
5923:1
5920:(
5915:2
5912:1
5907:=
5880:)
5875:5
5870:+
5867:1
5864:(
5859:2
5856:1
5851:=
5834:n
5818:n
5814:F
5777:n
5764:n
5753:=
5748:n
5744:F
5715:)
5712:n
5709:(
5706:P
5686:)
5683:1
5680:+
5677:n
5674:(
5671:P
5651:)
5648:0
5645:(
5642:P
5622:)
5619:n
5616:(
5613:P
5590:)
5587:n
5584:(
5581:P
5561:)
5558:n
5555:(
5552:Q
5532:)
5529:n
5526:(
5523:Q
5502:N
5495:n
5475:)
5472:1
5469:+
5466:n
5463:(
5460:Q
5440:)
5437:0
5434:(
5431:Q
5411:n
5405:m
5399:0
5379:m
5359:)
5356:m
5353:(
5350:P
5330:)
5327:n
5324:(
5321:Q
5301:)
5298:n
5295:(
5292:P
5273:m
5259:m
5253:n
5233:0
5227:m
5207:)
5204:m
5201:(
5198:P
5178:0
5172:m
5152:0
5149:=
5146:m
5126:)
5123:n
5120:(
5117:P
5097:)
5094:0
5091:(
5088:P
5068:0
5065:=
5062:m
5038:0
5032:m
5012:n
4992:)
4989:n
4986:(
4983:P
4963:)
4960:m
4957:(
4954:P
4929:n
4925:F
4901:)
4898:1
4895:(
4892:P
4872:)
4869:0
4866:(
4863:P
4840:)
4837:m
4834:(
4831:P
4811:1
4808:+
4805:m
4785:n
4761:)
4758:n
4755:(
4752:P
4732:)
4729:1
4726:+
4723:m
4720:(
4717:P
4683:)
4681:n
4679:(
4677:P
4670:P
4664:n
4647:)
4643:)
4640:k
4637:(
4634:P
4627:)
4618:k
4609:(
4604:P
4600:(
4595:k
4560:n
4556:n
4545:)
4543:n
4541:(
4539:P
4532:P
4527:n
4522:2
4503:)
4499:)
4496:k
4493:(
4490:P
4483:)
4474:2
4471:k
4462:(
4457:P
4453:(
4448:k
4425:)
4422:)
4419:1
4416:+
4413:k
4410:2
4407:(
4404:P
4398:)
4395:k
4392:2
4389:(
4386:P
4380:)
4377:k
4374:(
4371:P
4368:(
4364:k
4344:)
4342:n
4340:(
4338:P
4331:P
4326:n
4310:)
4307:)
4304:1
4301:+
4298:k
4295:(
4292:P
4286:)
4283:k
4280:(
4277:P
4274:(
4270:k
4247:x
4241:P
4236:x
4231:P
4226:n
4222:x
4214:P
4205:P
4200:n
4195:P
4182:n
4178:)
4176:n
4174:(
4172:Q
4167:n
4163:)
4161:n
4159:(
4157:P
4152:n
4148:m
4144:)
4142:m
4140:(
4138:Q
4133:)
4131:n
4129:(
4127:P
4119:n
4115:)
4113:n
4111:(
4109:Q
4100:m
4096:n
4092:)
4090:n
4088:(
4086:Q
4081:n
4077:)
4075:n
4073:(
4071:Q
4038:m
4034:n
4030:m
4026:n
4014:m
4008:m
4001:m
3996:m
3978:}
3972:,
3969:9
3966:,
3963:8
3960:,
3957:5
3954:,
3951:4
3948:{
3942:k
3932:)
3930:k
3928:(
3926:S
3916:k
3911:)
3909:k
3907:(
3905:S
3895:k
3893:(
3891:S
3884:k
3879:k
3873:k
3868:k
3862:k
3857:)
3855:k
3853:(
3851:S
3844:k
3842:(
3840:S
3833:(
3829:k
3824:)
3822:k
3820:(
3818:S
3805:k
3800:)
3798:k
3796:(
3794:S
3783:k
3777:k
3772:)
3770:k
3768:(
3766:S
3761:k
3757:)
3755:k
3753:(
3751:S
3734:0
3730:n
3726:)
3724:b
3720:n
3718:(
3716:P
3711:)
3709:n
3707:(
3705:P
3698:n
3691:n
3686:)
3684:n
3682:(
3680:P
3670:n
3663:n
3655:.
3651:n
3645:b
3641:n
3635:.
3632:b
3628:n
3619:b
3615:n
3588:)
3582:(
3577:)
3573:(
3559:.
3504:.
3501:n
3481:)
3478:n
3475:(
3472:P
3446:)
3443:1
3440:+
3437:k
3434:(
3431:P
3405:.
3401:|
3397:x
3387:|
3383:)
3380:1
3377:+
3374:k
3371:(
3368:=
3358:)
3346:|
3342:x
3332:|
3328:+
3324:|
3320:x
3310:|
3306:k
3293:)
3290:1
3283:|
3279:t
3269:|
3265:(
3256:|
3252:x
3242:|
3238:+
3234:|
3230:x
3227:k
3217:|
3202:|
3198:x
3195:k
3185:|
3180:|
3176:x
3166:|
3162:+
3158:|
3154:x
3144:|
3139:|
3135:x
3132:k
3122:|
3118:=
3099:|
3095:x
3092:k
3082:x
3072:|
3068:+
3064:|
3060:x
3051:x
3048:k
3038:|
3015:|
3011:x
3008:k
2999:x
2990:+
2987:x
2978:x
2975:k
2965:|
2961:=
2953:|
2949:x
2946:)
2943:1
2940:+
2937:k
2934:(
2924:|
2891:)
2888:k
2885:(
2882:P
2862:0
2856:k
2853:=
2850:n
2830:k
2810:)
2807:1
2804:+
2801:k
2798:(
2795:P
2787:)
2784:k
2781:(
2778:P
2749:)
2746:0
2743:(
2740:P
2719:|
2715:x
2705:|
2701:0
2698:=
2695:0
2689:0
2686:=
2682:|
2678:x
2675:0
2665:|
2638:n
2617:|
2613:x
2603:|
2599:n
2592:|
2588:x
2585:n
2575:|
2554:)
2551:n
2548:(
2545:P
2525:x
2498:|
2494:x
2484:|
2480:n
2473:|
2469:x
2466:n
2456:|
2434:N
2427:n
2406:R
2399:x
2371:n
2347:n
2324:=
2321:x
2317:,
2312:2
2309:1
2304:=
2301:n
2281:x
2278:,
2275:n
2250:|
2246:x
2236:|
2232:n
2225:|
2221:x
2218:n
2208:|
2184:n
2164:x
2140:|
2136:x
2126:|
2122:n
2115:|
2111:x
2108:n
2098:|
2072:n
2068:)
2066:n
2064:(
2062:P
2049:k
2047:(
2045:P
2030:.
2025:2
2021:)
2018:1
2015:+
2012:)
2009:1
2006:+
2003:k
2000:(
1997:(
1994:)
1991:1
1988:+
1985:k
1982:(
1976:=
1973:)
1970:1
1967:+
1964:k
1961:(
1958:+
1955:k
1952:+
1946:+
1943:2
1940:+
1937:1
1934:+
1931:0
1905:.
1900:2
1896:)
1893:1
1890:+
1887:)
1884:1
1881:+
1878:k
1875:(
1872:(
1869:)
1866:1
1863:+
1860:k
1857:(
1851:=
1839:2
1835:)
1832:2
1829:+
1826:k
1823:(
1820:)
1817:1
1814:+
1811:k
1808:(
1802:=
1790:2
1786:)
1783:1
1780:+
1777:k
1774:(
1771:2
1768:+
1765:)
1762:1
1759:+
1756:k
1753:(
1750:k
1744:=
1737:)
1734:1
1731:+
1728:k
1725:(
1722:+
1717:2
1713:)
1710:1
1707:+
1704:k
1701:(
1698:k
1666:.
1663:)
1660:1
1657:+
1654:k
1651:(
1648:+
1643:2
1639:)
1636:1
1633:+
1630:k
1627:(
1624:k
1618:=
1615:)
1612:1
1609:+
1606:k
1603:(
1600:+
1597:)
1594:k
1591:+
1585:+
1582:2
1579:+
1576:1
1573:+
1570:0
1567:(
1547:.
1542:2
1538:)
1535:1
1532:+
1529:k
1526:(
1523:k
1517:=
1514:k
1511:+
1505:+
1502:1
1499:+
1496:0
1486:)
1484:k
1482:(
1480:P
1474:k
1470:n
1465:k
1456:k
1454:(
1452:P
1447:)
1445:k
1443:(
1441:P
1434:k
1414:.
1407:2
1403:)
1400:1
1397:+
1394:0
1391:(
1388:0
1381:=
1378:0
1366:P
1357:n
1346:n
1332:.
1326:2
1322:)
1319:1
1316:+
1313:n
1310:(
1307:n
1300:=
1297:n
1294:+
1288:+
1285:2
1282:+
1279:1
1276:+
1273:0
1263:)
1261:n
1259:(
1257:P
1237:.
1231:2
1227:)
1224:1
1221:+
1218:n
1215:(
1212:n
1205:=
1202:n
1199:+
1193:+
1190:2
1187:+
1184:1
1181:+
1178:0
1157:N
1150:n
1119:2
1115:)
1112:1
1109:+
1106:2
1103:(
1100:)
1097:2
1094:(
1087:=
1084:2
1081:+
1078:1
1075:+
1072:0
1049:2
1045:)
1042:1
1039:+
1036:1
1033:(
1030:)
1027:1
1024:(
1017:=
1014:1
1011:+
1008:0
985:2
981:)
978:1
975:+
972:0
969:(
966:)
963:0
960:(
953:=
950:0
928:.
923:2
919:)
916:1
913:+
910:n
907:(
904:n
898:=
895:n
892:+
886:+
883:2
880:+
877:1
874:+
871:0
862::
858:)
855:n
852:(
849:P
839:n
835:)
833:n
831:(
829:P
806:n
801:n
789:n
783:.
779:n
774:n
768:n
763:n
759:n
720:n
714:n
709:n
639:n
628:n
603:.
593:n
589:k
585:n
581:k
577:n
573:n
565:n
499:n
422:N
416:n
396:N
393:=
390:n
370:1
367:=
364:n
344:0
341:=
338:n
318:n
298:1
295:+
292:k
289:=
286:n
262:k
259:=
256:n
228:0
225:=
222:n
164:,
161:)
158:3
155:(
152:P
149:,
146:)
143:2
140:(
137:P
134:,
131:)
128:1
125:(
122:P
119:,
116:)
113:0
110:(
107:P
87:n
64:)
61:n
58:(
55:P
36:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
