Beweis: wie man es weiß, nicht wie wahrscheinlich es ist

Mengen, boolesche Algebra und Big-O ruhen alle auf einem Schritt, den Sie bisher stillschweigend gemacht haben: ein paar Fälle prüfen und entscheiden, dass das Muster hält. Bei einer Menge mit zwei Elementen ist das in Ordnung, weil Sie alles sehen. Bei einer Aussage über jede ganze Zahl ist es das nicht, und der ganze Unterschied zwischen Profi und Anfänger versteckt sich in dieser Lücke. Ein Beweis ist kein stärkerer Test. Er ist ein Objekt anderer Art: ein endliches Argument, das unendlich viele Fälle auf einmal abdeckt.

Lesen Sie zuerst die Behauptung genau, denn die meisten schlechten Beweise greifen einen anderen Satz an als den an der Tafel. Eine Aussage der Form für jede ganze Zahl n hat per Definition keine Ausnahmen, und eine Aussage der Form es gibt ein n verlangt einen Zeugen. Das sind entgegengesetzte Strategien. Die Behauptung unten sieht hervorragend aus. Führen Sie sie aus, und sie hält vierzig Werte hintereinander, weit besser als die meisten Muster, denen Sie bisher vertraut haben.

claim: for every integer n >= 1,  n^2 + n + 41  is prime

n = 1    43         prime
n = 2    47         prime
n = 3    53         prime
n = 4    61         prime
n = 5    71         prime
n = 10   151        prime
n = 20   461        prime
n = 39   1601       prime
n = 40   1681 = 41 * 41   composite

confirmed: 39 cases before that one

Bei n = 40 zerfällt der Wert in ein Produkt. Dieser eine Fall ist eine vollständige, endgültige Widerlegung, und er kostet eine Zeile. Diese Asymmetrie ist das Nützlichste in der ganzen Lektion: um eine Allaussage zu beweisen, müssen Sie über alle Fälle auf einmal argumentieren, aber um sie zu zerstören, genügt genau einer. Beachten Sie auch, was die vierzig Erfolge wert waren — nichts. Sie waren keine schwachen Belege für die Behauptung, sondern gar keine, denn die Behauptung war die ganze Zeit falsch. Wenn Sie ein Gegenbeispiel suchen, suchen Sie an den Rändern: n = 0, n = 1, negative Zahlen, die leere Liste, der größte Wert, den Ihr Typ halten kann. Die meisten falschen Allaussagen über Code sterben am Randfall, nicht in der Mitte.

Ein direkter Beweis ist die gewöhnliche Art: von den Definitionen ausgehen und zur Behauptung gelangen, ohne etwas Unbewiesenes anzunehmen. Wenn das Argument in verschiedenen Situationen verschieden läuft, teilen Sie es in Fälle und stellen Sie sicher, dass die Fälle alles abdecken. Die Behauptung unten hat einen zweiseiligen Beweis, aber erst die letzte Zeile macht ihn zum Beweis: Sie stellt fest, dass jede ganze Zahl in einen der beiden Fälle fällt. Ohne diesen Satz haben Sie zwei Beispiele gezeigt, kein Theorem.

claim: for every integer n,  n^2 + n  is even

n^2 + n  =  n * (n + 1)

case A:  n = 2k       ->  n * (n + 1) = 2 * k * (n + 1)
case B:  n + 1 = 2k   ->  n * (n + 1) = 2 * k * n

int(n) = A union B

Der Widerspruchsbeweis ist für Behauptungen, die man frontal schwer angreifen kann, meist für Aussagen, dass etwas nicht existiert. Sie nehmen das Gegenteil an und folgen den Konsequenzen, bis zwei Tatsachen nicht mehr gleichzeitig wahr sein können. Das klassische Beispiel steht unten. Jeder Schritt ist gewöhnliche Algebra plus eine arithmetische Tatsache: ist a zum Quadrat gerade, so ist a gerade. Der Widerspruch ist nicht, dass etwas Überraschendes passiert, sondern dass das Ergebnis die Annahme angreift, mit der Sie begonnen haben: dass a und b keinen gemeinsamen Teiler haben.

claim: no integers a, b with  sqrt(2) = a / b

assume integers a, b exist, gcd(a, b) = 1

  a / b   = sqrt(2)
  a^2     = 2 * b^2
  a^2 even              ->  a = 2k
  4 * k^2 = 2 * b^2
  b^2     = 2 * k^2     ->  b = 2m
  gcd(a, b) >= 2  ->  contradicts gcd(a, b) = 1

assumption false

Genau hier sterben die meisten misslungenen Widerspruchsbeweise, und es lohnt sich, diese Sackgasse zu benennen, damit Sie sie erkennen. War Ihre Annahme zu schwach, zeigt der erreichte Widerspruch vielleicht nur, dass die Annahme unbequem war, nicht dass sie falsch ist. Mit einem Bruch, der einen gemeinsamen Teiler hat, wäre gar kein Widerspruch entstanden. Die Abhilfe besteht nie darin, stärker auf die Algebra zu drücken, sondern zurückzugehen und die stärkste, konkreteste Version des Gegenteils anzunehmen. Ein Widerspruchsbeweis ist genau so gut wie die Annahme, die er tötet.

Was ist ein Test also wert? Sehr viel, aber er ist kein Beweis und wird keiner, wenn man mehr Tests hinzufügt. Belege erhöhen die Zuversicht; ein Beweis beendet die Frage. Echte Ingenieursarbeit braucht beides, und ihre Verwechslung ist der Grund, warum Systeme mit einer Behauptung ausgeliefert werden, die niemand tatsächlich geprüft hat. Die ehrliche Position ist eng und nützlich: mein Beweis zeigt, dass der Algorithmus ein sortiertes Feld zurückgibt, und meine Tests zeigen, dass er in den Speicher passt, den wir haben. Keiner der beiden Sätze gibt sich als der andere aus.