Wie kann festgestellt werden, ob ein Beweis „Argumentationstechniken höherer Ordnung“ erfordert?

15

Die Frage:

Angenommen, ich habe eine Spezifikation eines Problems, das aus Axiomen und einem Ziel besteht (dh das zugehörige Beweisproblem ist, ob das Ziel unter Berücksichtigung aller Axiome erfüllbar ist). Nehmen wir auch an, dass das Problem keine Inkonsistenzen / Widersprüche zwischen den Axiomen enthält. Gibt es eine Möglichkeit, im Voraus zu bestimmen (dh ohne zuerst einen vollständigen Beweis zu erstellen), dass der Beweis des Problems "Argumentation höherer Ordnung" erfordert?

Mit "Argumentation höherer Ordnung" meine ich das Anwenden von Beweisschritten, die das Aufschreiben von Logik höherer Ordnung erfordern. Ein typisches Beispiel für "Argumentation höherer Ordnung" wäre Induktion: Das Aufschreiben eines Induktionsschemas erfordert im Prinzip die Verwendung von Logik höherer Ordnung.

Beispiel:

Man kann das Beweisproblem "Ist die Addition auf zwei natürliche Zahlen kommutativ?" Verwenden der Logik erster Ordnung (dh Definieren der natürlichen Zahl über Konstruktoren null / sukz zusammen mit Standardaxiomen zusammen mit Axiomen, die rekursiv eine "Plus" -Funktion definieren). Um dieses Problem zu beweisen, ist eine Einführung in die Struktur des ersten oder zweiten Arguments von "plus" erforderlich (abhängig von der genauen Definition von "plus"). Könnte ich das gewusst haben, bevor ich versucht habe, es zu beweisen, z. B. indem ich die Art des Eingabeproblems analysiere ...? (Dies ist natürlich nur ein einfaches Beispiel zu Illustrationszwecken - in Wirklichkeit wäre dies für schwierigere Beweisprobleme interessanter als die Kommutativität von Plus.)

Noch mehr Kontext:

In meiner Forschung versuche ich häufig, automatisierte Theoremprüfer erster Ordnung wie Vampire, Eprover usw. anzuwenden, um Beweisprobleme (oder Teile von Beweisproblemen) zu lösen, von denen einige möglicherweise eine Argumentation höherer Ordnung erfordern. Häufig benötigen Prüfer einige Zeit, um einen Beweis zu erbringen (vorausgesetzt, es gibt einen Beweis, der nur Argumentationstechniken erster Ordnung erfordert). Natürlich führt der Versuch, einen Satzbeweiser erster Ordnung auf ein Problem anzuwenden, das Argumentation höherer Ordnung erfordert, in der Regel zu einer Zeitüberschreitung.

Daher habe ich mich gefragt, ob es Methoden / Techniken gibt, die mir im Voraus sagen können, ob für ein Beweisproblem Argumentationstechniken höherer Ordnung erforderlich sind (was bedeutet: "Verschwenden Sie keine Zeit damit, es einem Theorembeweiser erster Ordnung zu übergeben"). ) oder nicht, zumindest für bestimmte Eingabeprobleme.

Ich habe in der Literatur nach einer Antwort auf meine Frage gesucht und einige Kollegen aus dem Bereich Theorem gefragt, die dies beweisen - aber bisher habe ich keine guten Antworten erhalten. Ich gehe davon aus, dass Menschen, die versuchen, die Prüfung interaktiver Theoreme mit der Prüfung automatisierter Theoreme zu kombinieren (Coq-Community? Isabelle-Community (Vorschlaghammer)?), Nachforschungen zu diesem Thema anstellen - aber bisher konnte ich nichts finden.

Ich denke, dass das Problem, das ich hier umrissen habe, im Allgemeinen nicht zu entscheiden ist (oder?). Aber vielleicht gibt es gute Antworten für verfeinerte Versionen des Problems ...?

automated-theorem-proving program-verification Sylvia Grewe
quelle
2
Was Sie fragen, ist im Wesentlichen zu entscheiden, ob eine gegebene Formel beweisbar ist (in Ihrem schwächeren System), was im Allgemeinen selbst für eine einfache Theorie wie Q nicht zu entscheiden ist. Die Beweisbarkeit ist jedoch nicht sehr nützlich, da eine stärkere Theorie Beweise eines Theorems verkürzen kann Menge. Die Entscheidung, ob ein Satz einen kurzen Beweis enthält, ist NP-vollständig. Ich bezweifle, dass es eine gute Heuristik gibt.
Kaveh
2
Peano-Arithmetik hat Induktion, und Peano-Arithmetik ist erster Ordnung (dh quantifiziert nur über Individuen). Gleiches gilt für ZFC. Martin Davis zitiert: "Logik höherer Ordnung ist nur eine notatorische Variante von Mengen-Theorien, die in der Logik erster Ordnung formalisiert sind. Die Frage nach der Verwendung von Formalismen höherer Ordnung bei der Beweisführung mechanischer Theoreme hängt einfach davon ab, ob solche Formalismen dies nahelegen oder nicht nützliche Algorithmen. "
Martin Berger
@MartinBerger Ich denke, für die Zwecke dieser Frage gelten Axiomschemata als "Argumentationstechniken höherer Ordnung"
fread2281
@ fread2281 Es ist hilfreich, mit der Terminologie vorsichtig zu sein. Es gibt Mengen-Theorien mit endlicher Axiomatisierung (zB Neumann-Bernays-Gödel-Mengen-Theorie, die eine konservative Erweiterung von ZFC darstellt). Im Gegensatz dazu können die Axiomschemata von ZFC nicht durch eine endliche Anzahl von Axiomen ausgedrückt werden. Ich denke, aber ich bin mir momentan nicht sicher, ob die Axiomschemata nicht die volle Kraft der Mengenlehre oder der Logik höherer Ordnung benötigen.
Martin Berger

Antworten:

6

Kurz gesagt hat jeder Satz, der in der Logik erster Ordnung angegeben ist, einen Beweis erster Ordnung.

In seinem Buch "Eine Einführung in die mathematische Logik und die Typentheorie" entwickelt Peter B. Andrews sowohl Logik erster Ordnung als auch ein System von Logik höherer Ordnung Q 0 , das allgemein als theoretische Grundlage moderner Beweiser höherer Ordnung angesehen wird . (Siehe beispielsweise die Einführung in die HOL-Logik.)

Für Q 0 und ähnliche Systeme zeigt Andrews, dass die Logik höherer Ordnung, die er beschreibt, als konservative Erweiterung der Logik erster Ordnung betrachtet werden kann und schreibt (zweite Ausgabe, S. 259), dass "Zusammenfassend jeder Satz erster Ordnung von Die Typentheorie hat einen Beweis erster Ordnung. "

In Anbetracht Ihrer praktischen Bedenken zitiere ich auch den folgenden Absatz:

Einige Theoreme der Logik erster Ordnung lassen sich jedoch am effizientesten unter Verwendung von Konzepten beweisen, die nur in der Logik höherer Ordnung ausgedrückt werden können. Beispiele finden sich in [Andrews und Bishop, 1996] und [Boolos, 1998, Kapitel 25]. Statman hat bewiesen [Statman, 1978, Proposition 6.3.5], dass die minimale Länge eines Beweises in der Logik erster Ordnung eines wff der Logik erster Ordnung außerordentlich länger sein kann als die minimale Länge eines Beweises desselben wff in Logik zweiter Ordnung: Ein verwandtes Ergebnis von Gödel [Gödel, 1936] ist, dass das Übergehen auf die Logik der nächsthöheren Ordnung im Allgemeinen den Effekt hat, nicht nur bestimmte Sätze, die vorher nicht beweisbar waren, beweisbar zu machen, sondern auch zu machen es ist möglich, unendlich viele der bereits verfügbaren Beweise um einen außerordentlichen Betrag zu verkürzen. “Ein vollständiger Beweis dafür findet sich in [Buss,1994]. "

Cris P
quelle