Erstveröffentlichung am 3. Mai 2002; inhaltliche Überarbeitung Mo 6. Mai 2019
Der Epsilon-Kalkül ist ein logischer Formalismus, den David Hilbert im Dienst seines Programms in den Grundlagen der Mathematik entwickelt hat. Der Epsilon-Operator ist ein termbildender Operator, der Quantifizierer in gewöhnlicher Prädikatenlogik ersetzt. Insbesondere im Kalkül bezeichnet ein Term (varepsilon x A) einige (x), die (A (x)) erfüllen, falls es eine gibt. In Hilberts Programm spielen die Epsilon-Begriffe die Rolle idealer Elemente; Das Ziel von Hilberts finitistischen Konsistenznachweisen ist es, ein Verfahren zu geben, das solche Begriffe aus einem formalen Beweis entfernt. Die Verfahren, mit denen dies durchgeführt werden soll, basieren auf Hilberts Epsilon-Substitutionsmethode. Der Epsilon-Kalkül findet jedoch auch in anderen Zusammenhängen Anwendung. Die erste allgemeine Anwendung des Epsilon-Kalküls erfolgte in Hilberts Epsilon-Theoremen.die wiederum die Grundlage für den ersten korrekten Beweis des Herbrandschen Theorems bilden. In jüngerer Zeit wurden Varianten des Epsilon-Operators in der Linguistik und Sprachphilosophie angewendet, um mit anaphorischen Pronomen umzugehen.
1. Übersicht
2. Der Epsilon-Kalkül
3. Die Epsilon-Sätze
4. Satz von Herbrand
5. Die Epsilon-Substitutionsmethode und die Arithmetik
6. Neuere Entwicklungen
7. Epsilon-Operatoren in Linguistik, Philosophie und nicht-klassischer Logik
Literaturverzeichnis
Akademische Werkzeuge
Andere Internetquellen
Verwandte Einträge
1. Übersicht
Um die Jahrhundertwende wurden David Hilbert und Henri Poincaré als die beiden wichtigsten Mathematiker ihrer Generation anerkannt. Hilberts Spektrum an mathematischen Interessen war breit und beinhaltete ein Interesse an den Grundlagen der Mathematik: Seine Grundlagen der Geometrie wurden 1899 veröffentlicht, und von der Liste der Fragen, die 1900 an den Internationalen Mathematikerkongress gestellt wurden, befassten sich drei mit eindeutig grundlegenden Fragen.
Nach der Veröffentlichung von Russells Paradoxon hielt Hilbert 1904 eine Ansprache vor dem Dritten Internationalen Mathematikerkongress, auf der er erstmals seinen Plan skizzierte, durch syntaktische Konsistenzbeweise eine strenge Grundlage für die Mathematik zu schaffen. Erst 1917 kehrte er ernsthaft zum Thema zurück, als er mit Unterstützung von Paul Bernays eine Reihe von Vorlesungen über die Grundlagen der Mathematik begann. Obwohl Hilbert von der Arbeit von Russell und Whitehead in ihrer Principia Mathematica beeindruckt war, war er überzeugt, dass der logistische Versuch, Mathematik auf Logik zu reduzieren, nicht erfolgreich sein konnte, insbesondere aufgrund des nicht logischen Charakters ihres Axioms der Reduzierbarkeit. Gleichzeitig beurteilte er die intuitionistische Ablehnung des Gesetzes der ausgeschlossenen Mitte als für die Mathematik inakzeptabel. Deshalb,Um Bedenken entgegenzuwirken, die durch die Entdeckung der logischen und satztheoretischen Paradoxien aufgeworfen wurden, war ein neuer Ansatz erforderlich, um moderne mathematische Methoden zu rechtfertigen.
Bis zum Sommer 1920 hatte Hilbert einen solchen Ansatz formuliert. Zunächst sollten moderne mathematische Methoden in formalen deduktiven Systemen dargestellt werden. Zweitens sollten diese formalen Systeme syntaktisch konsistent bewiesen werden, nicht durch Ausstellen eines Modells oder Reduzieren ihrer Konsistenz auf ein anderes System, sondern durch ein direktes metamathematisches Argument eines expliziten „endlichen“Charakters. Der Ansatz wurde als Hilberts Programm bekannt. Der Epsilon-Kalkül sollte die erste Komponente dieses Programms liefern, während seine Epsilon-Substitutionsmethode die zweite sein sollte.
Der Epsilon-Kalkül ist in seiner grundlegendsten Form eine Erweiterung der Prädikatenlogik erster Ordnung mit einer „Epsilon-Operation“, die für jede echte existenzielle Formel einen Zeugen des existenziellen Quantifizierers auswählt. Die Erweiterung ist insofern konservativ, als sie keine neuen Konsequenzen erster Ordnung hinzufügt. Umgekehrt können Quantifizierer jedoch in Bezug auf die Epsilons definiert werden, so dass die Logik erster Ordnung in Bezug auf quantifiziererfreies Denken verstanden werden kann, das die Epsilon-Operation beinhaltet. Es ist dieses letztere Merkmal, das den Kalkül zum Zweck des Nachweises der Konsistenz bequem macht. Geeignete Erweiterungen des Epsilon-Kalküls ermöglichen es, stärkere quantifizierende Theorien von Zahlen und Mengen in quantifiziererfreie Kalküle einzubetten. Hilbert erwartete, dass es möglich sein würde, die Konsistenz solcher Erweiterungen zu demonstrieren.
2. Der Epsilon-Kalkül
In seinem Hamburger Vortrag von 1921 (1922) stellte Hilbert zunächst die Idee vor, mit Auswahlfunktionen das Prinzip der ausgeschlossenen Mitte in einem formalen System für die Arithmetik zu behandeln. Diese Ideen wurden in einer Reihe von Vorlesungen zwischen 1921 und 1923 sowie in Hilberts (1923) zur Epsilon-Rechnung und zur Epsilon-Substitutionsmethode entwickelt. Die endgültige Darstellung des Epsilon-Kalküls findet sich in Wilhelm Ackermanns Dissertation (1924).
In diesem Abschnitt wird eine Version des Kalküls beschrieben, die der Logik erster Ordnung entspricht, während im Folgenden Erweiterungen der Arithmetik erster und zweiter Ordnung beschrieben werden.
Sei (L) eine Sprache erster Ordnung, dh eine Liste von Konstanten-, Funktions- und Beziehungssymbolen mit bestimmten Aritäten. Die Menge der Epsilon-Terme und die Menge der Formeln von (L) werden gleichzeitig induktiv wie folgt definiert:
Jede Konstante von (L) ist ein Term.
Jede Variable ist ein Begriff.
Wenn (s) und (t) Begriffe sind, dann ist (s = t) eine Formel.
Wenn (s_1, \ ldots, s_k) Begriffe sind und (F) ein (k) - Funktionssymbol von (L, F (s_1, \ ldots, s_k)) ein Begriff ist.
Wenn (s_1, \ ldots, s_k) Begriffe sind und (R) ein (k) - Beziehungssymbol von (L, R (s_1, \ ldots, s_k)) eine Formel ist.
Wenn (A) und (B) Formeln sind, sind dies auch (A \ Keil B, A \ Vee B, A \ Rechtspfeil B) und (Neg A).
Wenn (A) eine Formel und (x) eine Variable ist, ist (varepsilon x A) ein Begriff.
Die Substitution und die Begriffe der freien und gebundenen Variablen werden auf übliche Weise definiert. Insbesondere wird die Variable (x) an den Begriff (varepsilon x A) gebunden. Die beabsichtigte Interpretation ist, dass (varepsilon x A) einige (x) bezeichnet, die (A) erfüllen, falls es eine gibt. Somit werden die Epsilon-Terme durch das folgende Axiom (Hilberts „transfinites Axiom“) geregelt: [A (x) rechter Pfeil A (varepsilon x A)) Zusätzlich enthält der Epsilon-Kalkül einen vollständigen Satz von Axiomen, die das regeln klassische Satzverbindungen und Axiome, die das Gleichheitssymbol bestimmen. Die einzigen Regeln des Kalküls sind die folgenden:
Modus ponens
Substitution: Aus (A (x)) schließen Sie (A (t)) für einen beliebigen Begriff (t.)
Frühere Formen des Epsilon-Kalküls (wie das in Hilbert 1923 vorgestellte) verwenden eine doppelte Form des Epsilon-Operators, in der (varepsilon x A) einen Wert zurückgibt, der (A (x)) verfälscht. Die obige Version wurde in Ackermanns Dissertation (1924) verwendet und ist zum Standard geworden.
Beachten Sie, dass der gerade beschriebene Kalkül quantifiziererfrei ist. Quantifizierer können wie folgt definiert werden:) begin {align} existiert x A (x) & \ äquiv A (varepsilon x A) \ \ für alle x A (x) & \ äquiv A (varepsilon x () neg A)) end {align}) Daraus können die üblichen Quantifiziereraxiome und -regeln abgeleitet werden, sodass die obigen Definitionen dazu dienen, Logik erster Ordnung in den Epsilon-Kalkül einzubetten. Das Gegenteil ist jedoch nicht der Fall: Nicht jede Formel im Epsilon-Kalkül ist das Bild einer gewöhnlichen quantifizierten Formel unter dieser Einbettung. Daher ist der Epsilon-Kalkül aussagekräftiger als der Prädikat-Kalkül, einfach weil Epsilon-Terme auf komplexere Weise als Quantifizierer kombiniert werden können.
Es ist erwähnenswert, dass Epsilon-Begriffe nicht deterministisch sind und somit eine Form des Axioms der Wahl darstellen. Beispielsweise ist in einer Sprache mit konstanten Symbolen (a) und (b) (varepsilon x (x = a \ vee x = b)) entweder (a) oder (b)), aber der Kalkül lässt es völlig offen, was der Fall ist. Man kann dem Kalkül ein Schema der Extensionalität hinzufügen,) für alle x (A (x) linker rechter Pfeil B (x)) rechter Pfeil \ varepsilon x A = \ varepsilon x B), das behauptet, dass der epsilon-Operator dasselbe zuweist zeugen von äquivalenten Formeln (A) und (B). Für viele Anwendungen ist dieses zusätzliche Schema jedoch nicht erforderlich.
3. Die Epsilon-Sätze
Der zweite Band von Hilbert und Bernays 'Grundlagen der Mathematik (1939) liefert einen Bericht über die Ergebnisse der Epsilon-Rechnung, die zu diesem Zeitpunkt bewiesen worden waren. Dies beinhaltet eine Diskussion des ersten und zweiten Epsilon-Theorems mit Anwendungen auf die Logik erster Ordnung, die Epsilon-Substitutionsmethode für Arithmetik mit offener Induktion und eine Entwicklung der Analyse (dh Arithmetik zweiter Ordnung) mit dem Epsilon-Kalkül.
Der erste und der zweite Epsilon-Satz lauten wie folgt:
Erster Epsilon-Satz: Angenommen, (Gamma \ cup {A }) ist eine Menge quantifiziererfreier Formeln, die das Epsilon-Symbol nicht enthalten. Wenn (A) im Epsilon-Kalkül von (Gamma) ableitbar ist, ist (A) in der quantifiziererfreien Prädikatenlogik von (Gamma) ableitbar.
Zweiter Epsilon-Satz: Angenommen, (Gamma \ cup {A }) ist eine Reihe von Formeln, die das Epsilon-Symbol nicht enthalten. Wenn (A) im Epsilon-Kalkül von (Gamma) ableitbar ist, ist (A) in der Prädikatenlogik von (Gamma) ableitbar.
Im ersten Epsilon-Theorem soll die „quantifiziererfreie Prädikatenlogik“die obige Substitutionsregel enthalten, sodass sich quantifiziererfreie Axiome wie ihre universellen Abschlüsse verhalten. Da der Epsilon-Kalkül eine Logik erster Ordnung enthält, impliziert der erste Epsilon-Satz, dass jeder Umweg durch eine Prädikatenlogik erster Ordnung, die verwendet wird, um einen quantifiziererfreien Satz aus quantifiziererfreien Axiomen abzuleiten, letztendlich vermieden werden kann. Der zweite Epsilon-Satz zeigt, dass jeder Umweg durch den Epsilon-Kalkül, der verwendet wird, um einen Satz in der Sprache des Prädikatenkalküls aus Axiomen in der Sprache des Prädikatenkalküls abzuleiten, ebenfalls vermieden werden kann.
Allgemeiner legt der erste Epsilon-Satz fest, dass Quantifizierer und Epsilons immer aus einem Beweis einer quantifiziererfreien Formel aus anderen quantifiziererfreien Formeln eliminiert werden können. Dies ist für Hilberts Programm von besonderer Bedeutung, da die Epsilons die Rolle idealer Elemente in der Mathematik spielen. Wenn quantifiziererfreie Formeln dem „realen“Teil der mathematischen Theorie entsprechen, zeigt der erste Epsilon-Satz, dass ideale Elemente aus Beweisen realer Aussagen eliminiert werden können, vorausgesetzt, die Axiome sind auch reale Aussagen.
Diese Idee wird in einem bestimmten allgemeinen Konsistenzsatz präzisiert, den Hilbert und Bernays aus dem ersten Epsilon-Satz ableiten, der Folgendes besagt: Sei (F) ein beliebiges formales System, das sich aus der Prädikatenrechnung durch Addition einer konstanten Funktion ergibt und Prädikatsymbole plus wahre Axiome, die quantifizierer- und epsilonfrei sind, und nehmen an, dass die Wahrheit der Atomformeln in der neuen Sprache entscheidbar ist. Dann ist (F) in dem starken Sinne konsistent, dass jede ableitbare quantifizierer- und epsilonfreie Formel wahr ist. Hilbert und Bernays verwenden diesen Satz, um einen endlichen Konsistenznachweis der Elementargeometrie zu liefern (1939, Abschnitt 1.4).
Die Schwierigkeit, Konsistenzbeweise für Arithmetik und Analyse zu liefern, besteht darin, dieses Ergebnis auf Fälle auszudehnen, in denen die Axiome auch ideale Elemente enthalten, dh Epsilon-Terme.
Weiterführende Literatur. Die Originalquellen zum Epsilon-Kalkül und zu den Epsilon-Theoremen (Ackermann 1924, Hilbert & Bernays 1939) sind nur noch in deutscher Sprache verfügbar. Leisenring 1969 ist eine relativ moderne buchlange Einführung in die Epsilon-Rechnung in englischer Sprache. Der erste und der zweite Epsilon-Satz werden in Zach 2017 ausführlich beschrieben. Moser & Zach 2006 geben eine detaillierte Analyse für den Fall ohne Gleichheit. Die Originalbeweise sind für axiomatische Darstellungen des Epsilon-Kalküls angegeben. Maehara 1955 war der erste, der sequentielle Berechnungen mit Epsilon-Begriffen in Betracht zog. Er zeigte, wie man den zweiten Epsilon-Satz unter Verwendung der Schnitteliminierung beweist, und verstärkte dann den Satz, um das Schema der Extensionalität einzuschließen (Maehara 1957). Baaz et al. 2018 gibt eine verbesserte Version des ersten Epsilon-Theorems. Korrekturen zu Fehlern in der Literatur (einschließlich Leisenrings Buch) finden sich in Flannagan 1975; Ferrari 1987; und Yasuhara 1982. Eine Variation des Epsilon-Kalküls, die auf Skolem-Funktionen basiert und daher mit der Logik erster Ordnung kompatibel ist, wird in Davis & Fechter 1991 diskutiert.
4. Satz von Herbrand
Hilbert und Bernays verwendeten die Methoden des Epsilon-Kalküls, um Theoreme über die Logik erster Ordnung aufzustellen, die keinen Bezug zum Epsilon-Kalkül selbst haben. Ein solches Beispiel ist der Satz von Herbrand (Herbrand 1930; siehe Buss 1995, Girard 1982 und Abschnitt 2.5 von Buss 1998). Dies wird oft als die Aussage formuliert, dass, wenn eine existenzielle Formel) existiert x_1 \ ldots \ existiert x_k A (x_1, \ ldots, x_k)) in Prädikatenlogik erster Ordnung (ohne Gleichheit) ableitbar ist, wobei (A.) ist quantifiziererfrei, dann gibt es Folgen von Begriffen (t_ {1} ^ 1, \ ldots, t_ {k} ^ 1, \ ldots, t_ {1} ^ n, \ ldots, t_k ^ n), so dass [A (t_ {1} ^ 1, \ ldots, t_k ^ 1) vee \ ldots \ vee A (t_ {1} ^ n, \ ldots, t_k ^ n)) eine Tautologie ist. Wenn es sich um Logik erster Ordnung mit Gleichheit handelt,man muss "Tautologie" durch "tautologische Konsequenz von Substitutionsinstanzen der Gleichheitsaxiome" ersetzen; Wir werden den Begriff "Quasi-Tautologie" verwenden, um eine solche Formel zu beschreiben.
Die gerade beschriebene Version des Satzes von Herbrand folgt unmittelbar aus dem erweiterten ersten Epsilon-Theorem von Hilbert und Bernays. Hilbert und Bernays verwendeten jedoch Methoden, die mit dem Beweis des zweiten Epsilon-Theorems verbunden sind, und erzielten ein stärkeres Ergebnis, das wie Herbrands ursprüngliche Formulierung mehr Informationen liefert. Um die beiden folgenden Teile des Satzes zu verstehen, ist es hilfreich, ein bestimmtes Beispiel zu betrachten. Sei (A) die Formel
) existiert x_1 \ für alle x_2 \ existiert x_3 \ für alle x_4 B (x_1, x_2, x_3, x_4)) wobei (B) quantifiziererfrei ist. Die Negation von (A) entspricht) für alle x_1 \ existiert x_2 \ für alle x_3 \ existiert x_4 \ neg B (x_1, x_2, x _3, x_4).) Durch Skolemisieren, dh unter Verwendung von Funktionssymbolen, um die existenziellen Quantifizierer zu beobachten, erhalten wir) existiert f_2, f_4 \ für alle x_1, x_3 \ neg B (x_1, f_2 (x_1), x_3, f_4 (x_1, x_3)).) Wenn wir dies negieren, sehen wir, dass die ursprüngliche Formel "äquivalent" zu) für alle f_2, f_4 \ ist x_1, x_3 B (x_1, f_2 (x_1), x_3, f_4 (x_1, x_3)).)
Der erste Satz des folgenden Satzes besagt in diesem speziellen Fall, dass die obige Formel (A) in der Logik erster Ordnung genau dann ableitbar ist, wenn es eine Folge von Begriffen (t_ {1} ^ 1, t_ gibt {3} ^ 1, \ ldots, t_ {1} ^ n, t_ {3} ^ n) in der erweiterten Sprache mit (f_2) und (f_4), so dass [B (t_ {1} ^ 1, f_2 (t_ {1} ^ 1), t_ {3} ^ 1, f_4 (t_ {1} ^ 1, t_ {3} ^ 1)) vee \ ldots \ vee B (t_ {1} ^ n, f_2 (t_ {1} ^ n), t_ {3} ^ n, f_4 (t_ {1} ^ n, t_ {3} ^ n))) ist eine Quasi-Tautologie.
Der zweite Satz des folgenden Satzes besagt in diesem speziellen Fall, dass die obige Formel (A) in der Logik erster Ordnung genau dann ableitbar ist, wenn es Folgen von Variablen (x_ {2} ^ 1, x_ {gibt 4} ^ 1, \ ldots, x_2 ^ n, x_4 ^ n) und Begriffe (s_ {1} ^ 1, s_ {3} ^ 1, \ ldots, s_1 ^ n, s_3 ^ n) im Original Sprache so, dass [B (s_ {1} ^ 1, x_ {2} ^ 1, s_ {3} ^ 1, x_4 ^ 1) vee \ ldots \ vee B (s_1 ^ n, x_2 ^ n, s_3 ^ n, x_4 ^ n)) ist eine Quasi-Tautologie, so dass (A) aus dieser Formel nur unter Verwendung der nachstehend beschriebenen Quantifizierer- und Idempotenzregeln abgeleitet werden kann.
Angenommen, (A) ist eine beliebige Prenexformel der Form) mathbf {Q} _1 x_1 \ ldots \ mathbf {Q} _n x_n B (x_1, \ ldots, x_n),) wobei (B) ist quantifiziererfrei. Dann wird (B) als die Matrix von (A) bezeichnet, und eine Instanz von (B) wird erhalten, indem einige ihrer Variablen durch Begriffe in der Sprache von (B) ersetzt werden. Die Herbrand-Normalform (A ^ H) von (A) wird erhalten durch
Löschen jedes universellen Quantifizierers und
Ersetzen jeder universell quantifizierten Variablen (x_i) durch (f_i (x_ {i} ^ 1, \ ldots, x_ {i} ^ {k (i)})), wobei (x_ {i} ^ 1, \ ldots, x_ {i} ^ {k (i)}) sind die Variablen, die den existenziellen Quantifizierern vor (mathbf {Q} _i) in (A) (in der Reihenfolge) und (f_i) entsprechen) ist ein neues Funktionssymbol für diese Rolle.
Wenn wir uns auf eine Instanz der Matrix von (A ^ H) beziehen, meinen wir eine Formel, die durch Ersetzen von Begriffen in der erweiterten Sprache in der Matrix von (A ^ H) erhalten wird. Wir können jetzt Hilbert und Bernays Formulierung von angeben
Satz von Herbrand. (1) Eine Prenexformel (A) ist in der Prädikatenrechnung genau dann ableitbar, wenn eine Disjunktion von Instanzen der Matrix von (A ^ H) vorliegt, die eine Quasi-Tautologie ist.
(2) Eine Prenex-Formel (A) kann in der Prädikatenrechnung genau dann abgeleitet werden, wenn eine Disjunktion (bigvee_j B_j) von Instanzen der Matrix von (A) vorliegt, so dass (bigvee_j B_j) ist eine Quasi-Tautologie, und (A) kann unter Verwendung der folgenden Regeln von (bigvee_j B_j) abgeleitet werden:
aus (C_1 \ vee \ ldots \ vee C_i (t) vee \ ldots \ vee C_m)
schließen (C_1 \ vee \ ldots \ vee \ existiert x C_i (x) vee \ ldots \ vee C_m) und
aus (C_1 \ vee \ ldots \ vee C_i (x) vee \ ldots \ vee C_m)
schließen (C_1 \ vee \ ldots \ vee \ forall xC_i (x) vee \ ldots \ vee C_m) (wenn (x) nicht in (C_j) für (j \ ne i)),
sowie die Idempotenz von (vee) (aus (C \ vee C \ vee D) schließen (C \ vee D)).
Der Satz von Herbrand kann auch durch Verwendung der Eliminierung von Schnitten über Gentzens "Satz der mittleren Folge" erhalten werden. Der Beweis unter Verwendung des zweiten Epsilon-Theorems unterscheidet sich jedoch als erster vollständiger und korrekter Beweis des Herbrand-Theorems. Darüber hinaus, und dies wird selten anerkannt, während der auf der Schnitteliminierung basierende Beweis die Länge der Herbrand-Disjunktion nur in Abhängigkeit vom Schnittrang und der Komplexität der Schnittformeln im Beweis, der aus dem Beweis erhaltenen Länge, begrenzt basierend auf dem Epsilon-Kalkül liefert eine Grenze in Abhängigkeit von der Anzahl der Anwendungen des transfiniten Axioms und dem Rang und Grad der darin vorkommenden Epsilon-Terme. Mit anderen Worten, die Länge der Herbrand-Disjunktion hängt nur von der quantitativen Komplexität der beteiligten Substitutionen ab, und z.überhaupt nicht auf die Satzstruktur oder die Länge des Beweises.
Die am Anfang dieses Abschnitts angegebene Version des Satzes von Herbrand ist im Wesentlichen der Sonderfall von (2), in dem die Formel (A) existenziell ist. In Anbetracht dieses Sonderfalls entspricht (1) der Behauptung, dass eine Formel (A) in der Prädikatenlogik erster Ordnung genau dann ableitbar ist, wenn (A ^ H) ist. Die Vorwärtsrichtung dieser Äquivalenz ist viel einfacher zu beweisen; Tatsächlich ist für jede Formel (A, A \ rechter Pfeil A ^ H) in der Prädikatenlogik ableitbar. Das Beweisen der umgekehrten Richtung beinhaltet das Eliminieren der zusätzlichen Funktionssymbole in (A ^ H) und ist viel schwieriger, insbesondere bei Vorhandensein von Gleichheit. Hier spielen Epsilon-Methoden eine zentrale Rolle.
Bei gegebener Prenex-Formel wird die Skolem-Normalform (A ^ S) doppelt zu (A ^ H) definiert, dh indem existenziell quantifizierte Variablen durch Zeugenfunktionen ersetzt werden. Wenn (Gamma) eine Menge von Prenex-Sätzen ist, bezeichne (Gamma ^ S) die Menge ihrer Skolem-Normalformen. Unter Verwendung des Abzugssatzes und des Herbrandschen Satzes ist es nicht schwer zu zeigen, dass die folgenden paarweise äquivalent sind:) begin {align} Gamma & \ text {beweist} A \\ \ Gamma & \ text {beweist} A ^ H. \\ \ Gamma ^ S & \ text {beweist} A \\ \ Gamma ^ S & \ text {beweist} A ^ H \ end {align})
Eine bemerkenswerte Anwendung des Herbrandschen Theorems und verwandter Methoden findet sich in Luckhardts (1989) Analyse des Rothschen Theorems. Eine Diskussion nützlicher Erweiterungen von Herbrands Methoden finden Sie in Sieg 1991. Eine modelltheoretische Version davon wird in Avigad 2002a diskutiert.
5. Die Epsilon-Substitutionsmethode und die Arithmetik
Wie oben erwähnt, bestand das Hauptinteresse an der Epsilon-Berechnung in der Vergangenheit darin, Konsistenznachweise zu erhalten. In Hilberts Vorlesungen von 1917–1918 wird bereits festgestellt, dass man die Konsistenz der Aussagenlogik leicht beweisen kann, indem man Aussagenvariablen und Formeln so nimmt, dass sie über den Wahrheitswerten 0 und 1 liegen, und die logischen Verknüpfungen als die entsprechenden arithmetischen Operationen interpretiert. In ähnlicher Weise kann man die Konsistenz der Prädikatenlogik (oder des reinen Epsilon-Kalküls) beweisen, indem man sich auf Interpretationen spezialisiert, bei denen das Universum des Diskurses ein einziges Element hat. Diese Überlegungen legen das folgende allgemeinere Programm zum Nachweis der Konsistenz nahe:
Erweitern Sie den Epsilon-Kalkül so, dass er größere Teile der Mathematik darstellt.
Zeigen Sie mit endlichen Methoden, dass jeder Beweis im erweiterten System eine konsistente Interpretation hat.
Betrachten Sie beispielsweise die Sprache der Arithmetik mit Symbolen für (0), (1), (+), (times), (lt). Zusammen mit quantifiziererfreien Axiomen, die die Grundsymbole definieren, kann angegeben werden, dass die Epsilon-Terme (varepsilon x A (x)) den kleinsten Wert auswählen, der (A) erfüllt, falls es einen gibt, mit dem folgenden Axiom:) tag {*} A (x) rightarrow A (varepsilon x A (x)) wedge \ varepsilon x A (x) le x) Das Ergebnis ist ein System, das stark genug ist, um zuerst interpretiert zu werden -order (Peano) Arithmetik. Alternativ kann man das Epsilon-Symbol verwenden, um das folgende Axiom zu erfüllen: [A (y) rechter Pfeil A (varepsilon x A (x)) Keil \ varepsilon x A (x) ne y + 1.)
Mit anderen Worten, wenn es einen Zeugen (y) gibt, der (A (y)) erfüllt, gibt der epsilon-Term einen Wert zurück, dessen Vorgänger nicht dieselbe Eigenschaft hat. Der durch (*) beschriebene Epsilon-Term erfüllt eindeutig das alternative Axiom; Umgekehrt kann man überprüfen, ob bei gegebenem (A) ein Wert von (varepsilon x (existiert z \ le x A (x))), der das alternative Axiom erfüllt, zur Interpretation von (varepsilon x A verwendet werden kann) (x)) in (*). Man kann die Bedeutung des Epsilon-Ausdrucks weiter mit dem Axiom) varepsilon x A (x) ne 0 \ rightarrow A (varepsilon x A (x))) festlegen, das dies erfordert, wenn es keinen Zeugen für (gibt A), der Epsilon-Term gibt 0 zurück. Für die folgende Diskussion ist es jedoch am bequemsten, sich nur auf (*) zu konzentrieren.
Angenommen, wir möchten zeigen, dass das obige System konsistent ist. Mit anderen Worten, wir möchten zeigen, dass es keinen Beweis für die Formel (0 = 1) gibt. Indem alle Substitutionen in die Axiome verschoben und freie Variablen durch die Konstante 0 ersetzt werden, genügt es zu zeigen, dass es keinen aussagekräftigen Beweis für (0 = 1) aus einer endlichen Menge geschlossener Instanzen der Axiome gibt. Dafür genügt es zu zeigen, dass man bei einer endlichen Menge geschlossener Instanzen von Axiomen Begriffen numerische Werte zuweisen kann, so dass alle Axiome unter der Interpretation wahr sind. Da die arithmetischen Operationen (+) und (times) auf die übliche Weise interpretiert werden können, besteht die einzige Schwierigkeit darin, geeignete Werte zu finden, die den Epsilon-Termen zugewiesen werden können.
Hilberts Epsilon-Substitutionsmethode kann grob wie folgt beschrieben werden:
Beginnen Sie bei einer endlichen Menge von Axiomen damit, alle Epsilon-Terme als 0 zu interpretieren.
Suchen Sie eine Instanz des Axioms (*) darüber, die unter der Interpretation falsch ist. Dies kann nur passieren, wenn man einen Term t hat, so dass (A (t)) in der Interpretation wahr ist, aber entweder (A (varepsilon x A (x))) falsch ist oder der Wert von (t) ist kleiner als der Wert von (varepsilon x A (x)).
"Reparieren" Sie die Zuordnung, indem Sie (varepsilon x A (x)) den Wert von (t) zuweisen, und wiederholen Sie den Vorgang.
Ein endgültiger Konsistenznachweis wird erhalten, sobald in endlich akzeptabler Weise gezeigt wird, dass dieser Prozess aufeinanderfolgender „Reparaturen“endet. Wenn dies der Fall ist, sind alle kritischen Formeln echte Formeln ohne Epsilon-Terme.
Diese Grundidee (der „Hilbertsche Ansatz“) wurde zuerst von Hilbert in seinem Vortrag von 1922 (1923) dargelegt und 1922–23 in Vorlesungen ausgearbeitet. Die dort angegebenen Beispiele befassen sich jedoch nur mit Beweisen, bei denen alle Instanzen des transfiniten Axioms einem einzelnen Epsilon-Term (varepsilon x A (x)) entsprechen. Die Herausforderung bestand darin, den Ansatz auf mehr als einen Epsilon-Term, auf verschachtelte Epsilon-Terme und letztendlich auf Epsilons zweiter Ordnung auszudehnen (um einen Konsistenznachweis nicht nur für die Arithmetik, sondern auch für die Analyse zu erhalten).
Die Schwierigkeit beim Umgang mit verschachtelten Epsilon-Begriffen kann wie folgt beschrieben werden. Angenommen, eines der Axiome im Beweis ist das transfinite Axiom [B (y) rechter Pfeil B (varepsilon y B (y))) (varepsilon y B (y)), das natürlich in vorkommen kann andere Formeln im Beweis, insbesondere in anderen transfiniten Axiomen, z. B. [A (x, \ varepsilon y B (y)) rechter Pfeil A (varepsilon x A (x, \ varepsilon y B (y)), \ varepsilon y B (y))) Zunächst scheint es notwendig zu sein, eine korrekte Interpretation für (varepsilon y B (y)) zu finden, bevor wir versuchen, eine für (varepsilon x A (x, \ varepsilon) zu finden y B (y))). Es gibt jedoch kompliziertere Muster, in denen Epsilon-Terme in einem Beweis auftreten können. Eine Instanz des Axioms, die eine Rolle bei der Bestimmung der korrekten Interpretation für (varepsilon y B (y)) spielt, könnte [B (varepsilon x A (x,\ varepsilon y B (y))) rightarrow B (varepsilon y B (y))) Wenn (B) (0) falsch ist, dann in der ersten Runde des Verfahrens (varepsilon y B () y)) wird mit 0 interpretiert. Eine nachfolgende Änderung der Interpretation von (varepsilon x A (x, 0)) von 0 auf beispielsweise (n) führt zu einer Interpretation dieser Instanz als (B (n) rechter Pfeil B) (0), was falsch ist, wenn (B (n)) wahr ist. Die Interpretation von (varepsilon y B (y)) muss also auf (n) korrigiert werden, was wiederum zur Interpretation von (varepsilon x A (x, \ varepsilon y) führen kann B (y))) keine wahre Formel mehr sein.führt zu einer Interpretation dieser Instanz als (B (n) rightarrow B) (0), die falsch ist, wenn (B (n)) wahr ist. Die Interpretation von (varepsilon y B (y)) muss also auf (n) korrigiert werden, was wiederum zur Interpretation von (varepsilon x A (x, \ varepsilon y) führen kann B (y))) keine wahre Formel mehr sein.führt zu einer Interpretation dieser Instanz als (B (n) rightarrow B) (0), die falsch ist, wenn (B (n)) wahr ist. Die Interpretation von (varepsilon y B (y)) muss also auf (n) korrigiert werden, was wiederum zur Interpretation von (varepsilon x A (x, \ varepsilon y) führen kann B (y))) keine wahre Formel mehr sein.
Dies ist nur eine Skizze der Schwierigkeiten, Hilberts Idee auf den allgemeinen Fall auszudehnen. Ackermann (1924) lieferte eine solche Verallgemeinerung mit einem Verfahren, das immer dann „zurückverfolgt“, wenn eine neue Interpretation in einem bestimmten Stadium dazu führt, dass eine bereits in einem früheren Stadium gefundene Interpretation korrigiert werden muss.
Ackermanns Verfahren wurde auf ein System der Arithmetik zweiter Ordnung angewendet, bei dem jedoch Terme zweiter Ordnung eingeschränkt wurden, um eine Kreuzbindung von Epsilons zweiter Ordnung auszuschließen. Dies entspricht in etwa einer Beschränkung des arithmetischen Verständnisses als verfügbares Mengenbildungsprinzip (siehe Diskussion am Ende dieses Abschnitts). Weitere Schwierigkeiten mit Epsilon-Begriffen zweiter Ordnung traten auf, und es wurde schnell klar, dass der Beweis in seiner jetzigen Form trügerisch war. Bis 1930, als Gödel seine Unvollständigkeitsergebnisse bekannt gab, erkannte jedoch niemand in Hilberts Schule das Ausmaß der Schwierigkeit. Bis dahin glaubte man, dass der Beweis (zumindest mit einigen von Ackermann eingeführten Modifikationen,Einige davon beinhalteten Ideen aus von Neumanns (1927) Version der Epsilon-Substitutionsmethode), die zumindest für den Teil erster Ordnung durchgehen würden. Hilbert und Bernays (1939) schlagen vor, dass die verwendeten Methoden nur einen Konsistenznachweis für Arithmetik erster Ordnung mit offener Induktion liefern. 1936 gelang es Gerhard Gentzen, die Konsistenz der Arithmetik erster Ordnung in einer Formulierung zu beweisen, die auf Prädikatenlogik ohne das Epsilon-Symbol basiert. Dieser Beweis verwendet eine transfinite Induktion bis zu (varepsilon_0). Ackermann (1940) war später in der Lage, Gentzens Ideen anzupassen, um mithilfe der Epsilon-Substitutionsmethode einen korrekten Konsistenznachweis für Arithmetik erster Ordnung zu liefern. Gerhard Gentzen gelang es, die Konsistenz der Arithmetik erster Ordnung in einer Formulierung zu beweisen, die auf Prädikatenlogik ohne das Epsilon-Symbol basiert. Dieser Beweis verwendet eine transfinite Induktion bis zu (varepsilon_0). Ackermann (1940) war später in der Lage, Gentzens Ideen anzupassen, um mithilfe der Epsilon-Substitutionsmethode einen korrekten Konsistenznachweis für Arithmetik erster Ordnung zu liefern. Gerhard Gentzen gelang es, die Konsistenz der Arithmetik erster Ordnung in einer Formulierung zu beweisen, die auf Prädikatenlogik ohne das Epsilon-Symbol basiert. Dieser Beweis verwendet eine transfinite Induktion bis zu (varepsilon_0). Ackermann (1940) konnte später Gentzens Ideen anpassen, um mit der Epsilon-Substitutionsmethode einen korrekten Konsistenznachweis für Arithmetik erster Ordnung zu liefern.
Obwohl Ackermanns Versuche, einen Konsistenznachweis für die Arithmetik zweiter Ordnung zu erbringen, erfolglos waren, lieferten sie ein klareres Verständnis für die Verwendung von Epsilon-Begriffen zweiter Ordnung bei der Formalisierung der Mathematik. Ackermann verwendete Epsilon-Terme zweiter Ordnung (varepsilon f \ A (f)), wobei (f) eine Funktionsvariable ist. In Analogie zum Fall erster Ordnung ist (varepsilon f \ A (f)) eine Funktion, für die (A (f)) wahr ist, z. B. (varepsilon f (x + f (x)) = 2x)) ist die Identitätsfunktion (f (x) = x). Auch in Analogie zum Fall erster Ordnung kann man Epsilons zweiter Ordnung verwenden, um Quantifizierer zweiter Ordnung zu interpretieren. Insbesondere kann man für jede Formel zweiter Ordnung (A (x)) einen Term (t (x)) finden, so dass [A (x) linker rechter Pfeil t (x) = 1) ableitbar ist im Kalkül (die Formel (A) kann andere freie Variablen haben,in diesem Fall erscheinen diese auch im Begriff (t). Man kann diese Tatsache dann nutzen, um Verständnisprinzipien zu interpretieren. In einer Sprache mit Funktionssymbolen haben diese die Form) existiert f \ für alle x (A (x) linker rechter Pfeil f (x) = 1)) für eine beliebige Formel (A (x)). Das Verständnis wird häufiger in Form von Mengenvariablen ausgedrückt. In diesem Fall hat es die Form) existiert Y \ für alle x (A (x) linker rechter Pfeil x \ in Y)) und behauptet, dass jede Formel zweiter Ordnung Parameter enthält definiert eine Menge. In diesem Fall hat es die Form) existiert Y \ für alle x (A (x) leftrightarrow x \ in Y)) und behauptet, dass jede Formel zweiter Ordnung mit Parametern eine Menge definiert. In diesem Fall hat es die Form) existiert Y \ für alle x (A (x) leftrightarrow x \ in Y)) und behauptet, dass jede Formel zweiter Ordnung mit Parametern eine Menge definiert.
Analyse oder Arithmetik zweiter Ordnung ist die Erweiterung der Arithmetik erster Ordnung um das Verständnisschema für beliebige Formeln zweiter Ordnung. Die Theorie ist insofern beeindruckend, als sie es ermöglicht, Mengen natürlicher Zahlen unter Verwendung von Quantifizierern zu definieren, die sich über das gesamte Universum von Mengen erstrecken, einschließlich implizit der Menge, die definiert wird. Man kann prädikative Fragmente dieser Theorie erhalten, indem man die Art der Formeln einschränkt, die im Verständnisaxiom erlaubt sind. Beispielsweise entspricht die im Zusammenhang mit Ackermann oben diskutierte Einschränkung dem arithmetischen Verständnisschema, in dem Formeln keine Quantifizierer zweiter Ordnung enthalten. Es gibt verschiedene Möglichkeiten, stärkere Analysefragmente zu erhalten, die jedoch prädikativ gerechtfertigt sind. Zum Beispiel erhält man eine verzweigte Analyse, indem man einen Ordnungsrang dem Setzen von Variablen zuordnet;In der Definition eines Satzes eines gegebenen Ranges erstrecken sich Quantifizierer grob nur über Sätze mit niedrigerem Rang, dh über diejenigen, deren Definitionen logisch vorrangig sind.
Weiterführende Literatur. Hilberts und Ackermanns frühe Beweise werden in Zach 2003 diskutiert; 2004. Von Neumanns Beweis ist das Thema von Bellotti 2016. Ackermanns Beweis von 1940 wird in Hilbert & Bernays 1970 und Wang 1963 diskutiert. Eine moderne Präsentation wird von Moser 2006 gegeben. Eine frühe Anwendung der Epsilon-Substitution ist die Interpretation ohne Gegenbeispiel (Kreisel) 1951).
6. Neuere Entwicklungen
In diesem Abschnitt diskutieren wir die Entwicklung der Epsilon-Substitutionsmethode, um Konsistenzergebnisse für starke Systeme zu erhalten. Diese Ergebnisse sind mathematischer Natur. Wir können die Details der Beweise hier leider nicht diskutieren, möchten aber darauf hinweisen, dass die Epsilon-Substitutionsmethode mit Hilberts Programm nicht gestorben ist und dass ein erheblicher Teil der aktuellen Forschung in Epsilon-Formalismen durchgeführt wird.
Gentzens Konsistenzbeweise für die Arithmetik haben ein Forschungsfeld eröffnet, das als Ordnungsanalyse bekannt ist, und das Programm zur Messung der Stärke mathematischer Theorien unter Verwendung von Ordnungsnotationen wird bis heute fortgesetzt. Dies ist besonders relevant für das erweiterte Hilbert-Programm, bei dem das Ziel darin besteht, die klassische Mathematik in Bezug auf konstruktive oder quasi-konstruktive Systeme zu rechtfertigen. Gentzens Methoden zur Eliminierung von Schnitten (und Erweiterungen der von Paul Lorentzen, Petr Novikov und Kurt Schütte entwickelten unendlichen Logik) haben bei diesen Bestrebungen die Epsilon-Substitutionsmethoden weitgehend verdrängt. Epsilon-Kalkülmethoden bieten jedoch einen alternativen Ansatz, und es gibt immer noch aktive Forschungen darüber, wie Hilbert-Ackermann-Methoden auf stärkere Theorien ausgedehnt werden können. Das allgemeine Muster bleibt das gleiche:
Betten Sie die untersuchte Theorie in einen geeigneten Epsilon-Kalkül ein.
Beschreiben eines Prozesses zum Aktualisieren von Zuweisungen zu den epsilon-Begriffen.
Zeigen Sie, dass sich die Prozedur normalisiert, dh, wenn eine Reihe von Begriffen gegeben ist, gibt es eine Folge von Aktualisierungen, die zu einer Zuordnung führen, die die Axiome erfüllt.
Da der letzte Schritt die Konsistenz der ursprünglichen Theorie garantiert, interessiert man sich aus grundlegender Sicht für die Methoden zum Nachweis der Normalisierung. Zum Beispiel erhält man eine Ordnungsanalyse, indem man den Schritten in der Prozedur Ordnungsnotationen so zuweist, dass der Wert einer Notation mit jedem Schritt abnimmt.
In den 1960er Jahren erweiterte Tait (1960, 1965, 2010) Ackermanns Methoden, um eine ordinale Analyse von Erweiterungen der Arithmetik mit Prinzipien der transfiniten Induktion zu erhalten. Optimiertere und modernere Versionen dieses Ansatzes finden Sie in Mints 2001 und Avigad 2002b. In jüngerer Zeit haben Mints, Tupailo und Buchholz stärkere, aber dennoch prädikativ vertretbare Analysefragmente in Betracht gezogen, einschließlich Theorien des arithmetischen Verständnisses und einer (Delta ^ {1} _1) - Verständnisregel (Mints, Tupailo & Buchholz 1996); Mints & Tupailo 1999; siehe auch Mints 2016). Arai 2002 hat die Epsilon-Substitutionsmethode auf Theorien erweitert, die es ermöglichen, das arithmetische Verständnis entlang primitiver rekursiver Well-Ordnungen zu iterieren. Bestimmtes,Seine Arbeit liefert ordinale Analysen für prädikative Analysefragmente, die transfinite Hierarchien und transfinite Induktion beinhalten.
Bei der Analyse der Impredikativ-Theorien wurden einige erste Schritte zur Verwendung der Epsilon-Substitutionsmethode unternommen (siehe Arai 2003, 2006 und Mints 2015).
Eine Variation von Schritt 3 oben beinhaltet das Zeigen, dass das Normalisierungsverfahren nicht für die Auswahl von Aktualisierungen empfindlich ist, dh eine beliebige Folge von Aktualisierungen wird beendet. Dies nennt man starke Normalisierung. Mints 1996 hat gezeigt, dass viele der betrachteten Verfahren diese stärkere Eigenschaft haben.
Neben dem traditionellen, grundlegenden Zweig der Beweistheorie besteht heute ein großes Interesse an der strukturellen Beweistheorie, einem Zweig des Fachs, der sich auf logische deduktive Kalküle und ihre Eigenschaften konzentriert. Diese Forschung ist eng mit Informatikfragen verbunden, die mit automatisierter Ableitung, funktionaler Programmierung und computergestützter Verifizierung zu tun haben. Auch hier dominieren tendenziell Gentzen-Methoden (siehe auch den Eintrag zur Beweistheorie). Der Epsilon-Kalkül kann aber auch wertvolle Erkenntnisse liefern; vgl. zum Beispiel Aguilera & Baaz 2019 oder die Diskussion des obigen Satzes von Herbrand.
Neben den Untersuchungen des Epsilon-Kalküls in der Beweistheorie sind zwei Anwendungen zu nennen. Eine davon ist die Verwendung der Epsilon-Notation in Bourbakis Theorie des Ensembles (1958). Das zweite, derzeit vielleicht größere Interesse, ist die Verwendung des Epsilon-Operators in den Theoremprüfungssystemen HOL und Isabelle, bei denen die Ausdruckskraft von Epsilon-Begriffen erhebliche praktische Vorteile bietet.
7. Epsilon-Operatoren in Linguistik, Philosophie und nicht-klassischer Logik
Das Lesen des epsilon-Operators als Operator für unbestimmte Auswahl ("an (x), so dass (A (x))") legt nahe, dass er ein nützliches Werkzeug für die Analyse unbestimmter und bestimmter Nominalphrasen in der formalen Semantik sein könnte. Die Epsilon-Notation wurde tatsächlich so verwendet, und diese Anwendung hat sich insbesondere im Umgang mit anaphorischen Referenzen als nützlich erwiesen.
Betrachten Sie das bekannte Beispiel
Jeder Bauer, der einen Esel besitzt, schlägt ihn
Die allgemein akzeptierte Analyse dieses Satzes ergibt sich aus dem universellen Satz
Der Nachteil ist, dass „ein Esel“einen existenziellen Quantifizierer vorschlägt, und daher sollte die Analyse irgendwie parallel zur Analyse von Satz 3 sein, der durch 4 gegeben ist:
Jeder Bauer, der einen Esel besitzt, ist glücklich,
enthält ein freies Vorkommen von (y). Evans 1980 schlägt vor, dass Pronomen, die sich auf Ausdrücke beziehen, als eindeutige Beschreibungen analysiert werden sollten; und wenn das Pronomen in der Folge einer Bedingung auftritt, werden die beschreibenden Bedingungen durch den Vorgänger bestimmt. Dies führt zu der folgenden E-Typ-Analyse von (1):) begin {multline *} forall x ((mathrm {Farmer} (x) wedge \ existiert y (mathrm {Donkey} (y) Keil \ mathrm {Owns} (x, y)) rightarrow \(mathrm {Beats} (x, \ iota y (mathrm {Esel} (y) Wedge \ mathrm {Owns} (x, y))) end {multline *}) Hier ist (iota x) der definitive Beschreibungsoperator, also (iota y (mathrm {Esel} (y) wedge \ mathrm {Owns} (x, y)))) ist "der Esel von (x);". Das Problem dabei ist, dass bei der Standardanalyse die eindeutige Beschreibung eine Eindeutigkeitsbedingung enthält,und so wird (5) falsch sein, wenn es einen Bauern gibt, der mehr als einen Esel besitzt. Ein Ausweg besteht darin, einen neuen Operator einzuführen, der (wer auch immer) als verallgemeinernder Quantifizierer fungiert (Neale, 1990):) begin {multline *} forall x ((mathrm {Farmer} (x)))) wedge \ existiert y (mathrm {Donkey} (y) wedge \ mathrm {Owns} (x, y)) rightarrow \(mathrm {Beats} (x, \ mathrm {whe}, y () mathrm {Donkey} (y) wedge \ mathrm {Owns} (x, y)) end {multline *})
Wie von Heusinger (1994) ausgeführt, deutet dies darauf hin, dass Neale sich dazu verpflichtet fühlt, dass Pronomen zwischen bestimmten Beschreibungen ((iota) - Ausdrücken) und Whe-Ausdrücken mehrdeutig sind. Heusinger schlägt stattdessen vor, Epsilon-Operatoren zu verwenden, die durch Auswahlfunktionen indiziert sind (die vom Kontext abhängen). Nach diesem Ansatz ist die Analyse von (1)
Für jede Auswahlfunktion (i):) begin {multline *} forall x ((mathrm {Farmer} (x) wedge \ mathrm {Owns} (x, \ varepsilon_i y \ mathrm {Donkey} () y)) rightarrow \\\ mathrm {Beats} (x, \ varepsilon_ {a ^ *} y \ mathrm {Donkey} (y)) end {multline *})
Hier ist (a ^ *) eine Auswahlfunktion, die von (i) und dem Vorgänger der Bedingung abhängt: Wenn (i) eine Auswahlfunktion ist, die (varepsilon_i y \ mathrm {Donkey} (y)) aus der Menge aller Esel, dann wählt (varepsilon_ {a ^ *} y \ mathrm {Esel} (y)) aus der Menge der Esel aus, die (x) gehören.
Dieser Ansatz zum Umgang mit Pronomen unter Verwendung von Epsilon-Operatoren, die durch Auswahlfunktionen indiziert sind, ermöglicht es von Heusinger, mit einer Vielzahl von Umständen umzugehen (siehe Egli und von Heusinger, 1995; von Heusinger, 2000).
Anwendungen des epsilon-Operators in der formalen Semantik und Auswahlfunktionen im Allgemeinen haben in den letzten Jahren großes Interesse gefunden. Von Heusinger und Egli (2000a) listen unter anderem Folgendes auf: Darstellungen von Fragen (Reinhart, 1992), spezifische Unbestimmtheiten (Reinhart 1992; 1997; Winter 1997), E-Typ-Pronomen (Hintikka und Kulas 1985; Slater 1986; Chierchia) 1992, Egli und von Heusinger 1995) und bestimmte Nominalphrasen (von Heusinger 1997, 2004).
Zur Diskussion der Probleme und Anwendungen des Epsilon-Operators in der Linguistik und Sprachphilosophie siehe BH Slaters Artikel über Epsilon-Kalküle (zitiert im Abschnitt Andere Internetressourcen unten) sowie die Sammlungen von Heusinger und Egli 2000 sowie von Heusinger und Kempson 2004.
Eine andere Anwendung des Epsilon-Kalküls ist eine allgemeine Logik zum Überlegen beliebiger Objekte. Meyer Viol (1995a) liefert einen Vergleich des Epsilon-Kalküls mit Fines (1985) Theorie beliebiger Objekte. In der Tat ist der Zusammenhang nicht schwer zu erkennen. Angesichts der Äquivalenz (für alle x A (x) Äquiv) A ((varepsilon x (neg A))) ist der Begriff (varepsilon x (neg A)) ein beliebiges Objekt in dem Sinne, dass es ein Objekt ist, von dem (A) wahr ist, wenn (A) allgemein wahr ist.
Meyer Viol (1995a, 1995b) enthält weitere beweis- und modelltheoretische Untersuchungen des Epsilon-Kalküls; spezifisch intuitionistische Epsilonsteine. Hier gelten die Epsilon-Theoreme nicht mehr, dh die Einführung von Epsilon-Begriffen führt zu nicht konservativen Erweiterungen der intuitionistischen Logik. Weitere Untersuchungen von Epsilon-Operatoren in der intuitionistischen Logik finden sich in Shirai (1971), Bell (1993a, 1993b) und DeVidi (1995). Für Epsilon-Operatoren in vielwertigen Logiken siehe Mostowski (1963), für modale Epsilon-Berechnung, Fitting (1975).
Weiterführende Literatur. Das Folgende ist eine Liste einiger Veröffentlichungen auf dem Gebiet der Sprache und Linguistik, die für den Epsilon-Kalkül und seine Anwendungen relevant sind. Der Leser wird insbesondere auf die Sammlungen von Heusinger & Egli (Hrsg.) 2000 und von Heusinger & Kempson (Hrsg.) 2004 zur weiteren Diskussion und Bezugnahme verwiesen: Bell 1993a, 1993b; Chierchia 1992; DeVidi 1995; Egli & von Heusinger 1995; Fein 1985; Passend für 1975; von Heusinger 1994, 1997, 2000, 2004; von Heusinger & Egli (Hrsg.) 2000; von Heusinger & Kempson (Hrsg.) 2004; Hintikka & Kulas 1985; Kempson, Meyer Viol & Gabbay 2001; Meyer Viol 1995a, 1995b, Neale 1990; Mostowski 1963; Reinhart 1992, 1997; Slater 1986, 1988, 1994, 2000; und Winter 1997.
Literaturverzeichnis
Aguilera, JP, Baaz, M., 2019, "Unklare Schlussfolgerungen verkürzen die Beweise". Journal of Symbolic Logic 84: 102–122.
Ackermann, W., 1924, Begründung des tertium non datur mittels der Hilbertschen Theorie der Widerspruchsfreiheit, Mathematische Annalen, 93: 1–36.
–––, 1937–38, 'Mengentheoretische Begründung der Logik', Mathematische Annalen, 115: 1–22.
–––, 1940, 'Zur Widerspruchsfreiheit der Zahlentheorie', Mathematische Annalen, 117: 162–194.
Arai, T., 2002, 'Epsilon-Substitutionsmethode für Theorien von Sprunghierarchien', Archive for Mathematical Logic, 2: 123–153.
–––, 2003, 'Epsilon-Substitutionsmethode für ID (_ 1 (Pi ^ {0} _1 \ vee \ Sigma ^ {0} _1))', Annals of Pure and Applied Logic, 121: 163–208.
–––, 2006, 'Epsilon-Substitutionsmethode für (Pi ^ {0} _2) - FIX. Journal of Symbolic Logic 71: 1155–1188
Avigad, J., 2002a, "Gesättigte Modelle universeller Theorien", Annals of Pure and Applied Logic, 118: 219–234.
–––, 2002b, „Aktualisierungsverfahren und die 1-Konsistenz der Arithmetik“, Mathematical Logic Quarterly, 48: 3–13.
Baaz, M., Leitsch, A., Lolic, A., 2018, "Eine auf sequentiellen Berechnungen basierende Formulierung des erweiterten ersten Epsilon-Theorems", in: Artemov, S., Nerode, A. (Hrsg.), Logical Foundations Informatik, Berlin: Springer, 55–71.
Bell, JL, 1993a. 'Hilberts Epsilon-Operator und klassische Logik', Journal of Philosophical Logic, 22: 1–18.
Bourbaki, N., 1958, Theorie des Ensembles, Paris: Hermann.
Buss, S., 1995, 'On Herbrands Theorem', Logik und Computerkomplexität (Lecture Notes in Computer Science 960), Berlin: Springer, 195–209.
––– 1998, 'Einführung in die Beweistheorie', in: Buss (Hrsg.), The Handbook of Proof Theory, Amsterdam: Nordholland, 1–78.
Chierchia, G., 1992. "Anaphora und dynamische Logik". Linguistik und Philosophie, 15: 111–183.
Davis, M. und R. Fechter, 1991, "Eine freie variable Version des Prädikatenkalküls erster Ordnung", Journal of Logic and Computation, 1: 431–451.
DeVidi, D., 1995. 'Intuitionistic (varepsilon) - und (tau) - calculi', Mathematical Logic Quarterly 41: 523–546.
Egli, U., von Heusinger, K., 1995, "Der Epsilon-Operator und die E-Typ-Pronomen", in U. Egli et al. (Hrsg.), Lexikalisches Wissen in der Organisation der Sprache, Amsterdam: Benjamins, 121–141 (Current Issues in Linguistic Theory 114).
Evans, G., 1980, 'Pronomen', Linguistic Inquiry, 11: 337–362.
Ewald, WB (Hrsg.), 1996, Von Kant bis Hilbert. Ein Quellenbuch in den Grundlagen der Mathematik, Vol. 2, Oxford: Oxford University Press.
Ferrari, PL, 1987, 'Eine Notiz über einen Beweis von Hilberts zweitem (varepsilon) - Theorem', Journal of Symbolic Logic, 52: 214–215.
Fine, K., 1985. Argumentation mit willkürlichen Objekten, Oxford: Blackwell.
Fitting, M., 1975. 'Ein modaler Logik-Epsilon-Kalkül', Notre Dame Journal of Formal Logic, 16: 1–16.
Flannagan, TB, 1975, 'Über eine Erweiterung von Hilberts zweitem (varepsilon) - Theorem', Journal of Symbolic Logic, 40: 393–397.
Girard, J.-Y., 1982, "Herbrands Theorem und Beweistheorie", Proceedings of the Herbrand Symposium, Amsterdam: North-Holland, 29-38.
Herbrand, J., 1930, Recherches sur la thèorie de la dèmonstration, Dissertation, Universität Paris. Englische Übersetzung in Herbrand 1971, S. 44–202.
–––, 1971, Logical Writings, W. Goldfarb (Hrsg.), Cambridge, Mass.: Harvard University Press.
Hilbert, D., 1922, 'Neubegründung der Mathematik: Erste Mitteilung', Abhandlungen aus dem Seminar der Hamburgischen Universität, 1: 157–177, englische Übersetzung in Mancosu, 1998, 198–214 und Ewald, 1996, 1115–1134.
–––, 1923, 'Die logischen Grundlagen der Mathematik', Mathematische Annalen, 88: 151–165, englische Übersetzung in Ewald, 1996, 1134–1148.
Hilbert, D., Bernays, P., 1934, Grundlagen der Mathematik. 1, Berlin: Springer.
–––, 1939, Grundlagen der Mathematik, Bd. 2, Berlin: Springer.
–––, 1970, 'Grundlagen der Mathematik', Vol. 2, 2. Auflage, Berlin: Springer, Beilage V.
Hintikka, J., Kulas, J., 1985. Anaphora und bestimmte Beschreibungen: Zwei Anwendungen der spieltheoretischen Semantik, Dordrecht: Reidel.
Kempson, R., Meyer Viol, W. und Gabbay, D., 2001. Dynamische Syntax: Der Fluss des Sprachverständnisses, Oxford: Blackwell.
Kreisel, G, 1951, „Zur Interpretation nicht-finitistischer Beweise - Teil I“, Journal of Symbolic Logic, 16: 241–267.
Leisenring, AC, 1969, Mathematische Logik und Hilberts Epsilon-Symbol, London: Macdonald.
Luckhardt, H., 1989, "Herbrand-Analysen zweite Rechte des Satzes von Roth: Polynomiale Zahlenschranken", Journal of Symbolic Logic, 54: 234–263.
Maehara, S., 1955, 'Die Prädikatenrechnung mit (varepsilon) - Symbol', Journal der Mathematical Society of Japan, 7: 323–344.
–––, 1957, 'Gleichheitsaxiom auf Hilberts (varepsilon) - Symbol', Journal der Fakultät für Naturwissenschaften, Universität Tokio, Abschnitt 1, 7: 419–435.
Mancosu, P. (Hrsg.), 1998, From Brouwer to Hilbert. Die Debatte über die Grundlagen der Mathematik in den 1920er Jahren, Oxford: Oxford University Press.
Meyer Viol, WPM, 1995a, Instantial Logic. Eine Untersuchung zum Denken mit Instanzen, Ph. D. Diplomarbeit, Universität Utrecht. ILLC Dissertation Series 1995–11.
–––, 1995b. "Eine beweistheoretische Behandlung von Aufgaben", Bulletin der IGPL, 3: 223–243.
Mints, G., 1994, 'Gentzen-Systeme und Hilberts Epsilon-Substitutionsmethode. I ', Logik, Methodik und Wissenschaftstheorie, IX (Uppsala, 1991), Amsterdam: Nordholland, 91-122.
–––, 1996, „Starke Terminierung für die Epsilon-Substitutionsmethode“, Journal of Symbolic Logic, 61: 1193–1205.
–––, 2001, 'Die Epsilon-Substitutionsmethode und Kontinuität', in W. Sieg et al. (Hrsg.), Reflexionen über die Grundlagen der Mathematik: Essays zu Ehren von Solomon Feferman, Lecture Notes in Logic 15, Association for Symbolic Logic.
–––, 2008, 'Cut Elimination für eine einfache Formulierung des Epsilon-Kalküls', Annals of Pure and Applied Logic, 152 (1–3): 148–160.
–––, 2013. 'Epsilon-Substitution für Prädikatenlogik erster und zweiter Ordnung', Annals of Pure and Applied Logic, 164: 733–739.
–––, 2015. 'Nicht deterministische Epsilon-Substitutionsmethode für PA und ID (_ 1)', in: Kahle, R., Rathjen, M. (Hrsg.), Gentzen's Centenary: The Quest for Consistency. Berlin: Springer, S. 479–500.
Mints, G., Tupailo, S., 1999, "Epsilon-Substitutionsmethode für die verzweigte Sprache und (Delta ^ {1} _1) - Verständnisregel", in A. Cantini et al. (Hrsg.), Logik und Grundlagen der Mathematik (Florenz, 1995), Dordrecht: Kluwer, 107–130.
Mints, G., Tupailo, S., Buchholz, W., 1996, "Epsilon-Substitutionsmethode für die Elementaranalyse", Archive for Mathematical Logic, 35: 103–130.
Moser, G., 2006, 'Ackermanns Substitutionsmethode (remixt)', Annals of Pure and Applied Logic, 142 (1–3): 1–18.
Moser, G. und R. Zach, 2006, „Der Epsilon-Kalkül und die Herbrand-Komplexität“, Studia Logica, 82 (1): 133–155.
Mostowski, A., 1963. „Die Hilbert-Epsilon-Funktion in vielwertigen Logiken“, Acta Philosophica Fennica, 16: 169–188.
Neale, S., 1990, Descriptions, Cambridge, MA: MIT Press.
Reinhart, T., 1992. "Wh-in-situ: Ein offensichtliches Paradoxon". In: P. Dekker und M. Stokhof (Hrsg.). Proceedings of the Eighth Amsterdam Colloquium, 17.-20. Dezember 1991. ILLC. Universität Amsterdam, 483–491.
–––, 1997. 'Quantifiziererumfang: Wie die Arbeit zwischen QR- und Auswahlfunktionen aufgeteilt wird'. Linguistik und Philosophie, 20: 335–397.
Shirai, K., 1971, 'Intuitionistische Prädikatenrechnung mit (varepsilon) - Symbol', Annalen der Japan Association for Philosophy of Science 4: 49–67.
Sieg, W., 1991, "Herbrand-Analysen", Archive for Mathematical Logic, 30: 409–441.
Slater, BH, 1986, "E-Typ-Pronomen und (varepsilon) - Begriffe", Canadian Journal of Philosophy, 16: 27–38.
–––, 2010. 'Die Substitutionsmethode überarbeitet.' in: S. Feferman und W. Sieg (Hrsg.), Proofs, Categories and Computations: Essays zu Ehren der Grigori Mints, London: College Publications, S. 131–14.
von Heusinger, K., 1994, Review of Neale (1990). Linguistics 32: 378–385.
–––, 1997. 'Bestimmte Beschreibungen und Auswahlfunktionen'. In: S. Akama (Hrsg.). Logik, Sprache und Berechnung, Dordrecht: Kluwer, 61–91.
–––, 2000, 'The Reference of Indefinites', in von Heusinger und Egli, (2000), 265–284.
–––, 2004, „Auswahlfunktionen und die anaphorische Semantik bestimmter NPs“, Research in Language and Computation, 2: 309–329.
von Heusinger, K., Egli, U. (Hrsg.), 2000. Referenz und anaphorische Beziehungen, Dordrecht: Kluwer.
–––, 2000a. 'Einführung: Referenz und die Semantik der Anaphora', von Heusinger und Egli (2000), 1–13.
von Heusinger, K., Kempson, R. (Hrsg.), 2004. Auswahlfunktionen in der Semantik, Sonderausgabe der Sprach- und Rechenforschung 2 (3).
von Neumann, J., 1927, Zur Hilbertschen Beweistheorie, Mathematische Zeitschrift, 26: 1–46.
Wang, H., 1963, Ein Überblick über die mathematische Logik, Peking: Science Press.
Winter, Y., 1997. 'Auswahlfunktionen und die Skopalsemantik von Unbestimmten'. Linguistik und Philosophie, 20: 399–467.
Yasuhara, M., 1982, 'Cut Elimination in (varepsilon) - calculi', Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 28: 311–316.
Zach, R., 2003, 'Die Praxis des Finitismus. Epsilon-Kalkül und Konsistenzbeweise in Hilberts Programm ', Synthese, 137: 211–259.
–––, 2004. 'Hilberts „Verunglückter Beweis“, der erste Epsilon-Satz, und Konsistenzbeweise'. Geschichte und Philosophie der Logik, 25, 79–94.
–––, 2017. 'Semantik und Beweistheorie des Epsilon-Kalküls', in: Ghosh, S., Prasad, S. (Hrsg.), Logik und ihre Anwendungen. ICLA 2017, LNCS. Springer, Berlin, Heidelberg, S. 27–47.
Akademische Werkzeuge
Sep Mann Symbol
Wie man diesen Eintrag zitiert.
Sep Mann Symbol
Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
Inpho-Symbol
Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
Phil Papers Ikone
Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.
Andere Internetquellen
Epsilon Calculi von B. Hartley Slater (Internet Encyclopedia of Philosophy)
Bitte kontaktieren Sie die Autoren mit weiteren Vorschlägen.
