Logik zweiter Ordnung

Im Logik und Mathematik, Logik zweiter Ordnung ist eine Erweiterung von Logik erster Ordnung, was selbst eine Erweiterung von ist Aussagelogik.^[1] Die Logik der zweiten Ordnung wird wiederum um verlängert Logik höherer Ordnung und Typentheorie.

Logik erster Ordnung quantifiziert Nur Variablen, die sich über Individuen befinden (Elemente der Diskursbereich); Außerdem quantifiziert die Logik zweiter Ordnung auch über Beziehungen. Zum Beispiel die zweite Ordnung Satz ${\ displaystyle \ forall p \, \ forall x (px \ lor \ neg px)}$ sagt das für jeden Formel Pund jeder Einzelne x, entweder Px ist wahr oder nicht (nicht (Px) ist wahr (das ist das Gesetz der ausgeschlossenen Mitte). Logik zweiter Ordnung beinhaltet auch die Quantifizierung über Sets, Funktionenund andere Variablen (siehe Abschnitt unter). Sowohl Logik erster und zweiter Ordnung verwenden die Idee von a Diskursbereich (oft einfach als "Domain" oder "Universum" bezeichnet). Die Domäne ist ein Satz, über den einzelne Elemente quantifiziert werden können.

Beispiele

Graffiti in Neukölln (Berlin) zeigt den einfachsten Satz zweiter Ordnung, der nicht triviale Modelle zugibt, "∃φ φ".

Logik erster Ordnung kann über Einzelpersonen quantifizieren, jedoch nicht über Eigenschaften. Das heißt, wir können einen atomaren Satz wie Würfel nehmen (b) und erhalten Sie einen quantifizierten Satz, indem Sie den Namen durch eine Variable ersetzen und einen Quantifizierer anhängen:^[2]

∃x Würfel(x)

Wir können jedoch nicht das gleiche mit dem Prädikat tun. Das heißt, der folgende Ausdruck

∃p p (b)

ist kein Satz der Logik erster Ordnung, aber dies ist ein legitimer Satz der Logik zweiter Ordnung. Hier, P ist ein Prädikatvariable und ist semantisch ein einstellen von Individuen.^[2]

Infolgedessen hat die Logik zweiter Ordnung eine größere ausdrucksstarke Leistung als Logik erster Ordnung. Zum Beispiel gibt es in der Logik erster Ordnung keine Möglichkeit, die Menge aller Würfel und Tetraeder zu identifizieren. Die Existenz dieses Satzes kann jedoch in Logik zweiter Ordnung als geltend gemacht werden

∃p (∀x (PX ↔ (Würfel (Cube (x) ∨ tet (x)))).

Wir können dann Eigenschaften dieses Satzes geltend machen. Im Folgenden heißt es beispielsweise, dass die Menge aller Würfel und Tetraeder keine Dodekahedrons enthalten:

∀p (∀x (PX ↔ (Würfel (Cube (x) ∨ tet (x)))) → ¬ ∃x (Px ∧ dodec (x)).

Die Quantifizierung zweiter Ordnung ist besonders nützlich, da sie die Fähigkeit gibt, auszudrücken Erreichbarkeit Eigenschaften. Zum Beispiel, wenn Eltern (x, y) bezeichnet das x ist ein Elternteil von yDann kann die Logik erster Ordnung die Eigenschaft nicht ausdrücken, die x ist ein Vorfahr von y. In Logik zweiter Ordnung können wir dies ausdrücken, indem wir sagen, dass jede Reihe von Personen, die enthalten y und geschlossen unter der Elternbeziehung enthält x:

∀p py ∧ (∀a ∀b Pb ∧ Elternteil (a, b) → pa) → px.

Es ist bemerkenswert, dass wir zwar Variablen für Prädikate in Logik zweiter Ordnung haben, aber keine Variablen für Eigenschaften von Prädikaten haben. Wir können zum Beispiel nicht sagen, dass es eine Eigenschaftsform gibt (P) Das gilt für die Prädikate P Würfel, Tet und Dodec. Dies würde erfordern Logik der dritten Ordnung.^[3]

Syntax und Fragmente

Die Syntax der Logik zweiter Ordnung zeigt, welche Ausdrücke gut gebildet sind Formeln. In Ergänzung zu Syntax der Logik erster Ordnung, Logik zweiter Ordnung enthält viele neue Sorts (manchmal genannt Typen) von Variablen. Diese sind:

• Eine Art Variablen, die sich über Sätze von Individuen befinden. Wenn S ist eine Variable dieser Art und t ist ein Begriff erster Ordnung, dann der Ausdruck t ∈ S (auch geschrieben S(t), oder St Klammern zu retten) ist eine Atomformel. Sätze von Einzelpersonen können auch als als angesehen werden Unary Relations auf der Domäne.
• Für jede natürliche Zahl k Es gibt eine Art Variablen, die über alle hinausgehen k-ary Beziehungen zu den Individuen. Wenn R ist so ein k-ary Relation Variable und t₁, ...,t_k sind Begriffe erster Ordnung, dann der Ausdruck R(t₁, ...,t_k) ist eine Atomformel.
• Für jede natürliche Zahl k Es gibt eine Art Variablen, die über alle Funktionen übernommen werden k Elemente der Domäne und Rückgabe eines einzelnen Elements der Domäne. Wenn f ist so ein k-ary Funktionsvariable und t₁, ...,t_k sind Begriffe erster Ordnung, dann der Ausdruck f(t₁, ...,t_k) ist ein Begriff erster Ordnung.

Jede der gerade definierten Variablen kann allgemein und/oder existententiell quantifiziert sein, um Formeln aufzubauen. Somit gibt es viele Arten von Quantifizierern, zwei für jede Art von Variablen. EIN Satz In der Logik zweiter Ordnung befindet sich wie in Logik erster Ordnung eine gut geformte Formel ohne freie Variablen (jeglicher Art).

Es ist möglich, auf die Einführung von Funktionsvariablen in der oben angegebenen Definition zu verzichten (und einige Autoren dies tun dies), weil eine n-ary Funktionsvariable kann durch eine Beziehungsvariable von Arity dargestellt werden n+1 und eine geeignete Formel für die Einzigartigkeit des "Ergebniss" in der n+1 Argument der Beziehung. (Shapiro 2000, S. 63)

Monadische Logik zweiter Ordnung (MSO) ist eine Einschränkung der Logik zweiter Ordnung, bei der nur die Quantifizierung über einheitliche Beziehungen (d. H. Sätze) zulässig ist. Die Quantifizierung über Funktionen aufgrund der oben beschriebenen Äquivalenz wie oben beschrieben ist daher ebenfalls nicht zulässig. Die Logik zweiter Ordnung ohne diese Einschränkungen wird manchmal genannt Vollständige Logik zweiter Ordnung Um es von der monadischen Version zu unterscheiden. Eine monadische Logik zweiter Ordnung wird insbesondere im Kontext von verwendet Courcelle's Theoremein algorithmisches Meta-Theorem in Graphentheorie.

Genau wie in der Logik erster Ordnung kann die Logik zweiter Ordnung enthalten sein nicht logische Symbole in einer bestimmten Sprache zweiter Ordnung. Diese sind jedoch insofern eingeschränkt, als alle Begriffe, die sie bilden angemessene Sortierung).

Eine Formel in Logik zweiter Ordnung soll erster Ordnung erster Ordnung sein (und manchmal bezeichnet ${\ displayStyle \ sigma _ {0}^{1}}$ oder ${\ displayStyle \ pi _ {0}^{1}}$) Wenn seine Quantifizierer (die universell oder existentiell sein können) nur über Variablen erster Ordnung ausgesetzt, obwohl es freie Variablen zweiter Ordnung aufweisen kann. EIN ${\ displaystyle \ sigma _ {1}^{1}}$ (existentielle zweite Ordnung) Formel ist zusätzlich einige existenzielle Quantifizierer über Variablen zweiter Ordnung, d.h. ${\ displaystyle \ existiert r_ {0} \ ldots \ existiert r_ {m} \ phi}$, wo ${\ displayStyle \ phi}$ ist eine Formel erster Ordnung. Das Fragment der Logik zweiter Ordnung, das nur aus Formeln zweiter Ordnung besteht Existenzielle Logik zweiter Ordnung und als eso abkürzte ${\ displaystyle \ sigma _ {1}^{1}}$, oder sogar als ∃so. Das Fragment von ${\ displayStyle \ pi _ {1}^{1}}$ Formeln werden doppelt definiert, sie wird als universelle Logik zweiter Ordnung bezeichnet. Ausdrucksvollere Fragmente sind für jeden definiert k > 0 durch gegenseitige Rekursion: ${\ displayStyle \ sigma _ {k+1}^{1}}$ hat die Form ${\ displaystyle \ existiert r_ {0} \ ldots \ existiert r_ {m} \ phi}$, wo ${\ displayStyle \ phi}$ ist ein ${\ displayStyle \ pi _ {k}^{1}}$ Formel und ähnlich, ${\ displayStyle \ pi _ {k+1}^{1}}$ hat die Form ${\ displaystyle \ forall r_ {0} \ ldots \ forall r_ {m} \ phi}$, wo ${\ displayStyle \ phi}$ ist ein ${\ displaystyle \ sigma _ {k}^{1}}$ Formel. (Sehen analytische Hierarchie für die analoge Konstruktion von Arithmetik zweiter Ordnung.))

Semantik

Die Semantik der Logik zweiter Ordnung legt die Bedeutung jedes Satzes fest. Im Gegensatz zur Logik erster Ordnung, die nur eine Standardsemantik aufweist, gibt es zwei verschiedene Semantik, die üblicherweise für die Logik zweiter Ordnung verwendet werden: Standardsemantik und Henkin -Semantik. In jeder dieser Semantik sind die Interpretationen der Quantifizierer erster Ordnung und der logischen Konnektiven die gleiche wie in Logik erster Ordnung. Nur die Quantifiziererbereiche über Variablen zweiter Ordnung unterscheiden sich in den beiden Arten von Semantik (Väänänen 2001).

In der Standardsemantik, auch die vollständige Semantik genannt, reichen die Quantifizierer über alle Sätze oder Funktionen der entsprechenden Sortierung. Sobald die Domäne der Variablen erster Ordnung festgelegt ist, ist die Bedeutung der verbleibenden Quantifizierer festgelegt. Es ist diese Semantik, die die Ausdruckskraft zweiter Ordnung logisch verleihen, und sie werden für den Rest dieses Artikels angenommen.

Leon Henkin (1950) definierten eine alternative Art von Semantik für Theorien zweiter Ordnung und höherer Ordnung, in der die Bedeutung der Domänen höherer Ordnung teilweise durch eine explizite Axiomatisierung bestimmt wird und auf Typentheorievon den Eigenschaften der Sets oder Funktionen lag. Die Henkin-Semantik ist eine Art viel-sortierter Semantik erster Ordnung, bei der es eine Klasse von Modellen der Axiome gibt, anstatt dass die Semantik wie in der Standardsemantik auf das Standardmodell befestigt wird. Ein Modell in Henkin-Semantik liefert eine Reihe von Sätzen oder Funktionen als Interpretation von Domänen höherer Ordnung, die eine ordnungsgemäße Teilmenge aller Sätze oder Funktionen dieser Art sein können. Für seine Axiomatisierung bewies Henkin das Gödels Vollständigkeitstheorem und Kompaktheitstheorem, die für die Logik erster Ordnung gelten, übertragen Sie mit Henkin-Semantik auf Logik zweiter Ordnung. Da auch der Skolem -Löwenheim -Theorems für Henkin -Semantik halten, Lindströms Satz Importe, die Henkin -Modelle gerade sind Modelle erster Ordnung erbärmte Ordnung.^[4]

Für Theorien wie Arithmetik zweiter Ordnung ist das Vorhandensein nicht standardmäßiger Interpretationen von Domänen höherer Ordnung nicht nur ein Mangel der bestimmten Axiomatisierung, die aus der Typentheorie, die Henkin verwendete, abgeleitet ist, sondern eine notwendige Folge von Gödels Unvollständigkeitstheorem: Die Axiome von Henkin können nicht weiter ergänzt werden, um sicherzustellen, dass die Standardinterpretation das einzig mögliche Modell ist. Die Henkin -Semantik wird häufig in der Studie von verwendet Arithmetik zweiter Ordnung.

Jouko Väänänen (2001) argumentierte, dass die Wahl zwischen Henkin-Modellen und Vollmodellen für die Logik zweiter Ordnung analog zur Wahl zwischen der Wahl ist ZFC und V Als Grundlage für die festgelegte Theorie: "Wie bei der Logik zweiter Ordnung können wir nicht wirklich entscheiden, ob wir die Mathematik mithilfe der Mathematik axiomatisieren V oder ZFC. Das Ergebnis ist in beiden Fällen das gleiche wie ZFC ist Der bisher beste Versuch zu verwenden V Als Axiomatisierung der Mathematik. "

Ausdruckskraft

Logik der zweiten Ordnung ist ausdrucksstärker als Logik erster Ordnung. Zum Beispiel, wenn die Domäne der Satz von allen ist reale NummernMan kann in der Logik erster Ordnung die Existenz einer additiven Inverse jeder reellen Zahl durch Schreiben ∀ behaupten ∀x ∃y (x + y = 0) Aber man braucht Logik zweiter Ordnung, um die zu gründen am wenigsten gebunden Eigenschaft für reelle Zahlensätze, die besagt, dass jede begrenzte, nicht leere Reihe von reellen Zahlen a hat Supremum. Wenn die Domäne der Satz aller reellen Zahlen ist, drückt der folgende Satz zweiter Ordnung (über zwei Zeilen geteilt) die am wenigsten Obergrenze Eigenschaft aus:

(∀ a) ([(∃ w) (w ∈ A) ∧ (∃ z) (∀ u) (u ∈ A → u ≤ z)]

: → (∃ x) (∀ y) ([(∀ ∀ w) (w ∈ A → w ≤ x)] ∧ [(∀ ∀ u) (u ∈ A → u ≤ y)] → x ≤ y))

Diese Formel ist eine direkte Formalisierung von "jeder nicht leer, begrenzt set a hat eine am wenigsten Obergrenze. "Es kann gezeigt werden, dass jeder Bestellter Feld Das erfüllt diese Eigenschaft ist isomorph für das reelle Zahlenfeld. Andererseits hat der in den Real gültiger Satz erster Ordnung aufgrund des Kompaktheitstheorems willkürlich große Modelle. Somit kann die am wenigsten gebundene Eigenschaft nicht durch eine Reihe von Sätzen in Logik erster Ordnung ausgedrückt werden. (Tatsächlich alle Reales Feld erfüllt die gleichen Sätze erster Ordnung in der Signatur ${\ displayStyle \ Langle +, \ cdot, \ leq \ rangle}$ als reale Zahlen.)

In Logik zweiter Ordnung ist es möglich, formelle Sätze zu schreiben, die sagen: "Die Domäne ist endlich"oder" die Domäne ist von zählbar Kardinalität. "Um zu sagen, dass die Domain endlich ist, verwenden Sie den Satz, der sagt, dass jeder surjektiv Funktion von der Domäne zu sich selbst ist injektiv. Um zu sagen, dass die Domain zählbare Kardinalität hat, verwenden Sie den Satz, der besagt, dass es a gibt Bijection zwischen zwei unendlichen Untergruppen der Domäne. Es folgt aus dem Kompaktheitstheorem und die Nach oben Löwenheim -Skolem Theorem Dass es nicht möglich ist, die Endlichkeit bzw. die Zählbarkeit in Logik erster Ordnung zu charakterisieren.

Bestimmte Fragmente der Logik zweiter Ordnung wie ESO sind ebenfalls ausdrucksstärker als Logik erster Ordnung, obwohl sie streng weniger ausdrucksstark sind als die Logik zweiter Ordnung. ESO genießt auch die Übersetzungsäquivalenz mit einigen Erweiterungen der Logik erster Ordnung, die die nichtlineare Reihenfolge von Quantifiziererabhängigkeiten ermöglichen, wie die Logik erster Ordnung mit erweiterter Logik Henkin -Quantifizierer, Hintikka und Sandu Unabhängigkeitsfreundliche Logikund Väänänens Abhängigkeitslogik.

Deduktive Systeme

A deduktives System Für eine Logik ist ein Satz von Inferenzregeln und logische Axiome, die bestimmen, welche Sequenzen von Formeln gültige Beweise darstellen. Für die Logik zweiter Ordnung können mehrere deduktive Systeme verwendet werden, obwohl keine für die Standardsemantik abgeschlossen sein kann (siehe unten). Jedes dieser Systeme ist KlangDies bedeutet, dass jeder Satz, den sie beweisen können, in der entsprechenden Semantik logisch gültig ist.

Das schwächste deduktive System, das verwendet werden kann, besteht aus einem Standard-Deduktionssystem für Logik erster Ordnung (wie z. natürlicher Abzug) Augmentiert mit Substitutionsregeln für Begriffe zweiter Ordnung.^[5] Dieses deduktive System wird häufig in der Studie von verwendet Arithmetik zweiter Ordnung.

Die von Shapiro (1991) und Henkin (1950) berücksichtigten deduktiven Systeme tragen zum erweiterten deduktiven Schema erster Ordnung sowohl Verständnis-Axiome als auch Auswahl-Axiome bei. Diese Axiome sind für Semantik zweiter Ordnung ein Ton. Sie sind solide für Henkin -Semantik, die auf Henkin -Modelle beschränkt sind, die das Verständnis und die Auswahl von Axiomen erfüllen.^[6]

Nichtreduzierbarkeit zur Logik erster Ordnung

Man könnte versuchen, die Theorie der realen Zahlen zweiter Ordnung mit voller Semantik zweiter Ordnung auf die Theorie erster Ordnung auf folgende Weise zu reduzieren. Erweitern Sie zuerst die Domäne vom Satz aller realen Zahlen auf eine zwei-sortierte Domäne, wobei die zweite Sorte alle enthält Gruppen von reale Nummern. Fügen Sie der Sprache ein neues binäres Prädikat hinzu: die Mitgliedschaftsbeziehung. Dann werden Sätze zweiter Ordnung erster Ordnung, wobei die früheren Quantifizierer zweiter Ordnung stattdessen über die zweite Sorte liegen. Diese Reduzierung kann in einer einsortierten Theorie versucht werden, indem unäre Prädikate hinzugefügt werden, die feststellen, ob ein Element eine Zahl oder ein Satz ist, und die Domäne als Vereinigung der reellen Zahlen und der Leistungssatz der realen Zahlen.

Beachten Sie jedoch, dass die Domäne geltend gemacht wurde, um einzuschließen alle Sätze realer Zahlen. Diese Anforderung kann nicht auf einen Satz erster Ordnung reduziert werden, wie die Löwenheim -Skolem -Theorem zeigt an. Dieser Satz impliziert, dass es einige gibt Zähler Unendlich unendlich Teilmenge der realen Zahlen, deren Mitglieder wir anrufen werden interne Zahlenund einige zähe unendliche Sammlung von Sätzen interner Zahlen, deren Mitglieder wir "intern und Sätze realer Zahlen. Insbesondere erfüllt es eine Art von am wenigsten gebundenem Axiom, das betrifft:

Die Zählbarkeit des Satzes aller internen Zahlen (in Verbindung mit der Tatsache, dass diejenigen einen dicht geordneten Satz bilden) impliziert, dass dieser Satz das vollständige Axiom mit kleinsten Upper nicht erfüllt. Zählbarkeit des Satzes von allen intern Sets impliziert, dass es nicht der Satz von ist alle Teilmengen des Satzes von allen intern Zahlen (seit Cantors Theorem Impliziert, dass die Menge aller Teilmengen eines zähnen unendlichen Sets ein unkompliziert unendlich unendlichem Set ist). Diese Konstruktion ist eng mit dem verwandt mit Skolems Paradoxon.

Somit hat die Theorie erster Ordnung der realen Zahlen und Mengen realer Zahlen viele Modelle, von denen einige zählbar sind. Die Theorie zweiter Ordnung der realen Zahlen hat jedoch nur ein Modell. Dies folgt aus dem klassischen Theorem, dass es nur einen gibt Archimedan Vollständiges FeldZusammen mit der Tatsache, dass alle Axiome eines archimedischen vollständigen geordneten Feldes in Logik zweiter Ordnung exprimiert sind. Dies zeigt, dass die Theorie zweiter Ordnung der realen Zahlen nicht auf eine Theorie erster Ordnung reduziert werden kann, in dem Sinne, dass die Theorie zweiter Ordnung der reellen Zahlen nur ein Modell hat, aber die entsprechende Theorie erster Ordnung viele Modelle hat.

Es gibt extremere Beispiele, die zeigen, dass Logik zweiter Ordnung mit Standardsemantik ausdrucksvoller ist als Logik erster Ordnung. Es gibt eine endliche Theorie zweiter Ordnung, deren einziges Modell die realen Zahlen ist, wenn die Kontinuumshypothese hält und das hat kein Modell, wenn die Kontinuumshypothese nicht gilt (vgl. Shapiro 2000, S. 105). Diese Theorie besteht aus einer endlichen Theorie, die die realen Zahlen als ein vollständig archimedisch geordnetes Feld und ein Axiom charakterisiert, dass die Domäne von der ersten unzähligen Kardinalität ist. Dieses Beispiel zeigt, dass die Frage, ob ein Satz in der Logik zweiter Ordnung konsistent ist, äußerst subtil ist.

Zusätzliche Einschränkungen der Logik zweiter Ordnung werden im nächsten Abschnitt beschrieben.

Metallogische Ergebnisse

Es ist eine Folge von Gödels Unvollständigkeitstheorem dass es kein deduktives System gibt (dh keine Vorstellung von Vorsicht) für Formeln zweiter Ordnung, die diese drei gewünschten Attribute gleichzeitig erfüllen:^[7]

• (Solidität) Jeder nachweisbare Satz zweiter Ordnung ist allgemein gültig, d. H. In allen Domänen unter Standardsemantik.
• (Vollständigkeit) Jede allgemein gültige Formel zweiter Ordnung unter Standardsemantik ist nachweisbar.
• (Wirksamkeit) Da ist ein Proofprüfung Algorithmus, der korrekt entscheiden kann, ob eine bestimmte Abfolge von Symbolen ein Beweis ist oder nicht.

Diese Folge wird manchmal ausgedrückt, indem die Logik zweiter Ordnung keine vollständige zulässt Beweistheorie. In dieser Hinsicht unterscheidet sich die Logik zweiter Ordnung mit Standardsemantik von der Logik erster Ordnung; Quine (1970, S. 90–91) wies auf das Fehlen eines vollständigen Beweissystems als Grund für das Denken einer Logik zweiter Ordnung wie nicht hin Logikrichtig genommen.

Wie oben erwähnt, hat Henkin bewiesen, dass das deduktive Standardsystem für Logik erster Ordnung solide, vollständig und effektiv für Logik zweiter Ordnung mit ist Henkin -Semantikund das deduktive System mit Verständnis- und Auswahlprinzipien ist für die Henkin -Semantik solide, vollständig und effektiv, indem nur Modelle diese Prinzipien erfüllt werden.

Das Kompaktheitstheorem und die Löwenheim -Skolem -Theorem Halten Sie keine vollständigen Modelle der Logik zweiter Ordnung. Sie halten jedoch für Henkin -Modelle.^{[8]: Xi}

Geschichte und umstrittener Wert

Die Prädikatlogik wurde in die mathematische Gemeinschaft von eingeführt C. S. Peirce, der den Begriff geprägt hat Logik zweiter Ordnung und deren Notation der modernen Form am ähnlichsten ist (Putnam 1982). Heute sind die meisten Schüler der Logik jedoch mit den Werken von besser vertraut Frege, der seine Arbeiten einige Jahre vor Peirce veröffentlichte, deren Werke jedoch noch weniger bekannt waren, bis Bertrand Russell und Alfred North Whitehead machte sie berühmt. Frege verwendete verschiedene Variablen, um die Quantifizierung über Objekte von der Quantifizierung über Eigenschaften und Sätze zu unterscheiden; Aber er sah sich nicht als zwei verschiedene Arten von Logik. Nach der Entdeckung von Russells Paradox Es wurde erkannt, dass etwas mit seinem System nicht stimmte. Schließlich stellten Logiker fest, dass die Beschränkung der Frege -Logik auf verschiedene Weise - auf das, was jetzt genannt wird Logik erster Ordnung-Dieses Problem Eliminiert: Sätze und Eigenschaften können nicht allein in Logik erster Ordnung quantifiziert werden. Die inzwischen festgelegte Hierarchie der Anordnungen der Logik stammt aus dieser Zeit.

Man fand heraus, dass Mengenlehre könnte als axiomatisiertes System innerhalb des Apparats der Logik erster Ordnung (auf Kosten verschiedener Arten von Vollständigkeit, aber nichts so schlimm wie Russells Paradoxon), und das wurde getan (siehe Zermelo -Fraenkel -Set -Theorie), wie Sätze für entscheidend für Mathematik. Arithmetik, Mereologieund eine Vielzahl anderer mächtiger logischer Theorien könnten axiomatisch formuliert werden Gödel und SkolemDie Einhaltung der Logik erster Ordnung führte zu einem allgemeinen Abfall der Arbeit in der zweiten (oder einer höheren) Ordnung Logik.

Diese Ablehnung wurde von einigen Logikanern aktiv vorgegangen W. V. Quine. Quine hat die Ansicht fortgeschritten, die in prädikatübergreifenden Sätzen wie wie Fx das "x"soll als Variable oder Name ein Objekt bezeichnen, und kann daher wie in" für alle Dinge "quantifiziert werden. . ." aber die "F"soll als als angesehen werden Abkürzung für einen unvollständigen Satz nicht der Name eines Objekts (nicht einmal eines abstraktes Objekt wie eine Eigenschaft). Zum Beispiel könnte es bedeuten "... ist ein Hund." Aber es macht keinen Sinn zu glauben, dass wir über so etwas quantifizieren können. (Eine solche Position steht im Einklang mit den eigenen Argumenten von Freges auf die Konzept-Objekt Unterscheidung). Um ein Prädikat als Variable zu verwenden, muss es den Platz eines Namens einnehmen, die nur einzelne Variablen besetzen sollten. Diese Argumentation wurde von abgelehnt George Boolos.

In den vergangenen Jahren^[wenn?] Die Logik zweiter Ordnung hat eine Genesung gemacht, die durch die Interpretation der Quantifizierung zweiter Ordnung als Boolos als Bevölkerungszahl betrieben wurde Pluralquantifizierung über dieselbe Domäne von Objekten wie Quantifizierung erster Ordnung (Boolos 1984). Boolos verweist außerdem auf die Behaupteten Nicht -Firstorderizierbarkeit von Sätzen wie "Einige Kritiker bewundern nur einander" und "Einige von Fianchettos Männern gingen in das Lagerhaus, das von irgendjemandem unbegleitet wurde", von dem er argumentiert, dass er nur durch die volle Kraft der Quantifizierung zweiter Ordnung ausgedrückt werden kann. Jedoch, Verallgemeinerte Quantifizierung und teilweise bestellt (oder Verzweigungen) Die Quantifizierung kann ausreichen, um eine bestimmte Klasse angeblich nicht ordentlicher Sätze auszudrücken, und diese appellieren nicht an die Quantifizierung zweiter Ordnung.

Beziehung zur rechnerischen Komplexität

Die ausdrucksstarke Kraft verschiedener Formen der Logik zweiter Ordnung auf endlichen Strukturen ist eng gebunden mit Computerkomplexitätstheorie. Das Feld von Beschreibende Komplexität Studien, die rechnerisch Komplexitätsklassen kann durch die Kraft der Logik gekennzeichnet werden, die zum Ausdruck von Sprachen (in ihnen Sätze von endlichen Zeichenfolgen) erforderlich ist. Ein Faden w=w₁···w_n in einem endlichen Alphabet A kann durch eine endliche Struktur mit Domäne dargestellt werden D= {1, ...,n}, unäre Prädikate P_a für jeden a∈A, zufrieden mit diesen Indizes i so dass w_i=aund zusätzliche Prädikate, die dazu dienen, eindeutig zu identifizieren, welcher Index welcher ist (normalerweise nimmt man die Grafik der Nachfolgerfunktion auf D oder die Ordnungsbeziehung <, möglicherweise mit anderen arithmetischen Prädikaten). Umgekehrt das Cayley -Tische von jeder endlichen Struktur (über eine endliche endliche Struktur Unterschrift) kann durch eine endliche Zeichenfolge codiert werden.

Diese Identifizierung führt zu den folgenden Charakteren von Varianten der Logik zweiter Ordnung gegenüber endlichen Strukturen:

• Reg (der Satz von reguläre Sprachen) ist definierbar durch monadische Formeln zweiter Ordnung (Hüchis Theorem, 1960)
• Np ist der Satz von Sprachen, die von existenziellen Formeln zweiter Ordnung definierbar sind (Formeln zweiter Ordnung (Fagins Theorem, 1974).
• Co-NP ist der Satz von Sprachen, die durch universelle Formeln zweiter Ordnung definierbar sind.
• PH ist der Satz von Sprachen definierbar durch Formeln zweiter Ordnung.
• PSPACE ist der Satz von Sprachen definierbar durch Formeln zweiter Ordnung mit einem hinzugefügten Transitive Schließung Operator.
• Nachfolger ist der Satz von Sprachen definierbar durch Formeln zweiter Ordnung mit einem hinzugefügten am wenigsten fester Punkt Operator.

Beziehungen zwischen diesen Klassen beeinflussen direkt die relative Ausdruckskraft der Logik über endliche Strukturen; Zum Beispiel wenn PH=PSPACEWenn Sie dann einen transitiven Verschlussbetreiber in die Logik zweiter Ordnung hinzufügen, würde dies nicht ausdruckswerter über endliche Strukturen machen.

Siehe auch

• Logik erster Ordnung
• Logik höherer Ordnung
• Löwenheim -Nummer
• Omega -Sprache
• Second-order propositional logic
• Monadische Logik zweiter Ordnung

Anmerkungen

Verweise

• Andrews, Peter (2002). Eine Einführung in die mathematische Logik und Typtheorie: zur Wahrheit durch Beweise (2. Aufl.). KLUWER Academic Publishers.
• Boolos, George (1984). "Um zu sein, ist ein Wert einer Variablen (oder einige Werte einiger Variablen) zu sein." Journal of Philosophy. 81 (8): 430–50. doi:10.2307/2026308. JStor 2026308.. In Boolos nachgedruckt, Logik, Logik und Logik, 1998.
• Henkin, L. (1950). "Vollständigkeit in der Theorie der Typen". Zeitschrift für symbolische Logik. 15 (2): 81–91. doi:10.2307/2266967. JStor 2266967.
• Hinman, P. (2005). Grundlagen der mathematischen Logik. A k Peters. ISBN 1-56881-262-0.
• Putnam, Hilary (1982). "Peirce der Logiker". Historia Mathematica. 9 (3): 290–301. doi:10.1016/0315-0860 (82) 90123-9.. Nachdruck in Putnam, Hilary (1990), Realismus mit einem menschlichen Gesicht, Harvard University Press, S. 252–260.
• W. V. Quine (1970). Logikphilosophie. Prentice Hall. ISBN 9780674665637.
• Rossberg, M. (2004). "Logik erster Ordnung, Logik zweiter Ordnung und Vollständigkeit" (PDF). In V. Hendricks; et al. (Hrsg.). Logik erster Ordnung überarbeitet. Berlin: Logos-Verlag.
• Shapiro, S. (2000) [1991]. Grundlagen ohne Fundamentalismus: Ein Fall für die Logik zweiter Ordnung. Oxford: Clarendon Press. ISBN 0-19-825029-0.
• Väänänen, J. (2001). "Logik der zweiten Ordnung und Grundlagen der Mathematik" (PDF). Bulletin der symbolischen Logik. 7 (4): 504–520. Citeseerx 10.1.1.25.5579. doi:10.2307/2687796. JStor 2687796. S2CID 7465054.

Weitere Lektüre

• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, yde; Weinstein, Scott (2007). Finite -Modell -Theorie und ihre Anwendungen. Texte in theoretischer Informatik. Eine EATCS -Serie. Berlin: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.

• Väänänen, Jouko. Edward N. Zalta (Hrsg.). Logik der zweiten Ordnung und höherer Ordnung. Die Stanford -Enzyklopädie der Philosophie (Ausgabe von Herbst 2021).