2050:
38:
203:
There is in my opinion no important theoretical difference between natural languages and the artificial languages of logicians; indeed, I consider it possible to comprehend the syntax and semantics of both kinds of language within a single natural and mathematically precise theory. On this point I
81:
of which may be marks or a configuration of marks which form a particular pattern. Although the term "symbol" in common use refers at some times to the idea being symbolized, and at other times to the marks on a piece of paper or chalkboard which are being used to express that idea; in the
114:
which do not refer to any idea, but rather serve as a form of punctuation in the language (e.g. parentheses). Symbols of a formal language must be capable of being specified without any reference to any
57:
and well-formed formulas. A formal language can be thought of as identical to the set of its well-formed formulas. The set of well-formed formulas may be broadly divided into
259:
429:
1104:
1187:
328:
215:
However, this attempt to equate linguistic symbols with formal symbols has been challenged widely, particularly in the tradition of
1501:
1659:
447:
1514:
837:
1519:
1509:
1246:
1099:
452:
443:
1655:
997:
1752:
1496:
321:
301:
1057:
750:
491:
2013:
1715:
1478:
1473:
1298:
719:
403:
157:
17:
2008:
1791:
1708:
1421:
1352:
1229:
471:
1933:
1759:
1445:
1079:
678:
291:
1811:
1806:
1416:
1155:
1084:
413:
314:
2089:
1740:
1330:
724:
692:
383:
78:
2074:
2030:
1979:
1876:
1374:
1335:
812:
457:
123:
50:
486:
1871:
1801:
1340:
1192:
1175:
898:
378:
172:
2094:
1703:
1680:
1641:
1527:
1468:
1114:
1034:
878:
822:
435:
31:
2099:
1993:
1720:
1698:
1665:
1558:
1404:
1389:
1362:
1313:
1197:
1132:
957:
923:
918:
792:
623:
600:
195:
model looked upon syntax as autonomous from semantics. Building on these models, the logician
116:
95:
183:
The move to view units in natural language (e.g. English) as formal symbols was initiated by
1923:
1776:
1568:
1286:
1022:
928:
787:
772:
653:
628:
296:
216:
204:
differ from a number of philosophers, but agree, I believe, with
Chomsky and his associates."
153:
2084:
1896:
1858:
1735:
1539:
1379:
1303:
1281:
1109:
1067:
966:
933:
797:
585:
496:
8:
2025:
1916:
1901:
1881:
1838:
1725:
1675:
1601:
1546:
1483:
1276:
1271:
1219:
987:
976:
648:
548:
476:
467:
463:
398:
393:
127:
2079:
2054:
1823:
1786:
1771:
1764:
1747:
1551:
1533:
1399:
1325:
1308:
1261:
1074:
983:
817:
802:
762:
714:
699:
687:
643:
618:
388:
337:
192:
141:
a symbol may be used as a token in formal operations. The set of formal symbols in a
1007:
2049:
1989:
1796:
1606:
1596:
1488:
1369:
1204:
1180:
961:
945:
850:
827:
704:
673:
638:
533:
368:
188:
149:
98:
instance of the symbol. In logic, symbols build literal utility to illustrate ideas.
2003:
1998:
1891:
1848:
1670:
1631:
1626:
1611:
1437:
1394:
1291:
1089:
1039:
613:
575:
228:
209:
196:
145:
is referred to as an alphabet (hence each symbol may be referred to as a "letter")
111:
199:
proposed that semantics could also be constructed on top of the formal structure:
1984:
1974:
1928:
1911:
1866:
1828:
1730:
1650:
1457:
1357:
1345:
1251:
1165:
1139:
1094:
1062:
863:
665:
608:
558:
523:
481:
142:
83:
46:
1969:
1948:
1906:
1886:
1781:
1636:
1234:
1224:
1214:
1209:
1143:
1017:
893:
782:
777:
755:
356:
255:
251:
168:
164:
131:
42:
2068:
1943:
1621:
1128:
913:
903:
873:
858:
528:
247:
224:
220:
171:, though sometimes they may be associated with an interpretation or model (a
138:
94:, the term "symbol" refers to the idea, and the marks are considered to be a
30:
This article is about symbols in formal language theory. For other uses, see
1843:
1690:
1591:
1583:
1463:
1411:
1320:
1256:
1239:
1170:
1029:
888:
590:
373:
184:
1953:
1833:
1012:
1002:
949:
633:
553:
538:
418:
363:
87:
883:
738:
709:
515:
156:), a constant, a function (mapping to another member of universe) or a
2035:
1938:
991:
908:
868:
832:
768:
580:
570:
543:
306:
2020:
1818:
1266:
971:
565:
54:
37:
1616:
408:
70:
58:
1160:
506:
351:
91:
74:
260:
Introduction to
Automata Theory, Languages, and Computation
178:
167:
structures, composed into larger structures using a
106:Symbols of a formal language need not be symbols
2066:
163:Formal symbols are usually thought of as purely
322:
208:This is the philosophical premise underlying
514:
329:
315:
27:Token in a mathematical or logical formula
36:
187:(it was this work that resulted in the
179:Can words be modeled as formal symbols?
14:
2067:
336:
310:
24:
25:
2111:
152:may be a variable (member from a
110:anything. For instance there are
2048:
302:Terminal and nonterminal symbols
265:
241:
13:
1:
2009:History of mathematical logic
234:
130:if it is consistent with the
45:that may be constructed from
1934:Primitive recursive function
292:List of mathematical symbols
53:may be broadly divided into
7:
285:
191:in formal languages). The
148:A formal symbol as used in
101:
10:
2116:
998:SchröderâBernstein theorem
725:Monadic predicate calculus
384:Foundations of mathematics
126:of symbols may comprise a
29:
2044:
2031:Philosophy of mathematics
1980:Automated theorem proving
1962:
1857:
1689:
1582:
1434:
1151:
1127:
1105:Von NeumannâBernaysâGödel
1050:
944:
848:
746:
737:
664:
599:
505:
427:
344:
1681:Self-verifying theories
1502:Tarski's axiomatization
453:Tarski's undefinability
448:incompleteness theorems
219:, by philosophers like
41:This diagram shows the
32:Symbol (disambiguation)
2055:Mathematics portal
1666:Proof of impossibility
1314:propositional variable
624:Propositional calculus
62:
1924:Kolmogorov complexity
1877:Computably enumerable
1777:Model complete theory
1569:Principia Mathematica
629:Propositional formula
458:BanachâTarski paradox
297:List of logic symbols
223:, and linguists like
217:cognitive linguistics
154:universe of discourse
40:
1872:ChurchâTuring thesis
1859:Computability theory
1068:continuum hypothesis
586:Square of opposition
444:Gödel's completeness
2026:Mathematical object
1917:P versus NP problem
1882:Computable function
1676:Reverse mathematics
1602:Logical consequence
1479:primitive recursive
1474:elementary function
1247:Free/bound variable
1100:TarskiâGrothendieck
619:Logical connectives
549:Logical equivalence
399:Logical consequence
128:well-formed formula
1824:Transfer principle
1787:Semantics of logic
1772:Categorical theory
1748:Non-standard model
1262:Logical connective
389:Information theory
338:Mathematical logic
271:Richard Montague,
193:generative grammar
160:(mapping to T/F).
63:
51:strings of symbols
49:. The symbols and
43:syntactic entities
2090:Concepts in logic
2062:
2061:
1994:Abstract category
1797:Theories of truth
1607:Rule of inference
1597:Natural deduction
1578:
1577:
1123:
1122:
828:Cartesian product
733:
732:
639:Many-valued logic
614:Boolean functions
497:Russell's paradox
472:diagonal argument
369:First-order logic
273:Universal Grammar
189:Chomsky hierarchy
150:first-order logic
134:of the language.
112:logical constants
69:is a fundamental
61:and non-theorems.
16:(Redirected from
2107:
2075:Formal languages
2053:
2052:
2004:History of logic
1999:Category of sets
1892:Decision problem
1671:Ordinal analysis
1612:Sequent calculus
1510:Boolean algebras
1450:
1449:
1424:
1395:logical/constant
1149:
1148:
1135:
1058:ZermeloâFraenkel
809:Set operations:
744:
743:
681:
512:
511:
492:LöwenheimâSkolem
379:Formal semantics
331:
324:
317:
308:
307:
279:
269:
263:
245:
229:Ronald Langacker
210:Montague grammar
197:Richard Montague
173:formal semantics
84:formal languages
47:formal languages
21:
2115:
2114:
2110:
2109:
2108:
2106:
2105:
2104:
2065:
2064:
2063:
2058:
2047:
2040:
1985:Category theory
1975:Algebraic logic
1958:
1929:Lambda calculus
1867:Church encoding
1853:
1829:Truth predicate
1685:
1651:Complete theory
1574:
1443:
1439:
1435:
1430:
1422:
1142: and
1138:
1133:
1119:
1095:New Foundations
1063:axiom of choice
1046:
1008:Gödel numbering
948: and
940:
844:
729:
679:
660:
609:Boolean algebra
595:
559:Equiconsistency
524:Classical logic
501:
482:Halting problem
470: and
446: and
434: and
433:
428:Theorems (
423:
340:
335:
288:
283:
282:
270:
266:
246:
242:
237:
181:
143:formal language
132:formation rules
104:
35:
28:
23:
22:
15:
12:
11:
5:
2113:
2103:
2102:
2097:
2095:Syntax (logic)
2092:
2087:
2082:
2077:
2060:
2059:
2045:
2042:
2041:
2039:
2038:
2033:
2028:
2023:
2018:
2017:
2016:
2006:
2001:
1996:
1987:
1982:
1977:
1972:
1970:Abstract logic
1966:
1964:
1960:
1959:
1957:
1956:
1951:
1949:Turing machine
1946:
1941:
1936:
1931:
1926:
1921:
1920:
1919:
1914:
1909:
1904:
1899:
1889:
1887:Computable set
1884:
1879:
1874:
1869:
1863:
1861:
1855:
1854:
1852:
1851:
1846:
1841:
1836:
1831:
1826:
1821:
1816:
1815:
1814:
1809:
1804:
1794:
1789:
1784:
1782:Satisfiability
1779:
1774:
1769:
1768:
1767:
1757:
1756:
1755:
1745:
1744:
1743:
1738:
1733:
1728:
1723:
1713:
1712:
1711:
1706:
1699:Interpretation
1695:
1693:
1687:
1686:
1684:
1683:
1678:
1673:
1668:
1663:
1653:
1648:
1647:
1646:
1645:
1644:
1634:
1629:
1619:
1614:
1609:
1604:
1599:
1594:
1588:
1586:
1580:
1579:
1576:
1575:
1573:
1572:
1564:
1563:
1562:
1561:
1556:
1555:
1554:
1549:
1544:
1524:
1523:
1522:
1520:minimal axioms
1517:
1506:
1505:
1504:
1493:
1492:
1491:
1486:
1481:
1476:
1471:
1466:
1453:
1451:
1432:
1431:
1429:
1428:
1427:
1426:
1414:
1409:
1408:
1407:
1402:
1397:
1392:
1382:
1377:
1372:
1367:
1366:
1365:
1360:
1350:
1349:
1348:
1343:
1338:
1333:
1323:
1318:
1317:
1316:
1311:
1306:
1296:
1295:
1294:
1289:
1284:
1279:
1274:
1269:
1259:
1254:
1249:
1244:
1243:
1242:
1237:
1232:
1227:
1217:
1212:
1210:Formation rule
1207:
1202:
1201:
1200:
1195:
1185:
1184:
1183:
1173:
1168:
1163:
1158:
1152:
1146:
1129:Formal systems
1125:
1124:
1121:
1120:
1118:
1117:
1112:
1107:
1102:
1097:
1092:
1087:
1082:
1077:
1072:
1071:
1070:
1065:
1054:
1052:
1048:
1047:
1045:
1044:
1043:
1042:
1032:
1027:
1026:
1025:
1018:Large cardinal
1015:
1010:
1005:
1000:
995:
981:
980:
979:
974:
969:
954:
952:
942:
941:
939:
938:
937:
936:
931:
926:
916:
911:
906:
901:
896:
891:
886:
881:
876:
871:
866:
861:
855:
853:
846:
845:
843:
842:
841:
840:
835:
830:
825:
820:
815:
807:
806:
805:
800:
790:
785:
783:Extensionality
780:
778:Ordinal number
775:
765:
760:
759:
758:
747:
741:
735:
734:
731:
730:
728:
727:
722:
717:
712:
707:
702:
697:
696:
695:
685:
684:
683:
670:
668:
662:
661:
659:
658:
657:
656:
651:
646:
636:
631:
626:
621:
616:
611:
605:
603:
597:
596:
594:
593:
588:
583:
578:
573:
568:
563:
562:
561:
551:
546:
541:
536:
531:
526:
520:
518:
509:
503:
502:
500:
499:
494:
489:
484:
479:
474:
462:Cantor's
460:
455:
450:
440:
438:
425:
424:
422:
421:
416:
411:
406:
401:
396:
391:
386:
381:
376:
371:
366:
361:
360:
359:
348:
346:
342:
341:
334:
333:
326:
319:
311:
305:
304:
299:
294:
287:
284:
281:
280:
264:
256:Jeffrey Ullman
252:Rajeev Motwani
239:
238:
236:
233:
206:
205:
180:
177:
169:formal grammar
117:interpretation
103:
100:
67:logical symbol
26:
18:Symbol (logic)
9:
6:
4:
3:
2:
2112:
2101:
2100:Logic symbols
2098:
2096:
2093:
2091:
2088:
2086:
2083:
2081:
2078:
2076:
2073:
2072:
2070:
2057:
2056:
2051:
2043:
2037:
2034:
2032:
2029:
2027:
2024:
2022:
2019:
2015:
2012:
2011:
2010:
2007:
2005:
2002:
2000:
1997:
1995:
1991:
1988:
1986:
1983:
1981:
1978:
1976:
1973:
1971:
1968:
1967:
1965:
1961:
1955:
1952:
1950:
1947:
1945:
1944:Recursive set
1942:
1940:
1937:
1935:
1932:
1930:
1927:
1925:
1922:
1918:
1915:
1913:
1910:
1908:
1905:
1903:
1900:
1898:
1895:
1894:
1893:
1890:
1888:
1885:
1883:
1880:
1878:
1875:
1873:
1870:
1868:
1865:
1864:
1862:
1860:
1856:
1850:
1847:
1845:
1842:
1840:
1837:
1835:
1832:
1830:
1827:
1825:
1822:
1820:
1817:
1813:
1810:
1808:
1805:
1803:
1800:
1799:
1798:
1795:
1793:
1790:
1788:
1785:
1783:
1780:
1778:
1775:
1773:
1770:
1766:
1763:
1762:
1761:
1758:
1754:
1753:of arithmetic
1751:
1750:
1749:
1746:
1742:
1739:
1737:
1734:
1732:
1729:
1727:
1724:
1722:
1719:
1718:
1717:
1714:
1710:
1707:
1705:
1702:
1701:
1700:
1697:
1696:
1694:
1692:
1688:
1682:
1679:
1677:
1674:
1672:
1669:
1667:
1664:
1661:
1660:from ZFC
1657:
1654:
1652:
1649:
1643:
1640:
1639:
1638:
1635:
1633:
1630:
1628:
1625:
1624:
1623:
1620:
1618:
1615:
1613:
1610:
1608:
1605:
1603:
1600:
1598:
1595:
1593:
1590:
1589:
1587:
1585:
1581:
1571:
1570:
1566:
1565:
1560:
1559:non-Euclidean
1557:
1553:
1550:
1548:
1545:
1543:
1542:
1538:
1537:
1535:
1532:
1531:
1529:
1525:
1521:
1518:
1516:
1513:
1512:
1511:
1507:
1503:
1500:
1499:
1498:
1494:
1490:
1487:
1485:
1482:
1480:
1477:
1475:
1472:
1470:
1467:
1465:
1462:
1461:
1459:
1455:
1454:
1452:
1447:
1441:
1436:Example
1433:
1425:
1420:
1419:
1418:
1415:
1413:
1410:
1406:
1403:
1401:
1398:
1396:
1393:
1391:
1388:
1387:
1386:
1383:
1381:
1378:
1376:
1373:
1371:
1368:
1364:
1361:
1359:
1356:
1355:
1354:
1351:
1347:
1344:
1342:
1339:
1337:
1334:
1332:
1329:
1328:
1327:
1324:
1322:
1319:
1315:
1312:
1310:
1307:
1305:
1302:
1301:
1300:
1297:
1293:
1290:
1288:
1285:
1283:
1280:
1278:
1275:
1273:
1270:
1268:
1265:
1264:
1263:
1260:
1258:
1255:
1253:
1250:
1248:
1245:
1241:
1238:
1236:
1233:
1231:
1228:
1226:
1223:
1222:
1221:
1218:
1216:
1213:
1211:
1208:
1206:
1203:
1199:
1196:
1194:
1193:by definition
1191:
1190:
1189:
1186:
1182:
1179:
1178:
1177:
1174:
1172:
1169:
1167:
1164:
1162:
1159:
1157:
1154:
1153:
1150:
1147:
1145:
1141:
1136:
1130:
1126:
1116:
1113:
1111:
1108:
1106:
1103:
1101:
1098:
1096:
1093:
1091:
1088:
1086:
1083:
1081:
1080:KripkeâPlatek
1078:
1076:
1073:
1069:
1066:
1064:
1061:
1060:
1059:
1056:
1055:
1053:
1049:
1041:
1038:
1037:
1036:
1033:
1031:
1028:
1024:
1021:
1020:
1019:
1016:
1014:
1011:
1009:
1006:
1004:
1001:
999:
996:
993:
989:
985:
982:
978:
975:
973:
970:
968:
965:
964:
963:
959:
956:
955:
953:
951:
947:
943:
935:
932:
930:
927:
925:
924:constructible
922:
921:
920:
917:
915:
912:
910:
907:
905:
902:
900:
897:
895:
892:
890:
887:
885:
882:
880:
877:
875:
872:
870:
867:
865:
862:
860:
857:
856:
854:
852:
847:
839:
836:
834:
831:
829:
826:
824:
821:
819:
816:
814:
811:
810:
808:
804:
801:
799:
796:
795:
794:
791:
789:
786:
784:
781:
779:
776:
774:
770:
766:
764:
761:
757:
754:
753:
752:
749:
748:
745:
742:
740:
736:
726:
723:
721:
718:
716:
713:
711:
708:
706:
703:
701:
698:
694:
691:
690:
689:
686:
682:
677:
676:
675:
672:
671:
669:
667:
663:
655:
652:
650:
647:
645:
642:
641:
640:
637:
635:
632:
630:
627:
625:
622:
620:
617:
615:
612:
610:
607:
606:
604:
602:
601:Propositional
598:
592:
589:
587:
584:
582:
579:
577:
574:
572:
569:
567:
564:
560:
557:
556:
555:
552:
550:
547:
545:
542:
540:
537:
535:
532:
530:
529:Logical truth
527:
525:
522:
521:
519:
517:
513:
510:
508:
504:
498:
495:
493:
490:
488:
485:
483:
480:
478:
475:
473:
469:
465:
461:
459:
456:
454:
451:
449:
445:
442:
441:
439:
437:
431:
426:
420:
417:
415:
412:
410:
407:
405:
402:
400:
397:
395:
392:
390:
387:
385:
382:
380:
377:
375:
372:
370:
367:
365:
362:
358:
355:
354:
353:
350:
349:
347:
343:
339:
332:
327:
325:
320:
318:
313:
312:
309:
303:
300:
298:
295:
293:
290:
289:
278:
274:
268:
261:
257:
253:
249:
248:John Hopcroft
244:
240:
232:
230:
226:
225:George Lakoff
222:
221:Stevan Harnad
218:
213:
211:
202:
201:
200:
198:
194:
190:
186:
176:
174:
170:
166:
161:
159:
155:
151:
146:
144:
140:
139:formal system
135:
133:
129:
125:
120:
118:
113:
109:
99:
97:
93:
89:
85:
80:
76:
72:
68:
60:
56:
52:
48:
44:
39:
33:
19:
2046:
1844:Ultraproduct
1691:Model theory
1656:Independence
1592:Formal proof
1584:Proof theory
1567:
1540:
1497:real numbers
1469:second-order
1384:
1380:Substitution
1257:Metalanguage
1198:conservative
1171:Axiom schema
1115:Constructive
1085:MorseâKelley
1051:Set theories
1030:Aleph number
1023:inaccessible
929:Grothendieck
813:intersection
700:Higher-order
688:Second-order
634:Truth tables
591:Venn diagram
374:Formal proof
276:
272:
267:
243:
214:
207:
185:Noam Chomsky
182:
162:
147:
136:
122:A symbol or
121:
107:
105:
66:
64:
2085:Abstraction
1954:Type theory
1902:undecidable
1834:Truth value
1721:equivalence
1400:non-logical
1013:Enumeration
1003:Isomorphism
950:cardinality
934:Von Neumann
899:Ultrafilter
864:Uncountable
798:equivalence
715:Quantifiers
705:Fixed-point
674:First-order
554:Consistency
539:Proposition
516:Traditional
487:Lindström's
477:Compactness
419:Type theory
364:Cardinality
88:mathematics
86:studied in
2069:Categories
1765:elementary
1458:arithmetic
1326:Quantifier
1304:functional
1176:Expression
894:Transitive
838:identities
823:complement
756:hereditary
739:Set theory
235:References
2080:Metalogic
2036:Supertask
1939:Recursion
1897:decidable
1731:saturated
1709:of models
1632:deductive
1627:axiomatic
1547:Hilbert's
1534:Euclidean
1515:canonical
1438:axiomatic
1370:Signature
1299:Predicate
1188:Extension
1110:Ackermann
1035:Operation
914:Universal
904:Recursive
879:Singleton
874:Inhabited
859:Countable
849:Types of
833:power set
803:partition
720:Predicate
666:Predicate
581:Syllogism
571:Soundness
544:Inference
534:Tautology
436:paradoxes
165:syntactic
158:predicate
119:of them.
2021:Logicism
2014:timeline
1990:Concrete
1849:Validity
1819:T-schema
1812:Kripke's
1807:Tarski's
1802:semantic
1792:Strength
1741:submodel
1736:spectrum
1704:function
1552:Tarski's
1541:Elements
1528:geometry
1484:Robinson
1405:variable
1390:function
1363:spectrum
1353:Sentence
1309:variable
1252:Language
1205:Relation
1166:Automata
1156:Alphabet
1140:language
994:-jection
972:codomain
958:Function
919:Universe
889:Infinite
793:Relation
576:Validity
566:Argument
464:theorem,
286:See also
102:Overview
59:theorems
55:nonsense
1963:Related
1760:Diagram
1658: (
1637:Hilbert
1622:Systems
1617:Theorem
1495:of the
1440:systems
1220:Formula
1215:Grammar
1131: (
1075:General
788:Forcing
773:Element
693:Monadic
468:paradox
409:Theorem
345:General
71:concept
1726:finite
1489:Skolem
1442:
1417:Theory
1385:Symbol
1375:String
1358:atomic
1235:ground
1230:closed
1225:atomic
1181:ground
1144:syntax
1040:binary
967:domain
884:Finite
649:finite
507:Logics
466:
414:Theory
262:, 2000
124:string
79:tokens
1716:Model
1464:Peano
1321:Proof
1161:Arity
1090:Naive
977:image
909:Fuzzy
869:Empty
818:union
763:Class
404:Model
394:Lemma
352:Axiom
137:In a
96:token
92:logic
75:logic
1839:Type
1642:list
1446:list
1423:list
1412:Term
1346:rank
1240:open
1134:list
946:Maps
851:sets
710:Free
680:list
430:list
357:list
277:1970
254:and
227:and
90:and
1526:of
1508:of
1456:of
988:Sur
962:Map
769:Ur-
751:Set
175:).
73:in
2071::
1912:NP
1536::
1530::
1460::
1137:),
992:Bi
984:In
275:,
258:,
250:,
231:.
212:.
108:of
77:,
65:A
1992:/
1907:P
1662:)
1448:)
1444:(
1341:â
1336:!
1331:â
1292:=
1287:â
1282:â
1277:â§
1272:âš
1267:ÂŹ
990:/
986:/
960:/
771:)
767:(
654:â
644:3
432:)
330:e
323:t
316:v
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.