Techniken zum Nachweis der Nichtableitbarkeit in Logiken und anderen formalen Beweissystemen

Wenn man in Beweissystemen für die klassische Aussagenlogik zeigen will, dass eine bestimmte Formel nicht ableitbar ist, zeigt man einfach, dass abgeleitet werden kann (obwohl andere Techniken durchaus möglich sind). Die Nichtableitbarkeit ergibt sich im Wesentlichen aus der Richtigkeit und Vollständigkeit des Beweissystems. $\psi$ $\neg\psi$

Leider gibt es für nicht-klassische Logiken und exotischere Beweissysteme (wie die Regeln, die der operativen Semantik zugrunde liegen) keine solche direkte Technik. Dies könnte daran liegen, dass die Nichtableitbarkeit von nicht impliziert, dass ableitbar ist, wie es bei der intuitionistischen Logik der Fall ist, oder einfach, dass kein Negationsbegriff existiert. $\psi$ $\neg\psi$

Meine Frage erhält ein Beweissystem , wobei $(\mathcal{L},\vdash)$ , (und vermutlich seine Semantik), welche Techniken gibt es, um die Nichtableitbarkeit zu zeigen? $\vdash\;\subseteq\mathcal{L}^*\times\mathcal{L}$

Zu den relevanten Beweissystemen könnten operative Semantik von Programmiersprachen, Hoare-Logik, Typsysteme, eine nicht-klassische Logik oder Inferenzregeln für das, was Sie haben, gehören.

lo.logic Dave Clarke
quelle

Dave, ich denke, es ist ein Tippfehler in der Frage, um zu zeigen, dass

nicht ableitbar ist, wir zeigen nicht, dass

ableitbar ist, wir zeigen nur, dass es konsistent ist, und dies basiert nur auf der Konsistenz der klassischen Logik. Wenn die Logik klassische Logik erster Ordnung ist, dann gibt es Sätze, die wir weder beweisen noch widerlegen können (es sei denn, wir sprechen über eine vollständige Theorie ). Oder verstehe ich deine Frage falsch?

φ

$\varphi$

\neg φ

$\lnot \varphi$

Kaveh

Ich habe es in klassische Aussagenlogik geändert. Die Frage fragt nach einer anderen Technik als dem Beweis der Negation, da viele formale Systeme (Ansammlungen von Axiomen und Folgerungsregeln) keine Negation haben oder in der Tat nicht einmal wie "Logik" aussehen können.

Dave Clarke

Vielen Dank für die Klarstellung, meine Gedanken gehen standardmäßig zur Logik erster Ordnung, wenn ich klassische Logik lese. :)

Kaveh

Antworten:

IME ist die folgende Liste am einfachsten bis am schwierigsten (natürlich ist sie auch am wenigsten bis am leistungsfähigsten):

Wenn Ihr System einwandfrei ist und Sie nachweisen können , dann haben Sie natürlich ein Unwägbarkeitsergebnis. $\lnot \phi$
Wenn Sie eine gittertheoretische Semantik für Ihre Logik haben, für die alle Ihre Beweisregeln gültig sind, dann ist die Bedeutung eines Satzes nicht das oberste Element des Gitters, dann ist es kein ableitbarer Satz.
Wenn Sie wissen, dass Ihre Logik in Bezug auf eine Klasse von Modellen vollständig ist, prüfen Sie, ob es in dieser Klasse ein bestimmtes Modell gibt, das ungültig macht . $\phi$
Manchmal kann man mit einer Übersetzung in eine andere Logik davonkommen und zeigen, dass Ableitbarkeit hier drüben ein bekanntes Nicht-Ableitbarkeitsergebnis impliziert.
Wenn Sie einen natürlichen Abzug oder eine Folgerechnung haben, prüfen Sie, ob ein Ergebnis der Schnitteliminierung bekannt ist oder ob Sie dies nachweisen können. Wenn dies der Fall ist, können Sie die Subformula-Eigenschaft häufig ausnutzen, um einfache induktive Argumente zur Nicht-Aktivierbarkeit zu liefern. (Zum Beispiel ist Konsistenz durch Schnitteliminierung nur die Aussage, dass es keine schnittfreien Beweise für falsch gibt. Wenn also alle Schnitte beseitigt werden können, gibt es keine Inkonsistenzen.)
Wenn nichts anderes funktioniert, können Sie häufig Konsistenz- / Nichtdifferenzierbarkeitsergebnisse über ein logisches Beziehungsargument anzeigen. Dies ist die große Waffe, die funktioniert, wenn nichts anderes es tut - in satztheoretischen Begriffen läuft sie auf die Verwendung des Ersatzaxioms hinaus, mit dem Sie zeigen können, dass große Mengen geordnet sind. (Deshalb können Sie es verwenden, um Dinge wie die Normalisierung von System F zu beweisen.)

Neel Krishnaswami
quelle

F

$F$

P A^{2}

$PA^2$

F^{2}

$F^2$

Danke, ich verstehe jetzt, was Sie unter "Normalisierung von System F" verstanden haben. :)

Kaveh

@Kaveh, @Neel: Die starke Normalisierung von System F ist kein Satz von PA2, sondern entspricht über PA der Konsistenz von PA2. Vielmehr starke Normalisierung für alle Terme des Rangs n (Rang das Maß für die Tiefe der maxiumum nsted Typ Quantifizierer ist) kann unter Verwendung von ACA- nachgewiesen werden n . Ich rede gern davon, Garbenmodelle im Geheimen zu bauen ...

Charles Stewart

@Charles: Ich habe von dieser Idee aus einigen Aufsätzen von Jean Gallier erfahren, die überraschenderweise unterbewertet sind. Etwas perverserweise hat mir diese ausgefallene Ansicht geholfen, den einfacheren Bericht von Mitchell & Scedrov zu verstehen.

Neel Krishnaswami