Beweisstrukturen
Jeder Student (im folgenden wie allgemein üblich ist damit auch Studentin gemeint), der eine schon einmal eine Vorlesung mit hinreichend anspruchsvoller Mathematik gehört hat (etwa auch: Physik oder Informatik), weiß um die beherrschende Position von Beweisen in der Mathematik.
Für alle, die bisher nicht das Vergnügen hatten oder Vergnügen dabei haben es noch einmal zu rekapitulieren:
Die Mathematik ist die Wissenschaft, welche selbst erschaffene, abstrake Objekte untersucht. Dabei fordert man von diesen Objekten erst einmal ein paar Eigenschaften (etwa das Distributivgesetz der rellen Zahlen a · (b + c) = (a · b) + (a · c). Danach zeigt man auf diesen Eigenschaften in sogenannten Sätzen mittels Beweisen neue Eigenschaften.
Mit diesen neuen Sätzen und vielleicht auch noch neuen Objekten führt man das ganze dann fort. Eine ganz passende Klassifizierung der Mathematik ist ,,ein Spiel mit Regeln aber ohne Ziel”
Der geneigte Leser möge einmal überprüfen (mathematisch für: Ich habe keine Lust das jetzt genauer auszführen), dass es u.a. folgende wichtige Beweisklassen gibt:
Der direkte Beweis. Er ist der Albtraum aller Mathematikstudenten (inkl. Informatikstudenten) - braucht man hier doch ein sehr genaues Wissen über die gerade behandelten Strukturen. Beispiel: Wir wissen, dass 1 ≤ 2 und 2 ≤ 3. Daraus folgt sofort: 1 ≤ 3 weil ≤ eine Ordnungsrelation ist.
Der Widerspruchsbeweis ist dem direkten Beweis ähnlich. Aber man sieht hier oft leichter den zu gehenden Weg. Zum Beispiel: Nehmen wir an, dass nicht gilt: 1 ≤ 3. Wir wissen aber, dass 1 ≤ 2 und 2 ≤ 3 gilt. Damit steht die Annahme im Widerspruch zur Transitivität der Ordnungsrelation ≤. Damit folgt 1 ≤ 3.
Der Induktionsbeweis ist meiner Meinung nach die schönste Beweismethode und sie ist zum Glück die häufigste in der Informatik. Zum Beispiel kann man im Zusammenhang mit Automaten Induktionen über die Wortlänge machen. Ich erspare allen nicht Mathematik vorgeprägten Lesern die auf meine tölpelhaften Erklärungen und verweise lieber auf den Artikel bei Wikipedia zu diesem Thema.
Warum ich überhaupt darauf komme hier über Mathematik zu schreiben? Nun, mir wurde heute in der Informatik-Vorlesung klar, dass der vom Professor geführte Beweis didaktisch elegant und dennoch recht kurz war (ging über 2 Vorlesungen). Wir zeigten, dass man konstruktiv folgende Umformungen vornehmen kann: Regulärer Ausdruck ⇒ Nichtdeterminister Endlicher Automat (NEA) mit Epsilon-Übergänge ⇒ NEA ohne Epsilon-Übergänge ⇒ Deterministischer Endlicher Automat ⇒ Regulärer Ausdruck. Dabei bewiesen wir am Ende nicht die Äquivalenz der beiden regulären Ausdrücke sondern jeweils zwischen den einseitigen Umformungen, dass die beschriebenen formalen Sprachen die gleichen waren.
Statt also in die dritte Vorlesung zu gehen und erst einmal auf den regulären Ausdrücken eine Äquivalenzrelation zu definieren, gingen wir die Folgerungsschritte (die eh meist Äquivalenzen waren) zurück und erhielten mit viel weniger Beweisarbeit das gewünschte.
Nachzulesen ist das ganze auf den Vorlesungsfolien.