154:
even of itself). To avoid self-contradiction, it is necessary when discussing truth values to envision levels of languages, each of which can predicate truth (or falsehood) only of languages at a lower level. So, when one sentence refers to the truth-value of another, it is semantically higher. The sentence referred to is part of the "object language", while the referring sentence is considered to be a part of a "meta-language" with respect to the object language. It is legitimate for sentences in "languages" higher on the semantic hierarchy to refer to sentences lower in the "language" hierarchy, but not the other way around. This prevents a system from becoming self-referential.
1533:
109:(1999) adds this comment: "Well, the Mexican mathematical historian Alejandro Garcidiego has taken the trouble to find that letter , and it is rather a different paradox. Berry’s letter actually talks about the first ordinal that can’t be named in a finite number of words. According to Cantor’s theory such an ordinal must exist, but we’ve just named it in a finite number of words, which is a contradiction."
1523:
165:+1 which asserts that the first statement is false." This is a true, meaningful statement about the hierarchy that Tarski defines, but it refers to statements at every level of the hierarchy, so it must be above every level of the hierarchy, and is therefore not possible within the hierarchy (although bounded versions of the sentence are possible).
286:
paradoxes similar to this one, i.e. descriptions shorter than what the complexity of the described string implies. That is to say, the definition of the Berry number is paradoxical because it is not actually possible to compute how many words are required to define a number, and we know that such computation is not possible because of the paradox.
269:
may be used interchangeably, since a number is actually a string of symbols, e.g. an
English word (like the word "eleven" used in the paradox) while, on the other hand, it is possible to refer to any word with a number, e.g. by the number of its position in a given dictionary or by suitable encoding.
79:
Since there are only twenty-six letters in the
English alphabet, there are finitely many phrases of under sixty letters, and hence finitely many positive integers that are defined by phrases of under sixty letters. Since there are infinitely many positive integers, this means that there are positive
153:
to find how this resolution in languages falls short. Alfred Tarski diagnosed the paradox as arising only in languages that are "semantically closed", by which he meant a language in which it is possible for one sentence to predicate truth (or falsehood) of another sentence in the same language (or
129:
fallacies. Other terms with this type of ambiguity are: satisfiable, true, false, function, property, class, relation, cardinal, and ordinal. To resolve one of these paradoxes means to pinpoint exactly where our use of language went wrong and to provide restrictions on the use of language which may
285:
which avoids ambiguities about which string results from a given description. It can be proven that the
Kolmogorov complexity is not computable. The proof by contradiction shows that if it were possible to compute the Kolmogorov complexity, then it would also be possible to systematically generate
84:
positive integer that satisfies that property; therefore, there is a smallest positive integer satisfying the property "not definable in under sixty letters". This is the integer to which the above expression refers. But the above expression is only fifty-seven letters long, therefore it
133:
This family of paradoxes can be resolved by incorporating stratifications of meaning in language. Terms with systematic ambiguity may be written with subscripts denoting that one level of meaning is considered a higher priority than another in their interpretation. "The number not
97:
defined by this expression. This is a paradox: there must be an integer defined by this expression, but since the expression is self-contradictory (any integer it defines is definable in under sixty letters), there cannot be any integer defined by it.
169:
is credited with identifying this incompleteness in Tarski's hierarchy in his highly cited paper "Outline of a theory of truth," and it is recognized as a general problem in hierarchical languages.
261:
It is not possible in general to unambiguously define what is the minimal number of symbols required to describe a given string (given a specific description mechanism). In this context, the terms
274:. The complexity of a given string is then defined as the minimal length that a description requires in order to (unambiguously) refer to the full representation of that string.
618:
Glanzberg, Michael (2015). "Complexity and hierarchy in truth predicates". In
Achourioti, Theodora; Galinon, Henri; Fernández, JosĂ© MartĂnez; Fujimoto, Kentaro (eds.).
177:
Using programs or proofs of bounded lengths, it is possible to construct an analogue of the Berry expression in a formal mathematical language, as has been done by
519:
969:
667:(November 1975). "Outline of a theory of truth". Seventy-Second Annual Meeting American Philosophical Association, Eastern Division (Nov. 6, 1975).
1572:
1117:
80:
integers that cannot be defined by phrases of under sixty letters. If there are positive integers that satisfy a given property, then there is a
654:
635:
270:
Some long strings can be described exactly using fewer symbols than those required by their full representation, as is often achieved using
188:
30:
arising from an expression like "The smallest positive integer not definable in under sixty letters" (a phrase with fifty-seven letters).
1567:
860:
505:
311:
1178:
1147:
984:
727:
705:
608:
547:
909:
302:'s 5th century discussion of self-referential paradox, including the fact that stating something to be unnameable makes it nameable
1403:
1562:
1396:
1557:
1220:
1050:
326:
157:
However, this system is incomplete. One would like to be able to make statements such as "For every statement in level
813:
763:
181:. Though the formal analogue does not lead to a logical contradiction, it does prove certain impossibility results.
1577:
1172:
1112:
335:
1240:
1055:
1215:
125:
in less..." the term "nameable" is also one that has this systematic ambiguity. Terms of this kind give rise to
1335:
539:
126:
48:. Russell called Berry "the only person in Oxford who understood mathematical logic". The paradox was called "
121:
in the word "definable". In other formulations of the Berry paradox, such as one that instead reads: "...not
1463:
1423:
1300:
1097:
1015:
919:
914:
853:
715:
341:
295:
1340:
1230:
771:
561:
1381:
1325:
1210:
1045:
939:
745:
320:
256:
1498:
1483:
1458:
1453:
1305:
622:. Logic, Epistemology, and the Unity of Science. Vol. 36. Dordrecht: Springer. pp. 211–243.
1503:
1488:
1478:
1443:
1391:
1320:
1235:
1107:
1102:
1025:
1020:
949:
346:
49:
41:
1265:
1225:
1189:
1122:
989:
959:
954:
924:
889:
884:
776:
741:
1536:
1493:
1473:
1413:
1386:
1184:
1137:
1127:
1040:
904:
846:
684:
1438:
1085:
1080:
1070:
1035:
944:
36:, the first to discuss the paradox in print, attributed it to G. G. Berry (1867–1928), a junior
1526:
1508:
1448:
1428:
1418:
1345:
1330:
1250:
1245:
1075:
1030:
899:
821:
723:
701:
650:
631:
604:
543:
1468:
1433:
1408:
1360:
1285:
1260:
1255:
1167:
1157:
1132:
795:
737:
676:
623:
596:
576:
271:
53:
45:
33:
24:
588:
1376:
1355:
1350:
1310:
1152:
1142:
979:
974:
964:
929:
584:
557:
500:
282:
278:
178:
102:
69:
299:
236:
1315:
1290:
1280:
1275:
1205:
1005:
894:
1551:
1295:
1162:
531:
514:
146:
1092:
1065:
1060:
496:
150:
824:
247:
symbols" can be formalized and shown to be a definition in the sense just stated.
627:
1270:
664:
305:
192:
166:
829:
580:
118:
37:
93:
the smallest positive integer not definable in under sixty letters, and is
870:
688:
72:
27:
495:
Beall, J. C.; Glanzberg, Michael; Ripley, David (December 12, 2016).
439:
437:
435:
191:
in a new and much simpler way. The basic idea of his proof is that a
838:
785:
680:
117:
The Berry paradox as formulated above arises because of systematic
934:
122:
842:
517:(1989). "A New Proof of the Gödel Incompleteness Theorem".
187:
built on a formalized version of Berry's paradox to prove
316:
Pages displaying short descriptions of redirect targets
308: – Longest-running Turing machine of a given size
235:
symbols long} can be shown to be representable (using
323: – Real number uniquely specified by description
443:
331:
Pages displaying wikidata descriptions as a fallback
1369:
1198:
998:
877:
349: – Apparent contradiction in metamathematics
698:The Collected Papers of Bertrand Russell, vol. 5
402:
161:of the hierarchy, there is a statement at level
786:The False Assumption Underlying Berry's Paradox
243:is the first number not definable in less than
338: – On the smallest non-interesting number
854:
142:in less than eleven words under this scheme.
8:
520:Notices of the American Mathematical Society
647:The Cambridge Companion to Bertrand Russell
277:The Kolmogorov complexity is defined using
1522:
861:
847:
839:
722:(2nd ed.). Harvard University Press.
138:in less than eleven words" may be nameable
775:
454:
314: – Measure of algorithmic complexity
89:definable in under sixty letters, and is
764:"On Random and Hard-to-Describe Numbers"
466:
366:
359:
251:Relationship with Kolmogorov complexity
798:(1906) "Les paradoxes de la logique",
478:
426:
390:
184:
75:not definable in under sixty letters."
800:Revue de métaphysique et de morale 14
720:The Ways of Paradox, and Other Essays
414:
378:
101:Mathematician and computer scientist
7:
506:Stanford Encyclopedia of Philosophy
1179:What the Tortoise Said to Achilles
444:Beall, Glanzberg & Ripley 2016
14:
603:. European Mathematical Society.
601:The Blind Spot: Lectures on Logic
1532:
1531:
1521:
620:Unifying the Philosophy of Truth
329: – limit of classical logic
312:Chaitin's incompleteness theorem
812:Roosen-Runge, Peter H. (1997) "
1573:Algorithmic information theory
649:. Cambridge University Press.
189:Gödel's incompleteness theorem
1:
750:. Cambridge University Press.
790:Journal of Symbolic Logic 53
762:Bennett, Charles H. (1979).
628:10.1007/978-94-017-9673-6_10
403:Russell & Whitehead 1927
1594:
1568:Self-referential paradoxes
696:Moore, Gregory H. (2014).
645:Griffin, Nicholas (2003).
336:Interesting number paradox
254:
1517:
784:French, James D. (1988) "
669:The Journal of Philosophy
239:). Then the proposition "
231:has a definition that is
64:Consider the expression:
716:Quine, Willard Van Orman
540:Harvard University Press
207:for some natural number
149:'s contributions to the
16:Self-referential paradox
1098:Paradoxes of set theory
581:10.1002/cplx.6130010107
536:Logic, logic, and logic
342:Paradoxes of set theory
327:Hilbert–Bernays paradox
1563:Mathematical paradoxes
145:However, one can read
747:Principia Mathematica
321:Definable real number
257:Kolmogorov complexity
219:, and that the set {(
1464:Kavka's toxin puzzle
1236:Income and fertility
742:Whitehead, Alfred N.
542:. pp. 383–388.
296:Bhartrhari's paradox
1558:Eponymous paradoxes
1123:Temperature paradox
1046:Free choice paradox
910:Fitch's knowability
562:"The Berry paradox"
1499:Prisoner's dilemma
1185:Heat death paradox
1173:Unexpected hanging
1138:Chicken or the egg
822:Weisstein, Eric W.
298:, a 1981 paper on
1578:Logical paradoxes
1545:
1544:
1216:Arrow information
796:Russell, Bertrand
768:IBM Report RC7483
738:Russell, Bertrand
656:978-0-521-63634-6
637:978-94-017-9672-9
597:Girard, Jean-Yves
347:Richard's paradox
50:Richard's paradox
1585:
1535:
1534:
1525:
1524:
1336:Service recovery
1190:Olbers's paradox
890:Buridan's bridge
863:
856:
849:
840:
835:
834:
814:Berry's Paradox.
781:
779:
751:
733:
711:
692:
660:
641:
614:
592:
566:
553:
528:
510:
501:Zalta, Edward N.
482:
476:
470:
464:
458:
452:
446:
441:
430:
424:
418:
412:
406:
400:
394:
388:
382:
376:
370:
364:
332:
317:
279:formal languages
272:data compression
211:can be called a
173:Formal analogues
54:Jean-Yves Girard
46:Bodleian Library
34:Bertrand Russell
25:self-referential
1593:
1592:
1588:
1587:
1586:
1584:
1583:
1582:
1548:
1547:
1546:
1541:
1513:
1424:Decision-making
1370:Decision theory
1365:
1194:
1118:Hilbert's Hotel
1051:Grelling–Nelson
994:
873:
867:
825:"Berry Paradox"
820:
819:
809:
761:
758:
756:Further reading
736:
730:
714:
708:
695:
681:10.2307/2024634
675:(19): 690–716.
663:
657:
644:
638:
617:
611:
595:
564:
556:
550:
530:
527:: 388–390, 676.
513:
494:
491:
486:
485:
477:
473:
465:
461:
453:
449:
442:
433:
425:
421:
413:
409:
401:
397:
389:
385:
377:
373:
365:
361:
356:
330:
315:
292:
283:Turing machines
259:
253:
199:if and only if
179:Gregory Chaitin
175:
141:
137:
115:
103:Gregory Chaitin
62:
17:
12:
11:
5:
1591:
1589:
1581:
1580:
1575:
1570:
1565:
1560:
1550:
1549:
1543:
1542:
1540:
1539:
1529:
1518:
1515:
1514:
1512:
1511:
1506:
1501:
1496:
1491:
1486:
1481:
1476:
1471:
1466:
1461:
1456:
1451:
1446:
1441:
1436:
1431:
1426:
1421:
1416:
1411:
1406:
1401:
1400:
1399:
1394:
1389:
1379:
1373:
1371:
1367:
1366:
1364:
1363:
1358:
1353:
1348:
1343:
1341:St. Petersburg
1338:
1333:
1328:
1323:
1318:
1313:
1308:
1303:
1298:
1293:
1288:
1283:
1278:
1273:
1268:
1263:
1258:
1253:
1248:
1243:
1238:
1233:
1228:
1223:
1218:
1213:
1208:
1202:
1200:
1196:
1195:
1193:
1192:
1187:
1182:
1175:
1170:
1165:
1160:
1155:
1150:
1145:
1140:
1135:
1130:
1125:
1120:
1115:
1110:
1105:
1100:
1095:
1090:
1089:
1088:
1083:
1078:
1073:
1068:
1058:
1053:
1048:
1043:
1038:
1033:
1028:
1023:
1018:
1013:
1008:
1002:
1000:
996:
995:
993:
992:
987:
982:
977:
972:
970:Rule-following
967:
962:
957:
952:
947:
942:
937:
932:
927:
922:
917:
912:
907:
902:
897:
895:Dream argument
892:
887:
881:
879:
875:
874:
868:
866:
865:
858:
851:
843:
837:
836:
817:
808:
807:External links
805:
804:
803:
793:
782:
777:10.1.1.27.3492
757:
754:
753:
752:
734:
728:
712:
706:
693:
661:
655:
642:
636:
615:
609:
593:
558:Chaitin, G. J.
554:
548:
532:Boolos, George
515:Boolos, George
511:
497:"Liar Paradox"
490:
487:
484:
483:
471:
459:
455:Glanzberg 2015
447:
431:
419:
407:
395:
383:
381:, Appendix IV.
371:
358:
357:
355:
352:
351:
350:
344:
339:
333:
324:
318:
309:
303:
291:
288:
255:Main article:
252:
249:
195:that holds of
174:
171:
139:
135:
127:vicious circle
114:
111:
107:The Unknowable
77:
76:
68:"The smallest
61:
58:
15:
13:
10:
9:
6:
4:
3:
2:
1590:
1579:
1576:
1574:
1571:
1569:
1566:
1564:
1561:
1559:
1556:
1555:
1553:
1538:
1530:
1528:
1520:
1519:
1516:
1510:
1507:
1505:
1502:
1500:
1497:
1495:
1492:
1490:
1487:
1485:
1482:
1480:
1477:
1475:
1472:
1470:
1469:Morton's fork
1467:
1465:
1462:
1460:
1457:
1455:
1452:
1450:
1447:
1445:
1442:
1440:
1437:
1435:
1432:
1430:
1427:
1425:
1422:
1420:
1417:
1415:
1412:
1410:
1409:Buridan's ass
1407:
1405:
1402:
1398:
1395:
1393:
1390:
1388:
1385:
1384:
1383:
1382:Apportionment
1380:
1378:
1375:
1374:
1372:
1368:
1362:
1359:
1357:
1354:
1352:
1349:
1347:
1344:
1342:
1339:
1337:
1334:
1332:
1329:
1327:
1324:
1322:
1319:
1317:
1314:
1312:
1309:
1307:
1304:
1302:
1299:
1297:
1294:
1292:
1289:
1287:
1284:
1282:
1279:
1277:
1274:
1272:
1269:
1267:
1264:
1262:
1259:
1257:
1254:
1252:
1249:
1247:
1244:
1242:
1241:Downs–Thomson
1239:
1237:
1234:
1232:
1229:
1227:
1224:
1222:
1219:
1217:
1214:
1212:
1209:
1207:
1204:
1203:
1201:
1197:
1191:
1188:
1186:
1183:
1180:
1176:
1174:
1171:
1169:
1166:
1164:
1161:
1159:
1158:Plato's beard
1156:
1154:
1151:
1149:
1146:
1144:
1141:
1139:
1136:
1134:
1131:
1129:
1126:
1124:
1121:
1119:
1116:
1114:
1111:
1109:
1106:
1104:
1101:
1099:
1096:
1094:
1091:
1087:
1084:
1082:
1079:
1077:
1074:
1072:
1069:
1067:
1064:
1063:
1062:
1059:
1057:
1056:Kleene–Rosser
1054:
1052:
1049:
1047:
1044:
1042:
1039:
1037:
1034:
1032:
1029:
1027:
1024:
1022:
1019:
1017:
1014:
1012:
1009:
1007:
1004:
1003:
1001:
997:
991:
988:
986:
983:
981:
980:Theseus' ship
978:
976:
973:
971:
968:
966:
963:
961:
958:
956:
953:
951:
948:
946:
943:
941:
940:Mere addition
938:
936:
933:
931:
928:
926:
923:
921:
918:
916:
913:
911:
908:
906:
903:
901:
898:
896:
893:
891:
888:
886:
883:
882:
880:
878:Philosophical
876:
872:
864:
859:
857:
852:
850:
845:
844:
841:
832:
831:
826:
823:
818:
815:
811:
810:
806:
801:
797:
794:
791:
787:
783:
778:
773:
769:
765:
760:
759:
755:
749:
748:
743:
739:
735:
731:
729:9780674948358
725:
721:
717:
713:
709:
707:9780415820981
703:
700:. Routledge.
699:
694:
690:
686:
682:
678:
674:
670:
666:
662:
658:
652:
648:
643:
639:
633:
629:
625:
621:
616:
612:
610:9783037190883
606:
602:
598:
594:
590:
586:
582:
578:
574:
570:
563:
559:
555:
551:
549:0-674-53766-1
545:
541:
537:
533:
529:Reprinted in
526:
522:
521:
516:
512:
508:
507:
502:
498:
493:
492:
488:
480:
475:
472:
468:
463:
460:
456:
451:
448:
445:
440:
438:
436:
432:
428:
423:
420:
417:, p. 10.
416:
411:
408:
404:
399:
396:
393:, p. 16.
392:
387:
384:
380:
375:
372:
369:, p. 63.
368:
363:
360:
353:
348:
345:
343:
340:
337:
334:
328:
325:
322:
319:
313:
310:
307:
304:
301:
297:
294:
293:
289:
287:
284:
280:
275:
273:
268:
264:
258:
250:
248:
246:
242:
238:
237:Gödel numbers
234:
230:
226:
222:
218:
214:
210:
206:
202:
198:
194:
190:
186:
185:Boolos (1989)
182:
180:
172:
170:
168:
164:
160:
155:
152:
148:
147:Alfred Tarski
143:
131:
128:
124:
120:
112:
110:
108:
104:
99:
96:
92:
88:
83:
74:
71:
67:
66:
65:
59:
57:
55:
51:
47:
43:
39:
35:
31:
29:
26:
22:
21:Berry paradox
1489:Preparedness
1321:Productivity
1301:Mandeville's
1093:Opposite Day
1021:Burali-Forti
1016:Bhartrhari's
1010:
828:
799:
792:: 1220–1223.
789:
767:
746:
719:
697:
672:
668:
665:Kripke, Saul
646:
619:
600:
575:(1): 26–30.
572:
568:
535:
524:
518:
504:
474:
467:Chaitin 1995
462:
450:
422:
410:
398:
386:
374:
367:Griffin 2003
362:
276:
266:
262:
260:
244:
240:
232:
228:
224:
220:
216:
212:
208:
204:
200:
196:
183:
176:
162:
158:
156:
151:Liar Paradox
144:
132:
130:avoid them.
116:
106:
100:
94:
90:
86:
81:
78:
63:
32:
20:
18:
1419:Condorcet's
1271:Giffen good
1231:Competition
985:White horse
960:Omnipotence
479:Boolos 1989
427:Kripke 1975
391:Girard 2011
306:Busy beaver
193:proposition
167:Saul Kripke
1552:Categories
1494:Prevention
1484:Parrondo's
1474:Navigation
1459:Inventor's
1454:Hedgehog's
1414:Chainstore
1397:Population
1392:New states
1326:Prosperity
1306:Mayfield's
1148:Entailment
1128:Barbershop
1041:Epimenides
569:Complexity
489:References
415:Quine 1976
379:Moore 2014
300:Bhartṛhari
213:definition
113:Resolution
1509:Willpower
1504:Tolerance
1479:Newcomb's
1444:Fredkin's
1331:Scitovsky
1251:Edgeworth
1246:Easterlin
1211:Antitrust
1108:Russell's
1103:Richard's
1076:Pinocchio
1031:Crocodile
950:Newcomb's
920:Goodman's
915:Free will
900:Epicurean
871:paradoxes
830:MathWorld
802:: 627–650
772:CiteSeerX
119:ambiguity
38:librarian
1537:Category
1434:Ellsberg
1286:Leontief
1266:Gibson's
1261:European
1256:Ellsberg
1226:Braess's
1221:Bertrand
1199:Economic
1133:Catch-22
1113:Socratic
955:Nihilism
925:Hedonism
885:Analysis
869:Notable
744:(1927).
718:(1976).
599:(2011).
560:(1995).
534:(1998).
290:See also
134:nameable
123:nameable
82:smallest
70:positive
60:Overview
1439:Fenno's
1404:Arrow's
1387:Alabama
1377:Abilene
1356:Tullock
1311:Metzler
1153:Lottery
1143:Drinker
1086:Yablo's
1081:Quine's
1036:Curry's
999:Logical
975:Sorites
965:Preface
945:Moore's
930:Liberal
905:Fiction
689:2024634
589:1366300
503:(ed.).
73:integer
28:paradox
1346:Thrift
1316:Plenty
1291:Lerner
1281:Jevons
1276:Icarus
1206:Allais
1168:Ross's
1006:Barber
990:Zeno's
935:Meno's
774:
726:
704:
687:
653:
634:
607:
587:
546:
267:number
263:string
42:Oxford
1449:Green
1429:Downs
1361:Value
1296:Lucas
1163:Raven
1071:No-no
1026:Court
1011:Berry
685:JSTOR
565:(PDF)
499:. In
354:Notes
281:, or
52:" by
23:is a
1527:List
1351:Toil
1066:Card
1061:Liar
724:ISBN
702:ISBN
651:ISBN
632:ISBN
605:ISBN
544:ISBN
265:and
215:for
19:The
788:,"
677:doi
624:doi
577:doi
227:):
105:in
95:not
91:not
44:'s
40:at
1554::
827:.
770:.
766:.
740:;
683:.
673:72
671:.
630:.
585:MR
583:.
571:.
567:.
538:.
525:36
523:.
434:^
223:,
203:=
87:is
56:.
1181:"
1177:"
862:e
855:t
848:v
833:.
816:"
780:.
732:.
710:.
691:.
679::
659:.
640:.
626::
613:.
591:.
579::
573:1
552:.
509:.
481:.
469:.
457:.
429:.
405:.
245:k
241:m
233:k
229:n
225:k
221:n
217:n
209:n
205:n
201:x
197:x
163:α
159:α
140:1
136:0
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.