Die Sprache der Mathematik

1. IMPLIKATION

• 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.)

 2n+1     3
 ----  ≥  -   ⇔  2(2n+1) ≥ 3(n+1) ⇔ 4n+2 ≥ 3n+3  ⇔ n ≥ 1
  n+1     2            

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

1. 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
2. von einem beliebigen Objekt x mit einer Zusatzeigenschaft (zB einem Vektor ungleich 0) sprechen.
3. 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 ...")

• ∀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

• 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 ]).

∀b∈BA: [ b ist schnell ].

BA ⊆ S   (Die Menge der blauen Autos ist Teilmenge der Menge der schnellen Objekte.)

2c. Hinweis

• 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

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

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: x²-3>0∧x>0: x>1 sondern ∀x:( x²-3>0∧x>0 ⇒ x>1) oder noch deutlicher ∀x:( (x²-3>0∧x>0) ⇒ x>1)

2f. es gibt genau ein

• ∃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

3a. Namen

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.

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

Also z.B.: ∃x: A(x) und ∃y: B(y). Theoretisch könnten Sie natürlich auch die zweite Formel durch die äquivalente Formel ∃x: B(x) ersetzen, das kann aber zu Verwirrung führen, weil man den Eindruck bekommen könnte, dass es ein gemeinsames x mit beiden Eigenschaften A und B geben muss.

4. WORTE, FORMELN, BILDER

Wenn Sie zu Beispiel zeigen wollen, dass das Quadrat jeder geraden Zahl gerade ist, dann reicht es nicht, einfach die Rechnung (2k)²=4*k² = 2*2*k² 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 n² = (2k)²=4*k² = 2*(2*k²).
• Also lässt sich auch n² durch 2 ohne Rest dividieren (nämlich mit dem Quotienten 2*k²), 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, ...

• "Sei n eine beliebige natürliche Zahl mit n>4. Wir wollen zeigen, dass n die Eigenschaft E hat. Wir unterscheiden 3 Fälle:
  1. n=5.
  2. n>5, und n gerade.
  3. n>5 und n ungerade.
  Den 1.Fall haben wir letzte Woche behandelt.
  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

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

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 ...

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. Bevor Sie z.B. "oBdA x<y" sagen, überlegen Sie, welche anderen Fälle es noch gibt (hier: x>y und x=y), und ob diese tatächlich ähnlich wie der behandelte Fall x<y aussehen.

7. ZWISCHENRESULTATE

Wenn Ihr Beweis halbwegs kompliziert ist, empfiehlt es sich, zunächst ein paar Worte über die Struktur des Beweises zu sagen:

• Zuerst zeigen wir x≤z, dann z≤y. Damit haben wir x≤y. Schließlich (das wird der schwierigste Teil) beweisen wir x≠y, und erhalten so x<y.
  (Da in der UE oft nicht genug Zeit ist, um alle Einzelheiten zu präsentieren, kann es sein, dass Sie gebeten werden, nur den "interessanten" Teil Ihrer Argumentation vorzutragen.)

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

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

• 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

1. 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.
2. 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.
3. 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
4. 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..."
5. 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:= ...":
6. 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.
7. 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.)
8. 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".
  Wenn Sie also zeigen wollen, dass ein Allsatz "Für alle x..." falsch ist, dann geben Sie am besten ein Gegenbeispiel an.
  (EIN Gegenbeispiel; als Fleißaufgabe gerne auch die Menge aller Gegenbeispiele, aber Sie müssen auch zeigen, dass diese Menge nicht leer ist.)
• 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 0_K des Körpers gemeint sein, oder das additionsneutrale Element 0_V 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

Wenn eine Menge M durch M={x in V | E(x) } definiert ist, wobei E(x) eine Aussage ist, die meist irgendwie von x abhängt (z.B. "x ungleich 0" oder "∃y x=y*y), dann ist (für jedes a in V) die Aussage "a ∈ M" einfach äquivalent zu E(a). Zum Beispiel ist "x in ker(f)" äquivalent zu "f(x)=0", weil ker(f) als die Menge { x : f(x)=0 } definiert ist.

Oft 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; statt M ⊆ M' zeigen Sie "Wenn x in M ist, also Eigenschaft E hat, dann ist x in M'". Dazu müssen Sie natürlich immer die Definition von M im Kopf haben.

Wohldefiniertheit:

1. 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.

2. 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'...
   (Wenn Sie so eine Implikation beweisen wollen, dürfen Sie natürlich nicht die Funktion f verwenden. Dass es eine Funktion f gibt, die die gewünschte Eigenschaft hat, ist ja noch nicht bewiesen.)
   • Beispiel: Eine der beiden folgenden Definitionen liefert eine auf den positiven rationalen Zahlen wohldefinierte Funktion, die andere nicht:
     1. ∀x,y ∈ Q⁺: f(x/y) = y/x.
     2. ∀x,y ∈ Q⁺: g(y/x) = y-x.
3. Alternative Beschreibung des vorigen Punktes: Nehmen wir an, eine Funktion f wird durch Instruktionen beschrieben:
   • "Um f(r) zu berechnen, finden wir zunächst ein z sodass blabla (zum Beispiel: H(z)=r) , dann rechnen wir mit r und z wie folgt blabla und erhalten ein Resultat y - das soll f(r) sein.
   Damit so eine Definition eine wohldefinierte Funktion liefert, müssen wir sicher stellen, dass jeder, der diesen Instruktionen folgt, das gleiche Resultat bekommt. Zwei Beispiele, wo es um eine Funktion von den positiven reellen Zahlen in die reellen Zahlen geht:
   • Wir definieren f(x²) = x+1.
     Um f(r) zu berechnen, finden wir zunächst ein x in R mit x²=r. Dann addieren wir 1 zu x - das ist das Resultat.
     NICHT WOHLDEFINIERT! Für die Berechnung von f(9) könnten Sie 4 erhalten, ich aber -2. (Nachrechnen!)
   • Wir definieren g(x²) = |x|+ 1.
     Um g(r) zu berechnen, finden wir zunächst ein x in R mit x²=r. Dann addieren wir 1 zum Betrag von x - das ist das Resultat.
     WOHLDEFINIERT! Verschiedene Rechenwege, die beide dieser Instruktion folgen, führen zum gleichen Ziel.

Martin Goldstern, 2008, 2009,... , 2021, 2023