25:
556:
293:
360:
810:
157:
94:
if and only if the statement holds in that model. Nonfirstorderizable statements are sometimes presented as evidence that first-order logic is not adequate to capture the nuances of meaning in natural language.
875:
106:
symbolization, which can be interpreted as plural quantification over the same domain as first-order quantifiers use, without postulation of distinct "second-order objects" (
351:
697:
which is true of all and only models with finite domains. In other words, there is no first-order formula which can express "there is only a finite number of things".
43:
741:
671:
551:{\displaystyle \exists X(\exists x,y(Xx\land Xy\land (y=x+1\lor x=y+1))\land \exists x\neg Xx\land \forall x\,\forall y(Xx\land (y=x+1\lor x=y+1)\rightarrow Xy))}
673:
were added to the Peano axioms, it would mean that there were no non-standard models of the augmented axioms. However, the usual argument for the
297:
That this formula has no first-order equivalent can be seen by turning it into a formula in the language of arithmetic . Substitute the formula
677:
would still go through, proving that there are non-standard models after all. This is a contradiction, so we can conclude that no such formula
900:
formulae in the subset. Applying the compactness theorem, the entire infinite set must also have a model. Because of what we assumed about
1105:
102:
in his paper "To Be is to Be a Value of a
Variable (or to Be Some Values of Some Variables)". Quine argued that such sentences call for
288:{\displaystyle \exists X(\exists x,y(Xx\land Xy\land Axy)\land \exists x\neg Xx\land \forall x\,\forall y(Xx\land Axy\rightarrow Xy))}
1052:
61:
815:
674:
628:
1123:
631:
otherwise. Therefore, the formula given above is true only in non-standard models, because, in the standard model, the set
812:
which expresses that there are at least three distinct elements in the domain. Consider the infinite set of formulae
129:
984:
1068:
1044:
974:
107:
979:
929:
147:
969:
936:
947:
708:
which is true in all and only models with finite domains. We can express, for any positive integer
701:
300:
1024:
951:
103:
1007:(August 1984). "To Be Is to Be a Value of a Variable (or to Be Some Values of Some Variables)".
904:, the model must be finite. However, this model cannot be finite, because if the model has only
1048:
940:
694:
151:
83:
1016:
653:
82:
is the inability of a natural-language statement to be adequately captured by a formula of
1100:
1138:
1132:
1040:
1004:
964:
877:
Every finite subset of these formulae has a model: given a subset, find the greatest
99:
616:
91:
75:
805:{\displaystyle \exists x\exists y\exists z(x\neq y\wedge x\neq z\wedge y\neq z)}
646:
Let us assume that there is a first-order rendering of the above formula called
125:
1096:
1028:
1020:
932:
cannot be defined in first-order languages, merely indiscernibility.
1124:
Printer-friendly CSS, and nonfirstorderisability by
Terence Tao
90:
if there is no formula of first-order logic which is true in a
18:
939:
that may be used to identify the real numbers among the
915:. This contradiction shows that there can be no formula
888:
is in the subset. Then a model with a domain containing
39:
720:, call the formula expressing that there are at least
303:
818:
744:
656:
363:
160:
643:
satisfying the formula in every non-standard model.
34:
may be too technical for most readers to understand
869:
804:
665:
615:A model of a formal theory of arithmetic, such as
550:
345:
287:
623:if it only contains the familiar natural numbers
150:is the set of all critics, then a reasonable
134:: "Some critics admire only one another." If
8:
896:(because the domain is finite) and all the
870:{\displaystyle A,B_{2},B_{3},B_{4},\ldots }
1095:Noonan, Harold; Curtis, Ben (2014-04-25).
908:elements, it does not satisfy the formula
572:There is a number that does not belong to
954:cannot be expressed in first-order logic.
855:
842:
829:
817:
743:
655:
475:
362:
302:
242:
159:
62:Learn how and when to remove this message
46:, without removing the technical details.
996:
704:as follows. Suppose there is a formula
716:elements in the domain". For a given
44:make it understandable to non-experts
7:
1106:Stanford Encyclopedia of Philosophy
712:, the sentence "there are at least
635:must contain all available numbers
757:
751:
745:
657:
566:There are at least two numbers in
476:
469:
457:
451:
373:
364:
243:
236:
224:
218:
170:
161:
14:
1076:. Open Logic Project. p. 235
627:as elements. The model is called
675:existence of non-standard models
86:. Specifically, a statement is
23:
695:first-order logic with equality
919:with the property we assumed.
799:
763:
639:. In addition, there is a set
545:
542:
533:
530:
494:
482:
445:
442:
406:
385:
370:
346:{\textstyle (y=x+1\lor x=y+1)}
340:
304:
282:
279:
270:
249:
212:
182:
167:
1:
681:exists in first-order logic.
580:does not contain all numbers.
617:first-order Peano arithmetic
154:into second order logic is:
731:. For example, the formula
558:states that there is a set
152:translation of the sentence
1155:
123:A standard example is the
1009:The Journal of Philosophy
985:Reification (linguistics)
1045:Harvard University Press
685:Finiteness of the domain
1037:Logic, Logic, and Logic
1035:Boolos, George (1998).
700:This is implied by the
562:with these properties:
138:is understood to mean "
98:The term was coined by
16:Concept in formal logic
975:Generalized quantifier
892:elements will satisfy
881:for which the formula
871:
806:
667:
666:{\displaystyle \neg E}
552:
347:
289:
80:nonfirstorderizability
980:Plural quantification
872:
807:
668:
553:
348:
290:
148:universe of discourse
119:Geach-Kaplan sentence
970:Branching quantifier
937:Archimedean property
816:
742:
689:There is no formula
654:
361:
301:
158:
948:compactness theorem
702:compactness theorem
88:nonfirstorderizable
1070:Intermediate Logic
952:graph connectivity
941:real closed fields
867:
802:
663:
548:
343:
285:
84:first-order logic
72:
71:
64:
1146:
1111:
1110:
1101:Zalta, Edward N.
1092:
1086:
1085:
1083:
1081:
1075:
1065:
1059:
1058:
1032:
1001:
918:
914:
907:
903:
899:
895:
891:
887:
880:
876:
874:
873:
868:
860:
859:
847:
846:
834:
833:
811:
809:
808:
803:
737:
730:
723:
719:
715:
711:
707:
692:
680:
672:
670:
669:
664:
649:
642:
638:
634:
626:
610:
607:also belongs to
606:
602:
598:
594:
590:
586:
579:
575:
569:
561:
557:
555:
554:
549:
352:
350:
349:
344:
294:
292:
291:
286:
67:
60:
56:
53:
47:
27:
26:
19:
1154:
1153:
1149:
1148:
1147:
1145:
1144:
1143:
1129:
1128:
1120:
1115:
1114:
1094:
1093:
1089:
1079:
1077:
1073:
1067:
1066:
1062:
1055:
1034:
1021:10.2307/2026308
1003:
1002:
998:
993:
961:
928:The concept of
925:
916:
913:
909:
905:
901:
897:
893:
889:
886:
882:
878:
851:
838:
825:
814:
813:
740:
739:
736:
732:
729:
725:
721:
717:
713:
709:
705:
690:
687:
678:
652:
651:
647:
640:
636:
632:
624:
608:
604:
600:
596:
592:
588:
584:
577:
573:
567:
559:
359:
358:
357:. The result,
299:
298:
156:
155:
121:
116:
110:, sets, etc.).
68:
57:
51:
48:
40:help improve it
37:
28:
24:
17:
12:
11:
5:
1152:
1150:
1142:
1141:
1131:
1130:
1127:
1126:
1119:
1118:External links
1116:
1113:
1112:
1087:
1060:
1053:
1015:(8): 430–449.
1005:Boolos, George
995:
994:
992:
989:
988:
987:
982:
977:
972:
967:
960:
957:
956:
955:
944:
933:
924:
923:Other examples
921:
911:
884:
866:
863:
858:
854:
850:
845:
841:
837:
832:
828:
824:
821:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
734:
727:
686:
683:
662:
659:
613:
612:
581:
570:
547:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
342:
339:
336:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
284:
281:
278:
275:
272:
269:
266:
263:
260:
257:
254:
251:
248:
245:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
178:
175:
172:
169:
166:
163:
120:
117:
115:
112:
70:
69:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1151:
1140:
1137:
1136:
1134:
1125:
1122:
1121:
1117:
1108:
1107:
1102:
1098:
1091:
1088:
1072:
1071:
1064:
1061:
1056:
1054:0-674-53767-X
1050:
1046:
1042:
1041:Cambridge, MA
1038:
1033:Reprinted in
1030:
1026:
1022:
1018:
1014:
1010:
1006:
1000:
997:
990:
986:
983:
981:
978:
976:
973:
971:
968:
966:
965:Definable set
963:
962:
958:
953:
950:implies that
949:
945:
942:
938:
934:
931:
927:
926:
922:
920:
864:
861:
856:
852:
848:
843:
839:
835:
830:
826:
822:
819:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
760:
754:
748:
703:
698:
696:
684:
682:
676:
660:
644:
630:
622:
618:
582:
571:
565:
564:
563:
539:
536:
527:
524:
521:
518:
515:
512:
509:
506:
503:
500:
497:
491:
488:
485:
479:
472:
466:
463:
460:
454:
448:
439:
436:
433:
430:
427:
424:
421:
418:
415:
412:
409:
403:
400:
397:
394:
391:
388:
382:
379:
376:
367:
356:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
295:
276:
273:
267:
264:
261:
258:
255:
252:
246:
239:
233:
230:
227:
221:
215:
209:
206:
203:
200:
197:
194:
191:
188:
185:
179:
176:
173:
164:
153:
149:
145:
141:
137:
133:
131:
127:
118:
113:
111:
109:
105:
101:
100:George Boolos
96:
93:
89:
85:
81:
77:
66:
63:
55:
45:
41:
35:
32:This article
30:
21:
20:
1104:
1090:
1078:. Retrieved
1069:
1063:
1036:
1012:
1008:
999:
699:
688:
645:
637:0, 1, 2, ...
629:non-standard
625:0, 1, 2, ...
620:
619:, is called
614:
583:If a number
354:
296:
143:
139:
135:
124:
122:
104:second-order
97:
87:
79:
76:formal logic
73:
58:
49:
33:
587:belongs to
146:," and the
1097:"Identity"
991:References
108:properties
52:March 2016
865:…
794:≠
788:∧
782:≠
776:∧
770:≠
758:∃
752:∃
746:∃
724:elements
658:¬
534:→
513:∨
492:∧
477:∀
470:∀
467:∧
458:¬
452:∃
449:∧
425:∨
404:∧
395:∧
374:∃
365:∃
323:∨
271:→
259:∧
244:∀
237:∀
234:∧
225:¬
219:∃
216:∧
201:∧
192:∧
171:∃
162:∃
1133:Category
1080:21 March
959:See also
930:identity
621:standard
142:admires
132:sentence
114:Examples
1103:(ed.).
1029:2026308
576:, i.e.
38:Please
1051:
1027:
130:Kaplan
1139:Logic
1099:. In
1074:(PDF)
1025:JSTOR
650:. If
601:x - 1
597:x + 1
126:Geach
92:model
1082:2022
1049:ISBN
946:The
935:The
738:is:
591:and
353:for
1017:doi
912:m+1
693:in
599:or
595:is
355:Axy
136:Axy
74:In
42:to
1135::
1047:.
1043::
1039:.
1023:.
1013:81
1011:.
603:,
78:,
1109:.
1084:.
1057:.
1031:.
1019::
943:.
917:A
910:B
906:m
902:A
898:B
894:A
890:n
885:n
883:B
879:n
862:,
857:4
853:B
849:,
844:3
840:B
836:,
831:2
827:B
823:,
820:A
800:)
797:z
791:y
785:z
779:x
773:y
767:x
764:(
761:z
755:y
749:x
735:3
733:B
728:n
726:B
722:n
718:n
714:n
710:n
706:A
691:A
679:E
661:E
648:E
641:X
633:X
611:.
609:X
605:y
593:y
589:X
585:x
578:X
574:X
568:X
560:X
546:)
543:)
540:y
537:X
531:)
528:1
525:+
522:y
519:=
516:x
510:1
507:+
504:x
501:=
498:y
495:(
489:x
486:X
483:(
480:y
473:x
464:x
461:X
455:x
446:)
443:)
440:1
437:+
434:y
431:=
428:x
422:1
419:+
416:x
413:=
410:y
407:(
401:y
398:X
392:x
389:X
386:(
383:y
380:,
377:x
371:(
368:X
341:)
338:1
335:+
332:y
329:=
326:x
320:1
317:+
314:x
311:=
308:y
305:(
283:)
280:)
277:y
274:X
268:y
265:x
262:A
256:x
253:X
250:(
247:y
240:x
231:x
228:X
222:x
213:)
210:y
207:x
204:A
198:y
195:X
189:x
186:X
183:(
180:y
177:,
174:x
168:(
165:X
144:y
140:x
128:–
65:)
59:(
54:)
50:(
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.