Mathematische Grundlagen 1: Logik und Algebra · Warnung Dieses Skript enthält unter Umständen Fehler und Ungenauigkeiten jeder Art.FallsSiesolcheentdecken,wäreesnett,wennSiemirIhreAnmerkungen

Mathematische Grundlagen 1: Logik undAlgebra

Dr. Viktoriya Ozornova

20. Januar 2018

1

WarnungDieses Skript enthlt unter Umstnden Fehler und Ungenauigkeiten jederArt. Falls Sie solche entdecken, wre es nett, wenn Sie mir Ihre Anmerkungenper E-Mail an

[email protected]

schicken knnten. Dieses Skript erhebt keinerlei Anspruch auf Originalitt.Insbesondere habe ich bei der Erstellung dieses Skriptes die vorherigen Ma-terialen von Emanuele Delucchi und Martin Dlugosch herangezogen, sowiedie Bcher Mathematik fr Informatiker von G. Teschl und S. Teschl, Ma-thematik fr Informatiker von B. Kreuler und G. Pfister und Mathematikfr Informatiker von P. Hartmann.

Ferner mchte ich den Leuten danken, die bei der Erstellung dieses Skrip-tes auf die eine oder andere Weise hilfreich waren, insbesondere RomanBruckner, Emanuele Delucchi, Martin Dlugosch, Eva-Maria Feichtner, Di-mitry Feichtner-Kozlov, Tim Haga, Damien Imbs, Jan-Philipp Litza, LennartMeier, Jan Senge, Ingolf Schfer, Kirsten Schmitz sowie den vielen Studie-renden der Informatik, die mir zu dem Skript Rckmeldung gegeben haben.

Inhaltsverzeichnis

I Allgemeine Grundlagen 4

0 Chomp 4

1 Aussagenlogik 81.1 Was ist eine Aussage? . . . . . . . . . . . . . . . . . . . . . . 81.2 Verneinung von Aussagen . . . . . . . . . . . . . . . . . . . . 91.3 Und- und Oder-Verknpfungen . . . . . . . . . . . . . . . . . 101.4 Rechnen mit logischen Termen . . . . . . . . . . . . . . . . . . 121.5 Implikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.6 quivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.7 Disjunktive und konjunktive Normalformen . . . . . . . . . . . 18

2 Elementare Mengenlehre 222.1 Grundlegende Definitionen . . . . . . . . . . . . . . . . . . . . 222.2 Mengenoperationen . . . . . . . . . . . . . . . . . . . . . . . . 25

3 Vollstndige Induktion 29

4 Abzhlen I 38

Viktoriya Ozornova INHALTSVERZEICHNIS

5 Abbildungen 48

6 Abzhlen II 58

7 Relationen 65

II Zahlentheorie 75

8 Teilbarkeit 75

9 Modulare Arithmetik 80

10 Euklidischer Algorithmus I 91

11 Zahlentheorie in der Kryptographie 95

12 Euklidischer Algorithmus II 102

13 Primzahlen 111

14 Chinesischer Restsatz 121

III Graphentheorie 124

15 Grundbegriffe der Graphentheorie 124

16 Wege in Graphen 129

17 Bume 136

18 Grad einer Ecke in einem Graphen 143

19 Eulertouren und Eulerkreise in Graphen 148

20 Hamiltonkreise in Graphen 159

3

Viktoriya Ozornova 0 CHOMP

Teil I

Allgemeine Grundlagen0 ChompNach der Schule assoziieren die meisten mit der Mathematik vor allem Zahlenund Formeln; hufig wird z.B. die Geometrie, die eine andere Art und Weiseist, Mathematik zu betreiben, dabei vergessen. Bei Chomp haben wir einneues Beispiel dafr, wie Mathematik aussehen kann.

Chomp ist ein Spiel. Es gibt jeweils zwei Spieler, die A und B genanntwerden. Gespielt wird auf einem Spielfeld, das aus einer rechteckigen TafelSchokolade besteht. Diese Tafel ist in k n kleine quadratische Stckchenunterteilt, und das untere linke Stckchen ist vergiftet.

Die Spieler ziehen abwechselnd. Ein Spielzug, also ein Biss, besteht dar-in, sich eins der quadratischen Stckchen, die noch da sind, auszusuchenund dieses Stckchen sowie alle Stckchen rechts davon und alle oberhalbdavon abzubeien. Beim Abbeien entsteht ein Gerusch, das ungefhr wieChomp klingt. Man muss jedes Mal ziehen und kann keinen Zug aussetzen.Verloren hat, wer die vergiftete Ecke isst. Ein Beispielspiel knnte also wiefolgt aussehen:

4


A

B

A

An dieser Stelle bleibt B nichts anderes brig, als die vergiftete Ecke zuessen; somit hat B also verloren.

Wenn man das Spiel einige Male spielt, so fragt man sich, ob es ein Rezeptgibt, der einem erlaubt, immer zu gewinnen, eine sogenannte Gewinnstra-tegie. Etwas hnliches kennen die meisten aus Tic-Tac-Toe: da gibt es einRezept, wie man stets zumindest ein Unentschieden erreichen kann. An dieserStelle ist es eine wichtige Beobachtung - beim Chomp kann es kein Unent-schieden geben; nach einer gewissen Zeit wird alle Schokolade aufgegessensein, denn sie wird mit jedem Zug immer weniger, und am Ende von diesemProzess hat jemand die Giftecke gegessen. Es gibt also einen Verlierer undeinen Gewinner.

Fr jedes konkrete Chomp knnen wir die komplette Liste aller mgli-chen Spielstnde und aller Zge aufstellen. Wir machen das am Beispiel vom2 2-Chomp. brigens kann jeder Spieler sich jederzeit fr die giftige linkeuntere Ecke zum Abbeien entscheiden - allerdings ist es ziemlich dumm,denn dann verliert er sofort. In dem Diagramm, wo die Schokolade ab jetztetwas vereinfacht dargestellt wird, lassen wir diese dumme Option aus.

5


A

B

A

Aus dieser Tabelle sehen wir - macht A am Anfang den richtigen Zug(in diesem Fall ist es, die rechte obere Ecke abzubeien), so kann er sichden Gewinn sichern. Wenn er allerdings dumm spielt, hilft ihm diese theo-retische Mglichkeit nicht. In diesem Fall knnen wir also ganz einfach undsehr konkret eine Liste von Anweisungen erstellen, wie A spielen soll, um zugewinnen, und fr jeden Zug von B einen Gegenzug fr A bestimmen, derihm den Gewinn sichert. Eine solche Beschreibung, was ein Spieler in jederSituation tun soll, um mit Sicherheit - solange er die Anweisungen befolgt -zu gewinnen, heit Gewinnstrategie.

Wie sieht es mit anderen Chomps aus, hat da ein Spieler stets eine Ge-winnstrategie? Wenn man etwas rumprobiert, kommt man auf den Gedanken,dass A eventuell eine Gewinnstrategie haben sollte. Fr 2 3- oder 3 3-Chomps ist diese Gewinnstrategie noch ganz leicht hinzuschreiben, aber eswird immer komplizierter, je grer die Chomps werden. Tatschlich ist kei-ne ganz allgemeine Strategie fr beliebige kn-Chomps bekannt. Allerdingswissen wir trotzdem, dass - auer in dem uninteressanten Fall von einem1 1-Chomp - der erste Spieler stets eine Gewinnstrategie hat. Das wollenwir an dieser Stelle beweisen.

Satz 0.1. Fr jedes k n-Chomp, das nicht das 1 1-Chomp ist, hat der

6


beginnende Spieler eine Gewinnstrategie.

Beweis. Seien k und n fest, und wir nehmen an, dass nicht der 1 1-Chompvor uns liegt. Wir haben festgestellt, dass es in jeder Chomp-Partie einenGewinner gibt. Wir stellen uns vor, dass wir, hnlich wie beim 2 2-Chomp,uns die Liste aller mglichen Spielverlufe anlegen - diese ist unter Um-stnden sehr lang. Allerdings wissen wir mit Sicherheit, dass man von jederSpielstellung heraus entweder durch die richtige Zugfolge sich den Gewinn si-chern kann, oder notwendigerweise verliert. Das heit: Einer von den beidenSpielern muss also eine Gewinnstrategie haben. Es knnen natrlich nichtgleichzeitig A und B eine Gewinnstrategie haben; also ist es entweder A oderB.

Nun stellen wir uns vor, B htte eine solche Gewinnstrategie. An dieserStelle kommt der Strategiediebstahl ins Spiel. B hat einen Gegenzug frjeden Erffnungszug von A; er wei also insbesondere, welche Zugfolge erwhlen muss, wenn A nur die rechte obere Ecke abbeit. Er muss dann -laut seiner Gewinnstrategie - ein bestimmtes Feld, nennen wir dieses FeldX, fr seinen Zug auswhlen und auch danach hat er fr jeden Zug von Aeinen Gegenzug. Aber: Dann knnte A ja damit anfangen, dass er das FeldX auswhlt, was genau denselben Effekt wie soeben der zweite Zug von B.Jetzt nimmt sich A einfach die Strategie von B und tut einfach genau das,was die Strategie fr B vorgesehen hat - er stiehlt die Strategie von B. Dannhtte also A eine Gewinnstrategie. Das ist allerdings im Widerspruch zurAnnahme, dass B die Gewinnstrategie hat. Diese Annahme muss also falschsein! Also hat A eine Gewinnstrategie. Das ist genau das, was wir beweisenwollten. Insbesondere wissen wir jetzt, dass die Aussage des Satzes wahr ist,ohne die konkrete Strategie hingeschrieben zu haben!

7

Viktoriya Ozornova 1 AUSSAGENLOGIK

1 Aussagenlogik

1.1 Was ist eine Aussage?

Die Grundbausteine der Mathematik sind Aussagen.

Definition 1.1. Eine Aussage ist ein grammatikalischer Satz, der entwederwahr oder falsch ist.

Das ist eine Definition - also in etwa so viel wie eine Vokabel. Die De-finitionen an sich sind weder richtig noch falsch, sondern eine Festlegung.Es verhlt sich jedoch anders z.B. im Rahmen eines Mathematik-Kurses -hier sorgen einheitliche Definitionen dafr, dass wir ber dieselben Objektesprechen, wenn wir ein bestimmtes Wort benutzen, und wollen genau wieVokabeln gelernt sein. Insbesondere haben sich diese Definitionen als sinn-voll bewhrt, whrend andere Begriffe, die man vielleicht htte definierenknnen, sich nicht durchgesetzt haben.

Damit ein Satz eine Aussage ist, ist es nicht notwendig, dass man ent-scheiden kann, ob dieser Satz wahr oder falsch ist; es reicht das Wissen aus,dass (genau) eins von beiden zutreffen muss. Hier sind einige Beispiele vonAussagen:

Alle Schafe sind schwarz. (falsch)

Die Zahl 7 ist gerade. (falsch)

Die vorherige Aussage ist falsch. (wahr)

Die Summe der Winkel in jedem Dreieck betrgt 180. (wahr)

Die Zahl

250 ist grer als 16. (falsch)

Ob etwas eine Aussage ist, hngt teilweise vom Kontext ab und davon,ob alle darin vorkommende Objekte definiert bzw. festgelegt sind.

(y 7)2 0 ist ohne Kontext keine Aussage.

Die Decke ist blau. - Dies ist keine Aussage, solange nicht klar ist,welche Decke gemeint ist.

5 + 7. - Dies ist weder wahr noch falsch, also keine Aussage.

Grn. - Das ist nicht mal ein Satz, also insbesondere keine Aussage.

a2 + b2 = c2. - Dies ist ohne Kontext keine Aussage.

Wo ist mein Auto? - Das ist eine Frage, die kann weder wahr nochfalsch sein, also ist das keine Aussage.

8


Dieser Satz ist falsch. - Das ist ebenfalls keine Aussage, denn dieserSatz kann widerspruchsfrei weder wahr noch falsch sein.

Hingegen ist der Satz des Pythagoras eine Aussage (eine wahre, wie wir inder Schule gelernt haben):

Satz (Pythagoras). Sind a, b die Kathetenlngen und c die Hypotenusenlngein einem rechtwinkligen Dreieck, so gilt fr diese Zahlen a2 + b2 = c2.

Unter den Aussagen sind solche hervorzuheben, die fr alle Objekte xoder fr mindestens ein Objekt x gelten. Diese kommen hufig vor unddeswegen betrachten wir einige solche Aussagen etwas genauer.

Fr alle reellen Zahlen x gilt: x2 0. (wahr)

Fr alle reellen Zahlen x gilt x2 > 0. (falsch)

Es gibt reelle Zahlen x, fr die gilt: x2 > 0.(wahr)

Es gibt reelle Zahlen x, fr die gilt: x2 < 0. (falsch)

Solche Aussagen werden uns in Zukunft noch hufig begegnen.

1.2 Verneinung von Aussagen

Man kann Aussagen auf verschiedene Arten und Weisen verknpfen. Dieerste Operation, die wir kennenlernen, ist die Verneinung. Diese entsprichtungefhr unserem intuitiven Verstndnis: Die Verneinung ist das Gegenteilder vorgegebenen Aussage. Die Verneinung (man sagt auch: die Negation)einer Aussage ist genau dann wahr, wenn die ursprngliche Aussage falschist, und umgekehrt.

Notation. Fr eine Aussage A schreiben wir A fr die Verneinung von A.

Wir verdeutlichen das Prinzip der Verneinung an einigen Beispielen:

Aussage A: Die Zahl 7 ist gerade.Verneinung von A: Die Zahl 7 ist ungerade.

Aussage B: Alle Schafe sind schwarz.Verneinung von B: Nich alle Schafe sind schwarz.quivalente Formulierung: Es gibt Schafe, die nicht schwarz sind.Warnung: Alle Schafe sind wei ist keine gleichwertige Formulierungfr die Verneinung. Es stimmt nmlich sowohl, dass nicht alle Schafewei sind, als auch, dass nicht alle Schafe schwarz sind!

9


Wie wir am letzten Beispiel gesehen haben, ist es etwas subtiler, Aussagenzu verneinen, die fr alle Objekte x oder fr mindestens ein Objekt xgelten. Zunchst schauen wir uns zwei Beispiele fr Verneinung von fr alle-Aussagen.

Aussage: Fr alle reellen Zahlen x gilt: x2 0.Verneinung: Es gibt reelle Zahlen x, fr die x2 < 0 gilt.

Aussage: Fr alle ganzen Zahlen k gilt: k2 + 7 ist ungerade.Verneinung: Es gibt eine ganze Zahl k, fr die k2 + 7 gerade ist.

Generell haben wir die folgende Merkregel: Will man eine Aussage derForm Fr alle Objekte x mit Eigenschaft P gilt A(x). verneinen, so kannman das als Es gibt Objekte x mit Eigenschaft P , fr die A(x) gilt.formulieren.

Nun zu den es gibt-Aussagen (diese werden auch Existenz-Aussagengenannt):

Aussage: Es gibt eine reelle Zahl y mit y > 7.Verneinung: Fr alle reellen Zahlen y gilt: y 7.Auch mglich: Es gibt keine reelle Zahl y mit y > 7.

Aussage: Es gibt eine natrliche Zahl k, fr die k2 + 2 eine Primzahlist.Verneinung: Fr alle natrlichen Zahlen k gilt: k2+2 ist keine Primzahl.

In diesem Fall ist die Merkregel wie folgt. Will man eine Aussage der FormEs gibt Objekte x mit Eigenschaft P , fr die A(x) gilt. verneinen, so kannman das als Fr alle Objekte x mit Eigenschaft P gilt A(x). formulieren.

1.3 Und- und Oder-Verknpfungen

Verneinung ist eine Operation, bei der man aus einer Aussage eine neueAussage machen kann. Jetzt beschftigen wir uns mit zwei Arten, jeweilszwei Aussagen zu einer zu verbinden. Die erste ist die Und-Verknpfung.Damit eine Aussage der Form A und B wahr ist, muss sowohl die AussageA als auch die Aussage B wahr sein. Hier sind einige Beispiele:

Alle Schafe sind schwarz und 7 ist ungerade. (falsch, da die erste Teil-aussage falsch und die zweite wahr ist).

Die Zahl 7 ist prim und ungerade. (wahr, da beide Teilaussagen wahrsind).

Im 22-Chomp hat der erste Spieler eine Gewinnstrategie und fr allereellen Zahlen x gilt: x2 < 0. (falsch, da die erste Teilaussage wahr unddie zweite falsch ist).

10


Die Zahl 12ist natrlich und grer 1. (falsch, da beide Teilaussagen

falsch sind).

Notation. Wir bezeichnen die Und-Verknpfung mit dem Symbol .

Um den Wahrheitswert der Verknpfung zweier Variablen in Abhngig-keit von den Werten von Variablen festzuhalten, verwendet man Wahrheits-tabellen. Die Wahrheitstabelle der Und-Verknpfung sieht wie folgt aus:

A B A Bw w ww f ff w ff f f

Dabei stehen w und f abkrzend fr wahr bzw. falsch.Die zweite Verknpfung, die wir kennenlernen, ist die Oder-Verknpfung.

Das mathematische Oder ist etwas anders festgelegt, als wir es im Alltags-gebrauch handhaben. A oder B ist wahr, wenn A wahr ist, oder B wahrist, oder beides. Mit anderen Worten: Die A oder B-Aussage ist nur falsch,wenn sowohl A als auch B falsch sind.

Notation. Wir bezeichnen die Oder-Verknpfung mit dem Symbol .

In diesem Fall sieht die Wahrheitstabelle wie folgt aus:

A B A Bw w ww f wf w wf f f

In der Programmierung kommt der Typ boolean vor, der sehr hnlich zuAussagen behandelt werden kann. In Java steht ! fr die Verneinung, &&fr Und und || fr Oder (dabei gibt es einige Feinheiten zu beachten; essoll an dieser Stelle nur als Analogie betrachtet werden).

Auch beim Verknpfen von All-Aussagen oder Existenz-Aussagen mitUnd und Oder ist Vorsicht geboten. So sind beispielsweise die AussagenAlle natrlichen Zahlen sind gerade und Alle natrlichen Zahlen sind unge-rade beide falsch, also ist deren Oder-Verknpfung Alle natrlichen Zahlensind gerade oder alle natrlichen Zahlen sind ungerade falsch. Allerdings istdie Aussage Alle natrlichen Zahlen sind gerade oder ungerade wiederumwahr. Die Aussagenteile Fr alle oder Es gibt knnen nicht mit der Oder-und Und-Verknpfung vertauscht werden.

11


1.4 Rechnen mit logischen Termen

Versucht man eine Aussage, die sich als Und-Verknpfung zweier Aussagenzusammensetzt, zu verneinen, so merkt man, dass dabei etwas unintuitivespassiert. Tatschlich ist die Aussage Es gibt Schafe, die nicht schwarz sind,und 7 ist eine Primzahl nicht das Gegenteil der Aussage Alle Schafe sindschwarz und 7 ist keine Primzahl, wie man schon daran sieht, dass beideAussagen falsch sind. Um eine allgemeine Regel anzugeben, wie man Und-Aussagen verneint, fhren wir die logischen Terme und logische quivalenzvon solchen ein.

Definition 1.2 (vorlufig). Ein Ausdruck in Variablen A,B,C, . . ., die durch,, verknpft sind, heit (logischer) Term.

Beispiel. A B, ((A B)) C, A sind Terme.

Definition 1.3. Zwei Terme heien logisch quivalent, wenn sie fr alleWerte der darin vorkommenden Variablen denselben Wahrheitswert haben.

Wir machen ein einfaches Beispiel, um zu sehen, wie logische quivalenznachgewiesen werden kann.

Proposition 1.4. A und (A) sind logisch quivalente Terme.

Beweis. Wir prfen, dass die Terme A und (A) fr jedenWert der VariableA denselben Wahrheitswert haben.

A A A (A)w w f wf f w f

Die 2. und 4. Spalte, die zu A bzw. (A) gehren, stimmen berein, alsosind A und (A) logisch quivalent.

Nun stellen wir allgemeine Regeln zum Verneinen von Und- und Oder-Ausdrcken auf. Auerdem fhren wir noch weitere Rechenregeln fr Und-und Oder-Verknpfungen auf. Dabei erinnern einige Regeln an die Rechen-regeln, die wir aus der Schule fr Addition und Multiplikation der reellenZahlen kennen; diese Regeln tragen dann die entsprechenden Namen.

Satz 1.5 (De Morganschen Regeln). 1. Verneinung von Und: (AB)(A) (B).

2. Verneinung von Oder: (A B) (A) (B).

3. Und-Oder-Distributivgesetz: (A B) C (A C) (B C).

4. Oder-Und-Distributivgesetz: (A B) C (A C) (B C).

5. Assoziativitt von Und: (A B) C A (B C).

12


6. Assoziativitt von Oder: (A B) C A (B C).

7. Kommutativitt von Und: A B B A.

8. Kommutativitt von Oder: A B B A.

Beweis. Der Beweis ist in allen Fllen mit Hilfe von Wahrheitstabellen zuerbringen. Man hat in jedem Teilpunkt zu zeigen, dass die Wahrheitswerteder beiden Ausdrcke fr alle Werte von A,B und ggf. C dieselben sind.In den letzten vier Punkten wird dies als einfache bung dem/der LeserInberlassen. Fr die ersten vier Flle stellen wir die Wahrheitstabellen auf.Die Werte der zu untersuchender Ausdrcke werden jeweils hervorgehoben.

1. Fr die logischen Terme (A B) und (A) (B) erhalten wir:

A B A B (A B) A B (A) (B)w w w f f f fw f f w f w wf w f w w f wf f f w w w w

Somit sind die beiden Terme logisch quivalent.

2. Fr die logischen Terme (A B) und (A) (B) erhalten wir:

A B A B (A B) A B (A) (B)w w w f f f fw f w f f w ff w w f w f ff f f w w w w

Somit sind die beiden Terme logisch quivalent.

3. Fr die logischen Terme (A B) C und (A C) (B C) sieht dieWahrheitstabelle wie folgt aus:

A B C A B (A B) C A C B C (A C) (B C)w w w w w w w ww w f w w w w ww f w f w w w ww f f f f w f ff w w f w w w wf w f f f f w ff f w f w w w wf f f f f f f f

13


Da die Spalten, die zu (A B) C bzw. (A C) (B C) gehren,bereinstimmen, sind die beiden Terme logisch quivalent.

4. Fr die logischen Terme (A B) C und (A C) (B C) sieht dieWahrheitstabelle wie folgt aus:

A B C A B (A B) C A C B C (A C) (B C)w w w w w w w ww w f w f f f fw f w w w w f ww f f w f f f ff w w w w f w wf w f w f f f ff f w f f f f ff f f f f f f f

Da die Spalten, die zu (A B) C bzw. (A C) (B C) gehren,bereinstimmen, sind die beiden Terme logisch quivalent.

Die Rechenregeln knnen benutzt werden, um wiederum neue logischequivalenzen zu beweisen.

Beispiel. Wir vereinfachen den Term ((XY )Z) mit Variablen X, Y, Zmit Hilfe der Rechenregeln. Durch die De Morgan-Regel fr die Negation vonUnd erhalten wir:

((X Y ) Z) ((X Y )) ((Z)).

Wir lsen die erste Klammer auf, indem wir De Morgan-Regel fr die Nega-tion von Oder anwenden:

((X Y )) ((Z)) (X Y ) ((Z)).

Schlielich lsen wir die doppelte Negation auf:

(X Y ) ((Z)) (X Y ) Z.

Hier knnte man noch das Distributivgesetz anwenden; allerdings wird derTerm dadurch nicht krzer.

14


1.5 Implikation

Eine weitere Art, zwei Aussagen zu einer zu verknpfen, ist die wenn-dann-Verknpfung. Hier sind einige Beispiele:

Wenn es regnet, ist der Boden nass. (wahr)

Wenn p eine Primzahl ist, so ist p+ 1 auch eine Primzahl. (falsch)

Wenn k eine gerade Zahl ist, dann ist 7 ungerade. (wahr)

Wenn 7 ungerade ist, dann ist 2 + 3 = 7. (falsch)

Wenn eine ganze Zahl k gerade ist, dann ist k2 auch gerade. (wahr)

Wenn x eine positive reelle Zahl ist, dann ist x2 > 0. (wahr)

Dabei ist der Wahrheitswert der Verknpfung Aus A folgt B durch diefolgende Wahrheitstabelle vorgegeben:

A B A Bw w ww f ff w wf f w

Insbesondere folgt aus einer falschen Aussage alles; hingegen kann aus einerwahren Aussage nur eine wahre Aussage folgen.

Um ein besseres Verstndnis der Implikation zu erlangen, zeigen, wir, dassdie folgende Umformulierung dafr gilt.

Proposition 1.6. Die Terme A B und (A)B sind logisch quivalent.

Beweis. Wir prfen anhand der Wahrheitstabelle, dass die Terme A Bund (A) B fr jeden Wert der Variablen A,B denselben Wahrheitswerthaben.

A B A (A) B A Bw w f w ww f f f ff w w w wf f w w w

Da die letzten beiden Spalten, die zu den Termen A B bzw. (A) Bgehren, bereinstimmen, sind diese Terme logisch quivalent.

Beispiel. Die Aussage Wenn es regnet, ist der Boden nass ist quivalentzu Es regnet nicht, oder der Boden ist nass (oder vielleicht beides).

15


Ein weiterer quivalenter Ausdruck fr die Implikation A B ist B A, wie in der folgenden Proposition gezeigt wird. Dies mag im ersten Mo-ment kontraintuitiv erscheinen.

Proposition 1.7. Die Terme A B und B A sind logisch quivalent.

Beweis. Wir zeigen die Behauptung, indem wir die bisher bewiesenen Resul-tate verwenden, insbesondere die logischen Rechenregeln und die Proposition1.6. Dabei fangen wir mit dem zweiten Ausdruck an.

B A (B) A Proposition 1.6 B A Doppelte Neg. A B Kommutativitt A B Proposition 1.6

Damit haben wir also gezeigt, dass die logischen Terme A B undB A logisch quivalent sind.

Will man also eine Aussage vom Typ A B beweisen, so ist es quiva-lent, stattdessen die Aussage B A zu beweisen. Diese Beweistechniknennt man auch Kontraposition.

Beispiel. Die Aussage Wenn es regnet, ist der Boden nass ist quivalentzu Wenn der Boden nicht nass ist, regnet es nicht..

Als nchstes beschftigen wir uns damit, wie man eine Wenn-dann-Aussage verneint. Hat man beispielsweise die Behauptung Fr alle natrli-chen Zahlen k gilt: Ist k durch 7 teilbar, so ist 2k+3 eine Primzahl und willdiese widerlegen, so muss man sich klar machen, was das Gegenteil dieserAussage ist. Dafr haben wir - zunchst fr logische Terme - die folgendeProposition.

Proposition 1.8. Die logischen Terme (A B) und AB sind logischquivalent.

Beweis. Wir zeigen die Behauptung erneut durch Anwendung der Rechen-regeln und der Proposition 1.6. Dabei fangen wir mit dem ersten Ausdruckan.

(A B) (A B) Proposition 1.6 (A) B Neg. von Oder A B Doppelte Neg.

Daraus folgt, dass die logischen Terme (A B) und A B logisch qui-valent sind.

Um das zu verdeutlichen, betrachten wir erneut einige Beispiele.

16


Beispiel. Die Verneinung von Wenn es regnet, ist der Boden nass istEs regnet und der Boden nicht nass.

Die Verneinung der Aussage Fr alle natrlichen Zahlen k gilt: Ist kdurch 7 teilbar, so ist 2k+ 3 eine Primzahl lautet Es gibt eine natr-liche Zahl k, die durch 7 teilbar ist und sodass 2k + 3 keine Primzahlist. Diese zweite Aussage ist wahr, denn k = 21 erfllt die genanntenBedingungen.

Wir betrachten die Aussage Fr alle reellen Zahlen x gibt es eine reelleZahl y, sodass gilt: Wenn (x y)2 7, so ist x 2. Die Verneinungdieser Aussage lautet: Es gibt eine reelle Zahl x, sodass fr alle reellenZahlen y gilt: (x y)2 7 und x < 2. In diesem Fall ist die ursprng-liche Aussage wahr: Fr jede reelle Zahl x knnen wir y = x whlen;dann ist die Prmisse in der Aussage Wenn (xy)2 7, so ist x 2.falsch, und somit die Aussage wahr.

1.6 quivalenz

Wir lernen eine letzte Verknpfung von Aussagen kennen: Die quivalenz vonAussagen. Sind A und B Aussagen, so lautet die zusammengesetzte AussageA ist quivalent zu B oder A ist genau dann wahr, wenn B wahr ist, inZeichen A B. Diese Verknpfung ist durch die folgende Wahrheitstabelledefiniert:

A B A Bw w ww f ff w ff f w

Wir suchen wiederum einige Umformulierungen der quivalenz, um diesebesser zu verstehen:

Proposition 1.9. Die folgenden logischen Terme sind logisch quivalent:

A B,

(A B) (B A),

(A B) (A B),

(A B) (A B).

Beweis. Um die logische quivalenz der ersten drei logischen Terme zu be-weisen, stellen wir die Wahrheitstabelle fr diese auf. Abkrzend schreibenwir C = (A B) (B A) und D = (A B) (A B).

17


A B A B A B B A C A B A B Dw w w w w w w f ww f f f w f f f ff w f w f f f f ff f w w w w f w w

Da die Spalten der Wahrheitstabelle, die zu den Ausdrcken A B, C =(A B) (B A) und D = (A B) (A B) gehren, dieselbenWahrheitswerte aufweisen, sind diese drei logischen Terme logisch quivalent.

Die logische quivalenz vom vierten und zweiten Term ist eine Folgerungder Proposition 1.7. Somit ist die logische quivalenz aller vier logischenTerme bewiesen.

Die obige Proposition ist hufig ntzlich, um eine quivalenz zweier Aus-sagen zu beweisen.

Beispiel. Sei k eine natrliche Zahl. Wir betrachten die folgende Aussage:Die Zahl k ist genau dann gerade, wenn ihr Quadrat k2 gerade ist. Nach dervorherigen Proposition sind die folgenden vier Aussagen quivalent:

Die Zahl k ist genau dann gerade, wenn ihr Quadrat k2 gerade ist.

Ist k gerade, so auch k2, und ist k2 gerade, dann auch k.

Ist k gerade, so ist k2 gerade, und ist k ungerade, so ist k2 ungerade.

k und k2 sind beide gerade, oder k und k2 sind beide ungerade.

1.7 Disjunktive und konjunktive Normalformen

Als letztes in diesem Kapitel wollen wir ber zwei standardisierte Formenvon Termen sprechen, die disjunktive Normalform und die konjunktive Nor-malform. Deren Konstruktion beruht auf der folgenden Beobachtung. Hatman die Variablen X1, . . . , Xn vorgegeben und whlt sich von jeder VariableXi entweder die Variable selbst oder deren Negation als Term Yi, so ist derTerm Y1 . . . Yn fr genau eine Belegung der Variablen X1, . . . , Xn wahrund fr alle anderen falsch. Verknpft man nun mehrere Terme, die dieseEigenschaft haben, mit der Oder-Verknpfung, so erhlt man einen neuenTerm, der genau dort die Wahr-Eintrge in der Wahrheitstabelle hat, wo ei-nes der Und-Terme den Wert Wahr hat. Umgekehrt sieht es aus, wenn mansich nur den Falsch-Werten in der Wahrheitstabelle widmet.

Als grobe Idee lsst sich festhalten: Die konjunktive Normalform ist einbesonders einfacher Ausdruck, der als Und-Verknpfung von Oder-Termenbesteht; bei disjunktiver Normalform ist es die Oder-Verknpfung von Und-Termen. Jetzt knnen wir diesen Begriff przisieren.

18


Definition 1.10. Wir sagen, ein Term Z in den Variablen X1, X2, . . . , Xnist in konjunktiver Normalform, falls er sich schreiben lsst als

Z = Z1 Z2 . . . Zk

fr ein k 1, wobei sich jeder der Terme Zi fr 1 i k wiederum schreibenlassen soll als

Zi = Y1 Y2 . . . Yn,

und jedes Yj entweder die Variable Xj oder deren Negation Xj ist. (Dabeisind natrlich die Yj fr jedes Zi unterschiedlich. Wir befolgen dabei dieKonvention, dass alle Variablen in jedem Zj vorkommen sollen.)

Sehr hnlich ist die Definition der disjunktive Normalform:

Definition 1.11. Wir sagen, ein Term Z in den Variablen X1, X2, . . . , Xnist in disjunktiver Normalform, falls er sich schreiben lsst als

Z = Z1 Z2 . . . Zk

fr ein k 1, wobei sich jeder der Terme Zi fr 1 i k wiederum schreibenlassen soll als

Zi = Y1 Y2 . . . Yn,

und jedes Yj entweder die Variable Xj oder deren Negation Xj ist.

Wir betrachten einige Beispiele.

Beispiel. Der Term Z = (ABC)(ABC)(ABC)ist in disjunktiver Normalform. Denn dieser lsst sich schreiben alsZ = Z1 Z2 Z3, wobei Z1 = A B C, Z2 = A B C,Z3 = A B C. Insbesondere ist jeder der Terme Z1, Z2, Z3 eineUnd-Verknpfung, in der jede der Variablen A,B,C (ob verneint odernicht) einmal vorkommt.

Der Term X = (AB) ist weder in konjunktiver noch in disjunktiverNormalform. Es ist zwar eine Und- bzw. eine Oder-Verknpfung voneinem einzelnen Term mit sich selbst, aber dieser ist weder eine Und-noch eine Oder-Verknpfung von Variablen und ihren Negationen.

Der Term Y = (A B C) (A B C) ist in konjunktiverNormalform. Denn dieser lsst sich schreiben als Y = Y1 Y2, wobeiY1 = AB C und Y2 = AB C. Insbesondere ist sowohl Y1 alsauch Y2 eine Oder-Verknpfung, in der jede der Variablen A,B,C (obverneint oder nicht) einmal vorkommt.

19


Der Term T = A B ist in disjunktiver Normalform (in VariablenA,B): Dieser ist die Oder-Verknpfung T = T1 von einem einzigen Und-Term, in dem jede Variable einmal vorkommt. Nach unserer Definitionist dieser Term allerdings nicht in konjunktiver Normalform, da in denTeiltermen A bzw. B nicht jeweils alle Variablen vorkommen. Es gibtauch Konventionen, nach denen das die konjunktive Normalform istund unsere Normalform dann vollstndige konjunktive Normalformheit.

Dass die Normalformen wirklich zum Standardisieren geeignet sind, siehtman an dem folgenden Satz. Wir werden diesen nicht beweisen, da der Beweiszwar nicht schwierig, doch langwierig ist, allerdings schauen wir uns Beispielean, durch die die Grundidee des Beweises deutlich wird.

Satz 1.12. Jeder logische Term in den Variablen X1, . . . , Xn ist zu einemlogischen Term in konjunktiver Normalform in den Variablen X1, . . . , Xn lo-gisch quivalent, und letzterer ist bis auf die Reihenfolge der Teilterme, diedurch Und verknpft werden, eindeutig.

Jeder logische Term in den Variablen X1, . . . , Xn ist zu einem logischenTerm in disjunktiver Normalform in den Variablen X1, . . . , Xn logisch qui-valent, und letzterer ist bis auf die Reihenfolge der Teilterme, die durch Oderverknpft werden, eindeutig.

Beispiel. Manchmal lsst sich die konjunktive bzw. disjunktive Normalformerraten, oder man kann diese leicht durch logische Umformungen herleiten.Beispielsweise wissen wir fr den Term A B in den Variablen A,B nachProposition 1.9:

(A B) (A B) (A B),

und die rechte Seite ist in der disjunktiver Normalform. Fr die konjunktiveNormalform starten wir mit einer weiteren Beschreibung aus der Proposition1.9 und wenden dann die Proposition 1.6 an:

(A B) (A B) (B A) (A B) (A B),

und letzter Term ist in konjunktiver Normalform.

Beispiel. Wir wollen fr den Term T = ((A B C) (A C)) jeweilseinen logisch quivalenten Term in disjunktiver bzw. konjunktiver Normal-form. Bevor wir das tun, ist die folgende Beobachtung hilfreich: Ein TermY1 Y2 . . . Yn in den Variablen X1, . . . , Xn, in dem jedes Yj entwederdie Variable Xj oder ihre Negation Xj ist, ist fr genau eine Belegung vonVariablen X1, . . . Xn wahr und fr alle andere Belegungen falsch. Umgekehrtgibt es zu jeder Belegung der Variablen X1, . . . Xn einen Und-Term der obi-gen Form, der fr diese Belegung wahr ist und fr alle anderen Belegungen

20


falsch. Hat man eine nun eine disjunktive Normalform Z = Z1 . . . Zkvorgegeben, so ist jeder der Terme Zi fr genau eine Belegung der Variablenwahr; nimmt man die Wahr-Belegungen fr alle der k-Terme Z1, . . . , Zk zu-sammen, so erhlt man genau die Belegungen, an denen der Term Z wahrist. Umgekehrt liefert uns das eine Methode, wie wir zu einem vorgegebe-nen Term die disjunktive Normalform bilden knnen: Fr jede Belegung derVariablen, bei der der vorgegebene Term wahr ist, erhalten wir einen Und-Term, und durch die Oder-Verknpfung dieser Und-Terme erhalten wir einenzu dem vorgegebenen logisch quivalenten Term in der disjunktiven Normal-form. Bei konjunktiver Normalform muss man umgekehrt verfahren und frjede Falsch-Belegung den passenden Oder-Term finden, die man dann mitdem Und verknpft. Das demonstrieren wir in diesem Beispiel.

Dafr stellen wir zunchst die Wahrheitstabelle von T = ((ABC)(A C)) auf. Abkrzend schreiben wir S = (AB C) (A C). In denletzten beiden Spalten geben wir einen Und-Term an, der genau an dieserStelle wahr ist, oder einen Oder-Term an, der genau an dieser Stelle falschist - abhngig davon, ob T an dieser Stelle wahr oder falsch ist.

A B C A B C A C S T Und-Term Oder-Termw w w w w w f A B Cw w f w f f w A B Cw f w w w w f A B Cw f f w f f w A B Cf w w w w w f A B Cf w f w w w f A B Cf f w w w w f A B Cf f f f w f w A B C

Somit erhalten wir den Term (ABC)(ABC)(ABC)in disjunktiver Normalform, der logisch quivalent zum vorgegebenen TermT ist. Auerdem haben wir den Term

(A B C) (A B C) (A B C) (A B C) (A B C)

in konjunktiver Normalform, der zum vorgegebenen Term T logisch quiva-lent ist.

21

Viktoriya Ozornova 2 ELEMENTARE MENGENLEHRE

2 Elementare Mengenlehre

2.1 Grundlegende Definitionen

Mengen gehren zu den grundlegenden Objekten, die wir in der Mathema-tik betrachten. Einige davon haben wir bereits in der Schule kennengelernt,wie etwa die Menge der natrlichen Zahlen oder Lsungsmengen von Glei-chungen. Die folgende Definition, die auf G. Cantor zurckgeht, legen wirunserem Begriff von Menge zugrunde. Natrlicherweise besteht dabei dasProblem, dass wir auf andere Begriffe zurckgreifen mssen, die wir nochnicht definiert haben. Dieses Problem ist eines von grundstzlicher Naturund soll uns zunchst nicht weiter stren.

Definition 2.1. Eine Menge ist eine Zusammenfassung von bestimmtenund wohlunterschiedenen Objekten unseres Denkens oder unserer Anschau-ung zu einem Ganzen. Diese Objekte werden die Elemente der Menge ge-nannt.

Beispiel. Es gibt einige Wege, eine Menge zu spezifizieren. Die einfachsteist, alle Elemente der Menge einfach aufzulisten; als Notation verwendenwir geschweifte Klammern, um das Zusammenfassen von Objekten hervor-zuheben, z.B. {0, 1} fr die Menge, die die Objekte 0 und 1 zusammenfasst.Die Objekte der Menge mssen in keiner Verbindung miteinander stehen:Beispielsweise knnen wir die Menge {0, 1, 7

8, x, y,Erde} betrachten, wobei x

und y als Symbole zu verstehen sind.Weiterhin haben wir fr gewisse Mengen, die uns in der Mathematik

besonders hufig begegnen, feste Notation reserviert: N fr die Menge dernatrlichen Zahlen (je nach Kontext mit oder ohne 0; wenn wir betonenwollen, dass die 0 dazugehrt, schreiben wir N0), Z fr die Menge der ganzenZahlen, Q fr die Menge der rationalen Zahlen und R fr die Menge derreellen Zahlen.

Eine weitere Menge, die besonderer Erwhnung bedarf, ist die leereMenge . Diese ist als die Menge definiert, die keine Objekte zusammen-fasst.

Fr die Aussage Objekt x ist ein Element der Menge M haben wir dieKurzschreibweise x M , fr x ist kein Element der Menge M schreibenwir x / M . Beispielsweise ist

2 R, aber

2 / Q. Fr alle Objekte x ist

die Aussage x / wahr und x falsch, denn kein Objekt gehrt zuden Objekten, die von der leeren Menge zusammengefasst werden.

Eine vorerst letzte Mglichkeit, eine Menge zu beschreiben, besteht darin,Eigenschaften von Objekten zu fordern. Dies geschieht immer in der unge-fhren Form {Objekte x |x hat Eigenschaft P}.

Beispielsweise ist {x R |x > 3} die Menge aller reellen Zahlen, diegrer als 3 sind; die Menge {q N | 7 teilt q} ist die Menge der natrlichenZahlen, die durch 7 teilbar sind.

22


Um Mengen zu vergleichen, bentigen wir als erstes die folgende Defini-tion:

Definition 2.2. Zwei Mengen sind gleich, wenn sie dieselben Elemente ent-halten.

Insbesondere wird die Reihenfolge, in der Elemente aufgelistet werden,nicht bercksichtigt, und die Mehrfachnennungen werden zusammengefasst.So ist beispielsweise {0, 1} = {1, 0} und {z, z} = {z}. Das steht im Gegensatzzu geordneten Paaren (kurz auch: Paaren) von Objekten, bei denen es auf dieReihenfolge ankommt und auch Mehrfachnennungen (sinnvollerweise) mg-lich sind. Solche Paare begegneten uns im Schulunterricht als Koordinatenvon Punkten in der Ebene. So ist der Punkt (0, 1) ein anderer als der Punkt(1, 0), und der Punkt (3, 3) ist ebenfalls eine sinnvolle Koordinatenangabe.

Manchmal ist Gleichheit von Mengen auch nicht gnzlich offensichtlich.Hier sind einige Beispiele:

Beispiel. {x R |x < 2 und x > 3} = , da es keine reelle Zahl gibt,die beide Ungleichungen gleichzeitig erfllt.

{y R | 7y + 14 = 0} = {2}, denn 2 ist die eindeutige Lsung derGleichung 7y + 14 = 0.

{a R | a2 0} = R, denn die Ungleichung a2 0 gilt fr jede reelleZahl a.

Eine weitere Art, Mengen zueinander in Verbindung zu setzen, ist durchden Begriff der Teilmenge gegeben.

Definition 2.3. Eine Menge A heit Teilmenge einer Menge B, falls jedesElement von A auch ein Element von B ist. Wir schreiben dafr A B oderA B. In Zeichen sieht die Definition nochmal wie folgt aus:

(A B) : (x A x B).

Eine Menge A heit echte Teilmenge einer Menge B (in Zeichen: A ( B),wenn A eine Teilmenge von B ist und zustzlich A 6= B gilt.

Beispiel. {2, 7} ist eine Teilmenge der Menge {2, 7}, aber keine echteTeilmenge.

{1, 3, 5} ist eine echte Teilmenge der Menge {1, 2, 3, 4, 5}.

N ist eine echte Teilmenge der Menge Z. Jede natrliche Zahl ist ins-besondere eine ganze Zahl, also gilt N Z. Da es auch ganze Zahlengibt, die keine natrlichen Zahlen sind, z.B. 7 Z, aber 7 / N, giltauerdem N 6= Z.

23


Genauso gilt Z ( Q ( R. Fr letzteres wissen wir, dass es reelle Zahlengibt, wie z.B.

2 oder , die keine rationalen Zahlen sind.

Fr jede Menge A gilt: A A und A. Um letzteres zu berprfen,merken wir, dass jedes Element der leeren Menge - also kein Objekt -auch ein Element von A ist.

Manchmal ist es sinnvoll, die Gesamtheit aller Teilmengen einer Mengezu betrachten.

Definition 2.4. Sei A eine Menge. Die Potenzmenge von A (in Zeichen:P(A)) ist die Menge aller Teilmengen von A.

Beispiel. In kleinen Beispielen kann man sich die Potenzmenge einer MengeA komplett hinschreiben. Ist A = {1, 2}, so gilt:

P({1, 2}) = {, {1}, {2}, {1, 2}}.

An dieser Stelle solle man sich nochmal bewusst werden, dass die Zahl 2 unddie Menge {2} nicht dasselbe sind. So gilt 2 A, aber 2 / P(A). Hingegenist {2} / {1, 2}, sondern {2} {1, 2}, denn jedes Element von {2} - und dasist einzig die Zahl 2 - ist auch Element der Menge {1, 2} ist. Deswegen gilt{2} P(A), aber {2} 6 P(A), denn nicht alle Elemente von {2} - in diesemFall geht es um das einzige Element 2 - sind Elemente von P(A). Hingegengilt {{2}} P(A), denn das einzige Element der Menge {{2}} - nmlich dieMenge {2} - ist auch ein Element von P(A).

Die Potenzmengen von greren werden schnell grer; darauf werdenwir spter nochmal genauer eingehen. Als Beispiel sei die Potenzmenge von{1, 2, 3},

P({1, 2, 3}) = {, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

angefhrt, die bereits 8 Elemente hat. Manche Potenzmengen kann man zu-nchst nicht weiter beschreiben. So ist P(N) = {A |A N} schon eineBeschreibung, mit der man sich zufriedengeben muss. Trotzdem kann mannatrlich mit diesem Objekt arbeiten; beispielsweise knnen wir sagen, dass P(N), {1, 2, 3} P(N),N P(N); auch knnen wir sehen, dass

{{1}, {2}, {7, 9, 10}} P(N).

Ein sehr intuitiver Begriff ist die Anzahl der Elemente einer Menge A.Wir notieren diese mit |A| oder #A.

Beispiel. |{1, 2, 4}| = 3,

|P({1, 2})| = 4, wie wir im vorherigen Beispiel gesehen haben,

|| = 0,

24


Die Anzahl der Elemente von N kann durch keine natrliche Zahlangegeben werden - diese Anzahl ist unendlich. Wir schreiben dafr|N| = . Im Prinzip gibt es auch Methoden, um mit zu hantierenund auch, um verschiedene Unendlichkeiten zu unterscheiden, doch unssoll vorerst der einfachste Begriff des Unendlichen gengen.

2.2 Mengenoperationen

In diesem Abschnitt lernen wir einige Methoden kennen, um aus vorgegebe-nen Mengen neue Mengen zu konstruieren.

Definition 2.5. Seien A, B Mengen. Die Vereinigung von Mengen A undB (in Zeichen: AB) ist die Menge, die genau alle Elemente von A und alleElemente von B enthlt. In Zeichen:

(x A B) : ((x A) (x B)).

Beispiel. {1, 2, 3}{3, 4, 5} = {1, 2, 3, 4, 5}, insbesondere werden Mehr-fachnennungen zusammengefasst.

Die Objekte der jeweiligen Mengen mssen nichts miteinander zu tunhaben: Sind x, y Symbole, so knnen wir auch {x, y}{1, 2} = {x, y, 1, 2}bilden.

Manchmal lsst sich die Vereinigung zweier Mengen nicht in verein-fachter Form hinschreiben: N {

2,

3} ist die einfachste Art, dieseMenge hinzuschreiben.

Ist B eine Teilmenge von einer Menge A, so gilt BA = A. Denn jedesElement von B ist bereits in A enthalten, d.h. jedes Element von Aoder von B ist insbesondere ein Element von A. Andersrum ist jedesElement von A ein Element von A oder ein Element von B.

Insbesondere gilt fr jede Menge A: A A = A und A = A.

Definition 2.6. Seien A, B Mengen. Der Durchschnitt der Mengen A undB (in Zeichen: A B) ist die Menge, die genau alle Elemente enthlt, diesowohl in A als auch in B enthalten sind. In Zeichen:

(x A B) : ((x A) (x B)).

Beispiel. {1, 2, 3} {3, 4, 5} = {3}, denn 3 ist das einzige Element,das in beiden Mengen vorkommt.

Sind x, y Symbole, so gilt {x, y} {1, 2} = .

Fr jede Menge A gilt: A A = A.

25


Wir bezeichnen das abgeschlossene Intervall mit eckigen Klammernund das offene Intervall mit runden Klammern, z.B.

[3, 5] = {x R | 3 x 5}(3, 5) = {x R | 3 < x < 5}

Hier haben wir (3, 5) N = {4} und [3, 5] N = {3, 4, 5}.

Definition 2.7. Seien A, B Mengen. Die Mengendifferenz der Mengen Aund B (in Zeichen: A \ B) ist die Menge, die genau alle Elemente enthlt,die in A, aber nicht in B enthalten sind. In Zeichen:

(x A \B) : ((x A) (x / B)).

Ist B eine Teilmenge von einer Menge A, so wird A \ B auch das Kom-plement von B in A genannt.

Beispiel. Im Allgemeinen muss keine der beiden Mengen Teilmengeder anderen sein, um Mengendifferenz zu bilden. So ist beispielsweise{1, 2, 3} \ {3, 4, 5} = {1, 2}.

Manchmal kann man eine Mengendifferenz nicht weiter beschreiben,etwa R \ {1, 2}. Solche Mengen trifft man hufig schon in der Schuleals Definitionsbereiche von Funktionen.

[2, 4] \ (2, 4) = {2, 4}.

Definition 2.8. Zwei Mengen A,B heien disjunkt, falls A B = . EineAnsammlung A1, . . . , An von Mengen heit paarweise disjunkt, falls jezwei von diesen Mengen disjunkt sind; mit anderen Worten, die MengenAi, Aj sind fr 1 i, j n, i 6= j, disjunkt.

Um die verschiedenen Mengenoperationen besser zu verstehen, beweisenwir exemplarisch die folgende Proposition.

Proposition 2.9. Seien A,B beliebige Mengen. Dann gilt:

1. A = (A \B) (A B),

2. (A \B) (A B) = .

Beweis. 1. Zwei Mengen sind nach Definition gleich, wenn sie dieselbenElemente haben. Wir zeigen nun, dass ein Objekt x genau dann in Aliegt, wenn es in (A \B) (A B) liegt. Wir fangen mit der letzterenAussage an. Nach Definition von Vereinigung gilt:

x (A \B) (A B) ((x A \B) (x A B)).

26


Wir nutzen nun die Definitionen von Mengendifferenz und vom Durch-schnitt:

((x A \B) (x A B)) (x A x / B) (x A x B).

Auf diese Aussagen kann man nun das Distributivgesetz anwenden:

(x A x / B) (x A x B) (x A) (x / B x B).

Da die Aussage x / B x B stets wahr ist, folgt

(x A) (x / B x B) (x A).

Nimmt man die Kette der quivalenzen zusammen, so haben wir ge-zeigt, dass x (A \ B) (A B) genau dann wahr ist, wenn x Agilt. Damit haben wir die Gleichheit der Mengen bewiesen.

2. Wir gehen wie im ersten Teil vor: Wir zeigen, dass die Aussage x (A \ B) (A B) immer falsch ist und die Menge somit dieselbenElemente wie die leere Menge hat, nmlich gar keine. Wir benutzenzunchst die Definition vom Durchschnitt:

x (A \B) (A B) ((x A \B) (x A B)).

Im nchsten Schritt setzen wir die Definitionen von Mengendifferenzund vom Durchschnitt wieder ein:

((x A \B) (x A B)) (x A x / B) (x A x B).

Nun nutzen wir das Assoziativ- und das Kommutativgesetz fr die Und-Verknpfung und erhalten:

(x A x / B) (x A x B) (x / B x B) (x A x A).

Nun ist die Aussage x / Bx B immer falsch, und somit die gesamteAussage (x / B x B) (x A x A) immer falsch. Somit folgtdie Behauptung.

Wir fhren die vorerst letzte Mengenoperation ein.

Definition 2.10. Seien A,B Mengen. Das (kartesische) Produkt A Bder Mengen A und B ist die Menge aller (geordneter) Paare (a, b) mit a Aund b B. In Zeichen:

AB = {(a, b)|a A, b B}.

Man beachte, dass ein Paar stets geordnet ist, wir sagen nur manchmalgeordnete Paare, um das nochmal zustzlich zu unterstreichen.

27


Beispiel. Ein Beispiel ist meist aus der Schule bekannt: Die Menge vonPaaren (x, y) mit x R und y R wird meist als R2 geschrieben undwird benutzt, um Koordinaten von Punkten in der Ebene anzugeben.

{1, 2} {a, b} = {(1, a), (1, b), (2, a), (2, b)}. Man beachte, dass diesnicht dieselbe Menge ist wie

{a, b} {1, 2} = {(a, 1), (b, 1), (a, 2), (b, 2)}.

Wir wollen auch wissen, wie man die Anzahl der Elemente einer Mengeermittelt, die man aus vorgegebenen Mengen durch Verwendung von Men-genoperationen bekommen hat. Eine erste Aussage in diese Richtung ist diefolgende.

Proposition 2.11. Seien A,B endliche Mengen. Dann gilt:

1. |A B| = |A|+ |B| |A B|,

2. Sind A und B disjunkt, so ist |A B| = |A|+ |B|.

Beweis. 1. Nach Definition enthlt A B genau die Elemente, die in Aoder in B enthalten sind. Insgesamt ergibt es zunchst |A| + |B| Ele-mente, allerdings werden manche Elemente hierbei doppelt gezhlt,nmlich diejenigen, die sowohl in A als auch in B enthalten sind.Die Menge solcher Elemente ist nach Definition genau A B. Be-rcksichtigt man die Mehrfachnennungen, so erhlt man also genau|A B| = |A|+ |B| |A B|.

2. Nach Definition ist der Durchschnitt zweier disjunkten Mengen leer undhat somit 0 Elemente. Somit folgt der zweite Teil unmittelbar aus demersten.

Daraus erhalten wir als Folgerung:

Korollar 2.12. Seien A1, . . . , An paarweise disjunkte, endliche Mengen. Danngilt:

|A1 A2 . . . An| = |A1|+ . . .+ |An|.

28

Viktoriya Ozornova 3 VOLLSTNDIGE INDUKTION

3 Vollstndige InduktionWill man eine Aussage fr alle natrlichen Zahlen beweisen, so steht manzunchst vor einem Problem, denn es sind unendlich viele Zahlen und eineAussage, die fr 1, 2, 3, 4, 5 gilt, braucht nicht fr 6 zu gelten. Einen Auswegbietet das Induktionsprinzip. Bevor wir dieses genauer formulieren, beschf-tigen wir uns mit einem Beispiel.

Frage. Sei ein 10241024-groes Quadrat vorgegeben, das in 11-Kstchenunterteilt ist, wie kariertes Papier. Ist es mglich, dieses Quadrat mit L-Teilchen (s. Bild) zu pflastern, sodass keine zwei sich berlappen, kein Feldfrei bleibt und jedes Kstchen von jedem L-Teilchen auf einem Kstchenvom groen Quadrat liegt? (Wir sagen dafr in Zukunft nur noch pflastern,diese Bedingungen werden dabei stets angenommen. Das L-Teilchen darfaber gedreht werden.)

Diese erste Frage ist leicht zu beantworten: Wre das Quadrat mit L-Teilchen gepflastert, so wre es insbesondere in 3er-Gruppen unterteilt, alsomsste die Anzahl der Kstchen in dem Quadrat durch 3 teilbar sein. Aufder anderen Seite ist aber 1024 1024 = 220 nicht durch 3 teilbar, also kanndie Pflasterung nie aufgehen.

Wir modifizieren also die Frage:

Frage. Kann man ein 1024 1024-Quadrat ohne eine Ecke mit L-Teilchenpflastern?

Das Nachrechnen zeigt, dass 220 1 tatschlich durch 3 teilbar ist. Al-lerdings kann die Teilbarkeit durch 3 nicht das einzige Kriterium sein, denndas folgende Gebilde kann man auch nicht mit L-Teilchen pflastern:

Da 1024 zu gro zum Ausprobieren ist, fragen wir uns, wie es denn frkleinere Potenzen von 2 aussieht.

Frage. Kann man ein 22-Quadrat ohne eine Ecke mit L-Teilchen pflastern?

Die Antwort auf diese Frage ist ziemlich klar: Ein 2 2-Quadrat ohneeine Ecke ist genau ein L-Teilchen; die Antwort lautet also ja. Wenden wiruns dem nchsten Fall zu:

29


Frage. Kann man ein 44-Quadrat ohne eine Ecke mit L-Teilchen pflastern?

Diese Frage ist schon schwieriger, allerdings auch positiv zu beantworten.Man hat beispielsweise die folgende Pflasterung:

Es ist noch deutlich aufwendiger, den 8 8-Fall zu untersuchen. Machtman sich die Mhe, so stellt man auch dort fest, dass eine Pflasterung mglichist. Wir wollen also den allgemeinen Satz beweisen:

Satz 3.1. Man kann ein 2n 2n-Quadrat ohne eine Ecke fr jede natrlicheZahl n 1 mit L-Teilchen pflastern.

Die Hauptidee wird wie folgt sein: Hat man ein 2n+1 2n+1-Quadrat,so kann man dieses in vier 2n 2n-Quadrate zerschneiden, indem man jedeSeite halbiert. Dann werden wir unser bereits erlangtes Knnen - nmlichzupflastern von kleineren Quadraten ohne Ecke - anwenden knnen, um dasgroe Quadrat zu pflastern. Dabei muss das Vorgehen noch etwas genau-er erlutert werden. Dass eine solche Methode berhaupt funktioniert, wirddurch das sogenannte Induktionsaxiom gesichert. Es ist ein Axiom, also eineAussage, die wir als wahr annehmen, ohne diese zu beweisen. Ohne Axio-me - also grundlegende Aussagen, die nicht bewiesen werden - knnen wirkaum etwas beweisen, hnlich wie wir ohne Bedeutung von gewissen Wortenals bekannt vorauszusetzen nicht die Bedeutung von anderen Worten erkl-ren knnen. Man versucht allerdings im Allgemeinen in der Mathematik, sowenige Axiome wie mglich zu verwenden, und diese Annahmen, die nichtbewiesen werden, mglichst einfach und plausibel zu whlen. Wir benutzendie folgenden beiden Formulierungen.

Axiom (Induktionsaxiom I). Sei X N0 eine Teilmenge von natrlichenZahlen. Wir nehmen an, dass die folgenden zwei Bedingungen fr X gelten:

(I1) 0 X und

(I2) Ist eine natrliche Zahl k ein Element von X, so ist auch ihr Nachfolgerk + 1 in X.

Dann folgt bereits, dass X = N0 ist, also X alle natrlichen Zahlen enthlt.

Die zweite Version ist nur geringfgig anders:

Axiom (Induktionsaxiom II). Sei X {x N0|x m} eine Teilmenge vonnatrlichen Zahlen, die grer oder gleich der festen natrlichen Zahl m sind.Wir nehmen an, dass die folgenden zwei Bedingungen fr X gelten:

30


(I1) m X und

(I2) Ist eine natrliche Zahl k ein Element von X, so ist auch ihr Nachfolgerk + 1 in X.

Dann folgt bereits, dass X = {x N0 |x m} ist, also X alle natrlichenZahlen ab m enthlt.

Will man nun eine Behauptung B(n) fr alle natrlichen Zahlen ab einerbestimmten natrlichen Zahl m beweisen, so braucht man nur berprfen,ob B(m) wahr ist und ob die Aussage B(k) B(k + 1) wahr ist. Mitanderen Worten: Wir mssen berprfen, ob die Aussage fr den kleinstengewnschten Wert m gilt, und dann, ob die Gltigkeit der Aussage fr einenatrliche Zahl k m auch die Gltigkeit der Aussage fr die nachfolgendenatrliche Zahl k + 1 impliziert. Dann folgt nach dem Induktionsaxiom dieGltigkeit der Aussage B(n) fr alle natrlichen Zahlen ab m. (Um daraufdas Induktionsaxiom anzuwenden, betrachten wir nmlich die Menge X ={x N0 |x m und B(x) wahr}.)

Nun knnen wir diese neue Technik anwenden, um den Satz 3.1 zu be-weisen.

Beweis des Satzes 3.1. Wir beweisen den Satz durch Induktion nach n.Induktionsanfang: Zunchst mssen wir zeigen, dass die Aussage fr

den kleinsten relevanten Wert wahr ist. Da wir die Existenz der Pflasterungfr alle n 1 beweisen wollen, mssen wir fr den Induktionsanfang dieAussage fr n = 1 beweisen. Das haben wir oben bereits getan: Ein 2 2-Quadrat ohne Ecke ist genau das L-Teilchen, und somit lsst sich dieses durch(genau eines) L-Teilchen pflastern. Also ist die Aussage des Satzes wahr frn = 1.

Induktionsschritt: Im Induktionsschritt muss die folgende Aussage ge-zeigt werden: Gilt die Behauptung des Satzes fr eine feste natrliche Zahlk 1, so gilt sie auch fr Ihren Nachfolger k+ 1. Wir nehmen also an (ohnees bislang zu wissen!), dass die Aussage fr k 1 wahr ist. Diese Annahmenennen wir Induktionsvoraussetzung. Unter dieser Annahme zeigen wirdann, dass die Aussage auch fr k + 1 wahr ist. Konkret heit es in diesemFall: Wir nehmen an, wir htten bereits eine Pflasterung fr ein 2k 2k-Quadrat ohne Ecke, das ist die Induktionsvoraussetzung. Wir wollen diesenun nutzen, um zu zeigen, dass ein 2k+1 2k+1-Quadrat ohne Ecke ebenfallsmit L-Teilchen gepflastert werden kann. Dafr ist es ganz ntzlich, wenn manein Objekt, das in der Induktionsvoraussetzung vorkommt, in dem grerenObjekt wiederfinden knnen. Hierfr ist die folgende Beobachtung zentral:Teilt man die Seiten des 2k+1 2k+1-Quadrats jeweils in zwei Hlften auf, soerhlt man vier Quadrate der Gre 2k 2k:

31


2k

2k

2k+1

2k+1

2k2k

Macht man dies mit dem 2k+12k+1-Quadrat ohne Ecke, so bekommt manein 2k 2k-Quadrat ohne Ecke und drei unbeschdigte 2k 2k-Quadrate:

Man wei nach Induktionsvoraussetzung bereits, wie man das kleinereQuadrat ohne Ecke pflastert und muss sich fr die restlichen, unbeschdig-ten 2k 2k-Quadrate etwas berlegen. Da wir daraus auch Quadrate ohneeine Ecke machen wollen, stellt es sich als sinnvoll heraus, ein L-Teilchenin die Mitte zu legen, sodass es ein Ecke aus jedem dieser drei kleinerenQuadrate herausnimmt:

Dadurch entstehen drei weitere 2k 2k-Quadrate ohne Ecke, die wir nachInduktionsvoraussetzung bereits pflastern knnen. Damit haben wir aber -unter unserer Annahme, das 2k 2k-Quadrat ohne Ecke pflastern zu knnen

32


- das 2k+12k+1-Quadrat ohne Ecke mit L-Teilchen gepflastert. Das vervoll-stndigt den Induktionsschritt. Somit greift das Induktionsprinzip, und nachdem Induktionsaxiom ist die Aussage bewiesen.

Wir wollen im Folgenden an einigen Beispielen weiter verdeutlichen, wieInduktionsbeweise funktionieren. Dabei haben die Beweise stets hnlichesGrundmuster, aber im Induktionsschritt (und manchmal schon beim Induk-tionsanfang) werden stets Methoden herangezogen, die fr die Aussage spe-zifisch sind.

Proposition 3.2. Fr alle natrlichen Zahlen n 1 gilt: 2n > n.

Beweis. Wir beweisen die Proposition durch Induktion nach n.Induktionsanfang: Fr n = 1 haben wir die Aussage 21 > 1 zu prfen.

Diese ist offensichtlich wahr.Induktionsschritt: Fr den Induktionsschritt mssen wir die folgende

Aussage beweisen: Gilt fr eine natrliche Zahl k 1, dass 2k > k, sofolgt daraus auch 2k+1 > k + 1. Dafr nutzen wir die Umformungsregelnfr Ungleichungen, die wir kennengelernt haben. Dabei starten wir mit derInduktionsvoraussetzung und multiplizieren beide Seiten mit 2:

2k > k | 2 2k+1 > 2k .

Das ist mglich, da Multiplikation mit einer positiven reellen Zahl die Gltig-keit einer Ungleichung nicht ndert. Nun schreiben wir 2k = k+k und addie-ren zu beiden Seiten der Voraussetzung k 1 die reelle Zahl k, was die Gl-tigkeit der Ungleichung nicht ndert und die neue Ungleichung k+k k+ 1liefert. Zusammengesetzt erhalten wir

2k+1 > 2k k + 1,

was 2k+1 > k+1 impliziert. Das vervollstndigt den Induktionsschritt. Darausfolgt mit dem Induktionsaxiom die Behauptung.

Die nchste Proposition ist eine der berhmtesten Anwendungen der In-duktion.

Proposition 3.3. Fr alle natrlichen Zahlen n 1 gilt:

1 + 2 + . . .+ n =n(n+ 1)

2.

Dabei ist mit der Summe auf der linken Seite die Summe aller natrlichenZahlen von 1 bis einschlielich n gemeint. Um das prziser handhaben zuknnen, fhren wir die folgende Notation ein:

33


Notation. Ist P (k) ein Term in Abhngigkeit von einer natrlichen Zahl k,so schreiben wir die Summe der Werte von P fr natrliche Zahlen zwischenm und n als

nk=m

P (k).

Beispiel. 7i=1

i steht fr die Summe der natrlichen Zahlen zwischen 1

und 7, also

7i=1

i = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

4i=3

(i2 + 7i) = (32 + 7 3) + (42 + 7 4) = 74.

3i=0

2i = 20 + 21 + 22 + 23 = 15.

Mit dieser Notation lsst sich nun die obige Proposition schreiben alsni=1

i = n(n+1)2

. Diese Aussage wollen wir nun beweisen.

Beweis der Proposition 3.3. Wir beweisen die Proposition durch Induktionnach n.

Induktionsanfang: Fr n = 1 haben wir die Aussage 1 = 1(1+1)2

zuprfen. Diese ist wahr, wie man leicht nachrechnet.

Induktionsschritt: Fr den Induktionsschritt mssen wir die folgendeAussage beweisen: Gilt fr eine natrliche Zahl m 1 die Aussage:

mi=1

i =m(m+ 1)

2

so folgt daraus auchm+1i=1

i = (m+1)((m+1)+1)2

.

Diesmal fangen wir mit der linken Seite der Behauptung an und formendiese um. Erste wichtige Beobachtung bereitet die Anwendung der Indukti-onsvoraussetzung vor.

m+1i=1

i = 1 + 2 + . . .+m+ (m+ 1)

= (1 + 2 + . . .+m) + (m+ 1)

=mi=1

i+ (m+ 1).

34


Die Summe der natrlichen Zahlen von 1 bis m knnen wir nach Indukti-onsvoraussetzung bereits durch m(m+1)

2ersetzen. Danach klammern wir den

Faktor m+ 1 aus.mi=1

i+ (m+ 1)IV=

m(m+ 1)

2+ (m+ 1) = (m+ 1)

(m2

+ 1).

Nun vereinfachen wir den Term in der zweiten Klammer und formen den um,bis wir das gewnschte Ergebnis bekommen haben. .

(m+ 1)(m

2+ 1)

= (m+ 1) m+ 22

=(m+ 1)((m+ 1) + 1)

2.

Insgesamt haben wir also durch Termumformungen unter Zuhilfenahme derInduktionsvoraussetzung gezeigt:

m+1i=1

i =(m+ 1)((m+ 1) + 1)

2.

Damit ist der Induktionsschritt vollstndig. Die Behauptung folgt nun nachdem Induktionsaxiom.

In der nchsten Proposition soll es darum gehen, die Summe der ungera-den natrlichen Zahlen bis zu einer gewissen Zahl zu bestimmen. Bevor wirdas tun knnen, mssen wir uns berlegen, wie man die ungeraden natr-lichen Zahlen ausdrcken kann. Die i-te ungerade natrliche Zahl lsst sichals 2i 1 schreiben, z.B. ist die erste ungerade natrliche Zahl 2 1 1 = 1,die zweite 2 2 1 = 3, die zweiundzwanzigste 2 22 1 = 43. Damit lsstsich nun die folgende Proposition formulieren.

Proposition 3.4. Die Summe der ersten k ungerader natrlicher Zahlenbetrgt k2. Als Formel:

kj=1

(2j 1) = k2

fr alle natrlichen Zahlen k 1.Beweis. Wir beweisen die Proposition wieder mittels vollstndiger Induktionnach k.

Induktionsanfang: Fr k = 1 haben wir die Aussage1

j=1(2j1) = 12zu prfen. Die Summe lsst sich als 2 1 1 schreiben, und dieser Ausdruckhat tatschlich den Wert 1.

Induktionsschritt: Hier mssen wir zeigen, dass aus der Gltigkeit der

Gleichungkj=1

(2j 1) = k2 fr eine natrliche Zahl k auch die Gleichung

k+1j=1

(2j 1) = (k + 1)2

35


folgt. Wieder fangen wir mit der linken Seite an und merken, dass die Sum-me um einen einzigen Summanden im Vergleich zur Induktionsvoraussetzungerweitert worden ist. Also knnen wir wieder die Induktionsvoraussetzunganwenden und erhalten:

k+1j=1

(2j 1) =kj=1

(2j 1) + (2(k + 1) 1) IV= k2 + (2(k + 1) 1).

Nach Auflsen der Klammern sehen wir sofort, dass wir die 1-te binomischeFormel anwenden knnen:

k2 + (2(k + 1) 1) = k2 + 2k + 1 = (k + 1)2.

Das zeigt die Behauptung im Induktionsschritt und somit die Behauptungder Proposition.

Das nchste Beispiel fr die Anwendung der Induktion ist von etwas an-derer Natur. Um dieses genauer behandeln zu knnen, wollen wir nochmalden Begriff von Teilbarkeit prziser machen.

Definition 3.5. Wir sagen, die natrliche Zahl k 6= 0 teilt die natrlicheZahl m, falls m

keine ganze Zahl ist.

Damit knnen wir nun die folgende Proposition beweisen.

Proposition 3.6. Die Zahl 8m3m ist fr jede natrliche Zahl m 1 durch5 teilbar.

Beweis. Wir beweisen die Proposition durch Induktion nach m.Induktionsanfang: Fr m = 1 mssen wir nachprfen, ob 8131 durch

5 teilbar ist. Da 8131 = 5, ist die Aussage der Proposition fr m = 1 wahr.Induktionsschritt: Hier mssen wir beweisen, dass die Zahl 8m+13m+1

durch 5 teilbar sein muss, falls wir bereits wissen, dass 8m 3m durch 5teilbar ist. Wir benutzen die obige Definition der Teilbarkeit. Wir mssen alsoprfen, ob 8m+13m+1

5eine ganze Zahl ist. Dafr formen wir diesen Ausdruck

etwas um. Als erstes fgen wir dabei einen Summanden 38m im Zhler hinzuund ziehen ihn wieder ab:

8m+1 3m+1

5=

8m+1 3 8m + 3 8m 3m+1

5

Wir benutzen nun, dass 8m+1 = 8 8m und 3m+1 = 3 3m, und klammern dieFaktoren 8m bzw. 3 jeweils aus:

8m+1 3 8m + 3 8m 3m+1

5=

8m (8 3) + 3 (8m 3m)5

.

36


Nun teilen wir diese Summe auf:

8m (8 3) + 3 (8m 3m)5

= 8m + 3 8m 3m

5.

Nach Induktionsvoraussetzung wissen wir, dass 8m 3m durch 5 teilbar ist,also folgt aus der Induktionsvoraussetzung, dass 8m3m

5eine ganze Zahl ist.

Das bleibt genauso, wenn wir diese Zahl mit 3 multipliziert wird, und auch,wenn wir eine weitere ganze Zahl 8m dazu addieren. Also ist

8m+1 3m+1

5= 8m + 3 8

m 3m

5

eine ganze Zahl, und folglich haben wir aus der Induktionsvoraussetzunghergeleitet, dass 8m+13m+1 durch 5 teilbar ist. Also ist der Induktionsschrittvollstndig und die Proposition damit bewiesen.

37

Viktoriya Ozornova 4 ABZHLEN I

4 Abzhlen IWir wollen nun einige Methoden lernen, um die Anzahl von Objekten einerMenge (die beispielsweise durch Mengenoperationen, die wir kennengelernthaben, aus anderen Mengen bekannter Gre entstanden ist). Ein Beispielhierfr haben wir bereits in der Proposition 2.11 bereits gesehen. Ein weiteresResultat, das man leicht einsieht, ist das folgende:

Proposition 4.1. Seien A und B endliche Mengen, so gilt: |AB| = |A||B|.

Beweis. Listet man die Elemente von AB auf, also Paare von Elementen(a, b) mit a A und b B, so erhlt man fr jedes Element von A genau|B| Elemente, eins fr jedes Element von B. Da das fr jedes Element vonA gilt, erhlt man insgesamt |A| |B|.

Nun wollen wir eine weitere, deutlich schwierigere Aussage von diesemTyp mit Hilfe von vollstndiger Induktion beweisen.

Satz 4.2. Sei A eine n-elementige Menge. Dann hat die Potenzmenge vonA, P(A), genau 2n Elemente. Mit anderen Worten: Die Menge A hat genau2n Teilmengen.

Beweis. Wir beweisen die Aussage wieder durch Induktion nach n.Induktionsanfang: Fr n = 0 haben wir genau eine Menge, die 0 Ele-

mente hat, nmlich die leere Menge . Die leere Menge hat genau eine Teil-menge, und zwar die leere Menge selbst. Also gilt P() = {} und insbe-sondere |P()| = 1, was genau 20 ist. Die Aussage des Satzes stimmt alsofr n = 0.

Induktionsschritt: Nun mssen wir zeigen: Wenn fr jede k-elementigeMenge A gilt, dass |P(A)| = 2k gilt (fr ein festes k), so gilt auch fr jedek + 1-elementige Menge B: |P(B)| = 2k+1. Sei also B eine k + 1-elementigeMenge. Da k eine natrliche Zahl ist, ist k 0 und folglich k+ 1 1, sodasswir wissen, dass die Menge B nicht die leere Menge ist. Insbesondere knnenwir uns ein Element b B auswhlen. Wir betrachten nun die folgendenbeiden Teilmengen der Potenzmenge von B:

X = {C B | b C} undY = {C B | b / C}.

Da jede Teilmenge von B entweder das Element b enthlt oder es nicht ent-hlt, gilt

P(B) = X Y.

Da ferner nur eine von beiden Mglichkeit jeweils eintritt, sind die MengenX und Y disjunkt. Daraus folgt nun mit Proposition 2.11:

|P(B)| = |X|+ |Y |.

38


Man muss also nur die Anzahlen von Elementen von X und von Y bestim-men, um |P(B)| zu berechnen. Dazu bentigen wir zwei Schritte. Zunchstbestimmen wir dabei die Anzahl der Elemente von Y , und danach zeigen wir,dass X und Y gleich viele Elemente haben.

Schritt 1: In diesem Schritt bestimmen wir die Anzahl der Elemente von Y . Dafrmachen wir die folgende Beobachtung: Ist C eine Teilmenge von B, die bnicht enthlt, so ist C auch eine Teilmenge von B\{b}. Umgekehrt kannjede Teilmenge von B \ {b} als eine Teilmenge von B gesehen werden,die b nicht enthlt. Somit knnen wir sagen, dass Y = P(B \ {b}) gilt,da wir uns gerade berlegt haben, dass beide Mengen dieselbe Elementebesitzen. Insbesondere folgt daraus |Y | = |P(B \ {b})|. Da b B, hatdie Menge B\{b} genau k Elemente, da wir ein Element aus der (k+1)-elementigen Menge B entfernt haben. Das versetzt uns in die Lage,auf die Menge B \ {b} die Induktionsvoraussetzung anzuwenden. Darinhaben wir angenommen, dass wir bereits die Anzahl der Elemente in derPotenzmenge einer k-elementigen Menge bestimmen knnen. Wendenwir das auf die k-elementige Menge B \ {b} an, so erhalten wir:

|Y | = |P(B \ {b})| = 2k.

Die Menge Y hat also 2k Elemente.

Schritt 2: In diesem zweiten Schritt wollen wir zeigen, dass X und Y gleich vieleElemente haben. Dabei gehen wir wie folgt vor: Wir geben zu jedemElement von X einen Partner in Y an, und zeigen dann, dass jedesElement in X genau einen Partner bekommt, dass kein Element von Yzwei oder mehr Partner bekommen hat und dass auch jedes Elementvon Y an ein Element von X vergeben wurde. (Man knnte sich vor-stellen, man wrde eine Gruppe von Personen in Tanzpaare aufteilen,und wir mssen nachprfen, dass die Aufteilung genau aufgeht.)

Jedem Element C X wollen wir also ein Element von Y zuordnen.Wir starten also mit einem Element C von X. Nach Definition ist einElement von X eine Teilmenge von B, die das Element b enthlt. Wirwollen dieser ein Element von Y zuordnen, also eine Teilmenge von B,die das Element b nicht enthlt. Dafr tun wir etwas naheliegendes:Wir nehmen die Teilmenge C von B und entfernen daraus das Elementb, bilden also die Menge C \ {b}. Das ist wieder eine Teilmenge vonB, und auerdem enthlt sie das Element b nicht, denn das habenwir herausgenommen. Also ist C \ {b} Y . Wir haben also zu jedemElement von X einen Partner in Y gefunden. Jetzt mssen wir zweiAussagen prfen: Auf diese Weise haben wir jedem Element von X einElement von Y zugeordnet. A priori ist es allerdings unklar, ob jedesElement von Y dabei vergeben wurde, und ob nicht manche Elementevon Y doppelt vergeben wurden.

39


Kann es also sein, dass wir zwei unterschiedliche Teilmengen C1, C2 vonB genommen haben, die beide b enthalten, und durch das Entfernendes Elementes b die Mengen gleich wurden, also C1 \ {b} = C2 \ {b}gilt? Das kann nicht vorkommen, denn mindestens eine von den MengenC1, C2 muss ein Element enthalten, das nicht in der anderen liegt, sonstwren die Mengen gleich. Dieses Element kann aber nicht b sein, denn bist sowohl in C1 als auch in C2 enthalten. Also ist dieses Element nachwie vor in genau einer der Mengen C1 \ {b}, C2 \ {b} enthalten, unddiese Mengen wren also unterschiedlich. Es ist also kein Element vonY doppelt vergeben worden.

Knnte es nun mglicherweise sein, dass manche Elemente aus Y garnicht an Elemente von X vergeben wurden? Auch das kann nicht pas-sieren: Ist D Y , so ist D nach Definition von Y eine Teilmenge vonB, die das Element b nicht enthlt. Wir suchen also ein Element vonX, dem D zugeordnet wurde, also eine Teilmenge von B, die b enthltund die nach Entfernen von b zu der Menge D wird. Eine solche Mengeist durch D{b} gegeben. Diese Menge ist nach Definition ein Elementvon X, dessen Partner in Y genau D ist.

Somit haben wir nachgewiesen, dass X und Y genau dieselbe Anzahlvon Elementen haben, also |X| = |Y | = 2k.

Nimmt man nun die vorher hergeleitete Formel

|P(B)| = |X|+ |Y |

und setzt |X| = |Y | = 2k ein, so erhlt man

|P(B)| = 2k + 2k = 2k+1.

Das vervollstndigt den Induktionsschritt und zeigt somit die Behauptung.

Man sollte insbesondere bemerken, dass die Gre der Potenzmenge inAbhngigkeit von der Gre der ursprnglichen Menge sehr schnell wchst,und zwar exponentiell.

In nchsten Schritt will man noch etwas prziser werden und die Anzahlder Teilmengen einer festen Gre in der vorgegebenen Menge ermitteln.Dafr fhren wir Binomialkoeffizienten ein. Es werden dieselben sein, dievermutlich aus dem Schulunterricht bekannt sind, allerdings werden wir sieanders definieren. Wir sehen spter, dass beide Definitionen quivalent sind.

Definition 4.3. Die Anzahl der k-elementigen Teilmengen einer n-elementigenMenge ist der Binomialkoeffizient

(nk

)(Sprechweise: n ber k).

Beispiel. Eine n-elementige Menge A hat genau eine 0-elementige Teil-menge, nmlich die leere Menge. Deswegen gilt

(n0

)= 1 fr alle n 0.

40


Eine n-elementige Menge A hat auch genau eine n-elementige Teilmen-ge, nmlich sich selbst. Daher gilt stets

(nn

)= 1.

Eine n-elementige Menge A hat fr n 1 genau n unterschiedlicheeinelementige Teilmengen, denn man kann jedes der Elemente von Aals das einzige Element unserer Teilmenge aussuchen. Deswegen gilt(n1

)= n fr alle n 1.

Konkreter wollen wir noch(

32

)bestimmen. Dafr betrachten wir die

3-elementige Menge {a, b, c} und listen alle mglichen 2-elementigenTeilmengen von dieser auf: Das sind {a, b}, {a, c}, {b, c}. Also gilt

(32

)=

3.

Die Binomialkoeffizienten knnen im Pascalschen Dreieck angeordnetwerden. Die bis jetzt bestimmen Binomialkoeffizienten sowie die Bino-mialkoeffizienten der Form

(4k

)ergeben:

(00

)= 1(

10

)= 1

(11

)= 1(

20

)= 1

(21

)= 2

(22

)= 1(

30

)= 1

(31

)= 3

(32

)= 3

(33

)= 1(

40

)= 1

(41

)= 4

(42

)= 6

(43

)= 4

(44

)= 1

oder etwas gewohnter:

11 1

1 2 11 3 3 1

1 4 6 4 1

Im Pascalschen Dreieck ergibt die Summe der beiden Binomialkoeffizien-ten, die rechts und links oberhalb von einer Stelle stehen, genau den Bino-mialkoeffizienten an dieser Stelle. Das halten wir im folgenden Satz fest.

Satz 4.4. Fr alle natrlichen Zahlen n,k gilt:(n+1k

)=(nk

)+(nk1

).

Da der Beweis dem des Satzes 4.2 hnelt und recht aufwndig zum pr-zisen Aufschreiben ist, geben wir hier nur die Beweisidee fr diesen Satz.Diese ist wichtig, weil solche und hnliche Zhlmethoden hufiger zum Be-weis Identitten dieser Art herangezogen werden.

41


Beweisidee. Wir gehen ganz hnlich vor wie im Beweis des Satzes 4.2.Die Zahl

(n+1k

)beschreibt die Anzahl der k-elementigen Teilmengen einer

n+ 1-elementigen Menge, die wir fr diesen Beweis B nennen. Da n+ 1 1,hat die Menge B mindestens ein Element. Wir betrachten ein festes Ele-ment b B. Jede k-elementige Teilmenge von B enthlt b oder enthlt bnicht. Zunchst fragen wir uns, wie viele k-elementige Teilmengen von B dasElement b nicht enthalten. Diese sind genau die k-elementigen Teilmengenvon B \ {b}, also einer n-elementigen Menge. Da gibt es nach Definition derBinomialkoeffizienten genau

(nk

)verschiedene k-elementige Teilmengen.

Als nchstes mssen wir also die k-elementigen Teilmengen zhlen, die benthalten. Nimmt man das Element b aus solcher Teilmenge heraus, so erhltman eine (k1)-elementige Teilmenge von der n-elementigen Menge B \{b}.hnlich wie im Satz 4.2 kann man sich berlegen, dass jeder k-elementigenTeilmenge von B, die b enthlt, so genau eine (k 1)-elementige Teilmengevon B \ {b} zugeordnet wird. Umgekehrt kann jeder (k 1)-elementigenTeilmenge von B\{b} eine k-elementige Teilmenge von B zugeordnet werden,die b enthlt, einfach indem wir b als Element hinzufgen. Auf diese Weisekann man nachweisen, dass die Anzahl der k-elementigen Teilmengen von B,die b enthalten, genau

(nk1

)ist.

Daraus folgt die Behauptung.

Wie das Verfahren aus dieser Beweisidee etwas konkreter aussieht, sollam folgenden Beispiel veranschaulicht werden.

Beispiel. Die 3-elementigen Teilmengen der Menge {a, b, c, d, e} sind:

Die dreielementigen Teilmengen von {a, b, c, d, e}, die e nicht als Ele-ment enthalten:

{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d},

insgesamt(

43

)= 4 Mengen. (Diese Teilmengen sind insbesondere die

dreielementigen Teilmengen der Menge {a, b, c, d}.

Die dreielementigen Teilmengen von {a, b, c, d, e}, die das Element eenthalten:

{a, b, e}, {a, c, e}, {a, d, e}, {b, c, e}, {b, d, e}, {c, d, e},

insgesamt(

42

)= 6 Mengen. (Diese Teilmengen entstehen aus den 2-

elementigen Teilmengen der Menge {a, b, c, d} durch Hinzufgen desElementes e.)

Die Binomialkoeffizienten werden in der folgenden Verallgemeinerung derersten binomischen Formel benutzt.

42


Satz 4.5 (Binomischer Lehrsatz). Fr alle x, y R und alle natrlichenZahlen n gilt:

(x+ y)n =nk=0

(n

k

)xkynk.

Bevor wir eine Beweisidee fr diesen Satz geben, wollen wir uns verge-genwrtigen, in wie fern dies eine Verallgemeinerung der ersten binomischenFormel ist. Dafr setzen wir n = 2 ein und erhalten, indem wir die Summewieder ausschreiben:

(x+ y)2 =2

k=0

(2

k

)xky2k =

(2

0

)x0y20 +

(2

1

)x1y21 +

(2

2

)x2y22.

Setzt man die vorher bestimmten Werte fr Binomialkoeffizienten ein, soerhalten wir(

2

0

)x0y20 +

(2

1

)x1y21 +

(2

2

)x2y22 = 1 1 y2 + 2 xy + 1 x2 1

= y2 + 2xy + x2,

also genau die erste binomische Formel.Wir wollen, um die Funktionsweise der Formel besser zu verstehen, uns

auch den Fall n = 3 ansehen. Genauso wie zuvor erhalten wir

(x+ y)3 =3

k=0

(3

k

)xky3k

=

(3

0

)x0y30 +

(3

1

)x1y31 +

(3

2

)x2y32 +

(3

3

)x3y33

= 1 1 y3 + 3 xy2 + 3 x2y + 1 x3 1= y3 + 3xy2 + 3x2y + x3.

Allgemein knnen wir den binomischen Lehrsatz etwas informeller in derForm

(x+ y)n =

(n

0

)x0yn +

(n

1

)x1yn1 + . . .+

(n

n 1

)xn1y1 +

(n

n

)xny0

schreiben.Um uns auf die Beweisidee vorzubereiten, berlegen wir uns, wie man

Klammern simultan ausmultipliziert. Die grundstzliche Methode ist diesel-be, wie beim blichen Ausmultiplizieren von Klammern: Fr jeden neuenSummanden vom Ergebnis nimmt man jeweils einen Summanden aus jederKlammer, und jede Kombination von Summanden betrachtet man genaueinmal.

43


So erhalten wir durch ausmultiplizieren von (x+ y)3:

(x+ y)(x+ y)(x+ y) = x3 + yx2 + xyx+ x2y + xy2 + yxy + y2x+ y3.

Wir berlegen uns am Beispiel von (x + y)4, dass die Teilmengen von{1, 2, 3, 4} dazu genutzt werden knnen, die Summanden im ausmultiplizier-ten Term zu nummerieren. (Das ist kein allgemeiner Beweis, sondern eben nurein Beispiel. Hier soll auf einen Beweis verzichtet werden. Es ist hufig beimLsen von mathematischen Problemen so, dass man sich die grundstzlicheBeweismethode zunchst an Beispielen klarmacht, und im nchsten Schrittdann diese zu einem strikten Beweis formalisiert. Beide Schritte sind wichtigzu lernen; hier wollen wir den Schwerpunkt auf dem ersten Teil setzen.)

Wir lassen uns von jeder Teilmenge von {1, 2, 3, 4} also anzeigen, aus wel-chen Klammern wir den Summanden x auswhlen; aus den brigen Klam-mern whlen wir den Summanden y aus. Ist beispielsweise die Menge {1, 3}vorgegeben, so entspricht das dem Produkt xyxy, also nehmen wir x in derersten, y in der zweiten, x in der dritten, y in der vierten Klammer. DieMenge {1, 2, 3, 4} wrde dem Produkt x4 entsprechen, also der Wahl von xin jeder Klammer. Die leere Menge hingegen entspricht dem Produkt y4, dennin keiner Klammer wurde das x ausgewhlt - also wurde in jeder Klammery ausgewhlt. Insgesamt erhalten wir vor dem Zusammenfassen 24 Summan-den, fr jede Teilmenge von {1, 2, 3, 4} genau einen, und jeder Summandkann so beschrieben werden. Beim Zusammenfassen sehen wir, dass jede k-elementige Teilmenge von {1, 2, 3, 4} den Summanden xky4k liefert, denneine k-elementige Teilmenge lsst uns k-mal das x und (4 k)-mal das yauswhlen. Das ist auch das Herzstck des Beweises, den wir jetzt etwasallgemeiner, wenn auch nicht ganz formal, festhalten.

Beweisidee zu dem Satz 4.5. Wie in der Vorberlegung, multiplizieren wirdie Klammern in dem Produkt (x + y)n simultan aus. Dabei entsprechendie Summanden vom Ergebnis vor dem Zusammenfassen den Teilmengenvon {1, 2, . . . , n}. Das sieht man, indem man jeder Teilmenge den Summan-den zuordnet, bei dem x genau in den Klammern ausgewhlt wurde, dievon dieser Teilmenge angegeben sind, und y in den brigen Klammern. Aufdiese Weise entstehen vor dem Zusammenfassen 2n Summanden, und diek-elementigen Teilmengen entsprechen genau den Summanden xkynk. Nunhaben wir

(nk

)als die Anzahl der k-elementigen Teilmengen von einer n-

elementigen Menge definiert, also wird es nach dem Ausmultiplizieren genau(nk

)Summanden xkynk geben. Nach dem Zusammenfassen erhalten wir also

genaunk=0

(nk

)xkynk, wie behauptet.

Aus dem binomischen Lehrsatz lsst sich nun das folgende Korollar ab-leiten:

44


Korollar 4.6. Fr alle natrlichen Zahlen n gilt:nk=0

(nk

)= 2n.

Bevor wir das Korollar beweisen, veranschaulichen wir uns die Situationim Pascalschen Dreieck: Die Summe auf der linken Seite ist jeweils die Summealler Binomialkoeffizienten in der n-ten Zeile, die wir hier rechts neben jederZeile notieren:

1 11 1 2

1 2 1 41 3 3 1 8

1 4 6 4 1 161 5 10 10 5 1 32

Beweis des Korollars 4.6. Wir fgen bei den Summanden den Faktor 1 =1k 1nk hinzu, was die Summe nicht verndert.

nk=0

(n

k

)=

nk=0

(n

k

) 1k 1nk.

Darauf lsst sich nun der binomische Lehrsatz 4.5 anwenden. Wir erhaltenalso

nk=0

(n

k

)=

nk=0

(n

k

) 1k 1nk = (1 + 1)n = 2n,

was zu beweisen war.

Alternativer Beweis wrde wie folgt aussehen: Jede Teilmenge einer n-elementigen Menge hat eine gewisse Anzahl von Elementen, und diese Anzahlist eine natrliche Zahl zwischen 0 und n (einschlielich). Wenn wir also die

Summenk=0

(nk

)bilden, erhalten wir die Gesamtzahl aller mglichen Teilmen-

gen einer n-elementigen Menge, die wir nach Gre sortiert aufgeschriebenhaben. Auf der anderen Seite wissen wir nach Satz 4.2, dass die Anzahl derTeilmenge einer n-elementigen Menge 2n betrgt. Das zeigt die Behauptung.

Nun wollen wir auf die Beschreibung der Binomialkoeffizienten zurck-kommen, die in der Schule blicherweise benutzt wird. Dafr mssen wir denBegriff der Fakultt einer natrlichen Zahl wiederholen.

Definition 4.7. Fr jede natrliche Zahl n 1 ist n! (n Fakultt) dasProdukt der natrlichen Zahlen von 1 bis n:

n! = 1 2 . . . n.

Fr 0 definieren wir 0! = 1.

45


Beispiel. Wir bestimmen die Fakultten fr kleine natrliche Zahlen:

1! = 1

2! = 1 2 = 23! = 1 2 3 = 64! = 1 2 3 4 = 245! = 1 2 3 4 5 = 1206! = 1 2 3 4 5 6 = 7207! = 1 2 3 4 5 6 7 = 5040

Es ist eine wichtige Beobachtung, dass Fakultten sehr schnell wachsen.

Die Fakultten spielen eine wichtige Rolle beim Lsen von Abzhlproble-men. Hier ist ein Beispiel dafr.

Satz 4.8. Es gibt n! unterschiedliche Anordnungen von n Objekten.

Beispiel. Die Objekte a, b, c knnen auf 3! = 6 Arten angeordnet werden:

abc, acb, bac, bca, cab, cba

Der Beweis dieses Satzes wrde durch Induktion erfolgen. Da wir bereitssehr viele formale Induktionsbeweise gesehen haben, beschrnken wir unsauch hier auf eine Beweisidee.

Beweisidee. Die Aussage ist wahr fr n = 1.Bei einer Anordnung von den n Objekten hat man n Mglichkeiten, das

erste Objekt auszuwhlen. Fr jedes Anfangsobjekt und die restlichen (n1)Objekte gibt es (n 1)!-Mglichkeiten, die restlichen Objekte anzuordnen.Das liefert insgesamt n (n 1)! = n! Anordnungen.

Nun knnen wir die Binomialkoeffizienten mit Hilfe von Fakultten aus-drcken.

Satz 4.9. Fr alle natrlichen Zahlen n k gilt:(nk

)= n!

k!(nk)! .

Wieder erlutern wir zunchst die Beweisidee an einem Beispiel.

Beispiel. Wir suchen die 2-elementigen Teilmengen von {a, b, c, d}. Um die-se zu erhalten, betrachten wir alle mglichen Anordnungen der Objektea, b, c, d, und whlen in jeder solchen Anordnung die ersten zwei Elementezu den Elementen einer zweielementigen Menge aus. Dabei erhalten wir je-de 2-elementige Teilmenge von {a, b, c, d}, allerdings hufiger zweimal. Das

46


wollen wir konkret durchfhren (wir verzichten hier zwecks besseren ber-sichtlichkeit auf Klammern):

abcd acbd bacd bcad cabd cbad

abdc adbc badc bdac dabc dbac

acdb adcb cadb cdab dacb dcab

bcda bdca cbda cdba dbca dcba

Dabei merken wir, dass wir jede 2-elementige Teilmenge 4 Mal gezhlt haben.Dabei erzeugen die mglichen Anordnungen der zweielementigen Menge eineVerdopplung in der Zhlung, und die mglichen Anordnungen der brigge-bliebenen zwei Elementen erzeugen eine weitere Verdopplung. Daher erhltman 24 2-elementige Teilmengen der Menge {a, b, c, d}, wobei jede Teilmenge4 Mal gezhlt wurde, also 24

4= 6 zweielementige Teilmengen. Das Prinzip

verallgemeinern wir nun.

Beweisidee. Betrachte eine n-elementige Menge A. Betrachte alle n! mgli-chen Anordnungen der Elemente der Menge A. Bei jeder Anordnung fassenwir die ersten k Elemente zu einer Teilmenge auf. Auf diese Weise erhaltenwir jede k-elementige Teilmenge, jedoch werden diese im Allgemeinen mehr-fach vorkommen. Bislang haben wir n! Teilmengen, von denen manche gleichsind, markiert.

Als nchstes ermitteln wir, wie oft jede Teilmenge markiert wurde. DieTeilmenge und die restlichen (n k) Elemente knnen beliebig angeordnetwerden und liefert dabei immer dieselbe Teilmenge, da es bei Teilmengen nurauf die Elemente und nicht auf deren Reihenfolge ankommt. Somit wurde jedeTeilmenge k! (n k)! Mal markiert, da wir die k-elementige Menge auf k!verschiedene Arten anordnen knnen und die restlichen Element auf (n k)!verschiedene Arten, und diese Anordnungen sind voneinander unabhngig.Daher gibt es n!

k!(nk)! k-elementige Teilmengen von A, also folgt wie behauptet(n

k

)=

n!

k!(n k)!.

47

Viktoriya Ozornova 5 ABBILDUNGEN

5 AbbildungenIn diesem Abschnitt beschftigen wir uns mit Abbildungen. Abbildungen ge-ben uns eine Mglichkeit, unterschiedliche Mengen miteinander in Beziehungzu setzen. Abbildungen verallgemeinern den Begriff einer Funktion, der ausder Schule bekannt ist.

Definition 5.1. Seien A,B Mengen. Eine Abbildung f : A B ist eineZuordnung, die jedem Element von A genau ein Element von B zuordnet.Die Menge A heit Quelle und die Menge B das Ziel der Abbildung f .

Man bemerke, dass man von einer Abbildung erst sprechen kann, wennman Quelle und Ziel festgelegt hat. Ferner ist es wichtig, dass jedes Elementvon A einen Wert im Ziel B zugeordnet bekommt, und dieses Element sollteeindeutig sein. Letzteres entspricht der aus dem Schulunterricht bekannterTatsache, dass ein Funktionsgraph niemals zwei unterschiedliche y-Werte frdenselben x-Wert haben darf.

Beispiel. Funktionen aus dem Schulunterricht liefert Beispiel fr Ab-bildungen, z.B. f : R R, f(x) = x2. Alternativ schreibt man auchx 7 x2, um die Funktionsvorschrift zu beschreiben.

In manchen Fllen kann man die Abbildung durch die vollstndigeListe der Zuordnungen beschreiben. g : {1, 2, 3} {u, v, w}, g(1) = u,g(2) = v, g(3) = u ist eine Abbildung. Alternativ schreibt man auch:

1 7 u,2 7 v,3 7 u.

Man beachte, dass hier zwei Elementen der Quelle, nmlich den Ele-menten 1 und 3, dasselbe Element zugeordnet wird. Das ist bei Ab-bildungen durchaus zulssig; ausgeschlossen wird nur, dass zwei odermehr Elemente des Bildes die Werte fr ein Element der Quelle alsWerte ausgewhlt werden.

Die Zuordnung {KlausurteilnehmerInnen} {Gltige Noten}, die je-dem Prfling seine Klausurnote zuordnet, ist eine Abbildung. Jede(r)KlausurteilnehmerIn erhlt nmlich eine Klausurnote, und zwar genaueine.

Die Zuordnung g : R R,

a 7 Lsung der Gleichung x2 = a,

ist keine Abbildung. Dabei treten gleich zwei Probleme auf: Den nega-tiven Zahlen wird durch diese Vorschrift keine reelle Zahl zugeordnet,

48


denn die Gleichung x2 = a hat keine Lsung in den reellen Zahlen frdie negativen Werte von a. Fr die positiven Werte von a tritt allerdingsauch ein Problem auf, denn die Gleichung x2 = a hat zwei verschiedeneLsungen, und somit ist es nicht eindeutig, welche der beiden Lsungeneiner positiven Zahl a zugeordnet werden soll.

Die Vorschrift x 7 x2 ist (ohne Kontext) keine Abbildung, da Ziel undQuelle nicht spezifiziert wurden.

Die Zuordnung : [1, 2] [1, 2], x 7 x2, ist ebenfalls keine Abbil-dung. Jedem Element der Quelle soll durch die Vorschrift ein Elementdes Ziels zugeordnet werden, allerdings wrde die Vorschrift z.B. demElement 2 der Quelle die Zahl 4 zuordnen, die kein Element des Zielsist.

Um Abbildungen zu vergleichen, geben wir noch die folgende Definiti-on. Diese ist weitestgehend intuitiv, allerdings mssen Quelle und Ziel derAbbildungen ebenfalls bereinstimmen.

Definition 5.2. Zwei Abbildungen heien gleich, falls sie dieselbe Quelleund dasselbe Ziel haben und beide Abbildungen jedem Element der Quellejeweils dasselbe Element im Ziel zuordnen.

Im Folgenden wollen wir die Eigenschaften von Abbildungen studieren.Dabei fangen wir mit Injektivitt und Surjektivitt an.

Definition 5.3. Eine Abbildung f : X Y heit injektiv, wenn fr allex1, x2 X aus f(x1) = f(x2) folgt: x1 = x2.

Nach Proposition 1.7 knnen wir das unmittelbar zu der folgenden Aus-sage umformulieren: Eine Abbildung f : X Y ist genau dann injektiv,wenn fr alle x1, x2 X mit x1 6= x2 gilt: f(x1) 6= f(x2). UnterschiedlichenElementen der Quelle werden also unterschiedliche Elemente des Ziels zuge-ordnet. Das sollte nicht mit der Definition der Abbildung verwechselt werden:Da geht es darum, dass jedes einzelne Element der Quelle etwas Eindeutigeszugeordnet bekommt, whrend fr die Injektivitt verglichen wird, wie dieWerte fr unterschiedliche Elemente aussehen.

Beispiel. Die Abbildung : R R, (y) = 7y+3, ist injektiv. Um daszu prfen, nehmen wir an, dass y1, y2 R liegen und die Eigenschaft(y1) = (y2) haben. Wir mssen unter dieser Annahme zeigen, dassy1 = y2 folgt. Schreibt man die Annahme expliziter hin, so erhlt man

7y1 + 3 = 7y2 + 3.

Diese Gleichung formen wir nun quivalent um:

7y1 + 3 = 7y2 + 3 | 3 7y1 = 7y2 | : 7 y1 = y2

49


f : {1, 2, 3} {u, v, w}, f(1) = u, f(2) = v, f(3) = u ist keine in-jektive Abbildung. Negiert man die Definition der Injektivitt, so siehtman sofort: Eine Abbildung g : A B ist genau dann nicht injektiv,wenn es Elemente a1, a2 A gibt, sodass a1 6= a2, aber g(a1) = g(a2)gilt. Wendet man das auf die Abbildung f an, so hat man hier unter-schiedliche Elemente 1, 3 der Quelle auf dasselbe Element u des Zielsabgebildet.

Ergnzend zur Injektivitt gibt es auch die Surjektivitt, die im Allge-meinen von der Injektivitt aber unabhngig ist.

Definition 5.4. Seien X, Y zwei Mengen. Eine Abbildung f : X Y heitsurjektiv, wenn jedes Element y Y ein Urbild x X hat, d.h. zu jedemy Y gibt es ein x X mit f(x) = y.

Dabei kan

Mathematische Grundlagen 1: Logik und Algebra · Warnung Dieses Skript enthält unter Umständen Fehler und Ungenauigkeiten jeder Art.FallsSiesolcheentdecken,wäreesnett,wennSiemirIhreAnmerkungen

Text of Mathematische Grundlagen 1: Logik und Algebra · Warnung Dieses Skript enthält unter Umständen...

Logik I - eti.uni-siegen.de

Rechnerarchitektur · Kombinatorische Logik II

Einfuhrung in die Mathematische Logikadler/docs/logik.pdf · 2010. 2. 2. · Was ist mathematische Logik uberhaupt? Und was ist Logik? Die Logik ist ein wissenschaftliches Gebiet

Logik f¨ur Informatiker - userpages.uni-koblenz.desofronie/logik-ss-2012/slides/pred-logik-08.pdf · Pr¨adikatenlogische Resolution Grundidee Vor Resolutionsschritt durch geeignete

Logik - Benutzer-Homepages · PDF fileLogik > Logik > logische Aussagen Motivation Logik spielt in der Informatik eine wichtige Rolle. Anwendungen sind z.B. Modellierung von Wissen

Logik - ein Rätsel von Raymond Smullyan Knobelecke: Logik - ein … · 2017-03-26 · Mathe-Board Logik - ein Rätsel von Raymond Smullyan Mathe-Board: Knobelecke: Logik - ein Rätsel

Einf uhrung in die Mathematische Logik und Theoretische ... · kommen, was die Logik in den letzten 2000 Jahren Positives erreicht hat (und insbesondere, was die mathematische Logik

Klassische Logik - hu-berlin.de

Wissenschaftsmagazin Mathematische Logik

Prism Deploy - Software Deployment · PDF filePrism Deploy®- Paketierungsanleitung, herausgegeben im Juni 2012 Diese Publikation kann technische Ungenauigkeiten oder Schreibfehler

Jedem seine Logik! - Conrad Electronic · Jedem seine Logik! Die dritte Generation von Logik-Controllern für Ihre branchenspezifischen Anwendungen. Größerer Speicher für Ihre

Einführung in die mathematische Logik - ub-net · 2012. 1. 22. · Logik-1 Einführung in die mathematische Logik Ein Crashkurs über die Grundlagen wichtiger Logiken und Beweiskalküle

Logik f¨ur Informatiker - userpages.uni-koblenz.desofronie/logik-ss-2012/slides/aussagenlogik-06.pdf · Logik f¨ur Informatiker 2. Aussagenlogik Teil 6 14.05.2012 Viorica Sofronie-Stokkermans

Georg Wilhelm Friedrich Hegel - Die Wissenschaft der Logik. Die subjektive Logik (1834)

Grundkurs Logik

Selbstbeziehung in Hegels Logik

Logik & Argumentation

Ungenauigkeiten beim Einsatz von GPS-Handgeräten im Physikunterricht Von Frederik Schneider und Stephan Dzialas 1. Statische Messung 2. Dynamische Messung

Die Logik Der Reflexion

Logik für Informatiker - ls1- fileInhalt 1.1 Einleitende Beispiele 1.2 Logik und Mathematik 1.3 Logik und Informatik 1.4 Inhalt dieser Vorlesung 1.5 Literatur 1.6 Organisatorisches

Logik f¨ur Informatiker - userpages.uni-koblenz.desofronie/logik-ss-2012/slides/pred-logik-07.pdf · Vor Resolutionsschritt durch geeignete Substitution komplement¨ares Paar von

Intensionale Logik und theoretische Linguistik · Intensionale Logik und theoretische Linguistik Von Franz von Kutscher a y Regensburg I. Das Verhältnis von Sprache und Logik, ihre

Freges Allgemeine Logik. Freges Allgemeine Logik – Zitate Wie das Wort schön der Ästhetik und gut der Ethik, so weist wahr der Logik die Richtung. Zwar

Schmitz Hegels Logik

JAHRESZWISCHENBERICHT Quantifizierung von Ungenauigkeiten ... · Climate Research Unit (CRU) der University of East Anglia über den Landflächen Mitteleuropas (CRU-area) sind Referenzdaten

Nota Fce3102 Logik

Logik f¨ur Informatiker 1. Grundlegende Beweisstrategiensofronie/logik-ss-2012/slides/... · Logik f¨ur Informatiker 1. Grundlegende Beweisstrategien Viorica Sofronie-Stokkermans

Logik und Argumentation - Leibniz Universität Hannover · 2019-08-27 · Logik und Argumentation Materialien zu einführenden Vorlesungen über formale Logik und Argumentationstheorie

Einführung in die Mathematische Logik - math.uni-bonn.de logik... · Einführung in die Mathematische Logik by Peter Koepke Bonn, Sommersemester 2015 Vorläuﬁges Skript zur Vorlesung

Aussagen Logik

Documents

Mathematische Grundlagen 1: Logik und Algebra · Warnung Dieses Skript enthält unter Umständen Fehler und Ungenauigkeiten jeder Art.FallsSiesolcheentdecken,wäreesnett,wennSiemirIhreAnmerkungen

Text of Mathematische Grundlagen 1: Logik und Algebra · Warnung Dieses Skript enthält unter Umständen...