1. IMPLIKATION
Verwechseln Sie nicht die folgenden Aussagen:- Wenn A, dann B. (äquivalent: "B wenn A". Oder: "A ⇒ B". A ist hinreichend für B. B ist notwendig für A.)
- Wenn B, dann A.
- A genau dann, wenn B. (äquivalent: Wenn A, dann B, aber auch umgekehrt: Wenn B, dann A. Mit anderen Worten: A und B sind entweder beide wahr oder beide falsch.)
- A, daher B. (= wir wissen bereits A⇒B, und haben A festgestellt. Also B.)
Das Anwenden von arithmetischen Operationen (Addieren, Quadrieren, etc) oder ganz allgemein von Funktionen (zB Schneiden oder Vereinigen von Mengen) auf eine wahre Gleichung liefert wieder eine wahre Gleichung: aus x=y folgt a*x=a*y, und allgemeiner f(x)=f(y). Aber: im Allgemeinen gilt nicht die Umkehrung! Zum Beispiel können Sie die (falsche) Behauptung " -3 = 3 " nicht dadurch beweisen, dass Sie sie durch Quadrieren in die wahre Behauptung 9=9 überführen. Auch können Sie aus a*x=a*y nicht immer x=y schließen. (Allerdings schon, wenn a ein Inverses hat und das Assoziativgesetz gilt: a*x = a*y ⇒ a-1*(a*x) = a-1*(a*y) ⇒ (a-1*a)*x = (a-1*a)*y ⇒ e*x = e*y ⇒ x = y.)
2. ALLQUANTOR und EXISTENZQUANTOR
Machen Sie sich (und Ihren Zuhörern -- siehe Fußnote *) immer klar, ob sie gerade- von einem beliebigen Objekt x (zB einem beliebigen Vektor x) sprechen, etwa weil Sie gerade dabei sind, einen Allsatz der Form "für alle x gilt..." zu beweisen
- von einem beliebigen Objekt x mit einer Zusatzeigenschaft (zB einem Vektor ungleich 0) sprechen.
- von einem speziell ausgesuchten
Objekt x sprechen, etwa weil sie gerade einen Existenzsatz der Form "es gibt ein x ..." zeigen wollen.
In diesem Fall: machen Sie sich auch klar, wovon dieses x abhängt -- hängt die Wahl dieses x vielleicht von einem zuvor betrachteten y ab? (Etwa wenn Sie "für alle y gibt es ein x mit..." zeigen wollen.)
2a. Quantorenreihenfolge
- Die Aussage "für alle Zahlen x gibt es eine Zahl y, sodass die Relation x<y gilt" ist wahr.
- Die Aussage "es gibt eine Zahl y sodass für alle Zahlen x die Beziehung x<y gilt" ist aber falsch.
Bei einfachen Allaussagen ist es oft üblich, den Allquantor hinter die allquantifizierte Formel zu setzen ("x*x≥0 ∀x" statt "∀x ( x*x≥0)"). Vermeiden Sie diese Schreibweise, sie führt gelegentlich zu Unklarheiten! Bei einer komplizierteren Formel wie
∃y (x < y) ∀x ????
entsteht durch den nachgestellten Quantor Unklarheit. Welche der folgenden Formeln ist hier gemeint?
- "(∃y (x < y)) gilt für alle x" - das ist wahr. ("für jedes x gibt es ein y ...")
- Es gibt ein y mit der Eigenschaft " (x < y) ∀x " - das ist falsch. ("es gibt ein y sodass für alle x ...")
(∃y (x < y)) ∀x bzw ∃y ((x < y) ∀x )
Besser (weil übersichtlicher) ist es, die Quantoren voranstellen:
- ∀x ∃y (x < y) (in den natürlichen Zahlen wahr)
- ∃y ∀x (x < y) (in den natürlichen Zahlen falsch)
2b. Versteckte Quantoren, versteckte Implikationen
Wenn Sie zum Beispiel den Satz "Blaue Autos sind schnell" formalisieren wollen, müssen Sie zuerst überlegen, was eigentlich gemeint ist. Das Wort "sind" versteckt hier eigentlich einen Quantor. Aber was ist hier gemeint?- dass es schnelle blaue Autos gibt? ∃b: (b ist Auto) und (b ist blau) und (b ist schnell)
- oder
(vermutlich eher gemeint) dass alle blauen Autos schnell sind? ∀b: ( Wenn b Auto ist, und b blau ist, dann ist b schnell).
Oder kürzer: ∀b: ( [ b ist Auto und b ist blau ] ⇒ [ b ist schnell ]).
∀b: ( [ b ∈ BA ] ⇒ [ b ist schnell ]).
Oder noch kürzer so - Achtung, hier ist die Implikation nicht mehr explizit sichtbar!∀b∈BA: [ b ist schnell ].
Wenn auch die Menge der schnellen Objekte einen Namen hat, sagen wir S, dann geht es sogar noch kürzer:BA ⊆ S (Die Menge der blauen Autos ist Teilmenge der Menge der schnellen Objekte.)
Anmerkung: Hinter einer Teilmengenbeziehung P ⊆ Q steht immer eine Implikation, genauer: eine allquantifizierte Implikation, nämlich:∀x( x∈P ⇒ x∈Q )
2c. Hinweis
Hinter einem Allquantor "∀x" steht fast immer- entweder ein weiterer Allquantor: ∀x ∀y.
(Dies wird oft auch mit ∀x,y abgekürzt. Beachten sie, dass damit wirklich alle Paare (x,y) gemeint sind, und nicht nur jene, wo x≠y gilt.) - oder ein Existenzquantor: ∀x ∃y.
Oft wird durch so eine Aussage eine Funktion beschrieben, die jedem x ein passendes y zuordnet. Das ist aber nicht immer der Fall - es könnte aber auch mehrere y geben, die in Frage kommen. (Denken Sie etwa an ∀ε ∃δ) - ODER eine Implikation: ∀x (A ⇒ B), wobei A und B Aussagen sind, die meist von x abhängen.
Etwas ausführlicher: Für alle x gilt: Wenn A zutrifft, dann auch B.
Oder: Alle x mit der Eigenschaft A haben auch die Eigenschaft B.
- entweder ein weiterer Existenzquantor: ∃x ∃y.
(Dies wird oft auch mit ∃x,y abgekürzt. Beachten sie, dass die Frage, ob x=y oder x≠y gelten kann/muss, zunächst offen bleibt.) - oder ein Allquantor: ∃y ∀x .
(Hier gibt es ein festes y, das nicht von den danach quantifizierten x abhängt.) - ODER eine KONJUNKTION: ∃x (A ∧ B), wobei A und B Aussagen sind, die meist von x abhängen.
Etwas ausführlicher: Es gibt ein x, auf das sowohl A als auch B zutrifft.
2d. Notwendige Klammern
Wenn Sie eine Aussage ∀x P oder ∃x Q betrachten, dann empfiehlt es sich, sie als ∀x (P) bzw. ∃x(Q) anzuschreiben.Insbesondere dann, wenn P bzw. Q eine Implikation ist, oder eine halbwegs komplizierte Aussage. Die Aussagen ∀x (A ⇒ B) und ( ∀x A ) ⇒ B sind nicht äquivalent, analog für den Existenzquantor. Daher: Stellen Sie -- erstens für sich selbst, zweitens für Ihr Publikum -- immer mit Hilfe von Klammern klar, was gemeint ist.
2e. Doppelpunkt
Direkt nach einer quantifizierten Variable schreibt man gerne einen Doppelpunkt, der als "gilt" gelesen wird: "∀x: P(x)" = "für alle x gilt die Eigenschaft P", oder "∃x: P(x)" = "es gibt ein x, sodass gilt: x hat die Eigenschaft P".Wenn man die Aussage auf alle x mit einer gewissen einfachen Eigenschaft (wie "x in N" oder "x>0") einschränken möchte, kann man diese Eigenschaft vor den Doppelpunkt schreiben: ∃x>0: P(x) oder ∀x>0: P(x). Beachten Sie, dass die logische Bedeutung dieses Doppelpunkts vom Quantor abhängt:
- Die Formel ∀x>0: P(x) lässt sich ausführlicher als ∀x:(x>0 ⇒ P(x)) schreiben.
- Die Formel ∃x>0: P(x) lässt sich ausführlicher als ∃x:(x>0 ∧ P(x)) schreiben.
Sobald die einschränkende Eigenschaft komplizierter als nur "x>0" oder "x∈A" wird, verwenden Sie bitte keinen Doppelpunkt sondern das entsprechende logische Symbol. Also nicht ∀x: x2-3>0∧x>0: x>1 sondern ∀x:( x2-3>0∧x>0 ⇒ x>1) oder noch deutlicher ∀x:( (x2-3>0∧x>0) ⇒ x>1)
2f. es gibt genau ein
Die Aussage "es gibt genau ein x mit der Eigenschaft E" schreibt man oft als ∃|x: E(x) oder ∃!x: E(x) oder ∃=1x: E(x). Wenn man so eine Aussage beweisen will, empfiehlt es sich, diese Aussage in einfachere Teile zu zerlegen, etwa- ∃x: [ E(x) ∧ ¬∃y: (y≠x ∧ E(y)) ]. (Gelesen: es gibt ein x, sodass x erstens die Eigenschaft E hat, und es zweitens kein weiteres y gibt [das also ungleich x ist], welches auch die Eigenschaft E hat)
- ∃x: [ E(x) ∧ ∀y: (E(y) ⇒ y=x) ]. (Also: es gibt ein x, dass die Eigenschaft E hat, sodass jedes y, das auch die Eigenschaft E hat, bereits dieses x sein muss.)
- [ ∃x: E(x) ] ∧ [ ∀y ∀z: (E(y)∧E(z) ⇒ y=z) ]. Das heißt: erstens gibt es ein x mit Eigenschaft E, und zweitens gilt: wann immer sowohl y als auch z die Eigenschaft E haben, müssen sie gleich sein.
- Erstens "Existenz": Es gibt MINDESTENS ein x mit der Eigenschaft E.
Das könnte man auch als ∃≥1x: E(x) schreiben. - ... und
zweitens "Eindeutigkeit": Es gibt nicht zwei verschiedene Objekte y,z mit der Eigenschaft E, also kurz gesagt: es gibt HÖCHSTENS ein x mit der Eigenschaft E.
Das könnte man auch als ∃≤1x: E(x) schreiben.
3. VARIABLE
(Eine ausführlichere Version dieser Hinweise finden Sie auf dem Weblog von Tim Gowers: Tips for handling variables)3a. Namen
Verwenden Sie Namen (üblicherweise: Buchstaben, oder Buchstaben mit Indizes). Also nicht: "Betrachten wir einen beliebigen Vektor ..." sondern "Betrachten wir einen beliebigen Vektor x". (Das geht natürlich nur dann, wenn Sie den Namen "x" nicht schon früher vergeben haben.)Dies hat den Vorteil, dass Sie sich in späteren Sätzen sehr einfach auf diesen Vektor beziehen können und diesen Vektor auch in Formeln verwenden können. Sie können zum Beispiel sagen "Es gibt zwei Fälle: entweder x=0, oder x ungleich 0" und müssen nicht umständlich erklären: "Es gibt zwei Fälle: entweder der gerade betrachtete Vektor ist 0, oder der gerade betrachtete Vektor ist ungleich 0."
Dies ist insbesondere wichtig, wenn Sie eine Aussage "Für alle..." zeigen sollen. Wenn Sie zeigen sollen "jede natürliche Zahl > 4 hat die Eigenschaft E", dann sollte der Beweis mit den Worten
- "Sei n eine beliebige natürliche Zahl mit n>4. Wir wollen zeigen, dass n die Eigenschaft E hat."
3b. Guten Tag, mein Name ist Vektor x. Ich bin ein Element des Raums V.
Wann immer Sie einen neuen Namen vergeben, stellen Sie klar, um was für ein Objekt es sich handelt. Also nicht "betrachten wir ein beliebiges x", sondern "betrachten wir einen beliebigen Vektor x" oder "einen beliebigen Vektor x im Definitionsbereich von f".Sprechen Sie nicht unvermittelt von einer neuen Variable x, ohne zu erklären, welche Rolle dieses x spielt. Fast immer können Sie eine der folgenden beiden Phrasen verwenden:
- "Sei x beliebig", oder Varianten davon: "Sei x ein beliebiger Vektor im Raum U", "Sei x eine beliebige positive reelle Zahl", "Sei x eine beliebige Matrix
mit der Eigenschaft E" etc.
Diese Formulierung empfiehlt sich dann, wenn Sie eine allquantifizierte Aussage "Für alle x..." beweisen wollen.
Aus psychologischen Gründen empfiehlt es sich, hier zu überlegen, ob es so ein x überhaupt gibt; mathematisch notwendig ist dies hier aber nicht. Wenn es nämlich kein x mit der Eigenschaft E gibt, dann ist die Aussage "für alle x mit der Eigenschaft E gilt **" automatisch wahr, egal was Sie für "**" einsetzen; allerdings ist der Wahrheitswert solcher Aussagen oft uninteressant oder irrelevant. - "Sei x so definiert", oder "Wir wählen nun ein x mit der Eigenschaft E"; dies geht nur dann, wenn Sie schon gezeigt haben, dass es so ein x gibt. (Wenn es offensichtlich ist, dass es so ein x gibt, so brauchen Sie diese Tatsache nicht beweisen, sollten Sie aber zumindest erwähnen, um allen, die zuhören oder mitlesen, die Möglichkeit zu geben, sie zu bezweifeln.) Alles, was Sie ab jetzt zeigen, gilt nicht für alle x, sondern nur für dieses eine.
3c. Quantifizierte Variable
Wenn Sie verschiedene Eigenschaften durch quantifizierte Formeln beschreiben, ist es oft sinnvoll, in den verschiedenen Formeln verschiedene Variablen zu verwenden. Zum Beispiel könnten wir eine Zahl n "rot" nennen, wenn es ein k gibt, sodass eine vorgegebene Beziehung R(n,k) gilt; wir nennen n "blau", wenn es ein k gibt, sodass B(n,k) gilt. (Zum Beispiel könnte R(n,k) die Beziehung n=k*k sein; "rote" Zahlen sind dann einfach Quadratzahlen.)Abgekürzt lauten die Definitionen nun so:
- n ist rot ⇔ ∃ k: R(n,k)
- n ist blau ⇔ ∃ k: B(n,k)
- n ist rot ⇔ ∃ k: R(n,k)
- n ist blau ⇔ ∃ j: B(n,j) (Die existentiell quantifizierte Variable k wurde hier zu j umbenannt.)
4. WORTE, FORMELN, BILDER
Die Lösung einer Aufgabe besteht im allgemeinen nicht nur aus Formeln. Es ist in den Übungen erlaubt (und oft sogar erwünscht), dass sie ganze Sätze oder Halbsätze (wie z.B. "weil x laut Annahme nicht durch 10 teilbar ist") aussprechen oder sogar an die Tafel schreiben. Es genügt oft nicht, wenn Ihre Vorbereitung nur aus einer Rechnung besteht. (Und wenn Ihre Vorbereitung tatsächlich nur aus einer Rechnung besteht, dann führen Sie die Rechnung auch selbst durch. Es reicht nicht, etwas durchzulesen, was andere gerechnet haben! Auch nicht mehrmals.)Wenn Sie zu Beispiel zeigen wollen, dass das Quadrat jeder geraden Zahl gerade ist, dann reicht es nicht, einfach die Rechnung (2k)2=4*k2 = 2*2*k2 anzuschreiben, sondern Sie müssen Ihre Überlegungen auch verbalisieren (oder jedenfalls: auf Anfrage verbalisieren können):
- Sei n eine beliebige gerade Zahl. Dann lässt sich n in der Form n=2k schreiben. (Oder genauer: Dann gibt es eine ganze Zahl k mit n=2k, nämlich k:=n/2.)
- Daher ist n2 = (2k)2=4*k2 = 2*(2*k2).
- Also lässt sich auch n2 durch 2 ohne Rest dividieren (nämlich mit dem Quotienten 2*k2), ist also gerade.
Oft ist es sinnvoll und erhellend, eine Situation (wie etwa "p<q") graphisch darzustellen (etwa indem man zwei Punkte p und q einzeichnet, wo q über p liegt, oder rechts von p).
Bedenken Sie aber, dass
Sie Begründungen (auf Anfrage) auch verbalisieren müssen.
Z.B. reicht es meist nicht aus, wenn Sie die Frage "Woher wissen Sie, dass p<q ist?", mit "Das sehe ich in diesem Diagramm" beantworten. Eine bessere Antwort ist meistens
- "weil wir das schon früher bewiesen haben" Zum Beispiel: in der Vorlesung, oder in einer früheren Übungsaufgabe. In der Vorlesung ist allerdings meist ein allgemeinerer Satz bewiesen worden, z.B.: "r<s gilt immer dann wenn XXX". Wenn Sie sich auf so einen Satz berufen, müssen Sie den Satz erstens richtig zitieren und zweitens überprüfen, ob er sich hier auch anwenden lässt, d.h. ob die Voraussetzung XXX erfüllt ist -- wobei natürlich das r und s aus der Vorlesung durch das jetzt betrachtete p und q ersetzt werden muss.
- oder: "weil wir das hier bewiesen haben" Beim Wort "hier" zeigen Sie auf die Stelle an der Tafel, wo die angezweifelte Behauptung als bereits akzeptiertes Zwischenresultat steht -- daher ist es wichtig, Zwischenresultate auch anzuschreiben.
- oder, eine Variante: "weil das direkt aus diesem Resultat folgt" (wieder zeigen Sie auf eine Stelle an der Tafel). In unserem Beispiel: "weil wir hier schon p<x und x<q bewiesen haben und weil die hier verwendete Relation < transitiv ist."
- oder: "weil wir das angenommen haben", zB "weil wir gerade den Fall p<q betrachten". (Daher ist es wichtig, alle Annahmen auch aufzuschreiben, um sich leichter auf sie berufen zu können.)
- Variante: "weil das in der Definition steht" In welcher Definition? Vielleicht war ja q als die kleinste Primzahl größer als p definiert. Oder geht es um die Definition von <? Zeigen Sie einfach auf die Definition, die hoffentlich an der Tafel steht.
- oder: "weil das so in der Angabe steht."
5. FALLUNTERSCHEIDUNG
5a. Fall 1, Fall 2, ...
Oft ist es notwendig, verschiedene Szenarien durchzuspielen, z.B. kann ein Argument nur für gerade Zahlen funktionieren, und ungerade Zahlen werden mit einem anderen Beweis behandelt. Ein Beweis könnte vielleicht so aussehen:- "Sei n eine beliebige natürliche Zahl mit n>4. Wir wollen zeigen, dass n die Eigenschaft E hat. Wir unterscheiden 3 Fälle:
- n=5.
- n>5, und n gerade.
- n>5 und n ungerade.
Im 2.Fall ist n durch 2 teilbar, nennen wir die Zahl n/2 der Einfachkeit halber k, (abgekürzt: Sei n=2k) ..... (Argument für 2k durchführen, und dabei beachten, dass k mindestens 3 ist)
Im 3.Fall ist n von der Form 2k+1...
In jedem der 3 Fälle hat n die Eigenschaft E, also hat jedes n>4 die Eigenschaft E. "
5b Vollständigkeit, Redundanz
Manchmal ist es nicht ganz offensichtlich, dass tatsächlich bereits alle Fälle betrachtet wurden; die Vollständigkeit der Fallunterscheidung muss man dann noch separat beweisen. Wenn Sie zum Beispiel eine Aussage "für alle reellen Zahlen x und y: ..." beweisen müssen, genügt es nicht, nur die Fälle x<y und y<x zu betrachten; es könnte ja auch x=y gelten.In einem Beweis müssen die Fälle nicht immer disjunkt sein. Man kann zum Beispiel eine Aussage zuerst für alle x≥0 beweisen, dann für alle x≤0.
Wenn man aber eine Konstruktion mit Hilfe einer Fallunterscheidung durchführt, in der die Fälle nicht disjunkt sind,
- etwa "f(x):= A(x) für x≥0, und f(x):= B(x) für x≤0"
5c Division durch 0
Unmöglich. Nicht einmal an der Universität kann man durch 0 dividieren. Nicht einmal ich als Professor mit -zig Jahren an mathematischer Erfahrung kann das.In jedem Körper gilt, dass das additiv neutrale Element (meist "0" genannt) kein multiplikatives Inverses hat. Wenn in Ihrem Beweis also irgendwo ein Inverses y-1 oder ein Quotient x/y auftaucht, und Sie noch nicht wissen, ob y gleich 0 sein könnte, empfiehlt sich eine Fallunterscheidung: Im Fall, dass y ungleich 0 ist, können Sie den Beweis einfach fortführen, aber im Fall y=0 müssen Sie sich etwas anderes ausdenken. Oft ist der Fall y=0 ohnehin trivial oder zumindest rasch zu erledigen, aber manchmal findet sich hier der entscheidende Punkt Ihres Beweises oder Ihrer Rechnung.
(Die Vollständigkeit dieser Fallunterscheidung ist klar, denn einer der Fälle "gleich 0", "ungleich 0" muss ja eintreten.)
6. OHNE BESCHRÄNKUNG DER ALLGEMEINHEIT SEI ...
Diese Phrase hört man oft in einem mathematischen Beweis (und sehr selten in der Alltagssprache). Was bedeutet sie?Wenn wir zum Beispiel zeigen wollen, dass es zwischen zwei reellen Zahlen (genauer: zwischen zwei verschiedenen reellen Zahlen) immer eine rationale Zahl gibt, könnte der Beweis mit folgenden Worten beginnen:
- Seien x ungleich y reelle Zahlen, oBdA x < y. ...
- Es gibt eigentlich zwei Fälle: x<y, und y<x. Wir werden den Beweis zunächst unter der zusätzlichen Annahme x<y
führen; den Rest des Beweises, dass die behauptete Tatsache nämlich auch unter der Annahme y<x gilt, überspringen wir, weil er ganz genauso verläuft (indem man den ersten Teil des Beweises hernimmt und immer x und y vertauscht).
In Wirklichkeit liegt also eine Fallunterscheidung vor, bei der zwei Fälle einander aber so ähnlich sind, dass sie mit einer gemeinsamen Überlegung erledigt werden können.
- Oder, anders formuliert: Wir betrachten zwei beliebige verschiedene reelle Zahlen; eine der beiden muss kleiner als die andere sein -- nennen wir die kleinere x und die größere y.
Achtung! Eine gewisse Erfahrung ist nötig, um zu wissen, wann diese Phrase angewendet werden kann. Gehen Sie bei der Vorbereitung der Übungsaufgaben lieber auf Nummer Sicher und überspringen Sie keine Fälle. Bei der Präsentation der Aufgabe können Sie ja dann versuchen, die magische Formel oBdA einzusetzen - wenn das vom Übungsgruppenleiter zurückgewiesen wird, sind Sie darauf vorbereitet.
7. ZWISCHENRESULTATE
Wenn Sie ein Zwischenergebnis gefunden haben, notieren Sie dieses an der Tafel, um sich später darauf berufen zu können. Um sich selbst und dem Publikum klar zu machen, wie weit ein Beweis oder eine Konstruktion schon fortgeschritten ist, empfiehlt es sich, auch einen Satz der Form "Zu zeigen ist jetzt also nur noch: ... " einfließen zu lassen.Unterscheiden Sie bitte sorgfältig die folgenden Situationen:
- "Zu zeigen ist noch" oder "Behauptung": Sie schreiben eine Behauptung B an (oder eine Gleichung, eine Eigenschaft, einen
Satz, ein Lemma), die noch zu beweisen ist, sozusagen als Wegweiser, um das Ziel nicht aus den Augen zu verlieren.
(Es empfiehlt sich, der Klarheit halber darauf hinzuweisen, dass diese Behauptung noch nicht bewiesen ist, etwa indem man "Zu zeigen:" davor schreibt, oder indem man ein Fragezeichen über das zu zeigenden Gleichheitszeichen setzt, oder indem man gleich dahinter den Beweis der Behauptung mit dem Wort "Beweis:" beginnt, etc. Wenn Sie diese Behauptung erst später beweisen, empfiehlt es sich, ihr einen Namen zu geben (Lemma 1, Behauptung (*), etc), damit Sie dann später den Beweis mit den Worten "Beweis von Lemma 1" bzw "Beweis von (*)", etc, beginnen lassen können.) - Wir haben gezeigt: Sie schreiben eine Behauptung B an, die Sie gerade bewiesen haben, zur Dokumentation Ihres Fortschritts.
- Laut Annahme gilt: Sie schreiben eine Behauptung B an, die gilt, weil Sie sie angenommen haben. (Entweder weil die Angabe diese vorgibt, etwa weil Sie "aus B folgt C" beweisen müssen, oder weil Sie im Rahmen einer Fallunterscheidung B angenommen haben und den Fall nicht-B später betrachten.)
Am Schluss eines Beweises oder einer Konstruktion empfiehlt sich ein zusammenfassender Satz, in dem Sie noch einmal die wichtigste Tatsache wiederholen: "Also haben wir zu beliebigem y ein x mit f(x)=y gefunden, daher ist f wirklich surjektiv, was zu beweisen war."
8. INDIREKTER BEWEIS
8a. ... one of a mathematician’s finest weapons
Reduction ad absurdum is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game. Wenn Sie zeigen können, dass eine Annahme A auf einen Widerspruch führt, dann haben Sie damit gezeigt, dass A falsch sein muss. Umgekehrt: Wenn Sie zeigen können, dass die Annahme "B gilt nicht" auf einen Widerspruch führt, haben Sie damit gezeigt, dass B wahr sein
muss.
Um etwa zu zeigen, dass jede natürliche Zahl n>4 die Eigenschaft E hat, können Sie einen Beweis so beginnen:
- "Sei n eine beliebige natürliche Zahl mit n>4. Wir wollen zeigen, dass n die Eigenschaft E hat. Wir gehen indirekt vor: Nehmen wir an, dass n nicht die Eigenschaft E hat."
8b. Kontraposition
Die Kontraposition kann als Spezialfall des indirekten Beweises gesehen werden (oder als eigene Beweistechnik):- Statt "Aus A folgt B" zu beweisen, genügt es, "aus non-B folgt non-A" zu zeigen. (Oder umgekehrt: Statt "aus non-B folgt non-A" ist vielleicht "aus A folgt B" einfacher.)
- Statt "Aus A folgt non-C" zu beweisen, genügt es, "aus C folgt non-A" zu beweisen. Oder umgekehrt.
9. WEITERE BEWEISTECHNIKEN
9a. Logische Umformungen
- Um "aus A folgt B" zu beweisen, beginnt man meist mit "Angenommen, dass A gilt". Mit Hilfe dieser Annahme muss man B zeigen. Beachten Sie:
- Im Verlauf des Beweises dürfen Sie an beliebigen Stellen A verwenden: "... weil wir ja A angenommen haben".
- Hingegen ist die Phrase "... daher gilt A" zwar formal wahr, aber unsinnig. Die Aussage A brauchen Sie nicht beweisen; sie gilt bereits laut Annahme.
- Ebenso ist es nicht hilfreich, "Nehmen wir an, dass B gilt" zu sagen.
- Um "aus A folgt B" zu beweisen, kann man auch "A und nicht-B" annehmen, und daraus einen Widerspruch folgern.
- Es kann also im Beweis von "Aus A folgt B" durchaus sinnvoll sein, "Nehmen wir an, dass B nicht gilt" zu sagen. Sie könnten hier das Stichwort "indirekter Beweis" verwenden.
- Ebenso kann es sinnvoll sein, an irgend einer Stelle die Schlussfolgerung "daher gilt A nicht" zu ziehen, dann ist nämlich ein Widerspruch zur Annahme erreicht.
- Statt "A oder B" zu beweisen, kann man "aus nicht-A folgt B" beweisen, oder aus "nicht-A und nicht-B" einen Widerspruch herleiten.
Wenn man "A oder B" aus einer Annahme X beweisen soll, ist es oft einfacher, die Kontraposition zu beweisen: "Aus non-A und non-B folgt, dass X nicht gilt". Oder Sie zeigen, dass aus "X und non-A" die Behauptung B folgt.
Kurz gesagt, die folgenden drei Formeln sind äquivalent:- X ⇒ (A ∨ B)
- (¬A ∧ ¬B) ⇒ ¬X
- (X ∧ ¬A ) ⇒ B
- Wenn man einen Allsatz "für alle x" beweisen will, muss dieser Beweis für beliebige Auswahl von x funktionieren; stellen Sie sich vor, dass ein böswilliger Gegner das x auswählen kann. In Beweisen empfiehlt sich hier die Phrase "Sei x beliebig..."
- für einen Beweis einer Aussage der Form "es gibt ein x" dürfen Sie das x wählen. In Beweisen hört man oft "Sei x wie folgt definiert" oder "Wir zeigen, dass das folgende x die Eigenschaft ... hat", oder "es gibt ein x mit dieser Eigenschaft, nämlich x:= ...":
- Um eine Mengeninklusion A ⊆ B zu beweisen, muss man zeigen, dass jedes Element von A auch in B liegt; ein
Beweis beginnt daher oft mit "Sei x in A beliebig", und endet mit "... x in B. Jedes Element von A liegt also in B, das heißt A ⊆ B".
Um zu zeigen, dass A ⊆ B nicht gilt, genügt es, ein einziges "Gegenbeispiel" zu finden, also ein Element von A, welches nicht in B liegt. - Eine Mengengleichheit A=B beweist man oft, indem man A⊆B und B⊆A in 2 getrennten Schritten zeigt. (Machen Sie sich und Ihrem Publikum dabei immer klar, welche der beiden Inklusionen Sie gerade beweisen.)
- Zwei Funktionen f,g: A → B sind genau dann gleich, wenn für alle a in A die Gleichung f(a)=g(a) gilt. Wenn f und g durch explizite Formeln gegeben sind, kann man das meist leicht nachrechnen. Wenn f und/oder g durch Fallunterscheidungen definiert sind, muss man im Beweis auch möglicherweise Fälle unterscheiden.
Um die Ungleichheit von f und g zu zeigen, genügt es, ein einziges a in A zu finden, sodass f(a) ≠ g(a) gilt.
9b. Negation
- Die Negation der Aussage "Für alle x gilt A" ist äquivalent zu "es gibt ein x, sodass nicht-A gilt".
- Die Negation der Aussage "Es gibt ein x mit der Eigenschaft A" ist äquivalent zu "für alle x gilt nicht-A"
- Die Negation der Aussage "A oder B" ist äquivalent zu "nicht-A und nicht-B"
- Die Negation der Aussage "A und B" ist äquivalent zu "nicht-A oder nicht-B"
- Die Negation der Aussage "Aus A folgt B" ist äquivalent zu "A und nicht-B".
- Die Negation der Aussage "A ⇔ B" ist äquivalent zu "(A und nicht-B) oder (nicht-A und B)".
- Die Negation der Aussage "¬A" ist äquivalent zu A.
- ¬(∀x: A) ⇔ ∃x(¬A)
- ¬(∃x: A) ⇔ ∀x(¬A)
- ¬(A ∨ B) ⇔ ¬A ∧ ¬B
- ¬(A ∧ B) ⇔ ¬A ∨ ¬B
- ¬(A ⇒ B) ⇔ A ∧ ¬B (Diese Äquivalenz scheint mir besonders wichtig, weil sie helfen kann, die Implikation besser zu verstehen.)
- ¬(A ⇔ B) ⇔ (A ∧ ¬B) ∨ (¬A ∧ B)
- ¬(¬A) ⇔ A
10. Ergänzungen (WS 2015)
Mengen Beachten Sie den Unterschied zwischen Mengen und Elementen! Die Zahl 0 ist etwas anderes als die einelementige Menge {0}, deren einziges Element die Zahl 0 ist."Overloading" von Symbolen
Beachten sie auch, dass die Bedeutung des Symbols "0" vom Kontext abhängt. Wenn wir von einem Körper sprechen, ist mit 0 meistens das additionsneutrale Element gemeint; wenn wir von einem Vektorraum V über einen Körper K sprechen, kann mit 0 entweder das additionsneutrale Element 0K des Körpers gemeint sein, oder das additionsneutrale Element 0V des Vektorraums. Im allgemeinen sind die beiden nicht gleich.Gelegentlich ist mit dem Symbol 0 auch die "Nullabbildung" gemeint, das ist jene konstante Funktion (definiert auf dem gerade betrachteten Vektorraum, auf der gerade betrachteten Gruppe, etc), die für jede beliebige Eingabe den Wert 0 ausgibt.
Mit dem Symbol 1 ist oft die natürliche Zahl 1 gemeint, oft aber auch einfach das multiplikationsneutrale Element des gerade betrachteten Körpers.
Mit dem Symbol 2 ist so gut wie immer der Wert von 1+1 gemeint. Allerdings handelt es sich bei "1" oft nicht um die natürliche Zahl 1, und bei "+" nicht um die übliche Addition von ganzen Zahlen. Es kann durchaus vorkommen, dass 1+1=0 gilt; in diesem Fall ist der Bruch 1/2 undefiniert. (Ebenso kann es vorkommen, dass x+x=0 gilt,
ohne dass x=0 ist. Aus x+x=0 kann man in einem Körper zunächst nur schließen, dass (1+1)x=0 ist. Wenn 1+1 ungleich null ist, kann man diese Gleichung mit dem Inversen von 1+1 multiplizieren...) Mengennotation
Im Allgemeinen empfiehlt es sich, mit der Aussage E(x) statt mit "x in M" zu arbeiten, weil wir mit Elementen oft besser umgehen können als mit Mengen. Wohldefiniertheit:
- Wenn wir eine Funktion f durch eine Formel der Form f(x) = ...x... definieren, wobei ...x... irgend ein Ausdruck ist, der i.A. von x abhängt, muss man überprüfen, dass dieser Ausdruck immer einen Wert liefert. ("immer" heißt: für jedes
x im Definitionsbereich von f.)
Das ist meistens kein Problem, aber bei Ausdrücken, in denen zum Beispiel multiplikative Inverse vorkommen (z.B. Brüche wie 1/(x-3)), muss man sicherstellen, dass diese auch definiert sind (im Beispiel: dass 3 nicht im Definitionsbereich liegt, oder dass f(3) anders definiert wird). Ähnliches gilt, wenn Quadratwurzeln auftreten.
- WICHTIG Wenn wir eine Funktion f durch eine Formel der Form f(H(x)) = ...x... definieren, wobei H eine schon bekannte
Funktion ist (z.B. H(x) = x+U, Nebenklasse. In komplizierteren Fällen auch f(H(x,y)) = ...x...y... ), dann verwenden wir das Schlagwort "wohldefiniert" oder "vom Repräsentanten unabhängig", um zu behaupten, dass es überhaupt eine Funktion f gibt, die durch diese Funktion beschrieben wird. Die Wohldefiniertheit ist zu folgendem Sachverhalt äquivalent:
- für alle (relevanten) x und x' gilt: WENN H(x) = H(x'), DANN ...x... = ...x'...
- Beispiel: Eine der beiden folgenden Definitionen liefert eine auf den positiven rationalen Zahlen wohldefinierte Funktion, die andere nicht:
- ∀x,y ∈ Q+: f(x/y) = y/x.
- ∀x,y ∈ Q+: g(y/x) = y-x.