856:
Remove contraction inferences on previously existentially quantified formulas, since the formulas (now with terms substituted for previously quantified variables) might not be identical anymore after the removal of the quantifier
621:
The restriction to formulas in prenex form containing only existential quantifiers does not limit the generality of the theorem, because formulas can be converted to prenex form and their universal quantifiers can be removed by
455:
1027:
1065:
Herbrand disjunctions and expansion-tree proofs have been extended with a notion of cut. Due to the complexity of cut-elimination, Herbrand disjunctions with cuts can be non-elementarily smaller than a standard
Herbrand
848:
561:
733:
171:
1069:
Herbrand disjunctions have been generalized to
Herbrand sequents, allowing Herbrand's theorem to be stated for sequents: "a Skolemized sequent is derivable if and only if it has a Herbrand sequent".
913:
229:
1209:
337:
305:
266:
630:
Herbrandization is performed. Herbrandization can be avoided by imposing additional restrictions on the variable dependencies allowed in the
Herbrand disjunction.
612:
584:
61:. Although Herbrand originally proved his theorem for arbitrary formulas of first-order logic, the simpler version shown here, restricted to formulas in
349:
918:
757:
1185:
470:
645:
83:
231:
quantifier-free, though it may contain additional free variables. This version of
Herbrand's theorem states that the above formula is
1169:
590:
containing only existential quantifiers is provable (valid) in first-order logic if and only if a disjunction composed of
28:
1041:
were not known at the time of
Herbrand's proof, and Herbrand had to prove his theorem in a more complicated way.
58:
1084:
863:
751:
179:
1059:
1055:
66:
1126:
Samuel R. Buss: "Handbook of Proof Theory". Chapter 1, "An
Introduction to Proof Theory". Elsevier, 1998.
853:
Starting from leaves and working downwards, remove the inferences that introduce existential quantifiers.
638:
A proof of the non-trivial direction of the theorem can be constructed according to the following steps:
1214:
1204:
591:
736:
1094:
310:
278:
54:
1079:
1051:
42:
32:
1177:
1163:
1181:
1089:
615:
50:
1034:
743:
269:
241:
232:
46:
1159:
1173:
1038:
623:
597:
569:
1198:
1137:
860:
The removal of contractions accumulates all the relevant substitution instances of
236:
450:{\displaystyle F(t_{11},\ldots ,t_{1n})\vee \ldots \vee F(t_{r1},\ldots ,t_{rn})}
1155:
1022:{\displaystyle \vdash F(t_{11},\ldots ,t_{1n}),\ldots ,F(t_{r1},\ldots ,t_{rn})}
587:
62:
17:
1062:
corresponds to a
Herbrand disjunction, when restricted to first-order logic.
843:{\displaystyle \vdash (\exists y_{1},\ldots ,y_{n})F(y_{1},\ldots ,y_{n})}
740:
747:
556:{\displaystyle (\exists y_{1},\ldots ,y_{n})F(y_{1},\ldots ,y_{n}).}
728:{\displaystyle (\exists y_{1},\ldots ,y_{n})F(y_{1},\ldots ,y_{n})}
166:{\displaystyle (\exists y_{1},\ldots ,y_{n})F(y_{1},\ldots ,y_{n})}
915:
in the right side of the sequent, thus resulting in a proof of
1115:
Travaux de la société des
Sciences et des Lettres de Varsovie
49:(1930). It essentially allows a certain kind of reduction of
1113:
J. Herbrand: Recherches sur la théorie de la démonstration.
1117:, Class III, Sciences Mathématiques et Physiques, 33, 1930.
57:. Herbrand's theorem is the logical foundation for most
1029:, from which the Herbrand disjunction can be obtained.
921:
866:
760:
648:
600:
572:
473:
352:
313:
281:
244:
182:
86:
1021:
907:
842:
727:
606:
578:
555:
449:
331:
299:
260:
223:
165:
1135:Dale Miller: A Compact Representation of Proofs.
235:if and only if there exists a finite sequence of
1162:, in Maurice, Daniel; Leivant, Raphaël (eds.),
626:. Conversion to prenex form can be avoided, if
8:
1210:Theorems in the foundations of mathematics
1007:
985:
954:
935:
920:
896:
877:
865:
831:
812:
793:
774:
759:
716:
697:
678:
659:
647:
599:
571:
541:
522:
503:
484:
472:
460:is valid. If it is valid, it is called a
435:
413:
382:
363:
351:
312:
280:
249:
243:
212:
193:
181:
154:
135:
116:
97:
85:
33:Herbrand's theorem on ramification groups
1050:Herbrand's theorem has been extended to
1106:
176:be a formula of first-order logic with
908:{\displaystyle F(y_{1},\ldots ,y_{n})}
224:{\displaystyle F(y_{1},\ldots ,y_{n})}
1045:Generalizations of Herbrand's theorem
594:of the quantifier-free subformula of
7:
268:, possibly in an expansion of the
1165:Logic and Computational Complexity
767:
652:
477:
90:
25:
1170:Lecture Notes in Computer Science
754:, there is a cut-free proof of
1016:
978:
963:
928:
902:
870:
837:
805:
799:
764:
722:
690:
684:
649:
547:
515:
509:
474:
444:
406:
391:
356:
218:
186:
160:
128:
122:
87:
1:
1058:. The deep representation of
618:(propositionally derivable).
332:{\displaystyle 1\leq j\leq n}
300:{\displaystyle 1\leq i\leq r}
1141:, 46(4), pp. 347--370, 1987.
41:is a fundamental result of
1231:
26:
59:automatic theorem provers
27:Not to be confused with
1160:"On Herbrand's Theorem"
1085:Herbrand interpretation
1044:
752:cut-elimination theorem
69:, became more popular.
67:existential quantifiers
1023:
909:
844:
729:
608:
592:substitution instances
580:
566:Informally: a formula
557:
451:
333:
301:
262:
261:{\displaystyle t_{ij}}
225:
167:
29:Herbrand–Ribet theorem
1060:expansion-tree proofs
1056:expansion-tree proofs
1024:
910:
845:
746:, which follows from
730:
609:
581:
558:
452:
334:
302:
263:
226:
168:
1172:, Berlin, New York:
919:
864:
758:
646:
598:
570:
471:
462:Herbrand disjunction
350:
311:
279:
242:
180:
84:
1095:Compactness theorem
55:propositional logic
1080:Herbrand structure
1052:higher-order logic
1019:
905:
840:
735:is valid, then by
725:
604:
576:
553:
447:
329:
297:
258:
221:
163:
43:mathematical logic
39:Herbrand's theorem
1187:978-3-540-60178-4
1090:Herbrand universe
607:{\displaystyle A}
579:{\displaystyle A}
51:first-order logic
16:(Redirected from
1222:
1190:
1142:
1133:
1127:
1124:
1118:
1111:
1035:sequent calculus
1028:
1026:
1025:
1020:
1015:
1014:
993:
992:
962:
961:
940:
939:
914:
912:
911:
906:
901:
900:
882:
881:
849:
847:
846:
841:
836:
835:
817:
816:
798:
797:
779:
778:
744:sequent calculus
734:
732:
731:
726:
721:
720:
702:
701:
683:
682:
664:
663:
613:
611:
610:
605:
585:
583:
582:
577:
562:
560:
559:
554:
546:
545:
527:
526:
508:
507:
489:
488:
456:
454:
453:
448:
443:
442:
421:
420:
390:
389:
368:
367:
338:
336:
335:
330:
306:
304:
303:
298:
267:
265:
264:
259:
257:
256:
230:
228:
227:
222:
217:
216:
198:
197:
172:
170:
169:
164:
159:
158:
140:
139:
121:
120:
102:
101:
65:containing only
47:Jacques Herbrand
21:
1230:
1229:
1225:
1224:
1223:
1221:
1220:
1219:
1195:
1194:
1188:
1174:Springer-Verlag
1156:Buss, Samuel R.
1154:
1151:
1146:
1145:
1134:
1130:
1125:
1121:
1112:
1108:
1103:
1076:
1047:
1039:cut-elimination
1003:
981:
950:
931:
917:
916:
892:
873:
862:
861:
827:
808:
789:
770:
756:
755:
712:
693:
674:
655:
644:
643:
642:If the formula
636:
624:Herbrandization
596:
595:
568:
567:
537:
518:
499:
480:
469:
468:
431:
409:
378:
359:
348:
347:
309:
308:
277:
276:
245:
240:
239:
208:
189:
178:
177:
150:
131:
112:
93:
82:
81:
75:
36:
23:
22:
18:Herbrand theory
15:
12:
11:
5:
1228:
1226:
1218:
1217:
1212:
1207:
1197:
1196:
1193:
1192:
1186:
1150:
1147:
1144:
1143:
1128:
1119:
1105:
1104:
1102:
1099:
1098:
1097:
1092:
1087:
1082:
1075:
1072:
1071:
1070:
1067:
1063:
1046:
1043:
1031:
1030:
1018:
1013:
1010:
1006:
1002:
999:
996:
991:
988:
984:
980:
977:
974:
971:
968:
965:
960:
957:
953:
949:
946:
943:
938:
934:
930:
927:
924:
904:
899:
895:
891:
888:
885:
880:
876:
872:
869:
858:
854:
851:
839:
834:
830:
826:
823:
820:
815:
811:
807:
804:
801:
796:
792:
788:
785:
782:
777:
773:
769:
766:
763:
724:
719:
715:
711:
708:
705:
700:
696:
692:
689:
686:
681:
677:
673:
670:
667:
662:
658:
654:
651:
635:
632:
603:
575:
564:
563:
552:
549:
544:
540:
536:
533:
530:
525:
521:
517:
514:
511:
506:
502:
498:
495:
492:
487:
483:
479:
476:
458:
457:
446:
441:
438:
434:
430:
427:
424:
419:
416:
412:
408:
405:
402:
399:
396:
393:
388:
385:
381:
377:
374:
371:
366:
362:
358:
355:
341:
340:
328:
325:
322:
319:
316:
296:
293:
290:
287:
284:
255:
252:
248:
220:
215:
211:
207:
204:
201:
196:
192:
188:
185:
174:
173:
162:
157:
153:
149:
146:
143:
138:
134:
130:
127:
124:
119:
115:
111:
108:
105:
100:
96:
92:
89:
74:
71:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1227:
1216:
1213:
1211:
1208:
1206:
1203:
1202:
1200:
1189:
1183:
1179:
1175:
1171:
1167:
1166:
1161:
1157:
1153:
1152:
1148:
1140:
1139:
1138:Studia Logica
1132:
1129:
1123:
1120:
1116:
1110:
1107:
1100:
1096:
1093:
1091:
1088:
1086:
1083:
1081:
1078:
1077:
1073:
1068:
1064:
1061:
1057:
1053:
1049:
1048:
1042:
1040:
1036:
1011:
1008:
1004:
1000:
997:
994:
989:
986:
982:
975:
972:
969:
966:
958:
955:
951:
947:
944:
941:
936:
932:
925:
922:
897:
893:
889:
886:
883:
878:
874:
867:
859:
855:
852:
832:
828:
824:
821:
818:
813:
809:
802:
794:
790:
786:
783:
780:
775:
771:
761:
753:
749:
745:
742:
738:
717:
713:
709:
706:
703:
698:
694:
687:
679:
675:
671:
668:
665:
660:
656:
641:
640:
639:
633:
631:
629:
625:
619:
617:
601:
593:
589:
573:
550:
542:
538:
534:
531:
528:
523:
519:
512:
504:
500:
496:
493:
490:
485:
481:
467:
466:
465:
463:
439:
436:
432:
428:
425:
422:
417:
414:
410:
403:
400:
397:
394:
386:
383:
379:
375:
372:
369:
364:
360:
353:
346:
345:
344:
326:
323:
320:
317:
314:
294:
291:
288:
285:
282:
275:
274:
273:
271:
253:
250:
246:
238:
234:
213:
209:
205:
202:
199:
194:
190:
183:
155:
151:
147:
144:
141:
136:
132:
125:
117:
113:
109:
106:
103:
98:
94:
80:
79:
78:
72:
70:
68:
64:
60:
56:
52:
48:
44:
40:
34:
30:
19:
1215:Metatheorems
1205:Proof theory
1164:
1136:
1131:
1122:
1114:
1109:
1066:disjunction.
1032:
737:completeness
637:
634:Proof sketch
627:
620:
565:
461:
459:
342:
175:
76:
45:obtained by
38:
37:
1176:, pp.
857:inferences.
588:prenex form
343:such that
63:prenex form
1199:Categories
1149:References
628:structural
1054:by using
1033:However,
998:…
970:…
945:…
923:⊢
887:…
822:…
784:…
768:∃
762:⊢
707:…
669:…
653:∃
616:tautology
532:…
494:…
478:∃
426:…
401:∨
398:…
395:∨
373:…
324:≤
318:≤
292:≤
286:≤
203:…
145:…
107:…
91:∃
73:Statement
1158:(1995),
1074:See also
741:cut-free
272:, with
270:language
1178:195–209
748:Gentzen
1184:
1101:Notes
614:is a
464:for
237:terms
233:valid
77:Let
1182:ISBN
1037:and
307:and
750:'s
739:of
586:in
53:to
31:or
1201::
1180:,
1168:,
937:11
365:11
1191:.
1017:)
1012:n
1009:r
1005:t
1001:,
995:,
990:1
987:r
983:t
979:(
976:F
973:,
967:,
964:)
959:n
956:1
952:t
948:,
942:,
933:t
929:(
926:F
903:)
898:n
894:y
890:,
884:,
879:1
875:y
871:(
868:F
850:.
838:)
833:n
829:y
825:,
819:,
814:1
810:y
806:(
803:F
800:)
795:n
791:y
787:,
781:,
776:1
772:y
765:(
723:)
718:n
714:y
710:,
704:,
699:1
695:y
691:(
688:F
685:)
680:n
676:y
672:,
666:,
661:1
657:y
650:(
602:A
574:A
551:.
548:)
543:n
539:y
535:,
529:,
524:1
520:y
516:(
513:F
510:)
505:n
501:y
497:,
491:,
486:1
482:y
475:(
445:)
440:n
437:r
433:t
429:,
423:,
418:1
415:r
411:t
407:(
404:F
392:)
387:n
384:1
380:t
376:,
370:,
361:t
357:(
354:F
339:,
327:n
321:j
315:1
295:r
289:i
283:1
254:j
251:i
247:t
219:)
214:n
210:y
206:,
200:,
195:1
191:y
187:(
184:F
161:)
156:n
152:y
148:,
142:,
137:1
133:y
129:(
126:F
123:)
118:n
114:y
110:,
104:,
99:1
95:y
88:(
35:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.