Welche Beziehung besteht zwischen der Logik erster Ordnung und der Theorie erster Ordnung?

Ich dachte, dass jeder FOT eine Teilmenge von FOL ist, aber das scheint nicht der Fall zu sein, da FOL vollständig ist (jede Formel ist entweder gültig oder ungültig), während einige FOT (wie lineare Ganzzahlarithmetik) nicht vollständig sind.

Ist FOL ausdrucksstärker als FOT? Oder unvergleichlich?

Auch die Aussage "Es gibt Aussagen, die in LIA gültig sind, aber mit Axiomen von LIA nicht bewiesen werden können" ist seltsam. Wie kann die Aussage gültig sein, wenn wir ihre Gültigkeit nicht nachweisen können? Ich habe immer gedacht, wenn Sie die Gültigkeit der Aussage nicht nachweisen können, können Sie nicht behaupten, dass sie gültig ist.

logic first-order-logic Ayrat
quelle

Ich denke, dass die Aussage "Es gibt Aussagen, die in LIA gültig sind, aber nicht mit Axiomen von LIA bewiesen werden können" falsch ist. Der Vollständigkeitssatz von Godel stellt sicher, dass eine gültige Aussage schließlich in einer begrenzten Zeitspanne bewiesen werden kann. Ich denke, dass Sie logische Gültigkeit mit logischer Wahrheit verwechseln. Das sind zwei verschiedene Dinge. Die Bedeutung der Vollständigkeit, die im Vollständigkeitssatz von Gödel verwendet wird, und die im Unvollständigkeitssatz verwendete, ist nicht dieselbe.

Rotia

Antworten:

Logik erster Ordnung ist ein mathematisches Thema , das viele verschiedene Konzepte, wie definiert erster Ordnung Formel , erster Ordnung Struktur , erster Ordnung Theorie , und viele mehr. Eines dieser Konzepte ist die Theorie erster Ordnung : Es handelt sich um eine Reihe von Formeln erster Ordnung. Oft betrachten wir die Theorie erster Ordnung, die durch eine endliche Anzahl von Axiomen und Axiomschemata erzeugt wird. Eine solche Theorie ist in Bezug auf logische Ableitungen geschlossen , und wir betrachten normalerweise nur Theorien, die diese Bedingung erfüllen.

Eine Theorie erster Ordnung ist vollständig, wenn sie für jede Aussage entweder oder ihre Negation enthält. Nicht jede Theorie ist vollständig. In der Tat unterstreicht Gödels Unvollständigkeitssatz, dass viele interessante Theorien erster Ordnung notwendigerweise unvollständig sind. $\sigma$ $\sigma$

Ein Modell einer Theorie erster Ordnung ist eine gültige Interpretation der Theorie (wir belassen die genaue Definition für Lehrbücher). Zum Beispiel besteht die Gruppentheorie erster Ordnung aus allen Aussagen, die sich aus den Gruppenaxiomen ergeben. Jede Gruppe ist ein Modell der Gruppentheorie erster Ordnung.

Für jedes gegebene Modell ist ein sehr gegebener Satz entweder wahr oder falsch. Gödels Vollständigkeitssatz besagt, dass ein Satz erster Ordnung, wenn er in allen Modellen einer Theorie erster Ordnung wahr ist, aus einer endlichen Anzahl von Sätzen in der Theorie beweisbar ist. Zum Beispiel ist jede Aussage erster Ordnung in der Sprache der Gruppen, die für alle Gruppen gilt, aus den Gruppenaxiomen beweisbar.

LIA ist (vermutlich) eine Theorie erster Ordnung, die interessant genug ist, um aufgrund des Unvollständigkeitssatzes von Gödel unvollständig zu sein. Im Standardmodell - den "wahren" ganzen Zahlen - ist jedoch jeder Satz entweder wahr oder falsch. Insbesondere wenn eine Aussage ist, bei der weder noch zu LIA gehören, gilt entweder oder für die wahren ganzen Zahlen, aber diese Tatsache ist in LIA nicht beweisbar. $\sigma$ $\sigma$ $\lnot \sigma$ $\sigma$ $\lnot \sigma$

Yuval Filmus
quelle

Was ist das Besondere an "vollständigen" Theorien? warum sind sie interessant "Natürlich" sind viele Theorien unvollständig, weil der Mangel an Vollständigkeit fragt, ob ein Satz für alle Modelle wahr ist . Zur Unvollständigkeit: Im "Standard-Integer-Modell" kümmern wir uns nicht um alle Modelle, die die Axiome erfüllen, wir haben nur ein "Standard-Integer-Modell". Weist der Unvollständigkeitssatz nicht darauf hin, dass die Art und Weise, wie wir Gültigkeit definieren (insbesondere unsere Berücksichtigung aller Modelle, die die Axiome erfüllen), unangemessen ist?

Ayrat

Vollständige Theorien sind etwas Besonderes, da sie für jede Aussage einen bestimmten Wahrheitswert angeben. Das möchten Sie gerne haben. Der Rest Ihrer Fragen gehört zum Bereich der Philosophie. Der Vollständigkeitssatz von Gödel setzt jedoch die Gültigkeit in allen Modellen mit der Beweisbarkeit gleich.

Yuval Filmus

Ich sehe die Nützlichkeit immer noch nicht - betrachte FOL, das vollständig ist: Angenommen, Sie möchten überprüfen, ob F gültig ist oder nicht: 'Vollständigkeit' hilft nicht viel, wenn F ungültig ist, da die Gültigkeit von FOL halb entscheidbar ist. Vermisse ich etwas

Ayrat

Die Aussage "Logik erster Ordnung ist vollständig" ist entweder bedeutungslos oder falsch.

Yuval Filmus

Es ist nicht wahr, dass eine Theorie erster Ordnung eine konsistente Menge von Sätzen erster Ordnung ist. Das Richtige zu sagen ist: Eine Theorie erster Ordnung ist eine Reihe von Formeln erster Ordnung , die unter Abzug geschlossen werden. Ich kann durchaus eine inkonsistente Theorie formulieren. Es kann Jahre dauern, bis wir feststellen, dass es inkonsistent ist. Und eine Theorie kann Formeln enthalten, nicht nur Sätze (die geschlossene Formeln sind).

Andrej Bauer

Der Ausdruck "Logik erster Ordnung" hat zwei Bedeutungen:

Es ist ein Kapitel der mathematischen Logik, in dem wir bestimmte Arten formaler Systeme und alles, was damit zusammenhängt, untersuchen.
Es ist eine spezielle Art von Theorie erster Ordnung, nämlich die, die durch eine leere Signatur und einen leeren Satz von Axiomen erzeugt wird.

Ihre Frage bezieht sich auf die zweite Bedeutung, aber um dies zu verstehen, müssen wir Dinge aufbauen:

Es gibt eine bestimmte formale Sprache, die als Sprache der Logik erster Ordnung bezeichnet wird . Informell gesprochen ist es das Zeug, das Sie aus Variablen, Gleichheit, , , , , und . Dieses Zeug ist als Formeln erster Ordnung bekannt . $\land$ $\lor$ $\lnot$ $\Rightarrow$ $\forall$ $\exists$
Es gibt ein bestimmtes formales System namens Logik erster Ordnung, das uns sagt, was es bedeutet, dass wir eine Formel erster Ordnung beweisen . Das System wird als Satz von Inferenzregeln angegeben.
Eine Theorie erster Ordnung $\mathcal{T}$ ist gegeben durch:
- eine Signatur $\Sigma_{\mathcal{T}}$ die aus einer Reihe von Konstanten, Funktionssymbolen und Beziehungssymbolen besteht. Stellen Sie sich diese als Erweiterungen der Grundsprache der Logik erster Ordnung vor. Wir nennen es die Sprache von . $\mathcal{T}$
- ein deduktiv geschlossener Satz von Formeln erster Ordnung, die in der durch die Unterschrift erweiterten Sprache geschrieben sind.

Eine Menge von Formeln wird als deduktiv geschlossen bezeichnet, wenn irgendeine Anwendung von Inferenzregeln der Logik erster Ordnung auf Formeln in Formeln ergibt, die wiederum in . Mit anderen Worten, enthält alle seine logischen Konsequenzen. Ein üblicher Weg, eine solche Menge erstellen, ist: Beginnen Sie mit einer ausgewählten Menge von Formeln und fügen Sie alle logischen Konsequenzen und die Konsequenzen dieser Konsequenzen hinzu und so weiter. Dies wird als deduktiver Abschluss von . Wir nennen die Formeln oft in Axiomen . $S$ $S$ $S$ $S$ $S$ $A$ $A$ $A$

Eine Theorie kann vollständig sein oder nicht. Es ist nicht wichtig zu wissen, was "vollständig" hier bedeutet, aber es ist wichtig zu wissen, dass Folgendes passieren kann: Wir können zwei Sätze von Formeln und , so dass , der deduktive Abschluss von ist vollständige Theorie, und der deduktive Abschluss von ist keine vollständige Theorie. $A$ $B$ $A \subseteq B$ $A$ $B$

Wir sind jetzt bereit, Ihre Frage zu beantworten. Sei die Theorie, deren Signatur leer ist und deren Formelsatz der deduktive Abschluss der leeren Menge ist. Sei die Theorie, deren Signatur die der Peano-Arithmetik ist (Konstante , unäre Operation , binäre Operationen und ), und die Formeln sind der deduktive Abschluss von Peano-Axiomen. Es ist ein Fakt, dass $T$ $P$ $0$ $S$ $+$ $\times$

$T$ ist in (tatsächlich ist in jeder Theorie enthalten), $P$ $T$
$T$ ist vollständig,
$P$ ist nicht vollständig.

Die Theorie wird im Volksmund "Logik erster Ordnung" genannt, aber dies ist wirklich eine Fehlbezeichnung. Einige Leute sind etwas präziser und nennen es "die reine Theorie der Logik erster Ordnung". $T$

Zusammenfassend ergab Ihre Frage Folgendes:

Sie wussten nicht, dass sich "Logik erster Ordnung" auf die Theorie mit leerer Signatur beziehen kann, die durch die leeren Axiome erzeugt wird.
Eine vollständige Theorie kann unvollständig werden, wenn wir sie erweitern.
Sie haben die falsche Definition der Vollständigkeit verwendet. Die richtige Definition lautet: Eine Theorie ist vollständig, wenn jeder Satz oder seine Negation ein Theorem der Theorie ist.

NB: Ein Satz ist eine geschlossene Formel (eine, die keine freien Variablen enthält).

Lassen Sie mich zum Schluss Ihre Frage zur Gültigkeit beantworten:

Eine Formel ist nachweisbar, wenn es einen Beweis dafür gibt
Eine Formel ist gültig, wenn sie in jedem Modell wahr ist

Ein grundlegender Metasatz über die Logik erster Ordnung ist, dass jede nachweisbare Formel gültig ist. Das Gegenteil gilt auch und ist als Gödels Vollständigkeitssatz bekannt .

Es kommt jedoch häufig vor, dass in einer bestimmten Situation aus gutem Grund absichtlich ein Missverhältnis zwischen Gültigkeit und Beweisbarkeit hergestellt wird. Wenn wir zum Beispiel die Aufmerksamkeit auf endliche Modelle beschränken, kann es leicht vorkommen, dass es gültige Aussagen gibt, die keinen Beweis haben. Warum sollte man das tun? In der Informatik könnte dies aus algorithmischen Gründen sein oder weil man sich nur für eine bestimmte Klasse von Modellen interessiert.

Sie sagen: "Der einzige Weg zu wissen, dass ein Satz gültig ist, besteht darin, ihn zu beweisen." Dies mag auf einer informellen Ebene der Fall sein (ich denke, Gott würde Ihnen nicht zustimmen), aber beachten Sie, dass ein solcher Beweis der Gültigkeit außerhalb der Theorie auf der Metaebene erfolgt. Da die Feststellung der Gültigkeit erfordert, dass über alle Modelle gesprochen wird, ist dies sicherlich nicht etwas, was wir innerhalb der Theorie erwarten würden.

Andrej Bauer
quelle

Sie scheinen sich über den Vollständigkeitssatz von Godel und den Unvollständigkeitssatz von Godel verwechselt zu haben. Was Sie "Godels Unvollständigkeitssatz" nennen, scheint eine direkte Negation von Godels Vollständigkeitssatz zu sein. Gödels erster Unvollständigkeitssatz handelt von Sätzen, die weder bewiesen noch widerlegt werden können, nicht von Sätzen, die gültig, aber nicht beweisbar sind.

user2357112 unterstützt Monica

Danke, ich habe dieses Bit gerade gelöscht, weil es der Erklärung nichts hinzufügt.

Andrej Bauer

@AndrejBauer Könnten Sie das folgende 'Paradoxon' mit "1. ist in " klären ? : Da existiert unvollständig dann ist , so dass und . Fragen Sie jetzt " "? Da (deduktive Verschlüsse ihrer Axiome) ist, sollte es entweder oder , aber beide verletzen die Annahme der Existenz solcher !

T

$T$

P

$P$

P

$P$

s

$s$

s \notin P

$s \not\in P$

\neg s \notin P

$\neg s \not\in P$

s \in T

$s \in T$

T \subset P

$T \subset P$

s \in T

$s \in T$

\neg s \in T

$\neg s \in T$

s

$s$

Ayrat

eine andere Frage: Haben Sie ein Beispiel für eine gültige Aussage, für die es keinen Beweis gibt?

Ayrat

Eine kleine Klarstellung:

Sie denken vielleicht, dass die Theorie mit leerer Signatur eine leere Theorie ist, dh keine geschlossenen Formeln enthält. Das ist falsch. Die Logik erster Ordnung erlaubt es, bestimmte geschlossene Formeln, die als Tautologien bekannt sind, ohne Berufung auf Axiome zu beweisen . Diese sind allein aufgrund ihrer Form „wahr“; Sie haben keinen aussagekräftigen Inhalt als solchen. Der Vollständigkeitssatz von Godel besagt dann, dass die Sammlung von Tautologien vollständig ist - dh alle geschlossenen Formeln, die gültig sind (dh in allen Modellen wahr sind), können tatsächlich in der Logik erster Ordnung abgeleitet werden. [Der Beweis ist interessant und entschieden nicht trivial.]

PMar
quelle