Hat ein Proof-Checker-Fehler jemals einen Hauptbeweis für ungültig erklärt?

Bei den meisten (allen?) Proof-Assistenten wurden gelegentlich Fehler behoben. Von denen, die ich gesehen habe, sind diese Fehler jedoch normalerweise nur schwer unbeabsichtigt zu finden, und die Ergebnisse, die vor der Behebung des Fehlers überprüft wurden, halten im Allgemeinen nach der Behebung an.

Drei Fragen in der Reihenfolge ihrer Stärke:

Hat eine solche Fehlerbehebung jemals dazu geführt, dass ein wichtiger Beweis fehlgeschlagen ist, ohne dass der Beweis geändert wurde?
Wenn (1) wahr ist, waren jemals größere Änderungen erforderlich, um den Beweis zu fixieren?
Wenn (2) wahr ist, hat jemand einen falschen Hauptsatz aufgrund eines Soliditätsfehlers bewiesen ?

Ich überlasse die Definition von "Major" anderen.

proof-assistants soundness Geoffrey Irving
quelle

Dies zeigt wahrscheinlich meine Unwissenheit, aber wurde jemals ein Hauptsatz mit einem Beweisassistenten aufgestellt? Natürlich kenne ich mich mit dem 4-Farben-Theorem und der Kepler-Vermutung aus, aber ich glaube nicht, dass die ersten Beweise dort Beweisassistenten verwendet haben. Ich bin neugierig.

Sasho Nikolov

Ich glaube, bis zu CompCert hatte kein Mensch bewiesen, dass ein Compiler korrekt war, und er hatte auch nicht richtig gelegen. Aber Sie haben Recht, dass dies (3) insbesondere eine weniger interessante Frage machen würde.

Geoffrey Irving

@SashoNikolov: Das ist nicht wirklich relevant, da die meisten Beweise, die von Beweisassistenten in der Praxis durchgeführt werden, nicht die Mathematik betreffen. Es geht in der Regel um Softwaresysteme oder um Eigenschaften formaler Systeme usw. (Es ist nur eine Frage der Zeit, in der es bei den meisten Beweisen auf diesem Planeten nicht um reine Mathematik geht. Die Roboter kommen.) Es wäre ziemlich ärgerlich Wenn zum Beispiel jemand mithilfe eines Proof-Assistenten bewiesen hat, dass ein kritisches System sicher ist, und es sich später herausstellte, dass er versehentlich eine Inkonsistenz verwendet hat.

Andrej Bauer

Danke @AndrejBauer. "Hauptbeweis" und "Hauptsatz" bedeuten hier also nicht Hauptbeweis für Forschungsmathematiker, sondern Beweise für die Korrektheit wichtiger kritischer Systeme?

Sasho Nikolov

Ich denke, jeder Beweis, der von ausreichend vielen Leuten (Mathematikern, Sicherheitsexperten, Software-Ingenieuren) als wichtig angesehen wird, würde zählen. Ich fürchte , wir werden herausfinden, nicht weil , wenn jemand hat auf dieses Problem stolpern, die Chancen sind sie es ruhig fixiert.

Andrej Bauer

Antworten:

Meines Wissens wurde noch nie ein maschinengeprüfter Beweis für eine komplexe mathematische Entwicklung zurückgezogen.

Wie Andrej jedoch ausführt, kommt es gelegentlich vor, dass Fehler auftreten, die die Zuverlässigkeit beeinträchtigen (wenn auch normalerweise nicht lautlos , wie Andrej vorschlägt), und die Behebung dieses Fehlers beinhaltet einige Änderungen an vorhandenen Beweisen oder, was wahrscheinlicher ist, von die Standardbibliothek des beteiligten Beweissystems.

Einige Beispiele für solche in Coq brechenden Beweise für Bibliotheken:

https://coq.inria.fr/bugs/show_bug.cgi?id=4294

https://sympa.inria.fr/sympa/arc/coq-club/2013-12/msg00119.html

Es ist schwer zu sagen, ob die etablierten Proofs von der Inkonsistenz abhingen , da nach der Korrektur kleinere Optimierungen vom Proof Checker akzeptiert werden mussten. Dies geschieht jedoch bei jedem nicht trivialen Update!

Meiner persönlichen Meinung nach ist es unwahrscheinlich, dass solche Fehler auftreten, da der Papierproof gut poliert werden muss, bevor eine maschinelle Formalisierung überhaupt versucht werden kann.

Inkonsistenzen in Proof-Frameworks erfordern normalerweise den intensiven Einsatz seltsamer Kombinationen von esoterischen Merkmalen und treten daher nur sehr selten "zufällig" auf.

Cody
quelle

Ich bezog mich auf Leute, die Probleme in ihren Proof-Skripten stillschweigend oder gar unwissentlich behoben hatten, wie Geoffrey betonte, als Reaktion auf Fehler in Proof-Assistenten. Natürlich werden die Inkonsistenzen bei den Proofassistenten immer mit einem erstaunlichen Maß an Aufregung aufgenommen. Mathematiker sollten eine Inkonsistenz in der Mathematik haben, die für ein paar interessante Monate sorgen würde.

Andrej Bauer

Was ist mit Leuten, die Wikipedia-Links auf mich werfen? @ RickyDemer, bitte erläutern Sie Ihren Standpunkt. Ich habe von Russells Paradoxon gehört, wissen Sie. Das war vor mehr als 100 Jahren und führte zu einer exzellenten Mathematik. Ich schlage vor, dass wir reif für einen anderen sind.

Andrej Bauer

Ich werde diese Antwort vorerst akzeptieren, aber natürlich nicht akzeptieren, wenn jemand in die andere Richtung antwortet! (Vollständige Offenlegung: Dies war die Antwort, auf die ich gehofft hatte.)

Geoffrey Irving

@GeoffreyIrving Die Antwort ist etwas unbefriedigend, da es mir schwer fällt, einen Mangel an Retraktionen zu beweisen ! Die Antwort basiert daher zwangsläufig auf meinem Unwissen, obwohl es so wenige groß angelegte Maschinenformalisierungen gegeben hat, dass ich zumindest ein wenig zuversichtlich in meine Antwort bin. Ich habe auch gehört, dass gezeigt wurde, dass einige wichtige Formalisierungen in der B-Methode inkonsistente Annahmen haben (Sie müssen viele Axiome für nicht-triviale Aussagen hinzufügen, und die Sammlungen von Axiomen zusammen haben sich später als ...

cody erwiesen

... inkonsistent). Leider kann ich keine Referenz dafür finden, deshalb habe ich sie nicht in meine Antwort aufgenommen. Auch bei der Formalisierung ging es um ein großes Programm und nicht um reine Mathematik.

Cody