Intuitionistische Logik

2023 Autor: Noah Black | [email protected]. Zuletzt bearbeitet: 2023-05-24 11:17

Eintragsnavigation

• Eintragsinhalt
• Literaturverzeichnis
• Akademische Werkzeuge
• Freunde PDF Vorschau
• Autor und Zitierinfo
• Zurück nach oben

Intuitionistische Logik

Erstveröffentlichung Mi 1. September 1999; inhaltliche Überarbeitung Di 4. September 2018

Intuitionistische Logik umfasst die allgemeinen Prinzipien des logischen Denkens, die von Logikern aus der intuitionistischen Mathematik abstrahiert wurden, wie sie von LEJ Brouwer ab [1907] und [1908] entwickelt wurden. Da diese Prinzipien auch für die russische rekursive Mathematik und die konstruktive Analyse von E. Bishop und seinen Anhängern gelten, kann die intuitionistische Logik als logische Grundlage der konstruktiven Mathematik angesehen werden. Obwohl die intuitionistische Analyse im Widerspruch zur klassischen Analyse steht, ist die intuitionistische Heyting-Arithmetik ein Teilsystem der klassischen Peano-Arithmetik. Daraus folgt, dass die intuitionistische Aussagenlogik ein geeignetes Subsystem der klassischen Aussagenlogik ist und die reine intuitionistische Prädikatenlogik ein geeignetes Subsystem der reinen klassischen Prädikatenlogik ist.

Philosophisch unterscheidet sich der Intuitionismus vom Logikismus dadurch, dass er die Logik eher als Teil der Mathematik als als Grundlage der Mathematik behandelt. vom Finitismusdurch konstruktives Denken über unzählige Strukturen (z. B. monotone Balkeninduktion auf dem Baum potenziell unendlicher Sequenzen natürlicher Zahlen); und vom Platonismus, indem mathematische Objekte als mentale Konstrukte ohne unabhängige ideale Existenz betrachtet werden. Hilberts formalistisches Programm, die klassische Mathematik zu rechtfertigen, indem sie auf ein formales System reduziert wurde, dessen Konsistenz durch finitistische (daher konstruktive) Mittel hergestellt werden sollte, war der mächtigste zeitgenössische Rivale zu Brouwers sich entwickelndem Intuitionismus. In seinem Aufsatz Intuitionismus und Formalismus von 1912 sagte Brouwer zu Recht voraus, dass jeder Versuch, die Konsistenz einer vollständigen Induktion der natürlichen Zahlen zu beweisen, zu einem Teufelskreis führen würde.

Brouwer lehnte den Formalismus per se ab, räumte jedoch ein, dass die Formulierung allgemeiner logischer Prinzipien, die intuitionistisch korrekte Konstruktionen wie modus ponens ausdrücken, möglicherweise nützlich sei. Formale Systeme für intuitionistische Aussagen- und Prädikatenlogik und Arithmetik wurden von Heyting [1930], Gentzen [1935] und Kleene [1952] vollständig entwickelt. Gödel [1933] bewies die Gleichheit von intuitionistischen und klassischen Theorien. Beth [1956] und Kripke [1965] lieferten eine Semantik, in Bezug auf die die intuitionistische Logik korrekt und vollständig ist, obwohl die Vollständigkeitsbeweise für die intuitionistische Prädikatenlogik einige klassische Überlegungen erfordern.

• 1. Ablehnung von Tertium Non Datur

• 2. Intuitionistische Prädikatenlogik erster Ordnung

  • 2.1 Die formalen Systeme (mathbf {H - IPC}) und (mathbf {H - IQC})
  • 2.2 Alternative Formalismen und der Abzugssatz
• 3. Intuitionistische Zahlentheorie (Heyting-Arithmetik) (mathbf {HA})

• 4. Grundlegende Beweistheorie

  • 4.1 Klassik in intuitionistische Logik übersetzen
  • 4.2 Zulässige Regeln der intuitionistischen Logik und Arithmetik

• 5. Grundlegende Semantik

  • 5.1 Kripke-Semantik für intuitionistische Logik
  • 5.2 Realisierbarkeitssemantik für die Heyting-Arithmetik

• 6. Zusätzliche Themen und weiterführende Literatur

  • 6.1 Subintuitionistische und Zwischenlogik
  • 6.2 Fortgeschrittene Themen
  • 6.3 Empfohlene Lektüre
• Literaturverzeichnis
• Akademische Werkzeuge
• Andere Internetquellen
• Verwandte Einträge

1. Ablehnung von Tertium Non Datur

Intuitionistische Logik kann kurz und bündig als klassische Logik ohne das aristotelische Gesetz der ausgeschlossenen Mitte beschrieben werden:

) tag {LEM} A \ vee \ neg A)

oder das klassische Gesetz der doppelten Verneinungseliminierung:

) tag {DNE} neg \ neg A \ rightarrow A)

aber mit dem Gesetz des Widerspruchs:

[(A \ rightarrow B) rightarrow ((A \ rightarrow \ neg B) rightarrow \ neg A))

und ex falso sequitur quodlibet:

) neg A \ rightarrow (A \ rightarrow B).)

Brouwer [1908] beobachtete, dass LEM von endlichen Situationen abstrahiert und dann ohne Begründung auf Aussagen über unendliche Sammlungen ausgedehnt wurde. Zum Beispiel soll (x, y) über den natürlichen Zahlen (0, 1, 2, \ ldots) liegen und (B (y)) ((primepred (y) oldand) abkürzen Primzahl (y + 2))), wobei (Primzahl (y)) "(y) ist eine Primzahl" ausdrückt. Dann gilt (forall y (B (y) vee \ neg B (y))) sowohl intuitiv als auch klassisch, denn um festzustellen, ob eine natürliche Zahl eine Primzahl ist oder nicht, müssen wir nur prüfen, ob sie eine Primzahl ist oder nicht hat einen Teiler streng zwischen sich und 1.

Aber wenn (A (x)) (existiert y (y \ gt x \ alt und B (y))) abkürzt, dann um (für alle x (A (x) vee \ neg A (x))) Intuitionistisch würden wir eine effektive Methode (vgl. Die Church-Turing-These) benötigen, um zu bestimmen, ob es ein Paar von Zwillingsprimzahlen gibt, die größer als eine beliebige natürliche Zahl (x) sind, und bis jetzt Ein solches Verfahren ist nicht bekannt. Eine offensichtliche semi-effektive Methode besteht darin, die Primzahlpaare unter Verwendung einer Verfeinerung des Eratosthenes-Siebs aufzulisten (wobei die natürlichen Zahlen einzeln erzeugt werden und jede Zahl (y) gestrichen wird, die (B (y) nicht erfüllt).), und wenn es ein Paar von Zwillingsprimzahlen gibt, die größer als (x) sind, wird diese Methode schließlich die erste finden. (Forall x A (x)) drückt jedoch die Twin Primes-Vermutung aus, die noch nicht bewiesen oder widerlegt wurde.so können wir nach unserem derzeitigen Kenntnisstand weder (für alle x (A (x) vee \ neg A (x))) noch (für alle x A (x) vee \ neg \ für alle x behaupten Axt)).

Man kann einwenden, dass diese Beispiele von der Tatsache abhängen, dass die Twin Primes-Vermutung noch nicht geklärt ist. Eine Reihe von Brouwers ursprünglichen „Gegenbeispielen“hing von Problemen ab (wie Fermats letzter Satz), die seitdem gelöst wurden. Für Brouwer war das allgemeine LEM jedoch gleichbedeutend mit der Annahme von vornherein, dass jedes mathematische Problem eine Lösung hat - eine Annahme, die er ablehnte und die Gödels Unvollständigkeitssatz um ein Vierteljahrhundert vorwegnahm.

Die Ablehnung von LEM hat weitreichende Konsequenzen. Einerseits,

• Intuitivistisch beweist reductio ad absurdum nur negative Aussagen, da (neg \ neg A \ rightarrow A) im Allgemeinen nicht gilt. (Wenn dies der Fall wäre, würde LEM durch Modus Ponens aus dem intuitionistisch nachweisbaren (neg \ neg (A \ vee \ neg A)) folgen.)
• Intuitionistische Aussagenlogik hat keine endliche Interpretation der Wahrheitstabelle. Es gibt unendlich viele verschiedene axiomatische Systeme zwischen intuitionistischer und klassischer Logik.
• Nicht jede Satzformel hat eine intuitionistisch äquivalente disjunktive oder konjunktive Normalform, die aus Primformeln und ihren Negationen nur unter Verwendung von (vee) und (oldand) aufgebaut ist.
• Nicht jede Prädikatformel hat eine intuitionistisch äquivalente Prenex-Normalform, wobei alle Quantifizierer vorne stehen.
• Während (forall x \ neg \ neg (A (x) vee \ neg A (x))) ein Theorem der intuitionistischen Prädikatenlogik ist, ist (neg \ neg \ forall x (A (x) vee) neg A (x))) ist nicht; (neg \ forall x (A (x) vee \ neg A (x))) stimmt also mit der intuitionistischen Prädikatenlogik überein.

Andererseits,

• Jeder intuitionistische Beweis einer geschlossenen Aussage der Form (A \ vee B) kann effektiv in einen intuitionistischen Beweis von (A) oder einen intuitionistischen Beweis von (B) und ähnlich für geschlossene existenzielle Aussagen umgewandelt werden.
• Intuitionistische Aussagenlogik ist in dem Sinne effektiv entscheidbar, dass ein endlicher konstruktiver Prozess für jede Satzformel einheitlich gilt und entweder einen intuitionistischen Beweis der Formel liefert oder zeigt, dass kein solcher Beweis existieren kann.
• Das negative Fragment der intuitionistischen Logik (ohne (vee) oder (existiert)) enthält eine getreue Übersetzung der klassischen Logik, ähnlich wie für die intuitionistische und klassische Arithmetik.
• Intuitionistische Arithmetik kann konsequent durch Axiome erweitert werden, die der klassischen Arithmetik widersprechen und das formale Studium der rekursiven Mathematik ermöglichen.
• Brouwers kontroverse intuitionistische Analyse, die mit LEM in Konflikt steht, kann formalisiert und in Bezug auf eine klassisch und intuitionistisch korrekte Subtheorie konsistent gezeigt werden.

2. Intuitionistische Prädikatenlogik erster Ordnung

Die formalisierte intuitionistische Logik wird natürlich durch die informelle Brouwer-Heyting-Kolmogorov-Erklärung der intuitionistischen Wahrheit motiviert, die in den Einträgen zum Intuitionismus in der Philosophie der Mathematik und zur Entwicklung der intuitionistischen Logik beschrieben wird. Die konstruktive Unabhängigkeit der logischen Operationen (oldand, \ vee, \ rightarrow, \ neg, \ forall, \ existiert) steht im Gegensatz zur klassischen Situation, in der z. B. (A \ vee B) gleichbedeutend mit (neg (neg A \ oldand \ neg B)) und (existiert xA (x)) entspricht (neg \ forall x \ neg A (x)). Aus Sicht der BHK behauptet ein Satz der Form (A \ vee B), dass entweder ein Beweis von (A) oder ein Beweis von (B) konstruiert wurde;während (neg (neg A \ oldand \ neg B)) behauptet, dass ein Algorithmus konstruiert wurde, der effektiv jedes Konstruktionspaar konvertieren würde, das (neg A) bzw. (neg B) beweist, in einen Beweis eines bekannten Widerspruchs.

2.1 Die formalen Systeme (mathbf {H - IPC}) und (mathbf {H - IQC})

Es folgt ein Hilbert-Formalismus (mathbf {H-IQC}) von Kleene [1952] (vgl. Troelstra und van Dalen [1988]) für die intuitionistische Prädikatenlogik erster Ordnung. Die Sprache (L) von (mathbf {H - IQC}) hat Prädikatbuchstaben (P, Q (.), \ Ldots) aller Aritäten und einzelnen Variablen (x, y, z,) ldots) (mit oder ohne Indizes (1, 2, \ ldots)) sowie Symbole (oldand, \ vee, \ rightarrow, \ neg, \ forall, \ existiert) für die logischen Verknüpfungen und Quantifizierer und Klammern (,). Die Atomformeln (oder Primformeln) von (L) sind Ausdrücke wie (P, Q (x), R (x, y, x)), wobei (P, Q ({.}), R () {.} {.} {.})) sind (0) - ary, (1) - ary und (3) - ary Prädikatbuchstaben; Das heißt, das Ergebnis des Füllens jeder Lücke in einem Prädikatbuchstaben durch ein einzelnes Variablensymbol ist eine Primformel. Die (wohlgeformten) Formeln von (L) werden induktiv wie folgt definiert.

• Jede Atomformel ist eine Formel.
• Wenn (A) und (B) Formeln sind, sind dies auch ((A \ oldand B), (A \ vee B), (A \ rightarrow B)) und (neg A).
• Wenn (A) eine Formel und (x) eine Variable ist, dann sind (für alle xA) und (existiert xA) Formeln.

Im Allgemeinen verwenden wir (A, B, C) als Metavariablen für wohlgeformte Formeln und (x, y, z) als Metavariablen für einzelne Variablen. Bei der Antizipation von Anwendungen (zum Beispiel für intuitionistische Arithmetik) verwenden wir (s, t) als Metavariablen für Begriffe. Bei der reinen Prädikatenlogik sind Terme einfach einzelne Variablen. Das Auftreten einer Variablen (x) in einer Formel (A) ist gebunden, wenn sie im Bereich eines Quantifizierers (forall x) oder (existiert x) liegt, andernfalls frei. Intuitionistisch wie klassisch wird ((A \ leftrowarrow B)) (((A \ rightarrow B) oldand (B \ rightarrow A))) abgekürzt, und Klammern werden weggelassen, wenn dies keine Verwirrung verursacht.

Es gibt drei Inferenzregeln:

Modus Ponens

Aus (A) und (A \ rightarrow B) schließen Sie (B).

(forall) - Einführung

Aus (C \ rightarrow A (x)), wobei (x) eine Variable ist, die in (C) nicht frei vorkommt, schließen Sie (C \ rightarrow \ forall) x A (x)).

(existiert) - Eliminierung

Aus (A (x) rechter Pfeil C), wobei (x) eine Variable ist, die in (C) nicht frei vorkommt, schließen Sie (existiert x A () x) rechter Pfeil C).

Die Axiome sind alle Formeln der folgenden Formen, wobei in den letzten beiden Schemata die Unterformel (A (t)) das Ergebnis des Ersetzens eines Auftretens des Ausdrucks (t) für jedes freie Auftreten von (x \ ist)) in (A (x)), und keine in (t) freie Variable wird durch die Substitution in (A (t)) gebunden.

) begin {array} {l} A \ rightarrow (B \ rightarrow A) (A \ rightarrow B) rightarrow ((A \ rightarrow (B \ rightarrow C)) rightarrow (A \ rightarrow C)) \ A \ rightarrow (B \ rightarrow (A \ oldand B)) (A \ oldand B) rightarrow A \(A \ oldand B) rightarrow B \\ A \ rightarrow (A \ vee B) \ B \ rechter Pfeil (A \ vee B) (A \ rechter Pfeil C) rechter Pfeil ((B \ rechter Pfeil C) rechter Pfeil ((A \ vee B) rechter Pfeil C)) (A \ rechter Pfeil B) rechter Pfeil ((A \ rechter Pfeil \ neg B) rechter Pfeil \ neg A) \ \ neg A \ rechter Pfeil (A \ rechter Pfeil B) \ \ für alle xA (x) rechter Pfeil A (t) \ A (t) rechter Pfeil \ existiert xA (x) end {array})

Ein Beweis ist eine endliche Folge von Formeln, von denen jede ein Axiom oder eine unmittelbare Folge einer (zwei oder zwei) vorhergehenden Formeln der Folge ist. Jeder Beweis soll seine letzte Formel beweisen, die als Satz oder beweisbare Formel der intuitionistischen Prädikatenlogik erster Ordnung bezeichnet wird. Eine Ableitung einer Formel (E) aus einer Sammlung (F) von Annahmen ist eine beliebige Folge von Formeln, von denen jede nach einer Inferenzregel zu (F) gehört oder ein Axiom oder eine unmittelbare Konsequenz ist der vorhergehenden Formeln der Sequenz, so dass (E) die letzte Formel der Sequenz ist. Wenn eine solche Ableitung existiert, sagen wir, dass (E) von (F) ableitbar ist.

Intuitionistische Aussagenlogik (mathbf {H - IPC}) ist das Subsystem von (mathbf {H - IQC}), das sich ergibt, wenn die Sprache auf Formeln beschränkt ist, die aus Satzbuchstaben (P, Q, R, \ ldots) unter Verwendung der Satzverbindungen (oldand, \ vee, \ rightarrow) und (neg), und nur die Satzpostulate werden verwendet. Somit fehlen die letzten beiden Inferenzregeln und die letzten beiden Axiomschemata im Satzteilsystem.

Wenn in der gegebenen Liste von Axiomschemata für intuitionistische Aussagenlogik oder Prädikatenlogik erster Ordnung das Gesetz ex falso sequitur quodlibet ausdrückt:

) neg A \ rightarrow (A \ rightarrow B))

wird durch das klassische Gesetz der Eliminierung der doppelten Negation DNE ersetzt:

) neg \ neg A \ rightarrow A)

(oder gleichwertig, wenn das intuitionistische Gesetz der Negationseinführung:

[(A \ rightarrow B) rightarrow ((A \ rightarrow \ neg B) rightarrow \ neg A))

wird durch LEM) ersetzt, ein formales System (mathbf {H-CPC}) für die klassische Aussagenlogik oder (mathbf {H-CQC}) für die Ergebnisse der klassischen Prädikatenlogik. Da Ex-Falso und das Gesetz des Widerspruchs klassische Theoreme sind, ist die intuitionistische Logik in der klassischen Logik enthalten. In gewissem Sinne ist die klassische Logik auch in der intuitionistischen Logik enthalten; siehe Abschnitt 4.1 unten.

Es ist wichtig zu beachten, dass LEM und DNE zwar als Schemata über (mathbf {H - IPC}) äquivalent sind, die Implikation jedoch

[(neg \ neg A \ rightarrow A) rightarrow (A \ vee \ neg A))

ist kein Theoremschema von (mathbf {H - IPC}). Wenn für Theorien (mathbf {T}), die auf intuitionistischer Logik basieren, (E) eine beliebige Formel von (L (mathbf {T})) ist, dann per Definition:

(E) ist in (mathbf {T}) genau dann entscheidbar, wenn (mathbf {T}) (E \ vee \ neg E) beweist.

(E) ist in (mathbf {T}) genau dann stabil, wenn (mathbf {T}) (neg \ neg E \ rightarrow E) beweist.

(E) kann in (mathbf {T}) genau dann getestet werden, wenn (mathbf {T}) (neg E \ vee \ neg \ neg E) beweist.

Entscheidbarkeit impliziert Stabilität, aber nicht umgekehrt. Die Verbindung von Stabilität und Testbarkeit entspricht der Entscheidbarkeit. Brouwer selbst hat bewiesen, dass „Absurdität der Absurdität der Absurdität gleichbedeutend mit Absurdität ist“(Brouwer [1923C]), so dass jede Formel der Form (neg A) stabil ist; In den Primformeln (mathbf {H - IPC}) und (mathbf {H - IQC}) sind ihre Negationen jedoch nicht entscheidbar, wie in Abschnitt 5.1 unten gezeigt.

2.2 Alternative Formalismen und der Abzugssatz

Das Hilbert-System (mathbf {H - IQC}) ist nützlich für metamathematische Untersuchungen der intuitionistischen Logik, aber seine erzwungene Linearisierung von Ableitungen und seine Bevorzugung von Axiomen gegenüber Regeln machen es zu einem umständlichen Instrument zur Ermittlung der Ableitbarkeit. Ein natürliches Deduktionssystem (mathbf {N - IQC}) für intuitionistische Prädikatenlogik ergibt sich aus dem deduktiven System (mathbf {D}), das in Abschnitt 3 des Eintrags zur klassischen Logik in dieser Enzyklopädie vorgestellt wird, indem es weggelassen wird das Symbol und die Regeln für die Identität und das Ersetzen der klassischen Regel (DNE) der Eliminierung der doppelten Negation durch die intuitionistische Eliminierungsregel der Negation, die ex falso ausdrückt:

(INE) Wenn (F) (A) und (F) (neg A) beinhaltet, dann beinhaltet (F) (B)

Die Schlüssel zum Nachweis, dass (mathbf {H - IQC}) gleichbedeutend mit (mathbf {N - IQC}) ist, sind modus ponens und umgekehrt:

Abzugssatz

Wenn (B) von (A) und möglicherweise anderen Formeln (F) ableitbar ist, werden alle in (A) freien Variablen in der Ableitung konstant gehalten (dh ohne Verwendung der zweiten oder dritte Inferenzregel für jede Variable (x), die in (A) frei vorkommt, es sei denn, die Annahme (A) tritt bei der Ableitung vor der fraglichen Inferenz nicht auf), dann (A \ rightarrow B) ist ableitbar von (F).

Dieses grundlegende Ergebnis, das grob die Regel ((rightarrow I)) von (mathbf {I}) ausdrückt, kann für (mathbf {H - IQC}) durch Induktion der Definition von a bewiesen werden Ableitung. Die anderen Regeln von (mathbf {I}) gelten für (mathbf {H - IQC}) im Wesentlichen nach Modus ponens, was ((rightarrow E)) in (mathbf {N) entspricht –IQC}); und alle Axiome von (mathbf {H - IQC}) sind in (mathbf {N - IQC}) beweisbar.

Um die Nützlichkeit des Deduktionssatzes zu veranschaulichen, betrachten Sie das (scheinbar triviale) Theoremschema ((A \ rightarrow A)). Ein korrekter Beweis in (mathbf {H - IPC}) besteht aus fünf Zeilen:

• 1. (A \ rightarrow (A \ rightarrow A))
• 2. ((A \ rechtspfeil (A \ rechtspfeil A)) rechtspfeil ((A \ rechtspfeil ((A \ rechtspfeil A) rechtspfeil A)) rechtspfeil (A \ rechtspfeil A)))
• 3. ((A \ rightarrow ((A \ rightarrow A) rightarrow A)) rightarrow (A \ rightarrow A))
• 4. (A \ rightarrow ((A \ rightarrow A) rightarrow A))
• 5. (A \ rightarrow A)

wobei 1, 2 und 4 Axiome sind und 3, 5 aus früheren Zeilen von modus ponens stammen. (A) ist jedoch in einem offensichtlichen Schritt von (A) (als Annahme) ableitbar, so dass der Abzugssatz den Schluss zulässt, dass ein Beweis für (A \ rightarrow A) existiert. (Tatsächlich ist der soeben vorgelegte formale Beweis von (A \ rightarrow A) Teil des konstruktiven Beweises des Abzugssatzes!)

Es ist wichtig zu beachten, dass bei der Definition einer Ableitung von Annahmen in (mathbf {H - IQC}) die Annahmeformeln so behandelt werden, als ob alle ihre freien Variablen universell quantifiziert würden, so dass (forall x A (x)) ist aus der Hypothese (A (x)) ableitbar. Die Variable (x) wird jedoch in dieser Ableitung unter Verwendung der Regel von (forall) - Einführung variiert (nicht konstant gehalten); und so kann der Abzugssatz nicht verwendet werden, um (fälschlicherweise) zu schließen, dass (A (x) rechter Pfeil \ für alle x A (x)) (und daher durch (existiert) - Eliminierung (existiert x) A (x) rightarrow \ forall x A (x))) sind in (mathbf {H - IQC}) nachweisbar. Betrachten Sie als Beispiel für eine korrekte Verwendung des Abzugssatzes für die Prädikatenlogik die Implikation (existiert x A (x) rechtspfeil \ neg \ für alle x \ neg A (x)). Um dies zu zeigen, ist dies in (mathbf {H - IQC}) nachweisbar. Wir leiten zuerst (neg \ forall x \ neg A (x)) von (A (x)) ab, wobei alle freien Variablen konstant gehalten werden:

• 1. (forall x \ neg A (x) rightarrow \ neg A (x))
• 2. (A (x) rechter Pfeil (für alle x \ neg A (x) rechter Pfeil A (x)))
• 3. (A (x)) (Annahme)
• 4. (forall x \ neg A (x) rightarrow A (x))
• 5. ((forall x \ neg A (x) rightarrow A (x)) rightarrow ((forall x \ neg A (x) rightarrow \ neg A (x)) rightarrow \ neg \ forall x \ neg A (x)))
• 6. ((für alle x \ neg A (x) rechter Pfeil \ neg A (x)) rechter Pfeil \ neg \ für alle x \ neg A (x))
• 7. (neg \ forall x \ neg A (x))

Hier sind 1, 2 und 5 Axiome; 4 kommt von 2 und 3 durch modus ponens; und 6 und 7 stammen aus früheren Zeilen von modus ponens; Es wurden also keine Variablen variiert. Der Abzugssatz sagt uns, dass es in (mathbf {H - IQC}) einen Beweis (P) für (A (x) rightarrow \ neg \ forall) x (neg A (x) gibt.), und eine Anwendung von (existiert) - Eliminierung wandelt (P) in einen Beweis von (existiert x A (x) rightarrow \ neg \ für alle x \ neg A (x)) um. Die Umkehrung ist in (mathbf {H - IQC}) nicht beweisbar, wie in Abschnitt 5.1 unten gezeigt.

Andere wichtige Alternativen zu (mathbf {H - IQC}) und (mathbf {N - IQC}) sind die verschiedenen sequentiellen Kalküle für intuitionistische Aussagen- und Prädikatenlogik. Der erste derartige Kalkül wurde von Gentzen [1934–5] definiert, vgl. Kleene [1952]. Sequentielle Systeme, die genau die gleichen Formeln wie (mathbf {H - IQC}) und (mathbf {N - IQC}) beweisen, verfolgen bei jedem Schritt eines Beweises explizit alle Annahmen und Schlussfolgerungen und ersetzen sie modus ponens (der eine Zwischenformel eliminiert) durch eine Schnittregel (die als zulässige Regel (vgl. Abschnitt 4.2) für das verbleibende Teilsystem gezeigt werden kann, wenn es weggelassen wird).

Wenn die Details des Formalismus nicht wichtig sind, folgen wir von nun an Troelstra und van Dalen [1988], indem wir "(mathbf {IQC})" oder "(mathbf {IPC})" auf irgendwelche verweisen lassen formales System für intuitionistische Prädikat- bzw. Aussagenlogik und ähnlich "(mathbf {CQC})" und "(mathbf {CPC})" für klassische Prädikaten- und Aussagenlogik.

Sowohl (mathbf {IPC}) als auch (mathbf {IQC}) erfüllen Interpolationssätze, z. B.: Wenn (A) und (B) Satzformeln sind, die mindestens einen Satzbuchstaben gemeinsam haben, und wenn (A \ rightarrow B) in (mathbf {IPC}) beweisbar ist, dann gibt es eine Formel (C), die nur Satzbuchstaben enthält, die sowohl in (A) als auch in (B), so dass sowohl (A \ rightarrow C) als auch (C \ rightarrow B) nachweisbar sind. Diese Themen werden in Kleene [1952] und Troelstra und Schwichtenberg [2000] behandelt.

Während Identität natürlich zur intuitionistischen Logik hinzugefügt werden kann, wird das Gleichheitssymbol für Anwendungen (z. B. zur Arithmetik) im Allgemeinen als eine ausgezeichnete Prädikatkonstante behandelt, die die Axiome für eine Äquivalenzbeziehung (Reflexivität, Symmetrie und Transitivität) und zusätzliche nichtlogische Axiome (z, die primitiven rekursiven Definitionen von Addition und Multiplikation). Identität ist sowohl intuitiv als auch klassisch entscheidbar, aber intuitionistische Erweiterungsgleichheit ist nicht immer entscheidbar; siehe die Diskussion der Kontinuitätsaxiome von Brouwer in Abschnitt 3 des Eintrags über Intuitionismus in der Philosophie der Mathematik.

3. Intuitionistische Zahlentheorie (Heyting-Arithmetik) (mathbf {HA})

Intuitionistische (Heyting) Arithmetik (mathbf {HA}) und klassische (Peano) Arithmetik (mathbf {PA}) haben dieselbe Sprache erster Ordnung und dieselben nicht logischen Axiome. nur die Logik ist anders. Zusätzlich zu den logischen Verknüpfungen, Quantifizierern und Klammern und den einzelnen Variablen (x, y, z, \ ldots) (auch als Metavariablen verwendet) hat die Sprache (L (mathbf {HA})) der Arithmetik ein binäres Prädikatsymbol (=), eine individuelle Konstante (0), eine unäre Funktionskonstante (S) und endlich oder zählbar unendlich viele zusätzliche Konstanten für primitive rekursive Funktionen einschließlich Addition und Multiplikation; Die genaue Wahl ist eine Frage des Geschmacks und der Bequemlichkeit. Terme werden aus Variablen und (0) unter Verwendung der Funktionskonstanten erstellt. bestimmtes,Jede natürliche Zahl (n) wird in der Sprache durch die Zahl (mathbf {n}) ausgedrückt, die durch Anwenden von (S) (n) mal auf (0) erhalten wird (z. B. () S (S (0))) ist die Ziffer für (2)). Hauptformeln haben die Form ((s = t)), wobei (s, t) Begriffe sind, und daraus werden wie üblich zusammengesetzte Formeln erhalten.

Die logischen Axiome und Regeln von (mathbf {HA}) sind diejenigen der intuitionistischen Prädikatenlogik erster Ordnung (mathbf {IQC}). Die nichtlogischen Axiome umfassen die reflexiven, symmetrischen und transitiven Eigenschaften von (=):) für alle x (x = x),)) für alle x \ für alle y (x = y \ rechter Pfeil y = x),)) forall x \ forall y \ forall z ((x = y \ oldand y = z) rightarrow x = z);) das Axiom, das (0) als die am wenigsten natürliche Zahl charakterisiert:

) für alle x \ neg (S (x) = 0),)

das Axiom, das (S) als Eins-zu-Eins-Funktion charakterisiert:

) für alle x \ für alle y (S (x) = S (y) rechter Pfeil x = y),)

das Axiom der Erweiterungsgleichheit für (S):

) für alle x \ für alle y (x = y \ rechter Pfeil S (x) = S (y));)

die primitiven rekursiven Definitionsgleichungen für jede Funktionskonstante, insbesondere für die Addition:) für alle x (x + 0 = x),)) für alle x \ für alle y (x + S (y) = S (x +) y));) und Multiplikation:) für alle x (x \ cdot 0 = 0),)) für alle x \ für alle y (x \ cdot S (y) = (x \ cdot y) + x);) und das (universelle Schließen des) Schemas der mathematischen Induktion für beliebige Formeln (A (x)):

[(A (0) oldand \ forall x (A (x) rightarrow A (S (x)))) rightarrow \ forall x A (x).)

Erweiterungsgleichheitsaxiome für alle Funktionskonstanten können durch mathematische Induktion aus dem Gleichheitsaxiom für (S) und den primitiven rekursiven Funktionsaxiomen abgeleitet werden.

Die natürliche Ordnungsbeziehung (x \ lt y) kann in (mathbf {HA}) durch (existiert z (S (z) + x = y)) oder durch den quantifiziererfreien definiert werden Formel (S (x) Punkt {-} y = 0), wenn das Symbol und die primitiven rekursiven Definitionsgleichungen für den Vorgänger: [Pd (0) = 0,)) für alle x (Pd (S (x))) = x)) und Cutoff-Subtraktion:) forall x (x \ dot {-} 0 = 0),)) forall x (x \ dot {-} S (y) = Pd (x \ dot {-} y))) sind im Formalismus vorhanden. (mathbf {HA}) beweist das Vergleichsgesetz

) forall x \ forall y (x \ lt y \ vee x = y \ vee y \ lt x))

und eine intuitionistische Form des Prinzips der kleinsten Zahl für beliebige Formeln (A (x)):

) forall x) forall y (y \ lt x \ rightarrow (A (y) vee \ neg A (y))) rightarrow \(existiert y ((y \ lt x \ oldand A (y))))) oldand \ forall z (z \ lt y \ rightarrow \ neg A (z))) vee \\ \ forall y (y \ lt x \ rightarrow \ neg A (y)))].)

Die Hypothese wird benötigt, da nicht alle arithmetischen Formeln in (mathbf {HA}) entscheidbar sind. (Forall x \ forall y (x = y \ vee \ neg (x = y))) kann jedoch direkt durch mathematische Induktion bewiesen werden, und so weiter

Primformeln (und damit alle quantifiziererfreien Formeln) sind in (mathbf {HA}) entscheidbar und stabil.

Wenn (A (x)) in (mathbf {HA}) entscheidbar ist, dann sind durch Induktion auf (x) (forall y (y \ lt x \ rightarrow A (y))) und (existiert y (y \ lt x \ oldand A (y))). Daher

Formeln, in denen alle Quantifizierer begrenzt sind, sind in (mathbf {HA}) entscheidbar und stabil.

Die Sammlung (Delta_0) von arithmetischen Formeln, in denen alle Quantifizierer begrenzt sind, ist die niedrigste Ebene einer klassischen arithmetischen Hierarchie, die auf dem Muster der Wechsel von Quantifizierern in einer Prenex-Formel basiert. In (mathbf {HA}) hat nicht jede Formel eine Prenexform, aber Burr [2004] entdeckte eine einfache intuitionistische arithmetische Hierarchie, die Stufe für Stufe der klassischen entspricht. Nur für die Zwecke der nächsten beiden Definitionen bezeichnet (für alle x) einen Block von endlich vielen universellen Zahlenquantifizierern, und in ähnlicher Weise bezeichnet (existiert x) einen Block von endlich vielen existentiellen Zahlenquantifizierern. Mit diesen Konventionen werden Burrs Klassen (Phi_n) und (Psi_n) definiert durch:

• (Phi_0 = \ Psi_0 = \ Delta_0),
• (Phi_1) ist die Klasse aller Formeln der Form (für alle x A (x)), wobei (A (x)) in (Psi_0) steht. Für (n \ ge 2) ist (Phi_n) die Klasse aller Formeln der Form (forall x [A (x) rightarrow \ existiert y B (x, y)]) wobei (A (x)) ist in (Phi_ {n-1}) und (B (x, y)) ist in (Phi_ {n-2}),
• (Psi_1) ist die Klasse aller Formeln der Form (existiert x A (x)), wobei (A (x)) in (Phi_0) steht. Für (n \ ge 2) ist (Psi_n) die Klasse aller Formeln der Form (A \ rightarrow B), wobei (A) in (Phi_n) und (B) ist in (Phi_ {n-1}).

Die entsprechenden klassischen Prenex-Klassen sind einfacher definiert:

• (Pi_0 = \ Sigma_0 = \ Delta_0),
• (Pi_ {n +1}) ist die Klasse aller Formeln der Form (für alle x A (x)), wobei (A (x)) in (Sigma_n) steht.
• (Sigma_ {n +1}) ist die Klasse aller Formeln der Form (existiert x A (x)), wobei (A (x)) in (Pi_n) steht.

Die Peano-Arithmetik (mathbf {PA}) stammt aus der Heyting-Arithmetik (mathbf {HA}), indem LEM oder (neg \ neg A \ rightarrow A) zur Liste der logischen Axiome hinzugefügt werden, dh von mit klassischer statt intuitionistischer Logik. Die folgenden Ergebnisse gelten auch für die Fragmente von (mathbf {HA}) und (mathbf {PA}), wobei das Induktionsschema auf (Delta_0) -Formeln beschränkt ist.

Satz von Burr:

• Jede arithmetische Formel entspricht nachweislich in (mathbf {HA}) einer Formel in einer der Klassen (Phi_n).
• Jede Formel in (Phi_n) entspricht nachweislich in (mathbf {PA}) einer Formel in (Pi_n) und umgekehrt.
• Jede Formel in (Psi_n) entspricht nachweislich in (mathbf {PA}) einer Formel in (Sigma_n) und umgekehrt.

(mathbf {HA}) und (mathbf {PA}) sind beweistheoretisch äquivalent, wie in Abschnitt 4 gezeigt wird. Jedes kann (numerisch) sein eigenes Beweisprädikat ausdrücken. Wenn nach Gödels berühmtem Unvollständigkeitssatz (mathbf {HA}) konsistent ist, können weder (mathbf {HA}) noch (mathbf {PA}) seine eigene Konsistenz beweisen.

4. Grundlegende Beweistheorie

4.1 Klassik in intuitionistische Logik übersetzen

Eine grundlegende Tatsache der intuitionistischen Logik ist, dass sie die gleiche Konsistenzstärke wie die klassische Logik hat. Für die Aussagenlogik wurde dies erstmals von Glivenko [1929] bewiesen.

Glivenkos Theorem

Eine willkürliche Satzformel (A) ist klassisch beweisbar, wenn und nur wenn (neg \ neg A) intuitionistisch beweisbar ist.

Der Satz von Glivenko erstreckt sich nicht auf die Prädikatenlogik, obwohl eine beliebige Prädikatformel (A) nur dann klassisch beweisbar ist, wenn (neg \ neg A) in der intuitionistischen Prädikatenlogik plus dem Schema der „doppelten Negationsverschiebung“beweisbar ist.

) tag {DNS} für alle x \ neg \ neg B (x) rechtspfeil \ neg \ neg \ für alle x B (x))

Die differenziertere negative Übersetzung der Klassik in intuitionistische Theorien, unabhängig von Gödel und Gentzen, assoziiert mit jeder Formel (A) der Sprache (L) eine andere Formel (g (A)) (ohne) vee) oder (existiert)), so dass

• (I) Klassische Prädikatenlogik beweist (A \ leftrightarrow g (A)).
• (II) Intuitionistische Prädikatenlogik beweist (g (A) leftrightarrow \ neg \ neg g (A)).
• (III) Wenn die klassische Prädikatenlogik (A) beweist, dann beweist die intuitionistische Prädikatenlogik (g (A)).

Die Beweise ergeben sich aus der folgenden induktiven Definition von (g (A)) (unter Verwendung von Gentzens direkter Übersetzung der Implikation anstelle von Gödels in Bezug auf (neg) und (oldand)):

) begin {align *} g (P) & \ text {is} neg \ neg P, \ text {if} P \ text {is prime}. \\ g (A \ oldand B) & \ text { ist} g (A) oldand g (B). \\ g (A \ vee B) & \ text {is} neg (neg g (A) oldand \ neg g (B)). \\ g (A \ rechter Pfeil B) & \ text {is} g (A) rechter Pfeil g (B). \\ g (neg A) & \ text {is} neg g (A). \\ g (forall xA (x)) & \ text {is} forall xg (A (x)). \\ g (existiert xA (x)) & \ text {is} neg \ für alle x \ neg g (A (x)). \ end {align *})

Für jede Formel (A) ist (g (A)) genau dann intuitiv beweisbar, wenn (A) klassisch beweisbar ist. Insbesondere wenn (B \ oldand \ neg B) für eine Formel (B) klassisch beweisbar wäre, dann (g (B) oldand \ neg g (B)) (was (g () ist) B \ oldand \ neg B))) wäre wiederum intuitiv beweisbar. Daher

(IV) Klassische und intuitionistische Prädikatenlogik sind gleichkonsistent

Die negative Übersetzung der Klassik in die intuitionistische Zahlentheorie ist noch einfacher, da die Hauptformeln der intuitionistischen Arithmetik stabil sind. Somit kann (g (s = t)) als (s = t) angenommen werden, und die anderen Klauseln bleiben unverändert. Die negative Übersetzung eines Beispiels mathematischer Induktion ist ein weiteres Beispiel mathematischer Induktion, und die anderen nichtlogischen Axiome der Arithmetik sind ihre eigenen negativen Übersetzungen

(I), (II), (III) und (IV) gelten auch für die Zahlentheorie

Gödel [1933e] interpretierte diese Ergebnisse als Beweis dafür, dass intuitionistische Logik und Arithmetik reicher sind als klassische Logik und Arithmetik, da die intuitionistische Theorie Formeln unterscheidet, die klassisch äquivalent sind und dieselbe Konsistenzstärke wie die klassische Theorie haben. Insbesondere gelten Gödels Unvollständigkeitssätze sowohl für (mathbf {HA}) als auch für (mathbf {PA}).

Direkte Versuche, die negative Interpretation auf die Analyse auszudehnen, schlagen fehl, weil die negative Übersetzung des zählbaren Axioms der Wahl kein Theorem der intuitionistischen Analyse ist. Es steht jedoch im Einklang mit der intuitionistischen Analyse, einschließlich des umstrittenen Kontinuitätsprinzips von Brouwer, durch die funktionale Version von Kleenes rekursiver Realisierbarkeit (vgl. Abschnitt 6.2 unten). Daraus folgt, dass die intuitionistische Mathematik, die nur unter Verwendung aller logischen Standardverbindungen und -quantifizierer ausgedrückt werden kann, mit einer getreuen Übersetzung der klassischen Mathematik übereinstimmt, wobei (vee) und (existent) vermieden werden.

Dies ist wichtig, da Brouwers intuitionistische Analyse nicht mit LEM übereinstimmt. Wenn jedoch (A) eine negative Formel ist (ohne (vee) oder (existiert)), ist (neg \ neg A \ rightarrow A) unter Verwendung intuitionistischer Logik nachweisbar. Eine Versöhnung von intuitionistischer und klassischer Analyse in dieser Richtung, inspiriert von Kripkes Begriff der Wahlsequenz, wird in Moschovakis [2017] vorgeschlagen.

4.2 Zulässige Regeln der intuitionistischen Logik und Arithmetik

Gödel [1932] beobachtete, dass die intuitionistische Aussagenlogik die Disjunktionseigenschaft hat:

(DP) Wenn (A \ vee B) ein Theorem ist, dann ist (A) ein Theorem oder (B) ein Theorem

Gentzen [1935] etablierte die Disjunktionseigenschaft für geschlossene Formeln der intuitionistischen Prädikatenlogik. Daraus folgt, dass, wenn die intuitionistische Logik konsistent ist, (P \ vee \ neg P) kein Theorem ist, wenn (P) eine Atomformel ist. Kleene [1945, 1952] hat bewiesen, dass die intuitionistische Zahlentheorie erster Ordnung auch die verwandte (vgl. Friedman [1975]) Existenz-Eigenschaft besitzt:

(EP) Wenn (existiert x A (x)) ein geschlossener Satz ist, dann ist für einen geschlossenen Term (t) (A (t)) ein Satz

Die Disjunktions- und Existenzmerkmale sind Sonderfälle eines allgemeinen Phänomens, das nichtklassischen Theorien eigen ist. Die zulässigen Regeln einer Theorie sind die Regeln, nach denen die Theorie geschlossen wird. Zum Beispiel beobachtete Harrop [1960], dass die Regel

Wenn (neg A \ rightarrow (B \ vee C)) ein Theorem ist, ist es auch ((neg A \ rightarrow B) vee (neg A \ rightarrow C))

ist für die intuitionistische Aussagenlogik (mathbf {IPC}) zulässig, da (A), (B) und (C) beliebige Formeln sind, so dass (neg A \ rightarrow (B \ vee) C)) ist in (mathbf {IPC}) beweisbar, dann ist auch ((neg A \ rightarrow B) vee (neg A \ rightarrow C)) in (mathbf {IPC) beweisbar }). Harrops Regel kann in (mathbf {IPC}) nicht abgeleitet werden, da ((neg A \ rightarrow (B \ vee C)) rightarrow (neg A \ rightarrow B) vee (neg A \ rightarrow C))) ist nicht intuitiv beweisbar. Ein weiteres wichtiges Beispiel für eine zulässige nicht ableitbare Regel von (mathbf {IPC}) ist die Mints-Regel:

Wenn ((A \ rightarrow B) rightarrow (A \ vee C)) ein Theorem ist, ist dies auch (((A \ rightarrow B) rightarrow A) vee ((A \ rightarrow B) rightarrow C.)).

Die zweiwertige Wahrheitstabelleninterpretation der klassischen Aussagenlogik (mathbf {CPC}) liefert einen einfachen Beweis dafür, dass jede zulässige Regel von (mathbf {CPC}) ableitbar ist: Andernfalls kann eine Zuordnung zu (A), (B) usw. würden die Hypothese wahr und die Schlussfolgerung falsch machen und durch Ersetzen von z. B. (P \ rightarrow P) durch die Buchstaben "true" und (P \ oldand \ neg P)) Für diejenigen, denen "falsch" zugewiesen wurde, hätte man eine nachweisbare Hypothese und eine unbeweisbare Schlussfolgerung. Die Tatsache, dass die intuitionistische Situation interessanter ist, führt zu vielen natürlichen Fragen, von denen einige kürzlich beantwortet wurden.

Durch die Verallgemeinerung der Münzregel identifizierten Visser und de Jongh eine rekursiv aufzählbare Folge von sukzessive stärkeren zulässigen Regeln („Visser-Regeln“), die, wie sie vermuteten, eine Grundlage für die zulässigen Regeln von (mathbf {IPC}) im Sinne bildeten dass jede zulässige Regel aus der Disjunktionseigenschaft und einer der Regeln der Sequenz ableitbar ist. Aufbauend auf der Arbeit von Ghilardi [1999] gelang es Iemhoff [2001], ihre Vermutung zu beweisen. Rybakov [1997] hat bewiesen, dass die Sammlung aller zulässigen Regeln von (mathbf {IPC}) entscheidbar ist, aber keine endliche Grundlage hat. Visser [2002] zeigte, dass seine Regeln auch die zulässigen Satzregeln von (mathbf {HA}) und von (mathbf {HA}) sind, die durch Markovs Principle MP (definiert in Abschnitt 5.2 unten) erweitert wurden. In jüngerer ZeitJerabek [2008] fand eine unabhängige Basis für die zulässigen Regeln von (mathbf {IPC}) mit der Eigenschaft, dass keine Regel in der Basis eine andere ableitet.

Über die zulässigen Regeln der intuitionistischen Prädikatenlogik ist viel weniger bekannt. Pure (mathbf {IQC}) ohne Einzel- oder Prädikatkonstanten hat die folgende bemerkenswerte zulässige Regel für (A (x)) ohne freie Variablen, aber (x):

Wenn (existiert x A (x)) ein Theorem ist, ist es auch (für alle x A (x)).

Nicht jede zulässige Prädikatregel von (mathbf {IQC}) ist für alle formalen Systeme zulässig, die auf (mathbf {IQC}) basieren. Zum Beispiel verstößt (mathbf {HA}) offensichtlich gegen die gerade angegebene Regel. Visser hat in [1999] bewiesen, dass die Eigenschaft, eine zulässige Prädikatregel von (mathbf {HA}) zu sein, (Pi_2) vollständig ist, und in [2002], dass (mathbf {HA}) (+) MP hat die gleichen zulässigen Prädikatregeln wie (mathbf {HA}). Plisko [1992] hat bewiesen, dass die Prädikatenlogik von (mathbf {HA}) (+) MP (die Menge von Sätzen in der Sprache von (mathbf {IQC}), deren einheitliche Substitutionsinstanzen in Die Sprache der Arithmetik ist nachweisbar in (mathbf {HA}) (+) MP) ist (Pi_2) vollständig; Visser [2006] erweiterte dieses Ergebnis auf einige konstruktiv interessante konsistente Erweiterungen von (mathbf {HA}), die nicht in (mathbf {PA}) enthalten sind.

Obwohl sie nicht vollständig klassifiziert wurden, ist bekannt, dass die zulässigen Regeln der intuitionistischen Prädikatenlogik Markovs Regel für entscheidbare Prädikate enthalten:

Wenn (für alle x (A (x) vee \ neg A (x)) oldand \ neg \ für alle x \ neg A (x)) ein Theorem ist, so ist (existiert x A (x)).

und die folgende Unabhängigkeitsregel (wobei angenommen wird, dass (y) in (A (x)) nicht frei vorkommt):

Wenn (forall x (A (x) vee \ neg A (x)) oldand (forall x A (x) rightarrow \ existiert y B (y))) ein Satz ist, so ist (existiert y (für alle x A (x) rechter Pfeil B (y))).

Beide Regeln sind auch für (mathbf {HA}) zulässig. Die entsprechenden Implikationen (MP bzw. IP), die intuitiv nicht nachweisbar sind, werden durch Gödels „Dialectica“-Interpretation von (mathbf {HA}) verifiziert (vgl. Abschnitt 6.3 unten). Entspricht die Implikation (CT) einer der interessantesten zulässigen Regeln der Heyting-Arithmetik? Nennen wir sie die Church-Kleene-Regel:

Wenn (forall x \ existiert y A (x, y)) ein geschlossener Satz von (mathbf {HA}) ist, dann gibt es eine Zahl (n), so dass nachweislich in (mathbf {HA}), die partielle rekursive Funktion mit der Gödel-Zahl (n) ist total und ordnet jedes (x) einem (y) zu, das (A (x, y)) erfüllt (und darüber hinaus) (A (mathbf {x}, \ mathbf {y})) ist beweisbar, wobei (mathbf {x}) die Zahl für die natürliche Zahl (x) und (mathbf {y} ist)) ist die Ziffer für (y)).

Die Kombination von Markovs Regel mit der negativen Übersetzung ergibt das Ergebnis, dass klassische und intuitionistische Arithmetik die gleichen Formeln der Form (forall x \ existiert y A (x, y)) beweisen, wobei (A (x, y)) ist quantifiziererfrei. Im Allgemeinen ist, wenn (A (x, y)) nachweislich in (mathbf {HA}) entscheidbar ist und wenn (forall x \ existiert, y A (x, y)) ein geschlossener Satz von klassische arithmetik (mathbf {PA}), die Schlussfolgerung der Church-Kleene-Regel gilt auch in der intuitionistischen Arithmetik. Denn wenn (mathbf {HA}) (forall x \ forall y (A (x, y) vee \ neg A (x, y))) beweist, dann durch die Church-Kleene-Regel die charakteristische Funktion von (A (x, y)) hat eine Gödel-Zahl (m), nachweislich in (mathbf {HA}); also beweist (mathbf {HA}) (forall x \ existiert y A (x, y) leftrightarrow \ forall x \ existiert y \ existiert z B (mathbf {m}, x, y, z)) wobei (B) quantifiziererfrei ist,und die benachbarten existenziellen Quantifizierer können in (mathbf {HA}) kontrahiert werden. Daraus folgt, dass (mathbf {HA}) und (mathbf {PA}) dieselben nachweislich rekursiven Funktionen haben.

Hier ist ein Beweis dafür, dass die Regel "Wenn (für alle x (A \ vee B (x))) ein Theorem ist, ist auch (A \ vee \ für alle x B (x))" (wobei (x) ist nicht frei in (A)) ist für (mathbf {HA}) nicht zulässig, wenn (mathbf {HA}) konsistent ist. Die Gödel-Nummerierung liefert eine quantifiziererfreie Formel (G (x)), die (numerisch) das Prädikat "(x) ist der Code eines Beweises in (mathbf {HA}) von ((0) ausdrückt = 1)).” Durch intuitionistische Logik mit der Entscheidbarkeit quantifiziererfreier arithmetischer Formeln beweist (mathbf {HA}) (forall x (existiert y G (y) vee \ neg G (x))). Wenn jedoch (mathbf {HA}) bewiesen hat, dass (existiert yG (y) vee \ forall x \ neg G (x)), dann muss (mathbf {HA}) durch die Disjunktionseigenschaft beweisen, dass entweder (existiert yG (y)) oder (für alle x \ neg G (x)). Der erste Fall ist unmöglich,durch die Existenz-Eigenschaft mit der Konsistenzannahme und der Tatsache, dass (mathbf {HA}) alle wahren quantifiziererfreien Sätze beweist. Aber der zweite Fall ist nach Gödels zweitem Unvollständigkeitssatz auch unmöglich, da (forall x \ neg G (x)) die Konsistenz von (mathbf {HA}) ausdrückt.

5. Grundlegende Semantik

Intuitionistische Systeme haben eine Vielzahl von Interpretationen inspiriert, darunter Beths Tableaus, Rasiowa und Sikorskis topologische Modelle, Heyting-Algebren, Formeln als Typen, Kleenes rekursive Realisierbarkeit, die Kleene- und Aczel-Schrägstriche sowie Modelle, die auf Garben und Topoi basieren. Von all diesen Interpretationen ähnelt Kripkes [1965] Semantik der möglichen Welt, in Bezug auf die die intuitionistische Prädikatenlogik vollständig und konsistent ist, am meisten der klassischen Modelltheorie. Rekursive Realisierbarkeitsinterpretationen versuchen andererseits, die BHK-Erklärung der intuitionistischen Wahrheit effektiv umzusetzen.

5.1 Kripke-Semantik für intuitionistische Logik

Eine Kripke-Struktur (mathbf {K}) für (L) besteht aus einer teilweise geordneten Menge (K) von Knoten und einer Domänenfunktion D, die jedem Knoten (k) in (K) zugewiesen wird) eine bewohnte Menge (D (k)), so dass wenn (k \ le k '), dann (D (k) subseteq D (k')). Zusätzlich hat (mathbf {K}) eine Forcierungsbeziehung, die wie folgt bestimmt wird.

Für jeden Knoten (k) sei (L (k)) die Sprache, die (L) um neue Konstanten für alle Elemente von (D (k)) erweitert. Weisen Sie jedem Knoten (k) und jedem (0) - Prädikatbuchstaben (jedem Satzbuchstaben) (P) entweder (f (P, k) =) true zu oder lassen Sie (f () P, k)) undefiniert, in Übereinstimmung mit der Anforderung, dass wenn (k \ le k ') und (f (P, k) =) wahr sind, dann (f (P, k') =) wahr ist ebenfalls. Sag das

(k) (vDash) (P) genau dann, wenn (f (P, k) =) wahr ist.

Weisen Sie jedem Knoten (k) und jedem ((n + 1)) - Prädikatbuchstaben (Q (ldots)) eine (möglicherweise leere) Menge (T (Q, k)) zu. von ((n + 1)) - Tupel von Elementen von (D (k)) derart, dass wenn (k \ le k ') dann (T (Q, k) subseteq T. (Q, k ')). Sag das

(k) (vDash) (Q (d_0, \ ldots, d_n)) genau dann, wenn ((d_0, \ ldots, d_n) in T (Q, k)).

Definieren Sie nun (k) (vDash) (E) (was als "(k) Kräfte (E)" gelesen werden kann) für zusammengesetzte Sätze (E) von (L () k)) induktiv wie folgt:

(k) (vDash) ((A \ oldand B))	if (k) (vDash) (A) und (k) (vDash) (B).
(k) (vDash) ((A \ vee B))	if (k) (vDash) (A) oder (k) (vDash) (B).
(k) (vDash) ((A \ rightarrow B))	wenn für jedes (k '\ ge k), wenn (k') (vDash) (A) dann (k ') (vDash) (B).
(k) (vDash) (neg A)	wenn für nein (k '\ ge k) (k') (vDash) (A).
(k) (vDash) (forall x A (x))	wenn für jedes (k '\ ge k) und jedes (d \ in D (k')), (k ') (vDash) (A (d)).
(k) (vDash) (existiert x A (x))	wenn für einige (d \ in D (k)), (k) (vDash) (A (d)).

Eine solche Forcierungsbeziehung ist konsistent:

Für keinen Satz (A) und kein (k) ist es der Fall, dass sowohl (k) (vDash) (A) als auch (k) (vDash) (neg A).

und monoton:

Wenn (k \ le k ') und (k) (vDash) (A), dann (k') (vDash) (A).

Kripkes Soliditäts- und Vollständigkeitssätze legen fest, dass ein Satz von (L) in der intuitionistischen Prädikatenlogik genau dann beweisbar ist, wenn er von jedem Knoten jeder Kripke-Struktur erzwungen wird. Um zu zeigen, dass (neg \ forall x \ neg P (x) rightarrow \ x P (x)) existiert, ist es intuitiv nicht beweisbar, eine Kripke-Struktur mit (K = {k, k) zu betrachten '},) (k \ lt k',) (D (k) = D (k ') = {0 }), (T (P, k)) leer, aber (T (P, k ') = {0 }). Und um zu zeigen, dass das Gegenteil intuitiv beweisbar ist (ohne tatsächlich einen Beweis zu erbringen), braucht man nur die Konsistenz- und Monotonieeigenschaften beliebiger Kripke-Modelle mit der Definition von (vDash).

Kripke-Modelle für Sprachen mit Gleichheit können (=) an jedem Knoten durch eine willkürliche Äquivalenzbeziehung interpretieren, abhängig von der Monotonie. Für Anwendungen auf die intuitionistische Arithmetik reichen normale Modelle (solche, bei denen Gleichheit durch Identität an jedem Knoten interpretiert wird) aus, da die Gleichheit natürlicher Zahlen entscheidbar ist.

Die Aussagen-Kripke-Semantik ist besonders einfach, da eine beliebige Satzformel nur dann intuitiv beweisbar ist, wenn sie durch die Wurzel jedes Kripke-Modells erzwungen wird, dessen Rahmen (die Menge (K) der Knoten zusammen mit ihrer Teilordnung) endlich ist Baum mit einem kleinsten Element (der Wurzel). Zum Beispiel das Kripke-Modell mit (K = {k, k ', k' '}, k \ lt k') und (k \ lt k '') und mit (P) true nur bei (k '), zeigt, dass sowohl (P \ vee \ neg P) als auch (neg P \ vee \ neg \ neg P) in (mathbf {IPC}) nicht beweisbar sind..

Jeder Endknoten oder jedes Blatt eines Kripke-Modells ist ein klassisches Modell, da ein Blatt jede Formel oder ihre Negation erzwingt. Nur die Satzbuchstaben, die in einer Formel (E) vorkommen, und nur die Knoten (k '), so dass (k \ le k'), sind für die Entscheidung relevant, ob (k) Kräfte auftreten oder nicht (E). Solche Überlegungen ermöglichen es uns, mit jeder Formel (E) von (L (mathbf {IPC})) eine endliche Klasse endlicher Kripke-Strukturen effektiv zu verknüpfen, die ein Gegenmodell zu (E) enthält, falls eines existiert. Da die Klasse aller Sätze von (mathbf {IPC}) rekursiv aufzählbar ist, schließen wir daraus

(mathbf {IPC}) ist effektiv entscheidbar. Es gibt eine rekursive Prozedur, die für jede Satzformel (E) bestimmt, ob (E) ein Satz von (mathbf {IPC}) ist oder nicht, und entweder mit einem Beweis von (E) endet) oder ein (endliches) Kripke-Gegenmodell.

Die Entscheidbarkeit von (mathbf {IPC}) wurde erstmals 1935 von Gentzen erhalten. Die Unentscheidbarkeit von (mathbf {IQC}) folgt aus der Unentscheidbarkeit von (mathbf {CQC}) durch die negative Interpretation.

Bekannte nicht-intuitionistische logische Schemata entsprechen beispielsweise den strukturellen Eigenschaften von Kripke-Modellen

• DNS gilt in jedem Kripke-Modell mit endlichem Frame.
• ((A \ rightarrow B) vee (B \ rightarrow A)) gilt für jedes Kripke-Modell mit linear geordnetem Rahmen. Umgekehrt hat jede Satzformel, die in (mathbf {IPC} + (A \ rightarrow B) vee (B \ rightarrow A)) nicht ableitbar ist, ein Kripke-Gegenmodell mit linear geordnetem Rahmen (vgl. Abschnitt 6.1 unten).
• Wenn (x) in (A) nicht frei ist, dann gilt (forall x (A \ vee B (x)) rightarrow (A \ vee \ forall x B (x))) in jedem Kripke Modell (mathbf {K}) mit konstanter Domäne (so dass (D (k) = D (k ')) für alle (k, k') in (K)). Gleiches gilt für MP.

Kripke-Modelle und Beth-Modelle (die sich im Detail von Kripke-Modellen unterscheiden, aber intuitionistisch äquivalent sind) sind ein leistungsfähiges Werkzeug zur Ermittlung der Eigenschaften intuitionistischer formaler Systeme. vgl. Troelstra und van Dalen [1988], Smorynski [1973], de Jongh und Smorynski [1976], Ghilardi [1999] und Iemhoff [2001] [2005]. Es gibt jedoch keinen rein intuitionistischen Beweis dafür, dass jeder Satz, der in allen Kripke- und Beth-Modellen gültig ist, in (mathbf {IQC}) beweisbar ist. Nach einer Beobachtung von Gödel bestätigte Kreisel [1958], dass die Vollständigkeit der intuitionistischen Prädikatenlogik für die Beth-Semantik gleichbedeutend mit Markovs Principle MP ist, das Brouwer ablehnte.

Darüber hinaus haben Dyson und Kreisel [1961] gezeigt, dass wenn (mathbf {IQC}) für die Beth-Semantik schwach vollständig ist (dh wenn in jedem Beth-Modell kein unbeweisbarer Satz gilt), die folgende Konsequenz von MP gilt: [tag {GDK} forall \ alpha_ {B (alpha)} neg \ neg \ existiert x R (alpha, x) rightarrow \ neg \ neg \ forall \ alpha_ {B (alpha)} existiert x R (alpha, x),) wobei (x) sich über alle natürlichen Zahlen erstreckt, (alpha) sich über alle unendlichen Folgen natürlicher Zahlen erstreckt, (B (alpha)) Abkürzungen (forall x (alpha (x) leq 1)) und (R) drücken eine primitive rekursive Beziehung von (alpha) und (x) aus. Umgekehrt bringt GDK die schwache Vollständigkeit von (mathbf {IQC}) mit sich. Dieses interessante Prinzip, das die negative Interpretation einer Form von Brouwers Fan-Theorem rechtfertigen würde,ist schwächer als MP, aber in aktuellen Systemen der intuitionistischen Analyse nicht beweisbar. Kreisel [1962] schlug vor, dass die GDK möglicherweise auf der Grundlage noch unentdeckter Eigenschaften der intuitionistischen Mathematik nachweisbar sein könnte.

Indem Veldman [1976] die Definition eines Kripke-Modells so änderte, dass „explodierende Knoten“, die jeden Satz erzwingen, möglich sind, fand er einen Vollständigkeitsnachweis, der nur intuitionistische Logik verwendete. Er stellte jedoch die Frage, ob Kripke-Modelle mit explodierenden Knoten intuitionistisch bedeutsame mathematische Objekte waren.

5.2 Realisierbarkeitssemantik für die Heyting-Arithmetik

Eine Möglichkeit, die BHK-Erklärung der intuitionistischen Wahrheit für die Arithmetik zu implementieren, besteht darin, jedem Satz (E) von (mathbf {HA}) eine Sammlung numerischer Codes für Algorithmen zuzuordnen, die die konstruktive Wahrheit von (E bestimmen könnten). Nach Kleene [1945] realisiert eine Zahl (e) einen Satz (E) der Sprache der Arithmetik durch Induktion auf die logische Form von (E):

(e) realisiert (r = t)	wenn (r = t) wahr ist.
(e) realisiert (A \ oldand B)	wenn (e) ein Paar ((f, g)) so codiert, dass (f) (A) und (g) (B) realisiert.
(e) realisiert (A \ vee B)	Wenn (e) ein Paar ((f, g)) so codiert, dass wenn (f = 0), dann (g) (A) realisiert und wenn (f \ gt 0)) dann erkennt (g) (B).
(e) realisiert (A \ rightarrow B)	Wenn (f) (A) realisiert, wird die (e) -te partielle rekursive Funktion bei (f) definiert und ihr Wert realisiert (B).
(e) realisiert (neg A)	wenn kein (f) realisiert (A).
(e) realisiert (für alle x A (x))	wenn für jedes (n) die (e) -te partielle rekursive Funktion bei (n) definiert ist und ihr Wert (A (mathbf {n})) realisiert.
(e) erkennt (existiert x A (x))	Wenn (e) ein Paar codiert ((n, g)) und (g) realisiert (A (mathbf {n})).

Eine beliebige Formel ist realisierbar, wenn eine Zahl ihren universellen Verschluss realisiert. Beachten Sie, dass für jede Formel (A) nicht sowohl (A) als auch (neg A) realisierbar sind. Das grundlegende Ergebnis ist

Nelsons Theorem [1947]

Wenn (A) in (mathbf {HA}) von realisierbaren Formeln (F) ableitbar ist, dann ist (A) realisierbar.

Es kann gezeigt werden, dass einige nichtintuitionistische Prinzipien realisierbar sind. Zum Beispiel kann Markovs Prinzip (für entscheidbare Formeln) durch das Schema ausgedrückt werden

(MP) (für alle x (A (x) vee \ neg A (x)) alt und \ neg \ für alle x \ neg A (x) rechtspfeil \ existiert x A (x))

Obwohl in (mathbf {HA}) nicht beweisbar, ist MP durch ein Argument realisierbar, das das Markovsche Prinzip informell verwendet. Realisierbarkeit ist jedoch eine grundsätzlich nichtklassische Interpretation. In (mathbf {HA}) ist es möglich, ein Axiom der rekursiven Wahl CT (für „Church's Thesis“) auszudrücken, das LEM widerspricht, aber (konstruktiv) realisierbar ist. Daher ist nach Nelsons Theorem (mathbf {HA}) (+) MP (+) CT konsistent.

Kleene verwendete eine Variante der Zahlenrealisierbarkeit, um zu beweisen, dass (mathbf {HA}) die Church-Kleene-Regel erfüllt; Das gleiche Argument gilt für (mathbf {HA}) mit MP oder CT und für (mathbf {HA}) (+) MP (+) CT. In Kleene und Vesley [1965] und Kleene [1969] ersetzen Funktionen Zahlen als realisierende Objekte, wodurch die Konsistenz der formalisierten intuitionistischen Analyse und ihre Schließung unter einer Version zweiter Ordnung der Church-Kleene-Regel hergestellt wird.

Nelsons Theorem begründet die Unbeweisbarkeit einiger Sätze der klassischen Prädikatenlogik in (mathbf {IQC}). Wenn zu jedem (n) - Prädikatbuchstaben (P (ldots)) eine Formel (f (P)) von (L (mathbf {HA})) mit (n) gesetzt wird) freie Variablen werden zugewiesen, und wenn die Formel (f (A)) von (L (mathbf {HA})) aus der Formel (A) von (L) stammt, wird jede ersetzt Primformel (P (x_1, \ ldots, x_n)) durch (f (P) (x_1, \ ldots, x_n)), dann wird (f (A)) eine arithmetische Substitutionsinstanz von \ genannt (EIN). Wenn beispielsweise eine Formel von (L (mathbf {HA})), die "(x)" ausdrückt, einen Beweis in (mathbf {HA}) der Formel mit dem Code (y) codiert”Wird (P (x, y)) zugewiesen, die resultierende arithmetische Substitutionsinstanz von (forall y (existiert x P (x, y) vee \ neg \ existiert x P (x, y))) ist nicht realisierbar und daher in (mathbf {HA}) nicht beweisbar, ebenso wie seine doppelte Negation. Daraus folgt, dass (neg \ neg \ forall y (existiert x P (x, y) vee \ neg \ existiert x P (x, y))) in (mathbf {IQC} nicht nachweisbar ist).

De Jongh [1970] kombinierte Realisierbarkeit mit Kripke-Modellierung, um zu zeigen, dass intuitionistische Aussagenlogik (mathbf {IPC}) und ein Fragment von (mathbf {IQC}) für (mathbf {HA} arithmetisch vollständig sind). Eine einheitliche Zuordnung einfacher existenzieller Formeln zu Prädikatbuchstaben genügt, um dies zu beweisen

De Jonghs Theorem (für IPC) [1970]

Wenn eine Satzformel (A) der Sprache (L) in (mathbf {IPC}) nicht beweisbar ist, dann eine arithmetische Substitutionsinstanz von (A.) ist in (mathbf {HA}) nicht nachweisbar.

Der Beweis dieser Version von de Jonghs Theorem bedarf keiner Realisierbarkeit; vgl. Smorynski [1973]. Als Beispiel liefert Rossers Form von Gödels Unvollständigkeitssatz einen Satz (C) von (L (mathbf {HA})), so dass (mathbf {PA}) weder (C) noch beweist (neg C), also kann durch die Disjunktionseigenschaft (mathbf {HA}) ((C \ vee \ neg C)) nicht bewiesen werden. De Jonghs semantischer Beweis ergab jedoch auch, dass jede intuitionistisch unbeweisbare Prädikatformel einer eingeschränkten Art eine arithmetische Substitutionsinstanz aufweist, die in (mathbf {HA}) nicht beweisbar ist. Mit einer syntaktischen Methode erweiterte Daniel Leivant [1979] den Satz von de Jongh auf alle intuitionistisch unbeweisbaren Prädikatenformeln und bewies, dass (mathbf {IQC}) für (bf {HA}) arithmetisch vollständig ist. Siehe van Oosten [1991] für eine historische Darstellung und einen einfacheren Beweis des vollständigen Theorems, wobei die abstrakte Realisierbarkeit mit Beth-Modellen anstelle von Kripke-Modellen verwendet wird.

Ohne zu behaupten, dass die Realisierbarkeit von Zahlen mit der intuitionistischen arithmetischen Wahrheit übereinstimmt, beobachtete Nelson, dass für jede Formel (A) von (L (mathbf {HA})) das Prädikat "(y) (A) realisiert.”Kann in (mathbf {HA}) durch eine andere Formel (abgekürzt“(y \ realizesrel A)”ausgedrückt werden, und das Schema (A \ leftrightarrow \ existiert y (y \ realizesrel A)) stimmt mit (mathbf {HA}) überein. Troelstra [1973] zeigte, dass (mathbf {HA}) (+) ((A \ leftrightarrow \ existiert y (y \ realizesrel A))) (mathbf {HA}) entspricht. (+) ECT, wobei ECT eine verstärkte Form der CT ist. In (mathbf {HA}) (+) MP (+) ECT, das Troelstra als Formalisierung der russischen rekursiven Mathematik betrachtet (vgl. Abschnitt 3.2 des Eintrags zur konstruktiven Mathematik), wird jede Formel von Die Form ((y \ realizesrel A)) hat eine äquivalente "klassische" Prenexform (A ').(y)) bestehend aus einer quantifiziererfreien Subformel, der alternierende "klassische" Quantifizierer der Formen (neg \ neg \ existiert x) und (forall z \ neg \ neg) und so (vorangestellt sind) existiert y A '(y)) ist eine Art Prenex-Form von (A).

6. Zusätzliche Themen und weiterführende Literatur

6.1 Subintuitionistische und Zwischenlogik

Gegenwärtig gibt es mehrere andere Einträge in dieser Enzyklopädie, die sich mit intuitionistischer Logik in verschiedenen Kontexten befassen, aber eine allgemeine Behandlung schwächerer und stärkerer Aussagen- und Prädikatenlogiken scheint zu fehlen. Viele solcher Logiken wurden identifiziert und untersucht. Hier einige Beispiele.

Eine subintuitionistische Aussagenlogik kann aus (mathbf {IPC}) erhalten werden, indem die Sprache eingeschränkt oder die Logik oder beides geschwächt wird. Ein extremes Beispiel für das erste ist (mathbf {RN}), eine intuitionistische Logik mit einer einzigen Satzvariablen (P), die nach ihren Entdeckern Rieger und Nishimura [1960] benannt ist. (mathbf {RN}) ist durch das Rieger-Nishimura-Gitter unendlich vieler nichtäquivalenter Formeln (F_n) gekennzeichnet, so dass jede Formel, deren einzige Satzvariable (P) ist, durch intuitionistische Logik einigen (äquivalent ist) F_n). Nishimuras Version ist

) begin {align *} F _ { infty} & = P \ rightarrow P. \\ F_0 & = P \ oldand \ neg P. \\ F_1 & = P. \\ F_2 & = \ neg P. \\ F_ {2 n + 3} & = F_ {2 n + 1} vee F_ {2n + 2}. \\ F_ {2 n + 4} & = F_ {2 n + 3} rechter Pfeil F_ {2 n + 1}. \ end {align *})

In (mathbf {RN}) impliziert weder (F_ {2 n + 1}) noch (F_ {2 n + 2}) den anderen; aber (F_ {2 n}) impliziert (F_ {2 n + 1}), und (F_ {2 n + 1}) impliziert jeweils (F_ {2 n + 3}) und (F_ {2 n + 4}).

Fragmente von (mathbf {IPC}), denen eine oder mehrere logische Verknüpfungen fehlen, beschränken die Sprache und im Übrigen die Logik, da die intuitionistischen Verknüpfungen (oldand), (vee), (rightarrow), (neg) sind logisch unabhängig von (mathbf {IPC}). Rose [1953] hat bewiesen, dass das implikationslose Fragment (ohne (rightarrow)) in Bezug auf die Realisierbarkeit vollständig ist, in dem Sinne, dass wenn jede arithmetische Substitutionsinstanz einer Satzformel (E) ohne (rightarrow) ist (Zahl) -realisierbar, dann ist (E) ein Satz von (mathbf {IPC}). Dieses Ergebnis steht im Gegensatz zu

Roses Theorem [1953]

(mathbf {IPC}) ist hinsichtlich der Realisierbarkeit unvollständig.

Sei (F) die Satzformel [((neg \ neg D \ rightarrow D) rightarrow (neg \ neg D \ vee \ neg D)) rightarrow (neg \ neg D \ vee \ neg D)) wobei (D) ((neg P \ vee \ neg Q)) und (P), (Q) Primzahlen sind. Jede arithmetische Substitutionsinstanz von (F) ist realisierbar (unter Verwendung der klassischen Logik), aber (F) ist in (mathbf {IPC}) nicht beweisbar.

Daraus folgt, dass (mathbf {IPC}) für (mathbf {HA}) (+) ECT arithmetisch unvollständig ist (vgl. Abschnitt 5.2).

Die minimale Logik (mathbf {ML}) stammt aus der intuitionistischen Logik, indem ex falso gelöscht wird. Kolmogorov [1925] zeigte, dass dieses Fragment bereits eine negative Interpretation der klassischen Logik enthält, die beide Quantifizierer beibehält, vgl. Leivant [1985]. Minimale Logik beweist den Sonderfall (neg A \ rightarrow (A \ rightarrow \ neg B)) von ex falso für Negationen. Colacito, de Jongh und Vardas [2017] untersuchen verschiedene subminimale Logiken, die jeweils schwächer als (mathbf {ML}) sind.

Griss bestritt Brouwers Gebrauch der Negation und widersprach sowohl dem Gesetz des Widerspruchs als auch ex falso. Es ist erwähnenswert, dass Negation für die intuitionistische Mathematik nicht wirklich benötigt wird, da (0 = 1) ein bekannter Widerspruch ist, so dass (neg A) durch (A \ rightarrow 0 = 1) definiert werden kann. Dann kann ex falso als (0 = 1 \ rightarrow A) angegeben werden, und das Gesetz des Widerspruchs ist aus den verbleibenden Axiomen von (mathbf {H}) beweisbar.

Eine intermediäre Satzlogik ist jede konsistente Sammlung von Satzformeln, die alle Axiome von (mathbf {IPC}) enthalten und unter modus ponens geschlossen sind, und Satzsatzbuchstaben durch beliebige Formeln. Jede Zwischensatzlogik ist in (mathbf {CPC}) enthalten. Einige spezielle intermediäre Aussagenlogiken, die durch Hinzufügen eines oder mehrerer klassisch korrekter, aber intuitiv nicht beweisbarer Axiomschemata zu (mathbf {IPC}) gekennzeichnet sind, wurden ausführlich untersucht.

Eine der einfachsten Zwischensatzlogiken ist die Gödel-Dummett-Logik (mathbf {LC}), die durch Hinzufügen des Schemas ((A \ rightarrow B) vee (B) zu (mathbf {IPC}) erhalten wird \ rightarrow A)) Dies gilt für alle und nur für die Kripke-Frames, in denen die Teilreihenfolge der Knoten linear ist. Gödel [1932] verwendete eine unendliche Folge von sukzessive stärkeren Zwischenlogiken, um zu zeigen, dass (mathbf {IPC}) keine endliche Interpretation der Wahrheitstabelle hat. Für jede positive ganze Zahl (n) sei (mathbf {G_n}) (mathbf {LC}) plus das Schema ((A_1 \ rightarrow A_2) vee \ ldots \ vee (A_1) oldand \ ldots \ oldand A_n \ rightarrow A_ {n + 1})). Dann ist (mathbf {G_n}) für alle und nur für die linear geordneten Kripke-Frames mit nicht mehr als (n) Knoten gültig.

Die Jankov-Logik (mathbf {KC}), die (mathbf {IPC}) das Prinzip der Testbarkeit (neg A \ vee \ neg \ neg A) hinzufügt, hat offensichtlich keine Disjunktion Eigentum. Die Kreisel-Putnam-Logik (mathbf {KP}), die durch Hinzufügen des Schemas ((neg A \ rightarrow B \ vee C) rightarrow ((neg A) zu (mathbf {IPC}) erhalten wird \ rightarrow B) vee (neg A \ rightarrow C))) hat die Disjunktionseigenschaft, erfüllt jedoch nicht alle Visser-Regeln. Die Zwischenlogik, die durch Hinzufügen des Schemas (((neg \ neg D \ rightarrow D) rightarrow (D \ vee \ neg D)) rightarrow (neg \ neg D \ vee \ neg D)) erhalten wird, entspricht zu Roses Gegenbeispiel hat zu (mathbf {IPC}) auch die Disjunktionseigenschaft. Iemhoff [2005] hat bewiesen, dass (mathbf {IPC}) die einzige zwischengeschaltete Aussagenlogik mit der Disjunktionseigenschaft ist, die nach allen Visser-Regeln geschlossen ist. Iemhoff und Metcalfe [2009] entwickelten einen formalen Kalkül für die allgemeine Zulässigkeit von (mathbf {IPC}) und einigen Zwischenlogiken. Goudsmit [2015] ist eine gründliche Untersuchung der zulässigen Regeln der Zwischenlogik mit einer umfassenden Bibliographie.

Eine Zwischensatzlogik (mathbf {L}) soll die Finite-Frame-Eigenschaft haben, wenn es eine Klasse von Finite-Frames gibt, für die die Kripke-gültigen Formeln genau die Sätze von (mathbf {L}) sind.. Viele Zwischenlogiken, einschließlich (mathbf {LC}) und (mathbf {KP}), haben diese Eigenschaft. Jankov [1968] verwendete eine unendliche Folge von Kripke-Frames mit endlichen Wurzeln, um zu beweisen, dass es ein Kontinuum vieler Zwischenlogiken gibt. De Jongh, Verbrugge und Visser [2009] haben bewiesen, dass jede Zwischenlogik (mathbf {L}) mit der Eigenschaft des endlichen Rahmens die Aussagenlogik von (mathbf {HA (L)}) ist, d. H. Klasse aller Formeln in der Sprache von (mathbf {IPC}), deren arithmetische Substitutionsinstanzen in der logischen Erweiterung von (mathbf {HA}) um (mathbf {L}) nachweisbar sind.

Eine Zwischensatzlogik (mathbf {L}) ist strukturell vollständig, wenn jede für (mathbf {L}) zulässige Regel in (mathbf {L}) ableitbar ist, und erblich strukturell vollständig, wenn Jede Zwischenlogik, die (mathbf {L}) erweitert, ist auch strukturell vollständig. Jede Zwischenlogik (mathbf {L}) hat eine strukturelle Vervollständigung (mathbf { overline {L}}), die durch Anschließen aller zulässigen Regeln erhalten wird. (mathbf {LC}) und (mathbf {G_n}) sind erblich strukturell vollständig. Während (mathbf {IPC}), (mathbf {RN}) und (mathbf {KC}) nicht strukturell vollständig sind, sind ihre strukturellen Vervollständigungen erblich strukturell vollständig. Für diese und weitere Ergebnisse siehe Citkin [2016, Other Internet Resources].

Einige Zwischenprädikatenlogiken, die (mathbf {IQC}) erweitern und unter Substitution geschlossen werden, sind (mathbf {IQC}) (+) DNS (Abschnitt 4.1), (mathbf {IQC}) (+) MP (vgl. Abschnitt 5.2), (mathbf {IQC}) (+) MP (+) IP (vgl. Abschnitt 4.2) und die intuitionistische Logik konstanter Domänen (mathbf {CD}) erhalten durch Hinzufügen des Schemas (forall x (A \ vee B (x)) rightarrow (A \ vee \ forall x B (x)) zu (mathbf {IQC})) für alle Formeln (A), (B (x)), wobei (x) in (A) nicht frei vorkommt. Mints, Olkhovikov und Urquhart [2012, Other Internet Resources] zeigten, dass (mathbf {CD}) nicht über die Interpolationseigenschaft verfügt, und widerlegten früher veröffentlichte Beweise anderer Autoren.

6.2 Fortgeschrittene Themen

Brouwers Einfluss auf Gödel war bedeutend, obwohl Gödel nie Intuitionist wurde. Gödels [1933f] Übersetzung der intuitionistischen Aussagenlogik in die Modallogik (mathbf {S4}) ist in Abschnitt 2.5 des Eintrags über Gödel und in Troelstras einleitendem Hinweis zur Übersetzung von [1933f] in Band I von Gödels Collected beschrieben Funktioniert. Siehe auch Mints [2012]. Kripke-Modelle für modale Logik waren älter als Modelle für intuitionistische Logik.

Alternativen zur Kripke- und Beth-Semantik für die intuitionistische Aussagen- und Prädikatenlogik umfassen die topologische Interpretation von Stone [1937], Tarski [1938] und Mostowski [1948] (vgl. Rasiowa und Sikorski [1963], Rasiowa [1974]), die erweitert wurde zur intuitionistischen Analyse von Scott [1968] und Krol [1978]. M. Hyland [1982] definierte den effektiven Topos Eff und bewies, dass seine Logik intuitionistisch ist. Eine sehr informative Diskussion der Semantik für intuitionistische Logik und Mathematik von W. Ruitenberg und eine interessante neue Perspektive von G. Bezhanishvili und W. Holliday finden Sie unter Andere Internetquellen (unten).

Eine Alternative zur Realisierbarkeitssemantik für die intuitionistische Arithmetik ist Gödels [1958] "Dialectica" -Interpretation, die jeder Formel (B) von (L (mathbf {HA})) eine quantifiziererfreie Formel (B_D) zuordnet) in der Sprache der intuitionistischen Arithmetik aller endlichen Typen. Die "Dialectica" -Interpretation von (B), nennen wir es (B ^ D), ist (existiert Y \ für alle x B_D (Y, x)). Wenn (B) ein geschlossener Satz von (mathbf {HA}) ist, dann ist (B_D (F, x)) für einen Term (F) in Gödels Theorie (mathbf {beweisbar) T}) von "primitiven rekursiven" Funktionalen höheren Typs. Die Übersetzung von (B) nach (B ^ D) erfordert das Axiom der Wahl (bei allen endlichen Typen), MP und IP, ist also nicht streng konstruktiv; jedoch,Die zahlentheoretischen Funktionen, die durch die Begriffe (F) von (mathbf {T}) ausgedrückt werden können, sind genau die nachweislich rekursiven Funktionen von (mathbf {HA}) (und von (mathbf {PA}).). Die Interpretation wurde auf die Analyse von Spector [1962] erweitert; vgl. Howard [1973]. Klare Darstellungen und zusätzliche Referenzen finden sich in Troelstras Einführung in die englische Übersetzung in Gödel [1990] des ursprünglichen Dialectica-Artikels, in Avigad und Feferman [1998] und in Ferreira [2008].

Während (mathbf {HA}) ein fester Bestandteil der klassischen Arithmetik ist, führt die intuitionistische Haltung gegenüber mathematischen Objekten zu einer divergierenden Theorie der reellen Zahlen (vgl. Abschnitte 3.4–3.7 des Eintrags zum Intuitionismus in der Philosophie der Mathematik) aus dem klassischen. Kleenes Interpretation der Funktionsrealisierbarkeit, die entwickelt wurde, um die Konsistenz seiner Formalisierung (mathbf {FIM}) der intuitionistischen Sequenztheorie ("intuitionistische Analyse") zu beweisen, verändert die Interpretation arithmetischer Formeln; Zum Beispiel ist (neg \ neg \ für alle x (A (x) vee \ neg A (x))) für jede arithmetische Formel (A (x)) funktionsrealisierbar. In der Sprache der AnalyseMarkovs Prinzip und die negative Übersetzung des zählbaren Axioms der Wahl gehören zu den vielen nicht-intuitionistischen Prinzipien, die (durch klassische Argumente) funktionsrealisierbar sind und daher mit (mathbf {FIM}) übereinstimmen; vgl. Kleene [1965], Vesley [1972] und Moschovakis [2003].

Die konkrete und abstrakte Realisierbarkeitssemantik für eine Vielzahl formaler Systeme wurde von Logikern und Informatikern entwickelt und untersucht. vgl. Troelstra [1998] und van Oosten [2002] und [2008]. Variationen der Grundbegriffe sind besonders nützlich, um die relative Konsistenz und relative Unabhängigkeit der nichtlogischen Axiome in Theorien festzustellen, die auf intuitionistischer Logik basieren. Einige Beispiele sind Moschovakis [1971], Lifschitz [1979] und die von Rathjen [2006, 2012] und Chen [2012] entwickelten Realisierbarkeitsbegriffe für konstruktive und intuitionistische Mengen-Theorien. Frühe abstrakte Realisierbarkeitsbegriffe umfassen die Schrägstriche von Kleene [1962, 1963] und Aczel [1968] und Läuchli [1970]. Kohlenbach, Avigad und andere haben Realisierbarkeitsinterpretationen für Teile der klassischen Mathematik entwickelt.

Artemovs Rechtfertigungslogik ist eine alternative Interpretation der BHK-Erklärung der intuitionistischen Konnektiva und Quantifizierer, wobei (idealisierte) Beweise die Rolle der Realisierung von Objekten spielen. Siehe auch Artemov und Iemhoff [2007].

Eine andere Forschungsrichtung in der intuitionistischen Logik betrifft Brouwers sehr kontroverses "Erstellen von Gegenbeispielen für Subjekte" zu Prinzipien der klassischen Analyse (wie Markovs Prinzip), die auf der Grundlage der Theorie (mathbf {FIM}) von Kleene und nicht widerlegt werden konnten Vesley [1965]. Durch die Schwächung von Kleenes Form von Brouwers Prinzip der kontinuierlichen Wahl und das Hinzufügen eines Axioms, das er Kripkes Schema (KP) nannte, gelang es Myhill, die Argumente des erstellenden Subjekts zu formalisieren. KP ist inkonsistent mit (mathbf {FIM}), aber Vesley [1970] hat ein alternatives Prinzip (Vesleys Schema VS) gefunden, das konsistent zu (mathbf {FIM}) hinzugefügt werden kann und alle Gegenbeispiele impliziert, für die Brouwer benötigte ein erstellendes Thema. Krol [1978] und Scowcroft gaben topologische Konsistenzbeweise für die intuitionistische Analyse mit Kripkes Schema und schwacher Kontinuität.

6.3 Empfohlene Lektüre

Der Eintrag zu LEJ Brouwer behandelt Brouwers Philosophie und Mathematik mit einer Chronologie seines Lebens und einer ausgewählten Liste von Veröffentlichungen, einschließlich Übersetzungen und Sekundärquellen. Der beste Weg, um mehr zu erfahren, besteht darin, einige der Originalarbeiten zu lesen. Englische Übersetzungen von Brouwers Dissertation und anderen Artikeln, die ursprünglich auf Niederländisch erschienen, sowie eine Reihe von Artikeln auf Deutsch finden sich in LEJ Brouwer: Collected Works [1975], herausgegeben von Heyting. Das wesentliche Quellenbuch von Benacerraf und Putnam enthält Brouwer [1912] (in englischer Übersetzung), Brouwer [1949] und Dummett [1975]. Mancosus [1998] liefert englische Übersetzungen vieler grundlegender Artikel von Brouwer, Heyting, Glivenko und Kolmogorov mit aufschlussreichem Einführungsmaterial von W. van Stigt, dessen [1990] eine weitere wertvolle Ressource darstellt.

Die dritte Ausgabe [1971] von Heytings Klassiker [1956] ist eine attraktive Einführung in die intuitionistische Philosophie, Logik und mathematische Praxis. Van Dalen [1981] bietet im Rahmen des beeindruckenden Projekts zur Herausgabe und Veröffentlichung von Brouwers Nachlass einen umfassenden Überblick über Brouwers eigene intuitionistische Philosophie. Die englische Übersetzung von Brouwers [1927] in van Heijenoort [1969] (mit einer schönen Einführung von Parsons) ist immer noch eine unverzichtbare Referenz für Brouwers Theorie des Kontinuums. Veldman [1990] und [2005] sind authentische moderne Beispiele traditioneller intuitionistischer mathematischer Praxis. Troelstra [1991] stellt die intuitionistische Logik in ihren historischen Kontext als gemeinsame Grundlage der konstruktiven Mathematik im 20. Jahrhundert. Bezhanishvili und de Jongh [2005,Andere Internetquellen] umfasst die jüngsten Entwicklungen in der intuitionistischen Logik.

Kleene und Vesleys [1965] geben eine sorgfältige axiomatische Behandlung der intuitionistischen Analyse, einen Beweis ihrer Konsistenz in Bezug auf eine klassisch korrekte Subtheorie und eine erweiterte Anwendung auf Brouwers Theorie der reellen Zahlengeneratoren. Kleenes [1969] formalisiert die Theorie partieller rekursiver Funktionale und ermöglicht präzise Formalisierungen der in [1965] verwendeten Interpretation der Funktionsrealisierbarkeit und einer verwandten Interpretation der Q-Realisierbarkeit, die die Church-Kleene-Regel für die intuitionistische Analyse liefert.

Troelstra [1973], Beeson [1985] und Troelstra und van Dalen [1988] (mit Korrekturen) sind die umfassendsten Studien intuitionistischer und semi-intuitionistischer formaler Theorien, die sowohl konstruktive als auch klassische Methoden mit nützlichen Bibliographien verwenden. Troelstra und Schwichtenberg [2000] präsentieren parallel die Beweistheorie der klassischen, intuitionistischen und minimalen Logik, wobei sie sich auf sequentielle Systeme konzentrieren. Troelstras [1998] präsentiert Formeln als Typen und (Kleene und Aczel) Schrägstrichinterpretationen für Aussagen- und Prädikatenlogik sowie abstrakte und konkrete Realisierbarkeiten für eine Vielzahl von Anwendungen. Martin-Löfs konstruktive Typentheorie [1984] (vgl. Abschnitt 3.4 des Eintrags zur konstruktiven Mathematik) bietet einen weiteren allgemeinen Rahmen, in dem sich das intuitionistische Denken weiterentwickelt.

Literaturverzeichnis

• Aczel, P., 1968, "Gesättigte intuitionistische Theorien", in HA Schmidt, K. Schütte und H.-J. Thiele (Hrsg.), Beiträge zur mathematischen Logik, Amsterdam: Nordholland: 1–11.
• Artemov, S. und Iemhoff, R., 2007, „Die grundlegende intuitionistische Logik der Beweise“, Journal of Symbol Logic, 72: 439–451.
• Avigad, J. und Feferman, S., 1998, "Gödels funktionale (" Dialectica ") Interpretation", Kapitel V von Buss (Hrsg.) 1998: 337–405.
• Bar-Hillel, Y. (Hrsg.), 1965, Logik, Methodik und Wissenschaftstheorie, Amsterdam: Nordholland.
• Beeson, MJ, 1985, Grundlagen der Konstruktiven Mathematik, Berlin: Springer.
• Benacerraf, P. und Hilary Putnam (Hrsg.), 1983, Philosophie der Mathematik: Ausgewählte Lesungen, 2. Auflage, Cambridge: Cambridge University Press.
• Beth, EW, 1956, „Semantische Konstruktion intuitionistischer Logik“, Koninklijke Nederlandse Akad. von Wettenscappen, 19 (11): 357–388.
• Brouwer, LEJ, 1907, "Auf den Grundlagen der Mathematik", Dissertation, Amsterdam; Englische Übersetzung in Heyting (Hrsg.) 1975: 11–101.
• –––, 1908, „Die Unzuverlässigkeit der logischen Prinzipien“, englische Übersetzung in Heyting (Hrsg.) 1975: 107–111.
• –––, 1912, „Intuitionismus und Formalismus“, englische Übersetzung von A. Dresden, Bulletin der American Mathematical Society, 20 (1913): 81–96, nachgedruckt in Benacerraf und Putnam (Hrsg.) 1983: 77–89; auch nachgedruckt in Heyting (Hrsg.) 1975: 123–138.
• –––, 1923 [1954], „Zur Bedeutung des Prinzips der ausgeschlossenen Mitte in der Mathematik, insbesondere in der Funktionstheorie“, „Nachträge und Berichtigungen“und „Weitere Nachträge und Berichtigungen“, englische Übersetzung in van Heijenoort (Hrsg.) 1967: 334–345.
• –––, 1923C, „Intuitionistische Zerlegung mathematischer Grundbegriffe“, Jahresbericht der Deutschen Mathematiker-Vereinigung, 33 (1925): 251-256; Nachdruck in Heyting (Hrsg.) 1975, 275–280.
• –––, 1927, „Intuitionistische Überlegungen zum Formalismus“, ursprünglich 1927 veröffentlicht, englische Übersetzung in van Heijenoort (Hrsg.) 1967: 490–492.
• –––, 1948, „Bewusstsein, Philosophie und Mathematik“, ursprünglich veröffentlicht (1948), abgedruckt in Benacerraf und Putnam (Hrsg.) 1983: 90–96.
• Burr, W., 2004, "Die intuitionistische arithmetische Hierarchie", in J. van Eijck, V. van Oostrom und A. Visser (Hrsg.), Logic Colloquium '99 (Lecture Notes in Logic 17), Wellesley, MA: ASL und AK Peters, 51–59.
• Buss, S. (Hrsg.), 1998, Handbook of Proof Theory, Amsterdam und New York: Elsevier.
• Chen, RM. und Rathjen, M., 2012, „Lifschitz-Realisierbarkeit für die intuitionistische Zermelo-Fraenkel-Mengenlehre“, Archive for Mathematical Logic, 51: 789–818.
• Colacito, A., de Jongh, D. und Vargas, A., 2017, „Subminimal Negation“, Soft Computing, 21: 165–164.
• Crossley, J. und MAE Dummett (Hrsg.), 1965, Formale Systeme und rekursive Funktionen, Amsterdam: North-Holland Publishing.
• van Dalen, D. (Hrsg.), 1981, Brouwers Cambridge Lectures on Intuitionism, Cambridge: Cambridge University Press.
• Dummett, M., 1975, „Die philosophische Grundlage der intuitionistischen Logik“, ursprünglich veröffentlicht (1975), abgedruckt in Benacerraf und Putnam (Hrsg.) 1983: 97–129.
• Dyson, V. und Kreisel, G., 1961, Analyse von Beths semantischer Konstruktion intuitionistischer Logik, Technischer Bericht Nr. 3, Stanford: Labor für Angewandte Mathematik und Statistik, Stanford University.
• Ferreira, F., 2008, „Ein höchst künstlerisches Paket aus einem Durcheinander von Ideen“, Dialectica, 62: 205–222.
• Friedman, H., 1975, „Die Disjunktionseigenschaft impliziert die Eigenschaft der numerischen Existenz“, Proceedings of the National Academy of Science, 72: 2877–2878.
• Gentzen, G., 1934–5, „Untersuchungen über das logische Schliessen“, Mathematische Zeitschrift, 39: 176–210, 405–431.
• Ghilardi, S., 1999, „Vereinigung in intuitionistischer Logik“, Journal of Symbolic Logic, 64: 859–880.
• Glivenko, V., 1929, „Sur quelques points de la logique de M. Brouwer“, Académie Royale de Belgique, Bulletins de la Classe des Sciences, 5 (15): 183–188.
• Gödel, K., 1932, „Zum intuitionistischen Interessenkalkül“, Anzeiger der Akademie der Wissenschaften in Wien, 69: 65–66. Wiedergabe und Übersetzung mit einer Einführung von AS Troelstra in Gödel 1986: 222–225.
• –––, 1933e, „Zur intuitionistischen Arithmetik und Zahlentheorie“, Ergebnisse eines mathematischen Kolloquiums, 4: 34–38.
• –––, 1933f, „Eine Interpretation des intuitionistischen Interessenkalküls“, reproduziert und übersetzt mit einer Einführung von AS Troelstra in Gödel 1986: 296–304.
• –––, 1958, Dialektica, 12: 280–287. Wiedergabe mit englischer Übersetzung in Gödel 1990: 241–251.
• –––, 1986, Collected Works, Vol. Ich, S. Feferman et al. (Hrsg.), Oxford: Oxford University Press.
• –––, 1990, Collected Works, Vol. II, S. Feferman et al. (Hrsg.), Oxford: Oxford University Press.
• Goudsmit, JP, 2015, Intuitionistische Regeln: Zulässige Regeln der Zwischenlogik, Ph. D. Dissertation, Universität Utrecht.
• Harrop R., 1960, „Bezüglich Formeln der Typen (A \ rechtspfeil B \ vee C, A \ rechtspfeil (Ex) B (x)) in intuitionistischen formalen Systemen“, Journal of Symbolic Logic, 25: 27–32.
• van Heijenoort, J. (Hrsg.), 1967, Von Frege nach Gödel: Ein Quellenbuch in mathematischer Logik 1879–1931, Cambridge, MA: Harvard University Press.
• Heyting, A., 1930, „Die formalen Regeln der intuitionistischen Logik“, in drei Teilen, Sitzungsberichte der preussischen Akademie der Wissenschaften: 42–71, 158–169. Englische Übersetzung von Teil I in Mancosu 1998: 311–327.
• –––, 1956, Intuitionismus: Eine Einführung, Amsterdam: North-Holland Publishing, 3. überarbeitete Ausgabe, 1971.
• Heyting, A. (Hrsg.), 1975, LEJ Brouwer: Gesammelte Werke (Band 1: Philosophie und Grundlagen der Mathematik), Amsterdam und New York: Elsevier.
• Howard, WA, 1973, "Hereditär majorifizierbare Funktionale endlichen Typs", in Troelstra (Hrsg.) 1973: 454–461.
• Hyland, JME, 1982, "The Effective Topos", in Troelstra und van Dalen (Hrsg.) 1982: 165–216.
• Iemhoff, R., 2001, „Über die zulässigen Regeln der intuitionistischen Aussagenlogik“, Journal of Symbolic Logic, 66: 281–294.
• –––, 2005, „Zwischenlogik und Visser-Regeln“, Notre Dame Journal of Formal Logic, 46: 65–81.
• Iemhoff, R. und Metcalfe, G., 2009, „Beweistheorie für zulässige Regeln“, Annals of Pure and Applied Logic, 159: 171–186.
• Jankov, VA, 1968, "Die Konstruktion einer Folge stark unabhängiger superintuitionistischer Aussagenkalkulationen", sowjetische Mathematik. Doklady, 9: 801–807.
• Jerabek, E., 2008, „Unabhängige Grundlagen zulässiger Regeln“, Logic Journal der IGPL, 16: 249–267.
• de Jongh, DHJ, 1970, "Die Maximalität des intuitionistischen Satzkalküls in Bezug auf Heytings Arithmetik", Journal of Symbolic Logic, 6: 606.
• de Jongh, DHJ, und Smorynski, C., 1976, „Kripke-Modelle und die intuitionistische Theorie der Arten“, Annals of Mathematical Logic, 9: 157–186.
• de Jongh, D., Verbrugge, R. und Visser, A., 2011, „Intermediate Logics and the de Jongh Property“, Archive for Mathematical Logic, 50: 197–213.
• Kino, A., Myhill, J. und Vesley, RE (Hrsg.), 1970, Intuitionism and Proof Theory: Proceedings der Sommerkonferenz in Buffalo, NY, 1968, Amsterdam: Nordholland.
• Kleene, SC, 1945, „Zur Interpretation der intuitionistischen Zahlentheorie“, Journal of Symbolic Logic, 10: 109–124.
• –––, 1952, Einführung in die Metamathematik, Princeton: Van Nostrand.
• –––, 1962, „Disjunktion und Existenz unter Implikation in elementaren intuitionistischen Formalismen“, Journal of Symbolic Logic, 27: 11–18.
• –––, 1963, „Ein Nachtrag“, Journal of Symbolic Logic, 28: 154–156.
• –––, 1965, „Klassische Erweiterungen der intuitionistischen Mathematik“, in Bar-Hillel (Hrsg.) 1965: 31–44.
• –––, 1969, Formalisierte rekursive Funktionen und formalisierte Realisierbarkeit, Memoiren der American Mathematical Society 89.
• Kleene, SC und Vesley, RE, 1965, Die Grundlagen der intuitionistischen Mathematik, insbesondere in Bezug auf rekursive Funktionen, Amsterdam: Nordholland.
• Kreisel, G., 1958, „Elementare Vollständigkeitseigenschaften intuitionistischer Logik mit einem Hinweis auf Negationen von Prenex-Formeln“, Journal of Symbolic Logic, 23: 317–330.
• –––, 1962, „Über die schwache Vollständigkeit der intuitionistischen Prädikatenlogik“, Journal of Symbolic Logic, 27: 139–158.
• Kripke, SA, 1965, „Semantische Analyse der intuitionistischen Logik“, in J. Crossley und MAE Dummett (Hrsg.) 1965: 92–130.
• Krol, M., 1978, "Ein topologisches Modell der intuitionistischen Analyse mit Kripkes Schema", Zeitschrift für Math. Logik und Grundlagen der Mathematik. 24: 427–436.
• Leivant, D., 1979, "Maximality of Intuitionistic Logic", Mathematical Center Tracts 73, Mathematisch Centrum, Amsterdam.
• –––, 1985, „Syntaktische Übersetzungen und nachweislich rekursive Funktionen“, Journal of Symbolic Logic, 50: 682–688.
• Läuchli, H., 1970, "Ein abstrakter Begriff der Realisierbarkeit, für den die intuitionistische Prädikatenrechnung vollständig ist", in A. Kino et al. (Hrsg.) 1965: 227–234.
• Lifschitz, V., 1979, „CT (_ 0) ist stärker als CT (_ 0)!“, Proceedings of the American Mathematical Society, 73 (1): 101–106.
• Mancosu, P., 1998, Von Brouwer zu Hilbert: Die Debatte über die Grundlagen der Mathematik in den 1920er Jahren, New York und Oxford: Oxford University Press.
• Martin-Löf, P., 1984, Intuitionistische Typentheorie, Notizen von Giovanni Sambin zu einer Reihe von Vorlesungen in Padua, Juni 1980, Napoli: Bibliopolis.
• Mints, G., 2012, „Die Gödel-Tarski-Übersetzungen intuitionistischer Satzformeln“in Correct Reasoning (Lecture Notes in Computer Science 7265), E. Erdem et al. (Hrsg.), Dordrecht: Springer-Verlag: 487–491.
• Moschovakis, JR, 1971, „Kann es keine nicht rekursiven Funktionen geben?“, Journal of Symbolic Logic, 36: 309–315.
• –––, 2003, „Klassische und konstruktive Hierarchien in der erweiterten intuitionistischen Analyse“, Journal of Symbolic Logic, 68: 1015–1043.
• –––, 2009, „Die Logik von Brouwer und Heyting“, in Logik von Russell bis Kirche (Handbuch zur Geschichte der Logik, Band 5), J. Woods und D. Gabbay (Hrsg.), Amsterdam: Elsevier: 77 –125.
• –––, 2017, „Intuitionistische Analyse und das Ende der Zeit“, Bulletin of Symbolic Logic, 23: 279–295.
• Nelson, D., 1947, „Rekursive Funktionen und intuitionistische Zahlentheorie“, Transactions of the American Mathematical Society, 61: 307–368.
• Nishimura, I., 1960, „Über Formeln einer Variablen in der intuitionistischen Aussagenrechnung“, Journal of Symbolic Logic, 25: 327–331.
• van Oosten, J., 1991, „Ein semantischer Beweis des Satzes von de Jongh“, Archives for Mathematical Logic, 31: 105–114.
• –––, 2002, „Realisierbarkeit: ein historischer Aufsatz“, Mathematical Structures in Computer Science, 12: 239–263.
• –––, 2008, Realisierbarkeit: Eine Einführung in die kategoriale Seite, Amsterdam: Elsevier.
• Plisko, VE, 1992, „Zur arithmetischen Komplexität bestimmter konstruktiver Logiken“, Mathematical Notes, (1993): 701–709. Übersetzt aus Matematicheskie Zametki, 52 (1992): 94–104.
• Rasiowa, H., 1974, Algebraischer Ansatz zur nichtklassischen Logik, Amsterdam: Nordholland.
• Rasiowa, H. und Sikorski, R., 1963, The Mathematics of Metamathematics, Warschau: Panstwowe Wydawnictwo Naukowe.
• Rathjen, M., 2006, „Realisierbarkeit für die konstruktive Zermelo-Fraenkel-Mengenlehre“, im Logic Colloquium 2003 (Lecture Notes in Logic 24), J. Väänänen et al. (Hrsg.), AK Peters 2006: 282–314.
• –––, 2012, „Von der schwachen zur starken Existenz“, Annals of Pure and Applied Logic, 163: 1400–1418.
• Rose, GF, 1953, „Aussagenrechnung und Realisierbarkeit“, Transactions of the American Mathematical Society, 75: 1–19.
• Rybakov, V., 1997, Zulässigkeit logischer Inferenzregeln, Amsterdam: Elsevier.
• Scott, D., 1968, "Erweiterung der topologischen Interpretation auf die intuitionistische Analyse", Compositio Mathematica, 20: 194-210.
• Smorynski, CA, 1973, "Applications of Kripke Models", in Troelstra (Hrsg.) 1973: 324–391.
• Spector, C., 1962, „Nachweislich rekursive Analysefunktionen: ein Konsistenznachweis der Analyse durch eine Erweiterung der in der aktuellen intuitionistischen Mathematik formulierten Prinzipien“, Rekursive Funktionstheorie: Proceedings of Symposia in Pure Mathematics, Band 5, JCE Dekker (Hrsg.), Providence, RI: American Mathematical Society, 1–27.
• van Stigt, WP, 1990, Brouwers Intuitionismus, Amsterdam: Nordholland.
• Stone, MH, 1937, "Topologische Darstellung von Verteilungsgittern und Brouwer'scher Logik", Casopis Pest. Matte. Fys. 67: 1–25.
• Tarski, A., 1938, Der Derkalkül und die Topologie, Fundamenta Mathematicae, 31: 103–104.
• Troelstra, AS, 1991, „Geschichte des Konstruktivismus im 20. Jahrhundert“, ITLI Prepublication Series ML - 1991–05, Amsterdam. Endgültige Fassung in Mengenlehre, Arithmetik und Grundlagen der Mathematik (Lecture Notes in Logic 36), J. Kenney und R. Kossak (Hrsg.), Association for Symbolic Logic, Ithaca, NY, 2011: 150–179.
• –––, 1998, „Realisierbarkeit“, Kapitel VI von Buss (Hrsg.), 1998: 407–473.
• –––, Einleitung zu 1958 und 1972, in Gödel, 1990: 217–241.
• Troelstra, AS (Hrsg.), 1973, Metamathematische Untersuchung intuitionistischer Arithmetik und Analyse (Lecture Notes in Mathematics 344), Berlin: Springer-Verlag. Korrekturen und Ergänzungen im Editor erhältlich.
• Troelstra, AS und Schwichtenberg, H., 2000, Basic Proof Theory (Cambridge Tracts in Theoretical Computer Science: Band 43), 2. Auflage, Cambridge: Cambridge University Press.
• Troelstra, AS und van Dalen, D., 1988, Konstruktivismus in der Mathematik: Eine Einführung, 2 Bände, Amsterdam: North-Holland Publishing. [Siehe auch die Korrekturen unter Andere Internetquellen.]
• Troelstra, AS und van Dalen, D. (Hrsg.), 1982, LEJ Brouwer Centenary Symposium, Amsterdam: North-Holland Publishing.
• Veldman, W., 1976, „Ein intuitionistischer Vollständigkeitssatz für intuitionistische Prädikatenlogik“, Journal of Symbolic Logic, 41: 159–166.
• –––, 1990, „Ein Überblick über die Theorie der intuitionistischen deskriptiven Menge“, in PP Petkov (Hrsg.), Mathematical Logic, Proceedings of the Heyting Conference, New York und London: Plenum Press, 155–174.
• –––, 2005, „Zwei einfache Mengen, die nicht positiv Borel sind“, Annals of Pure and Applied Logic, 135: 151–209.
• Vesley, RE, 1972, „Auswahlsequenzen und Markovs Prinzip“, Compositio Mathematica, 24: 33–53.
• –––, 1970, „Eine schmackhafte Alternative zu Kripkes Schema“, in A. Kino et al. (Hrsg.) 1970: 197ff.
• Visser, A., 1999, „Regeln und Arithmetik“, Notre Dame Journal of Formal Logic, 40: 116–140.
• –––, 2002, „Substitutionen von (Sigma ^ {0} _1) Sätzen: Erkundungen zwischen intuitionistischer Aussagenlogik und intuitionistischer Arithmetik“, Annals of Pure and Applied Logic, 114: 227–271.
• –––, 2006, „Prädikatenlogik konstruktiver arithmetischer Theorien“, Journal of Symbolic Logic, 72: 1311–1326.

Akademische Werkzeuge

	Wie man diesen Eintrag zitiert.
	Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
	Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
	Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

• Bezhanishvili, G. und Holliday, W., 2018, „Eine semantische Hierarchie für intuitionistische Logik“, Manuskript, UC Berkeley Faculty Publications.
• Bezhanishvili, N. und de Jongh, DHJ, 2005, Intuitionistic Logic, Lecture Notes, präsentiert am ESSLLI, Edinburgh.
• Brouwer, Auszüge aus Brouwers Vorlesungen in Cambridge.
• Citkin, A., 2016, „Erblich strukturell vollständige superintuitionistische deduktive Systeme“, Manuskript auf arXiv.org.
• Mints, G., Olkhovikov, G. und Urquhart, A., 2012, „Versagen der Interpolation in der intuitionistischen Logik konstanter Domänen“, Manuskript, arXiv.org.
• Troelstra, AS und JR Moschovakis, 2018, Korrekturen an AS Troelstra und D. van Dalen, 1988, Konstruktivismus in der Mathematik.
• Probleme in der Beweisbarkeitslogik, gepflegt von Lev Beklemishev.
• Realisability Bibliography, gepflegt von Lars Birkedal.
• van Oosten 2000 und andere Preprints im Zusammenhang mit der Realisierbarkeit, die von Jaap van Oosten gepflegt werden.