Formale Beweise als Pfade
Ein formales Beweissystem definiert einen Satz von Axiomen & Ableitungsregeln. Jedes Theorem-Beweisprogramm navigiert dieses System als Suchproblem: Beginn bei den gegebenen Prämissen, wende Ableitungsregeln an, um neue Aussagen zu generieren, bis du das Ziel erreichst.
Stelle dies als gerichteten Graphen dar:
Knoten: wohlgeformte Aussagen im formalen System.
Kanten: einzelne Anwendungen von Ableitungsregeln (modus ponens, SAS-Kongruenz, etc.).
Beweis: ein gerichteter Pfad von den gegebenen Prämissen zur gewünschten Schlussfolgerung.
Beweislänge: Anzahl der Ableitungsschritte im Pfad.
Der kürzeste Beweis eines Theorems entspricht dem kürzesten Pfad zwischen dem Prämissenknoten & dem Schlussfolgerungsknoten in diesem Graphen.
Das Geometrie-Theorem-Beweisprogramm erforschte diesen Graphen durch: (1) direkte Anwendung von Regeln; (2) falls blockiert, Einführung von Hilfskonstruktionen (die neue Knoten zur Suche hinzufügen). Das Programm fand den Selbstkongruenzbeweis durch vollständiges Vermeiden der Hilfskonstruktion — es existierte ein kürzerer Pfad, den der klassische Ansatz verpasst hatte.
Beweislänge & Beweissuche
Die Beweissuche steht vor dem gleichen exponentiellen Wachstum wie die Spielbaumsuche. Der Verzweigungsfaktor an jedem Knoten ist gleich der Anzahl der anwendbaren Ableitungsregeln. Proof depth grows with theorem complexity.
Das Theorem-Beweisprogramm verwendete Heuristiken, um den Beweisraum zu beschneiden, analog zum Alpha-Beta-Schnitt in Spielen.
Punkte, Linien & Dualität
Der Selbstkongruenzbeweis des Geometrieprogramms für den Satz vom gleichschenkligen Dreieck verwendet eine Perspektive, die in klassischen euklidischen Beweisen nicht auftaucht. Die Einsicht: Statt das Dreieck ABC mit einem zweiten konstruierten Dreieck zu vergleichen, vergleiche ABC mit sich selbst mit den vertauschten Basisecken — die Entsprechung A↔A, B↔C, C↔B.
Dies ist ein geometrisches Symmetrieargument: das gleichschenklige Dreieck ist symmetrisch unter Spiegelung über die Höhe von der Spitze. Das Programm konstruierte die Spiegelung nicht explizit; es verwendete die Entsprechung als Abstraktion.
Das allgemeine Prinzip dahinter ist projektive Dualität: in der projektiven Ebene hat jeder Satz über Punkte & Linien einen dualen Satz, der durch Vertauschung der Wörter 'Punkt' und 'Linie' erhalten wird.
Dualitätslexikon:
- Punkt ↔ Linie
- Punkt liegt auf Linie ↔ Linie verläuft durch Punkt
- Zwei Punkte bestimmen eine eindeutige Linie ↔ Zwei Linien bestimmen einen eindeutigen Punkt
- Kollineare Punkte ↔ Konkurrierende Linien
Ein einziger Beweis eines Satzes über Punkte liefert automatisch einen Beweis des dualen Satzes über Linien — und umgekehrt. Die beiden Beweise haben die gleiche Struktur, die gleiche Länge, & die gleichen Ableitungsschritte. Das Auffinden der dualen Perspektive offenbart oft einen einfacheren Beweis des Originals.
Dualität anwenden
Satz von Desargues: Wenn zwei Dreiecke von einem Punkt aus perspektivisch sind (die drei Linien durch entsprechende Ecken treffen sich alle in einem Punkt), dann sind sie von einer Linie aus perspektivisch (die drei Schnittpunkte der entsprechenden Seiten liegen alle auf einer Linie).
Dieser Satz ist selbst-dual: Das Vertauschen von Punkten und Linien ergibt genau die gleiche Satzaussage.
Abtastrate & Frequenzraum
Das Computermusiksystem bei Bell Labs basierte auf einem mathematischen Satz: dem Nyquist-Shannon-Abtastsatz.
Aussage: ein bandbegrenztes Signal mit maximaler Frequenz f_max kann perfekt aus Abtastwerten rekonstruiert werden, die mit einer Rate von mindestens 2 × f_max Abtastwerten pro Sekunde entnommen werden.
Die geometrische Interpretation: ein bandbegrenztes Signal lebt in einem endlich-dimensionalen Untervektorraum des Raums aller stetigen Funktionen. Abtastung mit Rate 2f_max liefert genug Koordinaten, um einen Punkt in diesem Untervektorraum eindeutig zu identifizieren.
Aliasing: Die Geometrie des Abtastversagens
Unterhalb der Nyquist-Rate werden Frequenzen über f_max zu Aliase — sie erscheinen als niedrigere Frequenzen im abgetasteten Signal. Zwei unterschiedliche Signale werden nach Abtastung ununterscheidbar. Geometrisch: der Abtastoperator projiziert den Signalraum in einen niedrig-dimensionalen Raum, wodurch unterschiedliche Signale kollidieren.
Für digitales Audio (CD-Qualität): f_max = 22.050 Hz (etwas über der 20.000-Hz-Grenze des menschlichen Gehörs), Abtastrate = 44.100 Abtastwerte/Sekunde. Für Telefon: f_max = 4.000 Hz, Abtastrate = 8.000 Abtastwerte/Sekunde.
Nyquist-Raten-Berechnungen
Der Nyquist-Satz bestimmt die minimale Abtastrate, die erforderlich ist, um Informationsverlust zu vermeiden.
Beweisraum & Signalraum: Gemeinsame Geometrie
Der Beweis-als-Pfad und der Nyquist-Abtastsatz teilen eine gemeinsame geometrische Struktur: beide beinhalten das Finden der minimalen Darstellung von etwas Komplexem.
Beweis-Minimierung: Finde den kürzesten Pfad (minimale Anzahl von Ableitungsschritten) durch den Beweisdiagramm von Prämissen zu Schlussfolgerung. Der Selbstkongruenzbeweis minimierte Pfadlänge durch Ausnutzen von Symmetrie.
Signal-Abtastung: Finde die minimale Anzahl von Abtastwerten (niedrigste Abtastrate), die alle Informationen in einem bandbegrenzten Signal bewahrt. Der Nyquist-Satz minimiert die Darstellung durch Ausnutzen von Bandbreitengrenzen.
Beide Probleme leben in Räumen mit Struktur, die Minimum-Darstellungs-Ergebnisse ermöglicht. Beide scheitern, wenn diese Struktur zusammenbricht: Beweise werden länger, wenn der Axiomraum schlecht organisiert ist; Aliasing tritt auf, wenn das Signal nicht bandbegrenzt ist.