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