842:(p. 42), however, "parts of mathematics we want to retain, particularly analysis, also contain impredicative definitions." (ibid). Weyl in his 1918 ("Das Kontinuum") attempted to derive as much of analysis as was possible without the use of impredicative definitions, "but not the theorem that an arbitrary non-empty set M of real numbers having an upper bound has a least upper bound (CF. also Weyl 1919)" (p. 43).
49:. Roughly speaking, a definition is impredicative if it invokes (mentions or quantifies over) the set being defined, or (more commonly) another set that contains the thing being defined. There is no generally accepted precise definition of what it means to be predicative or impredicative. Authors have given different but related definitions.
868:
itself ("Is the definition of "impredicable" impredicable?"). He claims to show methods for eliminating the "paradoxes of syntax" ("logical paradoxes") — by use of the theory of types — and "the paradoxes of semantics" — by the use of metalanguage (his "theory of levels of language"). He attributes
841:
IMPREDICATIVE DEFINITION (p. 42). He states that his 6 or so (famous) examples of paradoxes (antinomies) are all examples of impredicative definition, and says that
Poincaré (1905–6, 1908) and Russell (1906, 1910) "enunciated the cause of the paradoxes to lie in these impredicative definitions"
461:
argued that "impredicative" definitions can be harmless: for instance, the definition of "tallest person in the room" is impredicative, since it depends on a set of things of which it is an element, namely the set of all persons in the room. Concerning mathematics, an example of an impredicative
408:
all objects that are dependent upon the notion defined, that is, that can in any way be determined by it". He gives two examples of impredicative definitions – (i) the notion of
Dedekind chains and (ii) "in analysis wherever the maximum or minimum of a previously defined "completed" set of
415:
is used for further inferences. This happens, for example, in the well-known Cauchy proof...". He ends his section with the following observation: "A definition may very well rely upon notions that are equivalent to the one being defined; indeed, in every definition
356:
observes that "The paradox shook the logicians' world, and the rumbles are still felt today. ... Russell's paradox, which uses the bare notions of set and element, falls squarely in the field of logic. The paradox was first published by
Russell in
339:
is not a predicate. Likewise there is no class (as a totality) of those classes which, each taken as a totality, do not belong to themselves. From this I conclude that under certain circumstances a definable collection does not form a
74:
is that such a set cannot exist: If it would exist, the question could be asked whether it contains itself or not—if it does then by definition it should not, and if it does not then by definition it should.
60:, which retains ramification (without the explicit levels) so as to discard impredicativity. The 'levels' here correspond to the number of layers of dependency in a term definition.
321:
You state ... that a function too, can act as the indeterminate element. This I formerly believed, but now this view seems doubtful to me because of the following contradiction. Let
361:(1903) and is discussed there in great detail ...". Russell, after six years of false starts, would eventually answer the matter with his 1908 theory of types by "propounding his
348:
Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build arithmetic.
371:
function: a function in which the types of apparent variables run no higher than the types of the arguments". But this "axiom" was met with resistance from all quarters.
435:
in his discussion of impredicative definitions; Kleene does not resolve this problem. In the next paragraphs he discusses Weyl's attempt in his 1918
56:(or ramified) theories where quantification over a type at one 'level' results in types at a new, higher, level. A prototypical example is
424:
are equivalent notions, and the strict observance of
Poincaré's demand would make every definition, hence all of science, impossible".
224:
in the wake of the paradoxes as a requirement on legitimate set specifications. Sets that do not meet the requirement are called
394:. Poincaré and Weyl argued that impredicative definitions are problematic only when one or more underlying sets are infinite.
404:" where he argued against "Poincaré (1906, p. 307) a definition is 'predicative' and logically admissible only if it
352:
While the problem had adverse personal consequences for both men (both had works at the printers that had to be emended),
759:
940:
884:
857:
830:
194:, p.34) (Russell used "norm" to mean a proposition: roughly something that can take the values "true" or "false".)
53:
935:
427:
Zermelo's example of minimum and maximum of a previously defined "completed" set of numbers reappears in
950:
547:
209:
provides a historical review of predicativity, connecting it to current outstanding research problems.
57:
379:
35:
19:"Predicativism" redirects here. For the other school of philosophy, also known as predicativism, see
213:
443:) to eliminate impredicative definitions and his failure to retain the "theorem that an arbitrary
273:
On the other hand, it may also be that the argument is determinate and the function indeterminate.
945:
524:
333:
be predicated of itself? From each answer its opposite follows. Therefore we must conclude that
586:
400:
in his 1908 "A new proof of the possibility of a well-ordering" presents an entire section "b.
864:(pp. 218 — wherein he demonstrates how to create antinomies, including the definition of
785:
541:
363:
154:
557:
528:
240:
79:
63:
919:
515:(2005) discusses predicative and impredicative theories at some length, in the context of
8:
872:
428:
353:
252:
232:
955:
260:
880:
853:
826:
818:
432:
67:
52:
The opposite of impredicativity is predicativity, which essentially entails building
383:
217:
915:
907:
845:
808:
796:
781:
520:
374:
The rejection of impredicatively defined mathematical objects (while accepting the
248:
221:
206:
771:
611:
in van
Heijenoort 1967:104; see also his commentary before Georg Cantor's (1899)
512:
458:
265:
255:. Russell's awareness of the problem originated in June 1901 with his reading of
375:
43:
177:
Norms (containing one variable) which do not define classes I propose to call
929:
891:
812:
397:
327:
be the predicate: to be a predicate that cannot be predicated of itself. Can
20:
801:"On Some Difficulties in the Theory of Transfinite Numbers and Order Types"
387:
244:
150:
462:
definition is the smallest number in a set, which is formally defined as:
452:
27:
911:
869:
the suggestion of this notion to
Russell and more concretely to Ramsey.
766:
46:
455:
having an upper bound has a least upper bound (cf. also Weyl 1919)".
444:
800:
877:
From Frege to Gödel: A Source Book in
Mathematical Logic, 1879-1931
552:
754:
317:
itself? Russell promptly wrote Frege a letter pointing out that:
71:
367:. It says that any function is coextensive with what he calls a
344:
Frege promptly wrote back to
Russell acknowledging the problem:
66:
is a famous example of an impredicative construction—namely the
895:
199:
The terms "predicative" and "impredicative" were introduced by
689:
Willard V. Quine's commentary before
Bertrand Russell's 1908
676:
Van
Heijenoort's commentary before Bertrand Russell's (1902)
516:
256:
247:
had apparently discovered the same paradox in his (Cantor's)
31:
790:
The Oxford Handbook of Philosophy of Mathematics and Logic
607:
van Heijenoort's commentary before Burali-Forti's (1897)
378:
as classically understood) leads to the position in the
624:
Commentary by van Heijenoort before Bertrand Russell's
300:
is the invariant part. So why not substitute the value
203:, though the meaning has changed a little since then.
149:. This definition quantifies over the set (potentially
16:
Notion of self-reference in mathematics and philosophy
896:"Neuer Beweis für die Möglichkeit einer Wohlordnung"
269:; the offending sentence in Frege is the following:
695:
157:in question) whose members are the lower bounds of
825:, North-Holland Publishing Company, Amsterdam NY,
691:Mathematical logic as based on the theory of types
927:
70:of all sets that do not contain themselves. The
402:Objection concerning nonpredicative definition
431:1952:42-42, where Kleene uses the example of
181:; those which do define classes I shall call
862:§40. The antinomies and the theory of types
755:"Predicative and Impredicative Definitions"
163:, one of which being the glb itself. Hence
879:, Harvard University Press, Cambridge MA,
96:, also has an impredicative definition:
890:
839:§12 First inferences from the paradoxes
795:
701:
231:The first modern paradox appeared with
200:
191:
928:
137:less than or equal to all elements of
382:known as predicativism, advocated by
792:. Oxford University Press: 590–624.
767:PlanetMath article on predicativism
760:Internet Encyclopedia of Philosophy
13:
14:
967:
609:A question on transfinite numbers
598:dates derived from Kleene 1952:42
237:A question on transfinite numbers
852:, Dover Publications, Inc., NY,
473:if and only if for all elements
107:if and only if for all elements
823:Introduction to Metamathematics
734:
725:
716:
707:
683:
670:
657:
654:in van Heijenoort 1967:124-125
644:
631:
618:
601:
592:
579:
570:
239:and would become known as the
167:would reject this definition.
1:
747:
359:The principles of mathematics
7:
875:1967, third printing 1976,
722:van Heijenoort 1967:190–191
534:
10:
972:
850:Elements of Symbolic Logic
667:in van Hiejenoort 1967:127
628:in van Heijenoort 1967:124
615:in van Heijenoort 1967:113
548:Impredicative polymorphism
170:
58:intuitionistic type theory
18:
941:Philosophy of mathematics
641:in van Heijenoort 1967:23
491:is less than or equal to
380:philosophy of mathematics
251:and this become known as
143:is less than or equal to
125:is less than or equal to
36:philosophy of mathematics
833:. In particular cf. his
778:. Princeton Univ. Press.
650:Bertrand Russell's 1902
563:
214:vicious circle principle
805:Proc. London Math. Soc.
731:van Heijenoort 1967:191
713:van Heijenoort 1967:190
663:Gottlob Frege's (1902)
525:second-order arithmetic
813:10.1112/plms/s2-4.1.29
350:
342:
277:In other words, given
275:
187:
900:Mathematische Annalen
837:(pp. 36–40) and
821:1952 (1971 edition),
637:Gottlob Frege (1879)
364:axiom of reducibility
346:
319:
271:
175:
529:axiomatic set theory
294:is the variable and
241:Burali-Forti paradox
80:greatest lower bound
38:, something that is
873:Jean van Heijenoort
807:, s2–4 (1): 29–53,
585:Solomon Feferman, "
542:Gödel, Escher, Bach
233:Cesare Burali-Forti
220:(1905–6, 1908) and
153:, depending on the
936:Mathematical logic
912:10.1007/BF01450054
613:Letter to Dedekind
261:mathematical logic
249:"naive" set theory
951:Concepts in logic
835:§11 The Paradoxes
819:Stephen C. Kleene
665:Letter to Russell
576:Kleene 1952:42–43
558:Richard's paradox
433:least upper bound
216:was suggested by
64:Russell's paradox
963:
922:
846:Hans Reichenbach
815:
782:Solomon Feferman
763:
741:
738:
732:
729:
723:
720:
714:
711:
705:
699:
693:
687:
681:
674:
668:
661:
655:
648:
642:
635:
629:
626:Lettern to Frege
622:
616:
605:
599:
596:
590:
583:
577:
574:
521:Peano arithmetic
508:
502:
496:
490:
484:
478:
472:
450:
414:
338:
332:
326:
316:
310:
299:
293:
287:
253:Cantor's paradox
222:Bertrand Russell
207:Solomon Feferman
195:
162:
148:
142:
136:
130:
124:
118:
112:
106:
95:
87:
44:self-referencing
971:
970:
966:
965:
964:
962:
961:
960:
926:
925:
753:
750:
745:
744:
739:
735:
730:
726:
721:
717:
712:
708:
700:
696:
688:
684:
678:Letter to Frege
675:
671:
662:
658:
652:Letter to Frege
649:
645:
639:Begriffsschrift
636:
632:
623:
619:
606:
602:
597:
593:
584:
580:
575:
571:
566:
537:
507:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
470:
466:
463:
448:
413:
410:
376:natural numbers
337:
334:
331:
328:
325:
322:
315:
312:
308:
304:
301:
298:
295:
292:
289:
285:
281:
278:
266:Begriffsschrift
259:'s treatise of
197:
189:
179:non-predicative
173:
161:
158:
147:
144:
141:
138:
135:
132:
129:
126:
123:
120:
117:
114:
111:
108:
104:
100:
97:
93:
89:
86:
83:
24:
17:
12:
11:
5:
969:
959:
958:
953:
948:
946:Self-reference
943:
938:
924:
923:
888:
870:
843:
816:
793:
779:
769:
764:
749:
746:
743:
742:
740:Kleene 1952:43
733:
724:
715:
706:
694:
682:
669:
656:
643:
630:
617:
600:
591:
578:
568:
567:
565:
562:
561:
560:
555:
550:
545:
536:
533:
505:
499:
493:
487:
481:
475:
468:
464:
411:
384:Henri Poincaré
354:van Heijenoort
335:
329:
323:
313:
306:
302:
296:
290:
283:
279:
218:Henri Poincaré
201:Russell (1907)
174:
172:
169:
159:
145:
139:
133:
127:
121:
115:
109:
102:
98:
91:
84:
15:
9:
6:
4:
3:
2:
968:
957:
954:
952:
949:
947:
944:
942:
939:
937:
934:
933:
931:
921:
917:
913:
909:
905:
902:(in German),
901:
897:
893:
889:
886:
885:0-674-32449-8
882:
878:
874:
871:
867:
863:
859:
858:0-486-24004-5
855:
851:
847:
844:
840:
836:
832:
831:0-7204-2103-9
828:
824:
820:
817:
814:
810:
806:
802:
798:
794:
791:
787:
786:Predicativity
783:
780:
777:
773:
770:
768:
765:
762:
761:
756:
752:
751:
737:
728:
719:
710:
703:
698:
692:
686:
679:
673:
666:
660:
653:
647:
640:
634:
627:
621:
614:
610:
604:
595:
588:
587:Predicativity
582:
573:
569:
559:
556:
554:
551:
549:
546:
544:
543:
539:
538:
532:
530:
526:
522:
518:
514:
510:
460:
456:
454:
446:
442:
441:The Continuum
438:
437:Das Kontinuum
434:
430:
425:
423:
419:
407:
403:
399:
398:Ernst Zermelo
395:
393:
392:Das Kontinuum
389:
385:
381:
377:
372:
370:
366:
365:
360:
355:
349:
345:
341:
318:
288:the function
274:
270:
268:
267:
262:
258:
254:
250:
246:
242:
238:
234:
229:
227:
226:impredicative
223:
219:
215:
210:
208:
204:
202:
196:
193:
186:
184:
180:
168:
166:
165:predicativism
156:
152:
81:
76:
73:
69:
65:
61:
59:
55:
50:
48:
45:
41:
40:impredicative
37:
33:
29:
22:
21:Ultrafinitism
903:
899:
876:
866:impredicable
865:
861:
849:
838:
834:
822:
804:
789:
776:Fixing Frege
775:
772:John Burgess
758:
736:
727:
718:
709:
702:Zermelo 1908
697:
690:
685:
677:
672:
664:
659:
651:
646:
638:
633:
625:
620:
612:
608:
603:
594:
581:
572:
540:
511:
457:
453:real numbers
440:
436:
426:
421:
417:
405:
401:
396:
391:
388:Hermann Weyl
373:
368:
362:
358:
351:
347:
343:
320:
276:
272:
264:
245:Georg Cantor
236:
230:
225:
211:
205:
198:
192:Russell 1907
188:
182:
178:
176:
164:
77:
62:
51:
39:
25:
906:: 107–128,
892:Zermelo, E.
797:Russell, B.
422:definiendum
369:predicative
263:, his 1879
183:predicative
28:mathematics
930:Categories
920:38.0096.02
860:. Cf. his
748:References
519:'s logic,
131:, and any
54:stratified
47:definition
956:Recursion
784:, 2005, "
445:non-empty
418:definiens
340:totality.
82:of a set
894:(1908),
799:(1907),
774:, 2005.
680:1967:124
589:" (2002)
553:Logicism
535:See also
409:numbers
406:excludes
235:'s 1897
151:infinite
513:Burgess
390:in his
171:History
72:paradox
918:
887:(pbk.)
883:
856:
848:1947,
829:
527:, and
503:is in
497:, and
467:= min(
459:Ramsey
429:Kleene
101:= glb(
788:" in
564:Notes
517:Frege
257:Frege
155:order
42:is a
32:logic
881:ISBN
854:ISBN
827:ISBN
447:set
420:and
386:and
311:for
212:The
90:glb(
78:The
34:and
916:JFM
908:doi
809:doi
479:of
451:of
113:of
68:set
26:In
932::
914:,
904:65
898:,
803:,
757:,
531:.
523:,
509:.
485:,
243:.
228:.
185:.
119:,
88:,
30:,
910::
811::
704:.
506:X
500:y
494:x
488:y
482:X
476:x
471:)
469:X
465:y
449:M
439:(
412:Z
336:w
330:w
324:w
314:f
309:)
307:a
305:(
303:f
297:a
291:f
286:)
284:a
282:(
280:f
190:(
160:X
146:y
140:X
134:z
128:x
122:y
116:X
110:x
105:)
103:X
99:y
94:)
92:X
85:X
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.