1106:
509:
1101:{\displaystyle {\begin{array}{lcl}(P)_{D}&\equiv &P\\(A\wedge B)_{D}(x,v;y,w)&\equiv &A_{D}(x;y)\wedge B_{D}(v;w)\\(A\vee B)_{D}(x,v,z;y,w)&\equiv &(z=0\rightarrow A_{D}(x;y))\wedge (z\neq 0\to B_{D}(v;w))\\(A\rightarrow B)_{D}(f,g;x,w)&\equiv &A_{D}(x;fxw)\rightarrow B_{D}(gx;w)\\(\exists zA)_{D}(x,z;y)&\equiv &A_{D}(x;y)\\(\forall zA)_{D}(f;y,z)&\equiv &A_{D}(fz;y)\end{array}}}
1370:
The basic dialectica interpretation of intuitionistic logic has been extended to various stronger systems. Intuitively, the dialectica interpretation can be applied to a stronger system, as long as the dialectica interpretation of the extra principle can be witnessed by terms in the system T (or an
1361:
is necessary and sufficient for characterising the formulas of HA which are interpretable by the
Dialectica interpretation. The choice axiom here is formulated for any 2-ary predicate in the premise and an existence claim with a variable of function type in its conclusion.
1464:
Several variants of the
Dialectica interpretation have been proposed since, most notably the Diller-Nahm variant (to avoid the contraction problem) and Kohlenbach's monotone and Ferreira-Oliva bounded interpretations (to interpret
1420:
In 1962 Spector extended Gödel's
Dialectica interpretation of arithmetic to full mathematical analysis, by showing how the schema of countable choice can be given a Dialectica interpretation by extending system T with
1407:
Formulas and proofs in classical arithmetic can also be given a
Dialectica interpretation via an initial embedding into Heyting arithmetic followed by the Dialectica interpretation of Heyting arithmetic.
1449:. Since linear logic is a refinement of intuitionistic logic, the dialectica interpretation of linear logic can also be viewed as a refinement of the dialectica interpretation of intuitionistic logic.
289:
1387:
means) it is reasonable to expect that system T must contain non-finitistic constructions. Indeed, this is the case. The non-finitistic constructions show up in the interpretation of
1330:
1258:
1196:
461:
411:
155:
1298:
1278:
1216:
1154:
1134:
501:
481:
369:
349:
329:
309:
235:
215:
195:
175:
113:
1630:
1502:
Provably recursive functionals of analysis: a consistency proof of analysis by an extension of principles in current intuitionistic mathematics
1412:, in his book, combines the negative translation and the Dialectica interpretation into a single interpretation of classical arithmetic.
95:
The interpretation has two components: a formula translation and a proof translation. The formula translation describes how each formula
66:
1452:
Although the linear interpretation in
Shirahata's work validates the weakening rule (it is actually an interpretation of
1380:
240:
1392:
32:
1303:
1659:
1391:. To give a Dialectica interpretation of induction, Gödel makes use of what is nowadays called Gödel's
1456:), de Paiva's dialectica spaces interpretation does not validate weakening for arbitrary formulas.
1466:
1354:
1611:
1221:
1159:
424:
374:
118:
1388:
1598:
1654:
1649:
1396:
1349:
1590:
1563:
1438:
1409:
77:. Gödel's motivation for developing the dialectica interpretation was to obtain a relative
8:
1519:
1624:
1539:
1283:
1263:
1201:
1139:
1119:
486:
466:
354:
334:
314:
294:
220:
200:
180:
160:
98:
74:
28:
1340:
It has also been shown that
Heyting arithmetic extended with the following principles
1612:
1591:
1586:
1446:
514:
90:
44:
1559:
1515:
1434:
70:
1527:. University of Cambridge, Computer Laboratory, PhD Thesis, Technical Report 213.
1344:
1504:. Recursive Function Theory: Proc. Symposia in Pure Mathematics. pp. 1–27.
1136:
is provable in
Heyting arithmetic then there exists a sequence of closed terms
1643:
1555:
1422:
40:
1453:
1442:
1332:
which requires the assumption that quantifier-free formulas are decidable.
54:
20:
1572:
1487:Ăśber eine bisher noch nicht benĂĽtzte Erweiterung des finiten Standpunktes
1469:). Comprehensive treatments of the interpretation can be found at, and.
78:
53:, where Gödel's paper was published in a 1958 special issue dedicated to
1617:
Metamathematical
Investigation of Intuitionistic Arithmetic and Analysis
1593:
1544:. Theory and Applications of Categories, Vol. 17, No. 4. pp. 49–79.
49:
47:
of arithmetic. The name of the interpretation comes from the journal
1575:
ed., The
Handbook of Proof Theory, North-Holland. pp. 337–405.
1541:
The Dialectica interpretation of first-order classical affine logic
1384:
1554:
1433:
The Dialectica interpretation has been used to build a model of
81:
proof for Heyting arithmetic (and hence for Peano arithmetic).
1383:(which implies that the consistency of PA cannot be proven by
73:
had already been reduced to the consistency of intuitionistic
115:
of Heyting arithmetic is mapped to a quantifier-free formula
1300:
is quite straightforward, except for the contraction axiom
311:
has enough information to witness the interpretation of
1615:(with C.A. Smoryński, J.I. Zucker, W.A.Howard) (1973).
1306:
1286:
1266:
1224:
1204:
1162:
1142:
1122:
512:
489:
469:
427:
377:
357:
337:
317:
297:
243:
223:
203:
197:
are tuples of fresh variables (not appearing free in
183:
163:
121:
101:
1198:is provable in the system T. The sequence of terms
463:is defined inductively on the logical structure of
27:
is a proof interpretation of intuitionistic logic (
1324:
1292:
1272:
1252:
1210:
1190:
1148:
1128:
1100:
495:
475:
455:
405:
363:
343:
323:
303:
283:
229:
209:
189:
169:
149:
107:
1585:
1116:The formula interpretation is such that whenever
1641:
1565:Gödel's functional ("Dialectica") interpretation
1537:
1514:
1499:
1111:
1335:
291:. The proof translation shows how a proof of
1629:: CS1 maint: multiple names: authors list (
284:{\displaystyle \exists x\forall yA_{D}(x;y)}
1280:in Heyting arithmetic. The construction of
1619:. Springer Verlag, Berlin. pp. 1–323.
1484:
1260:are constructed from the given proof of
1399:with primitive recursive descriptions.
84:
1642:
1325:{\displaystyle A\rightarrow A\wedge A}
416:
1597:. Springer Verlag, Berlin. pp.
351:can be converted into a closed term
13:
1402:
1019:
940:
250:
244:
67:Gödel–Gentzen negative translation
31:) into a finite type extension of
14:
1671:
1415:
1489:. Dialectica. pp. 280–287.
1428:
1393:primitive recursive functionals
69:, the consistency of classical
1605:
1579:
1548:
1531:
1508:
1493:
1478:
1381:Gödel's incompleteness theorem
1310:
1247:
1235:
1185:
1173:
1091:
1076:
1056:
1038:
1029:
1016:
1009:
997:
977:
959:
950:
937:
930:
915:
902:
899:
881:
861:
837:
828:
821:
815:
808:
805:
793:
780:
768:
762:
759:
747:
734:
722:
712:
682:
673:
660:
653:
641:
625:
613:
593:
569:
560:
547:
524:
517:
450:
438:
400:
388:
278:
266:
144:
132:
33:primitive recursive arithmetic
1:
1472:
1365:
1112:Proof translation (soundness)
60:
1374:
421:The quantifier-free formula
7:
1459:
1336:Characterisation principles
10:
1676:
1253:{\displaystyle A_{D}(t;y)}
1191:{\displaystyle A_{D}(t;y)}
456:{\displaystyle A_{D}(x;y)}
406:{\displaystyle A_{D}(t;y)}
150:{\displaystyle A_{D}(x;y)}
88:
1538:Masaru Shirahata (2006).
1521:The Dialectica Categories
1500:Clifford Spector (1962).
25:Dialectica interpretation
1371:extension of system T).
1355:Independence of premise
157:of the system T, where
39:. It was developed by
1397:higher-order functions
1389:mathematical induction
1357:for universal formulas
1326:
1294:
1274:
1254:
1212:
1192:
1150:
1130:
1102:
503:is an atomic formula:
497:
477:
457:
407:
365:
345:
325:
305:
285:
231:
211:
191:
171:
151:
109:
57:on his 70th birthday.
1327:
1295:
1275:
1255:
1213:
1193:
1151:
1131:
1103:
498:
478:
458:
408:
366:
346:
326:
306:
286:
232:
212:
192:
172:
152:
110:
1445:, via the so-called
1439:intuitionistic logic
1304:
1284:
1264:
1222:
1202:
1160:
1140:
1120:
510:
487:
467:
425:
375:
355:
335:
331:, i.e. the proof of
315:
295:
241:
221:
201:
181:
161:
119:
99:
85:Intuitionistic logic
16:Arithmetical concept
1485:Kurt Gödel (1958).
417:Formula translation
1660:1958 introductions
1467:weak KĹ‘nig's lemma
1350:Markov's principle
1322:
1290:
1270:
1250:
1208:
1188:
1146:
1126:
1098:
1096:
493:
483:as follows, where
473:
453:
403:
361:
341:
321:
301:
281:
237:is interpreted as
227:
207:
187:
167:
147:
105:
75:Heyting arithmetic
29:Heyting arithmetic
1613:Anne S. Troelstra
1587:Ulrich Kohlenbach
1447:Dialectica spaces
1437:'s refinement of
1293:{\displaystyle t}
1273:{\displaystyle A}
1218:and the proof of
1211:{\displaystyle t}
1149:{\displaystyle t}
1129:{\displaystyle A}
496:{\displaystyle P}
476:{\displaystyle A}
413:in the system T.
364:{\displaystyle t}
344:{\displaystyle A}
324:{\displaystyle A}
304:{\displaystyle A}
230:{\displaystyle A}
210:{\displaystyle A}
190:{\displaystyle y}
170:{\displaystyle x}
108:{\displaystyle A}
91:Logic translation
45:consistency proof
1667:
1635:
1634:
1628:
1620:
1609:
1603:
1602:
1596:
1583:
1577:
1576:
1570:
1560:Solomon Feferman
1552:
1546:
1545:
1535:
1529:
1528:
1526:
1516:Valeria de Paiva
1512:
1506:
1505:
1497:
1491:
1490:
1482:
1331:
1329:
1328:
1323:
1299:
1297:
1296:
1291:
1279:
1277:
1276:
1271:
1259:
1257:
1256:
1251:
1234:
1233:
1217:
1215:
1214:
1209:
1197:
1195:
1194:
1189:
1172:
1171:
1155:
1153:
1152:
1147:
1135:
1133:
1132:
1127:
1107:
1105:
1104:
1099:
1097:
1075:
1074:
1037:
1036:
996:
995:
958:
957:
914:
913:
880:
879:
836:
835:
792:
791:
746:
745:
681:
680:
640:
639:
612:
611:
568:
567:
532:
531:
502:
500:
499:
494:
482:
480:
479:
474:
462:
460:
459:
454:
437:
436:
412:
410:
409:
404:
387:
386:
370:
368:
367:
362:
350:
348:
347:
342:
330:
328:
327:
322:
310:
308:
307:
302:
290:
288:
287:
282:
265:
264:
236:
234:
233:
228:
217:). Intuitively,
216:
214:
213:
208:
196:
194:
193:
188:
176:
174:
173:
168:
156:
154:
153:
148:
131:
130:
114:
112:
111:
106:
71:Peano arithmetic
35:, the so-called
1675:
1674:
1670:
1669:
1668:
1666:
1665:
1664:
1640:
1639:
1638:
1622:
1621:
1610:
1606:
1584:
1580:
1568:
1553:
1549:
1536:
1532:
1524:
1513:
1509:
1498:
1494:
1483:
1479:
1475:
1462:
1431:
1418:
1405:
1403:Classical logic
1377:
1368:
1345:Axiom of choice
1338:
1305:
1302:
1301:
1285:
1282:
1281:
1265:
1262:
1261:
1229:
1225:
1223:
1220:
1219:
1203:
1200:
1199:
1167:
1163:
1161:
1158:
1157:
1141:
1138:
1137:
1121:
1118:
1117:
1114:
1095:
1094:
1070:
1066:
1064:
1059:
1032:
1028:
1013:
1012:
991:
987:
985:
980:
953:
949:
934:
933:
909:
905:
875:
871:
869:
864:
831:
827:
812:
811:
787:
783:
741:
737:
720:
715:
676:
672:
657:
656:
635:
631:
607:
603:
601:
596:
563:
559:
544:
543:
538:
533:
527:
523:
513:
511:
508:
507:
488:
485:
484:
468:
465:
464:
432:
428:
426:
423:
422:
419:
382:
378:
376:
373:
372:
371:and a proof of
356:
353:
352:
336:
333:
332:
316:
313:
312:
296:
293:
292:
260:
256:
242:
239:
238:
222:
219:
218:
202:
199:
198:
182:
179:
178:
162:
159:
158:
126:
122:
120:
117:
116:
100:
97:
96:
93:
87:
63:
17:
12:
11:
5:
1673:
1663:
1662:
1657:
1652:
1637:
1636:
1604:
1578:
1547:
1530:
1507:
1492:
1476:
1474:
1471:
1461:
1458:
1430:
1427:
1417:
1414:
1404:
1401:
1376:
1373:
1367:
1364:
1359:
1358:
1352:
1347:
1337:
1334:
1321:
1318:
1315:
1312:
1309:
1289:
1269:
1249:
1246:
1243:
1240:
1237:
1232:
1228:
1207:
1187:
1184:
1181:
1178:
1175:
1170:
1166:
1145:
1125:
1113:
1110:
1109:
1108:
1093:
1090:
1087:
1084:
1081:
1078:
1073:
1069:
1065:
1063:
1060:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1035:
1031:
1027:
1024:
1021:
1018:
1015:
1014:
1011:
1008:
1005:
1002:
999:
994:
990:
986:
984:
981:
979:
976:
973:
970:
967:
964:
961:
956:
952:
948:
945:
942:
939:
936:
935:
932:
929:
926:
923:
920:
917:
912:
908:
904:
901:
898:
895:
892:
889:
886:
883:
878:
874:
870:
868:
865:
863:
860:
857:
854:
851:
848:
845:
842:
839:
834:
830:
826:
823:
820:
817:
814:
813:
810:
807:
804:
801:
798:
795:
790:
786:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
744:
740:
736:
733:
730:
727:
724:
721:
719:
716:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
679:
675:
671:
668:
665:
662:
659:
658:
655:
652:
649:
646:
643:
638:
634:
630:
627:
624:
621:
618:
615:
610:
606:
602:
600:
597:
595:
592:
589:
586:
583:
580:
577:
574:
571:
566:
562:
558:
555:
552:
549:
546:
545:
542:
539:
537:
534:
530:
526:
522:
519:
516:
515:
492:
472:
452:
449:
446:
443:
440:
435:
431:
418:
415:
402:
399:
396:
393:
390:
385:
381:
360:
340:
320:
300:
280:
277:
274:
271:
268:
263:
259:
255:
252:
249:
246:
226:
206:
186:
166:
146:
143:
140:
137:
134:
129:
125:
104:
86:
83:
62:
59:
15:
9:
6:
4:
3:
2:
1672:
1661:
1658:
1656:
1653:
1651:
1648:
1647:
1645:
1632:
1626:
1618:
1614:
1608:
1600:
1595:
1594:
1588:
1582:
1574:
1567:
1566:
1561:
1557:
1556:Jeremy Avigad
1551:
1543:
1542:
1534:
1523:
1522:
1517:
1511:
1503:
1496:
1488:
1481:
1477:
1470:
1468:
1457:
1455:
1450:
1448:
1444:
1440:
1436:
1426:
1424:
1423:bar recursion
1416:Comprehension
1413:
1411:
1400:
1398:
1394:
1390:
1386:
1382:
1372:
1363:
1356:
1353:
1351:
1348:
1346:
1343:
1342:
1341:
1333:
1319:
1316:
1313:
1307:
1287:
1267:
1244:
1241:
1238:
1230:
1226:
1205:
1182:
1179:
1176:
1168:
1164:
1143:
1123:
1088:
1085:
1082:
1079:
1071:
1067:
1061:
1053:
1050:
1047:
1044:
1041:
1033:
1025:
1022:
1006:
1003:
1000:
992:
988:
982:
974:
971:
968:
965:
962:
954:
946:
943:
927:
924:
921:
918:
910:
906:
896:
893:
890:
887:
884:
876:
872:
866:
858:
855:
852:
849:
846:
843:
840:
832:
824:
818:
802:
799:
796:
788:
784:
777:
774:
771:
765:
756:
753:
750:
742:
738:
731:
728:
725:
717:
709:
706:
703:
700:
697:
694:
691:
688:
685:
677:
669:
666:
663:
650:
647:
644:
636:
632:
628:
622:
619:
616:
608:
604:
598:
590:
587:
584:
581:
578:
575:
572:
564:
556:
553:
550:
540:
535:
528:
520:
506:
505:
504:
490:
470:
447:
444:
441:
433:
429:
414:
397:
394:
391:
383:
379:
358:
338:
318:
298:
275:
272:
269:
261:
257:
253:
247:
224:
204:
184:
164:
141:
138:
135:
127:
123:
102:
92:
82:
80:
76:
72:
68:
58:
56:
52:
51:
46:
43:to provide a
42:
38:
34:
30:
26:
22:
1655:Intuitionism
1650:Proof theory
1616:
1607:
1592:
1581:
1564:
1550:
1540:
1533:
1520:
1510:
1501:
1495:
1486:
1480:
1463:
1454:affine logic
1451:
1443:linear logic
1432:
1429:Linear logic
1419:
1406:
1395:, which are
1378:
1369:
1360:
1339:
1115:
420:
94:
64:
55:Paul Bernays
48:
36:
24:
21:proof theory
18:
79:consistency
1644:Categories
1473:References
1410:Shoenfield
1385:finitistic
1366:Extensions
1156:such that
89:See also:
61:Motivation
50:Dialectica
41:Kurt Gödel
1625:cite book
1441:known as
1375:Induction
1317:∧
1311:→
1062:≡
1020:∀
983:≡
941:∃
903:→
867:≡
822:→
781:→
775:≠
766:∧
735:→
718:≡
667:∨
629:∧
599:≡
554:∧
536:≡
251:∀
245:∃
1589:(2008).
1562:(1999).
1518:(1991).
1460:Variants
65:Via the
37:System T
1573:S. Buss
1435:Girard
1379:Given
23:, the
1601:–536.
1571:. in
1569:(PDF)
1525:(PDF)
1631:link
1558:and
177:and
19:In
1646::
1627:}}
1623:{{
1425:.
1633:)
1599:1
1320:A
1314:A
1308:A
1288:t
1268:A
1248:)
1245:y
1242:;
1239:t
1236:(
1231:D
1227:A
1206:t
1186:)
1183:y
1180:;
1177:t
1174:(
1169:D
1165:A
1144:t
1124:A
1092:)
1089:y
1086:;
1083:z
1080:f
1077:(
1072:D
1068:A
1057:)
1054:z
1051:,
1048:y
1045:;
1042:f
1039:(
1034:D
1030:)
1026:A
1023:z
1017:(
1010:)
1007:y
1004:;
1001:x
998:(
993:D
989:A
978:)
975:y
972:;
969:z
966:,
963:x
960:(
955:D
951:)
947:A
944:z
938:(
931:)
928:w
925:;
922:x
919:g
916:(
911:D
907:B
900:)
897:w
894:x
891:f
888:;
885:x
882:(
877:D
873:A
862:)
859:w
856:,
853:x
850:;
847:g
844:,
841:f
838:(
833:D
829:)
825:B
819:A
816:(
809:)
806:)
803:w
800:;
797:v
794:(
789:D
785:B
778:0
772:z
769:(
763:)
760:)
757:y
754:;
751:x
748:(
743:D
739:A
732:0
729:=
726:z
723:(
713:)
710:w
707:,
704:y
701:;
698:z
695:,
692:v
689:,
686:x
683:(
678:D
674:)
670:B
664:A
661:(
654:)
651:w
648:;
645:v
642:(
637:D
633:B
626:)
623:y
620:;
617:x
614:(
609:D
605:A
594:)
591:w
588:,
585:y
582:;
579:v
576:,
573:x
570:(
565:D
561:)
557:B
551:A
548:(
541:P
529:D
525:)
521:P
518:(
491:P
471:A
451:)
448:y
445:;
442:x
439:(
434:D
430:A
401:)
398:y
395:;
392:t
389:(
384:D
380:A
359:t
339:A
319:A
299:A
279:)
276:y
273:;
270:x
267:(
262:D
258:A
254:y
248:x
225:A
205:A
185:y
165:x
145:)
142:y
139:;
136:x
133:(
128:D
124:A
103:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.