So schießen Sie Ihre Beweise ab

59

Was sind die allgemeinen Richtlinien für die Prüfung Ihrer Beweise? Ich glaube, das ist wichtig für Doktoranden wie mich. Ich weiß bereits, was wir tun müssen, um etwas zu beweisen, aber Sie müssen immer alles überprüfen, bevor Sie es versenden. Auch an Ihren eigenen Berater.

Ich habe mir durch Ausprobieren einige Strategien erarbeitet und viele Ratschläge von meinem Berater erhalten. Aber das ist immer eine sehr mühsame Arbeit. Wenn Sie mit etwas fertig sind, möchten Sie normalerweise nur mit dem nächsten Problem fortfahren, aber Sie müssen sich immer noch an das aktuelle Problem halten, bis alles perfekt ist. Hier präsentiere ich ein Beispiel meiner eigenen Trickliste:

  1. Füllen Sie die Details aus. Es gibt viele Fehler an Stellen, an denen Sie schreiben: "Es ist klar, dass ...", "Ohne Verlust der Allgemeinheit ..." usw.
  2. Probieren Sie einige Zahlen aus. Versuchen Sie extreme Fälle wie "Was passiert, wenn ich oder n = 1000 setze ? ".n=1n=1000
  3. Halten Sie ein sauberes Notizbuch. Schreiben Sie jeden Tag darauf und vergleichen Sie es mit Ihren groben Notizen. Ich versuche auch in Latex zu schreiben, ich habe so viele Fehler gefunden.

Was sind die allgemeinen Strategien, die Sie anwenden, um Ihre Beweise zu überprüfen?

Das Ziel dieser Frage ist es, es zu einem Community-Wiki zu machen.

Marcos Villagra
quelle
Wenn die Frage subjektiv erscheint, helfen Sie mir bitte, sie zu verbessern.
Marcos Villagra
Wie erstelle ich dieses Community-Wiki?
Marcos Villagra
1
Hey, cool! Die Antworten auf diese Frage interessieren mich sehr. Auch ich kann Ihr # 3 schätzen. (Wenn ich darüber nachdenke, habe ich tatsächlich überall Papierstapel verstreut, wenn ich vorsätzlich an einem Problem arbeite, das dann nach dem Zufallsprinzip verschoben wird. Yuck.) Ich bin schon einmal auf einen Fehler gestoßen und habe am Ende verschwendet ein guter Teil der Zeit.
Daniel Apon
@ Daniel: Ich hatte das gleiche Problem !! Deshalb schreibe ich sofort die Latex-Version, nachdem ich mit einem Proof fertig bin. Es ist gut zu wissen, dass ich nicht der einzige Kerl bin, der alles überall hat :-)
Marcos Villagra
1
Sie weisen den Moderator darauf hin.
Suresh Venkat

Antworten:

39

Softwareentwickler haben eine Vorstellung, die sie " Codegerüche " nennen. Dies sind Symptome im Code, die auf ein tieferes Problem hinweisen können. Software-Ingenieure sammeln mentale Geruchslisten, um sich dessen bewusst zu sein (dh zu lange Methoden oder zu viele Parameter). Dies bedeutet nicht unbedingt, dass ein Problem vorliegt, sondern weist lediglich darauf hin, dass der Verfasser möglicherweise eine Überprüfung durchführen möchte.

Ich schlage vor, dass wir auch "Beweisgerüche" berücksichtigen sollten . Dies gibt Ihnen keinen Algorithmus zum Überprüfen Ihrer Beweise, sondern eine Sprache und eine Metapher zum Erkennen möglicher Probleme bei Beweisen. Einige Beispiele für Beweise riechen:

  1. Die Adverbien "Eindeutig", "Offensichtlich" usw.
  2. Verweis auf den Nachweis eines vorherigen Ergebnisses anstelle eines Verweises auf das Ergebnis selbst.
  3. Flippige Nutzung eines Ergebnisses mit vielen technischen Voraussetzungen.

Es gibt auch subtilere Gerüche. Wenn ein Beweis beispielsweise den Binomialsatz verwendet, um einen Ausdruck zu erweitern, und später den Binomialsatz verwendet, um zu einer geschlossenen Form zurückzukehren, liegt möglicherweise eine direkte Manipulation an der geschlossenen Form vor, die dasselbe Ergebnis liefert.

Mein Vorschlag ist, eine (mentale oder schriftliche) Liste solcher Gerüche zusammenzustellen und beim Lesen Ihrer Arbeit auf sie zu prüfen. Der schöne Nebeneffekt dieses Ansatzes ist, dass Sie dadurch auch ein besserer Leser werden.

Hinweis: Ich hatte die Hoffnung, mit dieser Antwort die rigorose Antwort von Lamports How to Write a Proof, auf die in der Antwort von M. Alaggan verwiesen wird, auf intuitive Weise zu ergänzen.

Don Sheehy
quelle
4
Ich sage das immer meinen Schülern und sie denken, ich bin verrückt. Natürlich behaupte ich tatsächlich, ich kann einen Fehler riechen, der Teil des Problems sein könnte;)
Suresh Venkat
7
@ Suresh: Dieser Student denkt, du bist aus verschiedenen Gründen verrückt. ;-)
John Moeller
4
In der Code-Geruchsnotiz sind Dinge, die ich immer in den Beweisen anderer zu hinterfragen versuche, Ungleichungsketten. Oft haben wirklich grundlegende Fehler die Angewohnheit, sich unter die schwierigeren Ableitungen zu schleichen.
John Moeller
23

Es gibt eine sehr gute Arbeit von Leslie Lamport ( Wie man einen Proof schreibt ). Es ist eigentlich ein Vorschlag von ihm, detaillierte Beweise so zu schreiben, dass:

(1) Ermöglicht das direkte Erkennen von Fehlern

(2) Verdeutlicht, welche Annahmen und Theoreme in welchen Teilen verwendet wurden, und macht es ziemlich einfach zu sehen, was passiert, wenn Sie (zum Beispiel) schwächere Annahmen verwenden möchten

Es gibt auch einige Community-Erfahrungen und inspirierende Kommentare zu dieser Technik auf MO, die positive Erfahrungen im Allgemeinen (und einige andere Ressourcen auch) zeigen.

Update: Es gibt eine neue Version Wie man einen Proof für das 21. Jahrhundert schreibt .

M. Alaggan
quelle
5
Diese Beweise sind sehr ähnlich zu dem, was man in einer PL-Forschungsarbeit schreiben würde. Die Kette der Logik ist sehr explizit. Nachdem ich gelernt hatte, wie man Beweise im PL-Stil liest und schätzt, fiel es mir schwer, "normale" mathematische Beweise zu verstehen. Solche Beweise erfordern oft, dass der Leser genauso denkt wie der Autor, und wenn Sie sich an einen anderen Beweisstil gewöhnt haben, ist dies einfach nicht der Fall (zumindest für mich!)
Christopher Monsanto
2
@Christopher Monsanto: PL steht für Programmiersprachen? Ich würde mich
freuen,
5
Ich hatte immer das Gefühl, dass das, was Lamport vorschlägt, nicht mit Paul Lockharts "A Mathematician's Lament" ( maa.org/devlin/LockhartsLament.pdf ) kompatibel ist .
Marcos Villagra
14

Ich erinnere mich an einen populären Bericht vor langer Zeit darüber, wie Physiker mit einem analogen Problem umgehen. Wer weiß, wie genau die folgende Version davon ist; Korrekturen sind willkommen. Aber ich fand die zugrunde liegende Strategie ziemlich bemerkenswert.

Sie erklärten, wie sie an Schwarze Löcher glaubten. Schwarze Löcher waren anfangs rein mathematische Konstrukte, wie andere seltsame Objekte in der Physik wie Wurmlöcher. Ihre Strategie war bemerkenswert: Sie warfen mathematisch andere Objekte auf das zu testende Objekt. Wurmlöcher haben ihre Tests nicht bestanden, weil sie herausfanden, dass das Wurmloch selbst bei Vorhandensein eines normalen physischen Objekts, vielleicht eines Asteroiden, zusammenbrechen würde. Aber Schwarze Löcher haben diesen Test bestanden: Das Schwarze Loch würde überleben, wenn ein Asteroid darauf geworfen würde. Also haben sie versucht, einen Stern darauf zu werfen. Gleiches Ergebnis. Schließlich warfen sie ein weiteres Schwarzes Loch auf das Schwarze Loch und es überlebte. Infolgedessen waren sie zuversichtlich genug, dass es Schwarze Löcher gab, um sie tatsächlich im realen Universum zu suchen.

Die Relevanz und Anwendung der oben genannten Strategie besteht also darin, Dinge nach Ihren Wünschen zu werfen. Überlebt es die Gesundheitskontrolle ? Wenn Sie eine notwendige Annahme entfernen, bricht sie dann wie gewünscht zusammen? Kollabiert es so, wie es sollte, wenn es auf Fälle angewendet wird, die außerhalb seines Anwendungsbereichs liegen? Hält es vernünftigen Verallgemeinerungen und Spezialisierungen stand? Schauen Sie sich die Liste der Heuristiken in Polya's How to Solve It an . Versuchen Sie, Ihren Beweis mit diesen Heuristiken zu mutieren, und prüfen Sie, ob er so steht und fällt, wie er sollte.

Schüchterne Person
quelle
Der größte Teil Ihrer Antwort konzentriert sich auf die Überprüfung von Beweisen, indem Sie überprüfen, ob sie in Situationen falsch sind, in denen sie falsch sein sollten. Das funktioniert nicht, weil es nicht überprüft, ob das Theorem dort wahr ist, wo es wahr sein sollte! Angenommen, ich habe "bewiesen", dass jede ungerade Zahl durch drei teilbar ist. Ich überprüfe, ob mein Beweis fehlschlägt, wenn ich ihn auch auf gerade Zahlen ausdehne: Das tut es, da vier nicht durch drei teilbar ist. Hurra, mein Beweis muss stimmen!
David Richerby
12

Ich denke, einer der sichersten Ansätze besteht darin, mehrere unabhängige Beweise zu erstellen. Dann können Sie sicher sein, dass Ihr Hauptergebnis korrekt ist, auch wenn Sie in einigen Details eines Beweises einen Fehler haben.

Jukka Suomela
quelle
9

Eine Technik, die ich für nützlich befunden habe, besteht darin, darüber nachzudenken, welche anderen Ergebnisse die Proof-Strategie nachweisen könnte. Wenn ich die Proof-Strategie leicht anpassen kann, um ein großes offenes Problem zu beweisen, oder sogar ein Problem, das nicht offen ist, dessen Lösung im Vergleich zur Komplexität der Proof-Strategie jedoch viel zu kompliziert ist, dann ist das ein großer Grund zu bezweifeln der Beweis.

Opt
quelle
5
PNP
6

Ich überprüfe meine Proofs immer wieder mit einem Proof-Checker wie COQ oder ISABELLE . Wenn Sie Ihren Proof in einer dieser Programmiersprachen nachweisen können, können Sie sicher sein, dass Ihr Proof korrekt ist. So einfach wie ein Lambda-Term;).

Gopi
quelle
Ich habe Coq noch nie benutzt, aber ich sollte es versuchen. Tatsächlich versuche ich mit Mathematica einige untere Schranken zu beweisen, aber ich habe nicht den richtigen Weg gefunden. Vielleicht brauche ich spezielle Pakete oder so.
Marcos Villagra
1
Vielleicht ist es ein Longshot, aber wenn Sie einige untere Schranken mit Real
Gopi
Einverstanden, aber jede Programmiersprache funktioniert. Meistens mache ich das umgekehrt. Formulieren Sie die Problemdomäne in einer Programmiersprache (normalerweise Ruby) und verwenden Sie diese als Vorlage für meinen Proof.
Chad Brewbaker