Skript IMI1 AK

8/19/2019 Skript IMI1 AK

1/227

Mathematik f ̈ur Informatiker 1

Eine Vorlesung von

Dr. Alexandra KötheInstitut f ̈ur angewandte Mathematik

Ruprecht-Karls-Universiẗat Heidelberg

Version vom 3. April 2014


2/227

Inhaltsverzeichnis

Inhaltsverzeichnis 2

Vorwort 4

1 Einleitung 5

1.1 Was ist Mathematik? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Was ist Informatik? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Woher kommt die Informatik? . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Warum muss ich als Informatiker Mathematik lernen? . . . . . . . . . . . . 71.5 Ziele der Vorlesung Mathematik f ̈ur Informatiker . . . . . . . . . . . . . . . 71.6 Einige ermunternde Worte f ̈ur Mathe-Anf ̈anger . . . . . . . . . . . . . . . . 9

I Grundlagen 11

2 Grundlagen der mathematischen Logik 122.1 Aussagen und Quantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2 Verknüpfungen von Aussagen . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.1 Die Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.2 Zweiwertige Verknüpfungen . . . . . . . . . . . . . . . . . . . . . . . 17

2.3 Beweisarten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Grundlagen der Mengenlehre 223.1 Notation und Operationen auf Mengen . . . . . . . . . . . . . . . . . . . . . 223.2 Abbildungen zwischen Mengen . . . . . . . . . . . . . . . . . . . . . . . . . 283.3 Relationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 Algebraische Strukturen 39

4.1 Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.2 Gruppenhomomorphismen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.3 Ringe und Körper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.4 Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5 Zahlenmengen 505.1 Die natürlichen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.2 Die ganzen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.3 Die rationalen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.4 Die reellen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625.5 Die komplexen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.6 Restklassenringe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

2


3/227

II Lineare Algebra 78

6 Vektorräume 796.1 Vektorräume und Untervektorräume . . . . . . . . . . . . . . . . . . . . . . 79

6.2 Basis und Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 836.3 Summen und direkte Summen . . . . . . . . . . . . . . . . . . . . . . . . . . 91

7 Matrizen, LGS und lineare Abbildungen 967.1 Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 967.2 Lineare Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1087.3 Lineare Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1157.4 Basiswechsel und Äquivalenz von Matrizen . . . . . . . . . . . . . . . . . . 132

8 Determinanten und Diagonalisierbarkeit 1478.1 Determinanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

8.2 Eigenwerte und Eigenvektoren . . . . . . . . . . . . . . . . . . . . . . . . . 159

9 Bilinearformen, Skalarprodukte, Spektralsatz 1729.1 Bilinearformen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1729.2 Skalarprodukte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1829.3 Orthogonale Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1889.4 Sebstadjungierte Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . 1929.5 Die Singul̈arwertzerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

10 Anwendungen 20510.1 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

10.2 Total Least Squares Regression . . . . . . . . . . . . . . . . . . . . . . . . . 20910.3 Codierungstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216


4/227

Inhaltsverzeichnis Inhaltsverzeichnis

Vorwort

Dieses Skript wurde erstellt um das Erarbeiten und Lernen des Stoffs der Vorlesung“Mathematik f ̈ur Informatiker 1” zu vereinfachen. Es gilt dabei zu beachten:

• Das Skript basiert auf dem Skript des letzten Jahres von Dr. Daniel Kondermann undDr. Martin Rheinländer. Einige Abschnitte wurden übernommen, andere überarbeitet,wieder andere völlig neu erstellt. So ist ein nicht ganz einheitlicher Stil entstanden,der im Laufe der Zeit hoffentlich immer mehr angeglichen wird.

• Manche Themen hier im Skript sind ausf ̈uhrlicher behandelt als in der Vorlesung.Für die Klausur gilt: relevant ist alles, was in Übung und Vorlesung vorkam. DasSkript soll helfen, eventuell fehlenden Mitschriften zu ergänzen.

• Das Skript ersetzt also auf keinen Fall die eigenen Mitschriften!

• Es gibt hunderte (wenn nicht tausende) von Tippfehlern! Wenn Ihnen beim Lesendes Skripts welche auffallen, dann teilt sie mir bitte mit, insbesondere wenn durchden Tippfehler, der Inhalt falsch wird!!

Grundsätzlich gilt f ̈ur Skript und Vorlesung im Allgemeinen: Solltet ihr deshalb eigeneBeiträge, Fragen, Vorschläge oder Kritik haben: immer her damit! Je mehr ihr zu einergelungenen Vorlesung beitragt, desto befriedigender wird das Ergebnis f ̈ur alle Beteiligten.

4


5/227

1. Einleitung – Was hat Mathematik mitInformatik zu tun?

1.1. Was ist Mathematik?

Die Mathematik wird neben der Philosophie (und vielleicht auch der Medizin) als dieälteste Wissenschaft angesehen. Der Name Mathematik entstammt der griechischen Spracheund hat eine sehr universelle Bedeutung, die weit über das hinausgeht, was heutzutageunter Mathematik verstanden wird. Das griechische Wort ανθάνω beinhaltet so viel wieLernen, Erkennen vor allem durch Beobachtung und Nachdenken. Daraus leitet sich derBegriff αθηατικ τεχνή ab, was der Kunst des Lernens bzw. Erkennens (d.h. wie manErkenntnisse gewinnt) entspricht.Als die Mathematik in Griechenland im Entstehen war, gab es weder etablierte Wis-senschaften noch Universitäten als Orte des Lernens, wie in unserer Zeit. Wissen und

Erkenntnisse mussten erst einmal zu einem ansehnlichen Lehrgebäude aufgetürmt werden.Das Lernen bestand in jenen Tagen im wesentlichen aus dem, was man durch eigene Er-fahrung, Beobachtung und gedankliche Reflexion herausfinden konnte. Es war kein relativpassiver Wissenskonsum wie heute, wo vielfach das Auswendiglernen gewisser Fakten imVordergrund steht, sondern es war eine Aktivität, ein Studium im Sinne einer Untersuchungoder Analyse.Während andere Völker wie die Babylonier und Ägypter es zwar bei einer beachtlichenaber im wesentlichen doch rein praktisch orientierten Rechenkunst beließen, waren esdie Griechen, die als erste danach gesucht haben, mathematische Zusammenhänge undGesetzmäßigkeiten (vor allem aus der Geometrie) jenseits von Beispielen in allgemeingültigerWeise zu begründen. Daraus ist die Beweiskultur der Mathematik enstanden, die Präzisiondes Denkens, die nicht nur innerhalb der Mathematik von Nöten und von hohem Nutzemist. Ebenso waren es auch die Griechen, die gemerkt haben, daß man nicht umhin kommt,bestimmte Aussagen nicht mehr weiter zu hinterfragen. Diese sind klar und deutlichzu benennen, um darauf aufbauend mit umso strengerer logischer Argumentation neueAussagen herzuleiten.Trotz ihrer inzwischen f ̈ur eine einzelne Person kaum zu überschauende Auff ̈acherung, ver-sucht man die Mathematik oft eng abzugrenzen. Dennoch sind mathematische Methodenund darauf beruhende Maschinen seit Jahrzehnten schon die Grundlage f ̈ur den Erkennt-nisgewinn in allen Wissenschaften, die jenseits von Spekulation und Meinungsäußerungstehen. Somit ist die Mathematik der ursprünglichen Bedeutung ihres Namens bis heutetreu geblieben.Neben dem vordergründigen Lehrstoff hoffen wir, daß es uns gelingt, in der Vorlesungimmer wieder die folgenden Aspekte mitschwingen zu lassen:

• Mathematik Lernen ist kein stumpfes Pauken sondern erfordert eine intensive, kriti-sche Auseinandersetzung mit gewissen Fragestellungen.

• Genau darin liegt der Reiz, denn es macht Spaß, Zusammenhänge zu verstehen.

5


6/227

KAPITEL 1. EINLEITUNG 1.2. WAS IST INFORMATIK?

• Mathematik ist nützlich, man kann damit tolle Dinge machen insbesondere auch mitBlick auf die Informatik.

• Mathematik ist das paradigmatische Warum-Fach , in dem man beispielhaft lernt

Dinge zu hinterfragen und zu begründen. Deshalb hilft Mathematik mittel- undunmittelbar, sich andere Fächer besser zu erschließen.

Aber nicht nur die Griechen prägten die Grundzüge der modernen Mathematik. In Persienschrieb ein Mathematiker aus Bagdad um das Jahr 820 ein Meisterwerk mit dem Titel

“Kita-b al-muchtasar fi hisab al-dschabr wa-l-muqabala”. Das Wort al-dschabr im Titelwurde später ins lateinische als Algebra übersetzt. Der Name des Authors war Abu Dscha’farMuhammad ibn Musa al-Chwarizmi. Sein Nachname al-Chwarizmi ist der Ursprung desBegriffes Algorithmus . Ein Algorithmus ist eine Aneinanderreihung von Anweisungen, umbereits vorliegende Eingabeinformationen umzuwandeln in Ausgabeformationen.Als Informatiker wendet man Algorithmen an, indem man sie programmiert. Ein Computer

kann das so entstehende Programm ausf ̈uhren, um Menschen die Arbeit zu erleichtern.

1.2. Was ist Informatik?

Informatik kann als modernes Teilgebiet der Mathematik verstanden werden: Sehr grobzusammengefasst ist das Ziel der Informatik als Wissenschaft, Algorithmen zu entwerfen,

auf ihre Eigenschaften (wie Genauigkeit, Komplexität, usw.) zu untersuchen, Computer(weiter-)zuentwickeln die man mit Algorithmen f ̈uttern kann, die Algorithmen möglichstgeschickt in Programmen zu implementieren, diese Programme gründlich zu testen und siebezüglich ihrer Eigenschaften wie z.B. Geschwindigkeit oder Bedienbarkeit zu optimieren.

1.3. Woher kommt die Informatik?

Entstanden ist die Informatik zu keinem bestimmten Zeitpunkt, denn sie hat sich nach undnach aus verschiedenen anderen Wissenschaftlichen Disziplinen herauskristallisiert. Diewichtigste Disziplin war wie gesagt die Mathematik - dicht gefolgt von den Ingenieuren, diedurch Anwendung der zugrundeliegenden mathematischen Prinzipien die ersten Computerentwickelt haben. Man kann leicht streiten, welche Mathematiker gleichzeitig auch zuden wichtigsten Informatikern gehören. Einer der bedeutensten Preise der Informatik inDeutschland ist der Leibniz-Preis. Er wurde nach Gottfried Wilhelm Leibniz benannt,

wahrscheinlich weil dieser lange vor jedem Computer um 1700 das Binärsystem entwickelt

hat. Dieses System arbeitet ausschließlich mit zwei Werten (z.B. 0 und 1). Darauf basierendentwickelte eine Weile später (1854) George Boole die Boolesche Algebra. Jedes digitaleGerät auf dieser Welt benutzt diese Methode um Informationen (Daten) und Algorithmen(Programme) elektronisch zu repräsentieren. Deshalb werden wir diese Algebra etwasausf ̈uhrlicher besprechen und parallel dazu auch gleich im Programmierkurs den Datentypbool kennen lernen.Diese Entwicklung f ̈uhrte schon damals zum Wunsch, Algorithmen völlig automatischvon Maschinen ausf ̈uhren zu lassen. So stammt z.B. der Begriff etwas zu t ̈ urken nichtvon vermeintlich betrügerischen Personen türkischer Herkunft, sondern von einem sehrbekannten Betrug des ungarischen Erfinders Wolfgang von Kempelen. Dieser war zwarweder Mathematiker noch Informatiker (er studierte Jura und Philosophie), aber er erfand

den sogenannten mechanischen Türken. Der mechanische Türke war ein Schachcomputer,

6


7/227

KAP ITEL 1 . EI NLEI TUN G 1 .4. WARUM MU SS I CH ALS I NFORMAT IKER MAT HEMAT IK LERNEN ?

der offenbar vollautomatisch so gut spielte, dass er die meisten Menschen besiegen konnte.Erst etwa 50 Jahre später stellte sich heraus, dass sich in der Maschine versteckt ein echterMensch befand, der meistens ziemlich schacherfahren war.Einer der wichtisten Mathematiker f

¨ur die Informatik war Alan Mathison Turing (1912-

1954). Turing hat viele bedeutende Beiträge f ̈ur die Mathematik, die Informatik und sogardie theoretische Biologie geleistet. Dass er 1953 eines der ersten wirklichen Schachprogrammeentwickelte, war vielleicht der unwichtigste davon. Er definierte den Turingtest, der festlegt,unter welchen Kriterien man von einer echten künstlichen Intelligenz sprechen kann.Im letzten Weltkrieg entzifferte er mit seinen Kollegen auch Nachrichten der deutschenVerschlüsselungsmaschine Enigma. Der Turingpreis trägt seinem Namen ehre, denn es istso etwas wie der

”Nobel-Preis“ der Informatik. Mit seiner Turingmaschine legte er eine

wesentliche Grundlage der theoretischen Informatik. Sie ist der Stoff jeder Grundvorlesungzu diesem Thema.Claude Elwood Shannon sollte in dieser Liste ebenfalls genannt werden. Er war ebenfalls

Mathematiker; aber er studierte ebenfalls Elektrotechnik und war dadurch ein wichtigesBindeglied zur Entwicklung von elektrischen Maschinen, die mathematische Algorithmenausf ̈uhren können. In seiner theoretischen Arbeit begründete er die Informationstheorieund formulierte den fundamentalen Satz von Nyquist-Shannon (Abtasttheorem). AlsElektrotechniker wandte er 1937 als erster die Boolesche Algebra in seiner Masterarbeit an,indem er sie in elektronischen Schaltern (Relais) realisierte.In dieser Zeit beschäftigte sich bereits eine Vielzahl von Ingenieuren (wie neben Shannonz.B. auch George Stiblitz, John Atanasoff und Clifford Berry) mit der Entwicklung vonautomatischen Rechenmaschinen. John von Neumann (1903-1957, ebenfalls Mathematiker)setzte sich stark f ̈ur deren Entwicklung ein und die nach ihm benannte von NeumannRechnerarchitektur ist nach wie vor aktuell. 1941 stellte schließlich Konrad Zuse den

weltweit ersten universell programmierbaren binären Digitalrechner namens Zuse Z3 vorund begründete damit endgütltig das Informationszeitalter.

1.4. Warum muss ich als Informatiker Mathematik lernen?

Mathematiker wie Leibniz, Boole, Turing und Shannon haben Wissen dokumentiert,das nach wie vor absolut unabdinglich ist, wenn man heute in irgendeinem Teilgebietder Informatik arbeiten möchte. Als Informatiker möchte man Algorithmen verstehen,anwenden und evtl. auch selbst entwickeln. Um diese mathematischen Modelle zu verstehen,muss man einerseits lernen, wie ein Mathematiker denkt und arbeitet; andererseits benötigtman Wissen über die wichtigsten Grundlagen der Mathematik: lineare Algebra, Analysis

und - je nach späterer Spezialisierung - auch Statistik und Numerik. Dies ist die ersteVorlesung zu diesem Thema.

1.5. Ziele der Vorlesung Mathematik f ̈ur Informatiker

Informatiker haben eine besondere Sicht auf die Mathematik. Einerseits ist sie “nur” einWerkzeug; andererseits können neue Algorithmen oft nur entworfen werden, wenn mansich sehr genau in der Mathematik auskennt. Da die Informatik aus so vielen und teilweisestark unterschiedlichen Teildisziplinen besteht, ist es schwierig eine Vorlesung zu halten,die allen gerecht wird. Wir wollen deshalb zwei unserer Meinung nach besonders wichtigeAspekte betonen:

7


8/227

KAPITEL 1. EINLEITUNG 1.5. ZIELE DER VORLESUNG MATHEMATIK FÜR INFORMATIKER

Mathematisches Denken Wenn man neue Algorithmen entwirft oder auch nur existie-rende programmiert, muss man sich jedes Detail bewusst machen und verstehen. Ohnediese Herangehensweise schleichen sich schnell Fehler in die Software ein (Bugs), die in derGeschichte (wie zum Beispiel in der Raumfahrt) bereits mehrfach zum Tod der Anwenderder Software gef ̈uhrt hat. Die Mathematik ist besonders stark strukturiert und pflegt einestrenge Vorgehensweise. Eine besondere Rolle haben hier Axiome, Definitionen, Sätze(zentrale mathematische Aussagen) und deren Beweise. Diese Struktur findet man auch(vereinfacht betrachtet) beim Programmieren wieder: Variablen und Funktionen müssendeklariert und definiert werden; Sätze fassen logische Schlussfolgerungen zusammen, wasim Falle eines konstruktiven Beweises auch einem Algorithmus entspricht.Logische Programmiersprachen wie Prolog werden sogar zur automatischen Beweisf ̈uhrungeingesetzt und funktionale Sprachen wie Haskell basierend fast ausschließlich auf derAnwendung von mathematischen Funktionsdefinitionen. Deshalb ist es enorm wichtig, jedes Problem (jede Aufgabe) aus der Informatik zunächst genau zu definieren: wassind die Eingaben, wie sollen Ausgaben aussehen? Wie funktioniert ganz konkret jedereinzelner Schritt des Algorithmus? Um sich so präzise ausdrücken zu können, wie einComputer es erwartet, sollte man sich eine mathematische Denkweise aneignen. Einwichtiger Unterschied zur Mathematik ist jedoch, dass Mathematiker in der Regel versuchen,ein Problem so abstrakt wie möglich zu formulieren, um alle betrachtetenden Fälle mit demgleichen theoretischen Unterbau betrachten zu können. Das reduziert die Schreibarbeit,und verbindet zuvor scheinbar völlig unterschiedliche Gebiete. Wer hätte z.B. gedacht dassdie Primzahlzerlegung viel mit der Zerlegung eines Polynoms in seine irreduziblen Faktorenzu tun hat?Informatiker können es sich jedoch nicht leisten, ein Programm auf die abstraktest möglicheWeise zu implementieren, weil eine abstrakte Formulierung des Problem oft Geschwindig-

keitseinbußen bringt, den Code aufgrund der Komplexität schlecht wartbar macht und denAnwender womöglich überfordert.Deshalb ist es f ̈ur Informatiker wichtig, den richtigen Abstraktionsgrad f ̈ur das gegebeneProblem zu finden. Wir werden uns deshalb in dieser Vorlesung besonders darum bemühen,einen Grad zu finden, der einerseits so abstrakt wie möglich ist, um viele Anwendungen zuermöglichen, aber andererseits so konkret wie möglich ist, um den Stoff verständlich undübersichtlich zu gestalten.

Gründliche Motivationen Auch wenn während der Vorlesung selbst nicht immer genugZeit sein wird, um genau zu motivieren, was wir gerade erklären, welche Ziele wir damiterreichen und welche Anwendungen in der Informatik zu jedem Einzelthema vorhanden

sind, wollen wir doch in den Übungen und hier im Skript darauf eingehen, warum der Stoff f ̈ur einen Informatiker so wichtig und auch interessant ist.

Dabei wollen wir einerseits illustrieren, welche Industrien oder auch konkrete Firmen sichbesonderns der erklärten Konzepte und Methoden bedienen. Andererseits wollen wir auchimmer wieder betonen, in welchen späteren Fächern des Studiums in Heidelberg der Stoff als Grundlage benötigt wird.Diese Herangehensweise soll auch dabei helfen zu entscheiden, ob man als Informatikerlieber einen theoretischen, technischen oder praktischen Weg wählen möchte. Ist völlig klar,dass die Karriere in die theoretische Richtung, also die Entwicklung von neuen Algorithmengehen soll (und damit in Forschung oder in die Anwendungen im wissenschaftlichen Rechnenwie Maschinenlernen, Optimierung und zahlreichen Ingineursdisziplinen), empfehlen wir

besonders die Vorlesungen in der reinen Mathematik, wo die vollständige Abstraktion einen

8


9/227

KAPITEL 1. EINLEITUNG 1.6. EINIGE ERMUNTERNDE WORTE FÜR MATHE-ANFÄNGER

höheren Stellenwert hat.

1.6. Einige ermunternde Worte f ̈ur Mathe-Anf ̈anger

Schulmathematik unterscheidet sich stark von Unimathematik. Während man in der Schulemeistens ganz viel rechnet, haben an der Uni Beweise eine große Bedeutung. Da Beweise inder Schule gerne mal als besonders schwer oder fortgeschritten dargestellt werden, erzeugtdas immer wieder Angst und Unsicherheit und die Frage: “Kann ich das?”Der zuvor erwähnte John von Neumann soll einmal gesagt haben: “Mathematik kann mannicht lernen, man muss sich daran gewöhnen.” Damit meint er wahrscheinlich, dass dieDenkweise nur erlernt werden kann, indem man immer wieder Definitionen versteht undSätze beweist - bis man sich daran gewöhnt hat. Es gibt angeblich sogar Forschungsergeb-nisse die gezeigt haben, dass sich die Struktur des Gehirns durch praktizierte Mathemtikdeutlich verändert! Das zu hören hätte Herrn Neumann mit Sicherheit gefreut.

Es ist hilfreich f ̈ur die Beschäftigung mit dieser Vorlesung sie nicht als Fortsetzung desSchulunterrichts, sondern als etwas Neues zu betrachten. Und wie bei einer neuer Sportartoder einem neuen Musikinstrument kann es einiges an Zeit und Arbeit in Anspruch nehmenbis man die Grundlagen verstanden hat und sicher beherrscht. Das ist völlig normal undauch ihr werdet euch irgendwann wundern warum euch einiges am Anfang so schwergefallen ist.Wir haben immer wieder festgestellt, dass starke Gef ̈uhle wie Frust das Erlernen derMathematik sehr erschweren können. Gerade wurde noch vom Dozenten verkündet, dassder Stoff doch “trivial” sei und der schlaue Student von nebenan pflichtet dem auch nocheifrig bei. Zu Hause sitzt man dann vor einer Aufgabe, versteht scheinbar gar nichts undist abwechselnd wütend und frustriert und fragt sich, ob der Dozent zu schlecht erklärt

oder ob man einfach nicht f ̈ahig ist diesen Kram zu verstehen.Das Wichtigste in solchen Momenten ist es, einerseits irgendwie entspannt zu bleiben,und trotzdem in der Lage zu sein, mit den Zähnen zu knirschen und den Stoff so langedurchzukauen, bis man ihn verdaut hat. Wichtig ist sich zu erinnern, dass fast jederInformatiker auf der Welt einmal eine ähnliche Vorlesung wie diese gehört und die Klausurbestanden hat! Deshalb ein paar Tipps:

• Jeder hat sein eigenes Tempo. Langsam im Verstehen zu sein bedeutet nicht, es garnicht zu können. Hat also der Nachbar bereits alles verstanden: ruhig bleiben undweitermachen. Viele Wiederholungen des gleichen Denkprozesses helfen tatsächlichnicht nur beim Auswendiglernen, sondern auch beim Nachvollziehen von logischen

Schlussfolgerungen.

• Jeder muss f ̈ur sich selbst herausfinden, wie er am besten lernt. Es kann helfendie Aufzeichnungen, das Skript oder ein Buch mehrfach zu lesen oder aber es istbesser den Stoff abzuschreiben und zusammenzufassen. Oft hilft es unklare Gedankeneinfach auszusprechen um sie besser im Kopf sortieren zu können. Das geht natürlicham besten mit anderen Studenten aus der Vorlesung, aber manchmal funktioniert esauch, wenn ihr einfach eurem Mitbewohner sagt, was euch gerade durch den Kopf geht.

• Es hilft sehr, das Gelernte gemeinsam zu diskutieren und auswendig zu lernen. Ameinfachsten geht das fast immer in kleinen Gruppen von zwei oder höchstens drei

9


10/227

KAPITEL 1. EINLEITUNG 1.6. EINIGE ERMUNTERNDE WORTE FÜR MATHE-ANFÄNGER

Leuten. Erklärt euch gegenseitig den Stoff, ihr werdet merken dass beide Seiten davonprofitieren.

• Beweise sind keine Zauberei. In den meisten Fällen - und insbesondere bei den

hier behandelten - bedeutet Beweisen lediglich das Einsätzen von zuvor behandelteDefinitionen. Die beste Herangehensweise könnte also tatsächlich sein, Sätze undDefinitionen gründlich auswendig zu lernen! Das kann jeder (mit unterschiedlichemZeitaufwand) und es erleichtert das Jonglieren mit den gelernten Begriffen späterenorm.

• Das Verstehen von Definitionen ist mal manchmal gar nicht so einfach. Hier hilftein Denken, das f ̈ur Informatiker typisch ist: man versuche, sich möglichst vieleFälle oder Situationen vorzustellen, bei denen die Definition erf ̈ullt ist, und ganzbesonders wann sie nicht erf ̈ullt ist. So finden Hacker zum Beispiel Sicherheitslücken.Das ist ein kreativer Prozess, der gemeinsam viel Spaß machen kann. Manchmal

kann man sich auch als Abkürzung eine vereinfachte, intuitiv anschauliche Versionder Definition ausdenken. Wichtig ist nur, dass man beim späteren Anwenden derDefinition sich dann immer wieder daran erinnert, dass man im Kopf vielleicht geradenur die vereinfachte Arbeitsversion hat!

• In vielen mathematische Beweisen werden Aussagen in gleichbedeutende Aussagenumformuliert. Daf ̈ur ist es hilfreich Formeln umzuschreiben um besser zu sehenwelche Aussage aus ihnen folgen. Nur ist es am Anfang nicht unbedingt klar, wieman etwas geschickt umschreiben kann. Da hilft oft nur ausprobieren und die Tricks

zu verwenden, die mal jemand herausgefunden hat. Hier zwei einfache Beispiele, wieman durch geschicktes Umschreiben etwas schneller ausrechnen kann:

1. Wir wollen 27 · 33 ausrechnen. Daf ̈ur schreiben wir 27 · 33 = (30 − 3) · (30 + 3)und verwenden jetzt die 3. binomische Formel und erhalten 30 · 30 − 3 · 3 =900 − 9 = 891.

2. Um die Summe der ersten 100 Zahlen zu berechnen, hat schon der junge Gaussfestgestellt, dass es einfacher ist, wenn man die Zahlen umsortiert. So ergibt1 + 100 = 2 + 99 = 3 + 98 = · · · = 101, da wir genau 50 solcher Summen haben,ist 1 + 2 + 3 + · · · + 98 + 99 + 100 = 50 · 101 = 5050.

• Mathematik kann man in den meisten Fällen nicht nur “mal so grob” verstehen.Wie in der Informatik muss man jedes Detail verstehen, um eine Chance zu haben,das gesamte System zu verstehen. Taucht also ein Beweis auf und man kommt an

einem Schritt an, den man einfach nicht versteht, hilft es selten bis nie, diesenSchritt einfach “in den Skat zu drücken” und zu überspringen. Der Rest des Beweiseswird wahrscheinlich auch nur noch wenig Sinn ergeben. Hier sind Geduld, Disziplinund Ausdauer gefragt! Es hilft sehr, anderen sein Problem zu erklären und ganz

konkrete Fragen zu formulieren und nochmal die vorher besprochenen Definitionennachzuschlagen. Es ist aber auch nicht falsch, den Schritt beim ersten Durchgang zuüberspringen, damit man ein Gef ̈uhl daf ̈ur bekommt, was man noch vor sich hat.

10


11/227

Teil I.

Grundlagen

11


12/227

2. Grundlagen der mathematischen Logik

Wie in vielen anderen Wissenschaften so ist man auch in der Mathematik ständig mitSätzen in der Form von Behauptungen und Vermutungen konfrontiert, deren Wahrheitsge-halt festzustellen ist. Im Unterschied zu experimentellen, empirischen oder investigativen

Wissenschaften erfolgt die Überprüfung in der Mathematik meist anhand einer Argumen-tationskette, die entweder die Gültigkeit der fraglichen Aussage belegt (beweist, verifiziert)oder widerlegt (falsifiziert). Eine solche Argumentationskette wird als Beweis bezeichnet,wenn sie streng nach den Regeln der formalen Logik durchgef ̈uhrt wird und sich nur auf bereits gesicherte Aussagen stützt.Aus diesem Grunde ist es geboten, sich mit den Regeln der Logik vertraut zu machen,bevor man sich ernsthaft mit Mathematik beschäftigen kann. Die formale Logik ist jedochkeineswegs nur ein mehr oder weniger lästiges, aber unentbehrliches Vorgeplänkel sondernbereits selbst eine mathematische Disziplin mit dem Teilgebiet der Schaltalgebra als einerwesentlichen theoretischen Grundlage f ̈ur die Funktionsprinzipien von Computern.

2.1. Aussagen und Quantoren

Definition 2.1.1 Eine Aussage ist ein Satz von dem man eindeutig entscheiden kann,

ob er wahr oder falsch ist.Einer wahren Aussage wird der Wahrheitswert “wahr” = w = “true”= 1 zugeordnet,einer falschen Aussage wird der Wahrheitswert “falsch”= f = “false”= 0 zugeordnet.

In der gesprochenen und geschriebenen Sprache gibt es Sätze, die keine Aussagen sind; dazugehören vor allem Fragen, Meinungsäußerungen, Befehle, Aufforderungen, Wünsche undKlageausrufe. Darüberhinaus gibt es aber auch aussageähnliche Sätze, denen aus verschie-denen Gründen nicht in eindeutiger oder sinnvoller Weise einer der beiden Wahrheitswertezugeordent werden kann.Das Zweiwertigkeitsprinzip, dh. die Beschränkung auf das, was sich in sinnvoller und eindeu-tiger Weise als wahr oder falsch qualifizieren lässt, bzw. das Prinzip vom ausgeschlossenen

Dritten stellt daher eine erheblich vereinfachende bzw. einschränkende Reduktion derRealität dar, die aber erstaunlicherweise f ̈ur fast die gesamte Mathematik und viele andereWissenschaften völlig ausreichend ist.

Beispiel 2.1.2 Handelt es sich bei den folgenden Sätzen um Aussagen?

1. Heidelberg ist die Hauptstadt von Deutschland.

2. 1 + 5 = 6

3. Guten Morgen!

4. Heute ist Dienstag.

12


13/227

KAP ITEL 2 . G RUN DLAG EN DER MATH EMAT ISC HEN LOG IK 2 .1. AU SS AG EN U ND QU AN TO REN

Antwort:

1. ja, dies ist eine falsche Aussage

2. ja, dies ist eine wahre Aussage

3. nein, dies ist eine Begrüßungsformel, die zwar korrekt oder inkorrekt verwendetwerden kann, aber man kann ihr keinen Wahrheitswert zuordnen.

4. Wenn klar ist, was heute f ̈ur ein Wochentag ist, dann ist es eine Aussage. Sonst istdieser Satz eine Aussageform.

Bemerkung 2.1.3 Trotz ihrer enormen Leistungsf ̈ahigkeit kann man mit der zwei-wertigen Logik schnell an Grenzen stoßen. Ein Beispiel daf ̈ur stellen die sogenanntenAntinomien dar. Darunter versteht man Sätze, die durch eine raffinierte Rückbezüglichkeitwidersinnig sind. Hier zur Illustration zwei Klassiker:

(i) In der Stadt schneidet der Barbier jedem Mann den Bart, der sich ihn nicht selbstschneidet.

(ii) Ein Kreter sagt: Alle Kreter sind Lügner.

Im ersten Fall läßt sich nicht entscheiden, ob der Barbier sich selbst rasiert oder nicht.Denn wenn er zu den Männern zählt, die sich nicht selbst den Bart stutzen, dann müßteer die Dienste des Barbiers in Anspruch nehmen, sich also doch selbst den Bart schneiden.

Startet man jedoch mit der Annahme, daß sich der Barbier den Bart selbst schneidet, soergibt sich kein Widerspruch.Ebensowenig läßt sich im zweiten Fall entscheiden, ob nun alle Kreter Lügner sind odernicht. Denn wenn tatsächlich alle Kreter Lügner wären, dann auch derjenige, welchergenau dieses behauptet. Da dieser Kreter dann die Unwahrheit spräche, ist die Aussagegelogen ergo falsch, d.h. es gäbe auch ehrliche Kreter. Auch gilt, daß sich aus derumgekehrten Annahme (nicht alle Kreter sind Lügner) kein Widerspruch entwickelt.

Bemerkung 2.1.4 Es sei noch angemerkt, daß der österreichische Logiker Kurt Gödel

(1906-1978) mit seinem Unvollst ̈ andigkeitssatz bewiesen hat, daß praktisch in jeder Theo-rie Behauptungen bzw. Sätze formuliert werden können, die prinzipiell nicht beweisbarbzw. entscheidbar sind.

Definition 2.1.5 Ersetzt man in einer Aussage a eine Konstante durch eine Variable x,so entsteht eine Aussageform a(x).Für einen festgewählte Wert von x kann der Wahrheitswert von a(x) bestimmt werden.

13


14/227

KAP ITEL 2 . G RUN DLAG EN DER MATH EMAT ISC HEN LOG IK 2 .1. AU SS AG EN U ND QU AN TO REN

Beispiel 2.1.6 a(x) : x > 50 ist eine Aussageform mit der Variablen x. Setzen wir f ̈urx Zahlen ein, so erhalten wir Aussagen, z. B.a(100) : 100 > 50 ist eine wahre Aussage und

a(10) : 10 > 50 ist eine falsche Aussage.

Mithilfe von sogenannten Quantoren, können wir aus einer Aussageform wieder eine Aussagemachen.

Definition 2.1.7 Sei a(x) eine Aussageform.

• Die Aussage “Für alle x (aus einer vorgegebenen Menge) gilt a(x)” ist genaudann wahr, wenn a(x) f ̈ur alle in Frage kommenden x wahr ist. Dies ist eineALL-Aussage und wir schreiben abkürzend

∀x : a(x).

∀ ist der Allquantor und wird “f ̈ur alle” gelesen.• Die Aussage “Es gibt ein x (aus einer vorgegebenen Menge) so dass a(x)” ist genau

dann wahr, wenn a(x) f ̈ur mindestens ein in Frage kommendes x wahr ist. Dies isteine EXISTENZ-Aussage und wir schreiben abkürzend

∃x : a(x).

∃ ist der Existenzquantor und wird “es gibt” oder “es existiert” gelesen.• Die Aussage “Es gibt genau ein x (aus einer vorgegebenen Menge) so dass a(x)”

ist genau dann wahr, wenn a(x) f ̈ur genau ein in Frage kommendes x wahr ist. Wirschreiben abkürzend

∃!x : a(x).

Quantoren werden spielen in der Mathematik eine wichtige Rolle um Aussagen kurz undpräzise zu formulieren. Dabei ist zu beachten, dass die Reihenfolge der Quantoren eineRolle spielt.

Beispiel 2.1.8 • ∀x ∈ N : x + 1 > x ist eine wahre Aussage.• ∀x ∈ N : x2 = 25 ist eine falsche Aussage, da sie z. B. f ̈ur x = 1 nicht stimmt.• ∃x ∈ N : x2 = 25 ist eine wahre Aussage, da 52 = 25.• ∃x ∈ Z : x2 = 25 ist eine wahre Aussage, da 52 = 25.• ∃!x ∈ Z : x2 = 25 ist eine falsche Aussage, da 52 = 25 und (−5)2 = 25.

Für den Nachweis eine Allaussage ist also zu prüfen, ob sie f ̈ur alle in Frage kommenden x(das können unendlich viele sein) richtig ist. Für die Widerlegung einer Allaussage hingegengenügt ein Element x, f ̈ur das die Aussage a(x) falsch ist.

14


15/227

KAP ITEL 2 . G RUN DLAG EN DER MATH EMAT ISC HEN LOG IK 2 .2. V ERKNÜPFUNGEN VON AUSSAGEN

Für den Nachweis einer Existenzaussage genügt ein x f ̈ur das a(x) richtig ist. Zur Widerle-

gung einer Existenzaussage hingegen muss f ̈ur alle in Frage kommenden x geprüft werden,ob a(x) falsch ist.

2.2. Verknüpfungen von Aussagen

Das Anliegen der Aussagenlogik ist es, die Regeln des Argumentierens und Schlußfolgernsauf eine solide Basis zu stellen, ihnen eine Form zu geben, sie zu formalisieren. Da Ar-gumentationsstrukturen nicht an den Inhalt gebunden sondern allein durch die Logikvorgegeben sind, beschäftigt sich die Aussagenlogik mit Aussagen von einem rein formalenStandpunkt aus, der sowohl den sprachlichen Aufbau (Syntax) einer Aussage als auch ihreinhaltliche Bedeutung (Semantik) außer Acht läßt. Eine Aussage ist dann nichts anderesals der Träger eines Wahrheitswertes. Daher identifizieren wir Aussagen mit sogenannten

logischen Variablen , welche wir etwas mißverständlich auch Aussagevariablen1 nennen,

obwohl sie weniger f ̈ur Aussagen selbst als vielmehr f ̈ur ihre Wahrheitswerte stehen. EineAussagenvariable a ist also nicht Element der Menge aller Aussagen sondern es gilt lediglicha ∈ {wahr, falsch} ≡ {0, 1}. Gegenstand der Aussagenlogik ist zunächst die Beantwortungder beiden folgenden, eng zusammenhängenden Fragen:

• Wie lassen sich aus gegebenen (Elementar)Aussagen a ,b ,c , . . . neue Aussagen gewin-nen, d.h. welche Verknüpfungsmöglichkeiten gibt es überhaupt?

• Wie hängt der Wahrheitswert der zusammengesetzten Aussage von den Wahrheits-werten der Elementaraussagen ab?

Die verschiedenen Verknüpfungsmöglichkeiten von Aussagen, welche wir weiter unten

behandeln, werden auf der Ebene der Aussagevariablen durch Verknüpfungszeichen oderJunktoren bzw. logische Operatoren angedeutet.

Definition 2.2.1 • Eine Aussagevariable ist eine Variable a die nur die Werte 0oder 1 annehmen kann.

• Ein logischer Ausdruck (eine aussagenlogische Formel) ist eine Aneinanderrei-hung von Aussagevariablen und Junktoren.

• Enthält ein logischer Ausdruck n verschiedene Aussagevariablen, dann definiert ereinen Funktion (Logikfunktion) von {0, 1}n → {0, 1}, diese wird auch als n-stelligeVerknüpfung bezeichnet.

1 Korrekter wäre es von Wahrheitswertvariablen zu sprechen, denn die Variablen übernehmen nur denWahrheitswert nicht aber den Inhalt einer Aussage. So ist im Sinne der Aussagenlogik die Zuweisung

a = Alle Fische können fliegen.

gleichbedeutend mit a = 0, da die Aussage “Alle Fische können fliegen” bekanntermaßen falsch ist. Man

kann den Satz als eine etwas längliche, alternative Bezeichnungsweise f ̈ur falsch betrachten. Alternative

Schreibweise: a wirklich als Platzhalter f ¨ur Aussage betrachten und nicht a = 0 sondern w(a) = 0

schreiben.

15


16/227


2.2.1. Die Negation

Betrachten wir zunächst eine einzelne Aussage a. Da a nichts weiter ist als eine Variablemit dem Wahrheitswert 0 oder 1, gibt es nur eine Möglichkeit, aus a “etwas Neues” zu

schaffen, nämlich den Wert von a zu invertieren bzw. zu negieren.

Definition 2.2.2 Die Verneinung (Negation) einer Aussage a ist genau dann wahr,wenn a falsch ist. Wir schreiben ¬a f ̈ur die Verneinung von a und lesen “nicht a” oder

“es trifft nicht zu, dass a”.Dies kann mithilfe einer Wahrheitstabelle ausgedrückt werden:

a ¬a0 1

1 0

Beispiel 2.2.3 Wir betrachten folgende Aussagen:

1. Der Tank ist voll.

2. 1 + 3 = 6

3. 7 < 10

und ihre Verneinung:

1. Der Tank ist nicht voll.

2. 1 + 3 = 63. 7 ≥ 10

Wie man leicht der Defintion des Negationsoperators ¬ entnimmt, liefert die doppelte Verneinung die ursprüngliche Aussage zurück. Es gilt also

¬(¬a) = a .

Man kann

¬ als eine spezielle logische Funktion auf der Menge der möglichen Wahrheits-

werte, d.h. auf der Menge {0, 1}, auffassen. Wieviele verschiedene logische Funktionen gibtes eigentlich auf {0, 1}? Eine kurze Überlegung zeigt, daß genau vier Funktionen existieren,die in der Tabelle

A ¬1 ¬2 ¬3 ¬40 0 0 1 1

1 0 1 0 1

dargestellt sind. Neben der Negation ¬3 = ¬ gibt es nur noch die “langweilige” Identität¬2 und die beiden konstanten Funktionen ¬1 und ¬4.

Neben der Aussagenlogik, benötigen wir in der Mathematik auch die Prädikatenlogik,die eine Erweiterung der Aussagenlogik darstellt. Um Aussagen in der Prädikatenlogikformulieren zu können, benötigen wir den Existenz- und den Allquantor.

16


17/227


Für die Verneinung von Existenz- und Allaussagen müssen wir besonders aufpassen, da siein der Umgangssprache nicht immer formal korrekt verwendet werden.

Satz 2.2.4 Durch die Verneinung einer All-Aussage entsteht eine Existenz-Aussage undumgekehrt. Es gilt:

¬∀x : a(x) = ∃x : ¬a(x)¬∃x : a(x) = ∀x : ¬a(x)

Beispiel 2.2.5 Wir betrachten folgende Aussagen

1. Alle Menschen mögen Mathe,

2. ∀x : x > 0,3. ∃x : x2 + 1 = 0.

und ihre Verneinungen

1. Es gibt einen Menschen, der nicht Mathe mag,

2. ∃x : x ≤ 0,3. ∀x : x2 + 1 = 0.

2.2.2. Zweiwertige Verknüpfungen

Im nächsten Schritt wollen wir zwei von einander unabhängige Aussagen zu einer Neuenverknüpfen und deren Wahrheitswert bestimmen. Auf diese Weise erhalten wir zweiwertige(binäre) Verknüpfungen. Insgesamt gibt es davon 16:

A B ∗1 ∗2 ∗3 ∗4 ∗5 ∗6 ∗7 ∗8 ∗9 ∗10 ∗11 ∗12 ∗13 ∗14 ∗15 ∗161 1 0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1

1 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0 0

0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 0 10 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0

Die sechzehn logischen Verknüpfungen sind nicht unabhängig voneinander. Ist eine dersechzehn logischen Verknüpfungen, dann definiert ¬(AB) eine andere logische Verknüpfung,welche sich ebenfalls unter den sechzehn befinden muß. Auf diese Weise sieht man, daßnicht wirklich sechzehn Verknüpfungen zu unterscheiden sind sondern lediglich nur acht,weil sich die restlichen acht dann als Verneinung ergeben. So gilt f ̈ur alle k ∈ {1, ..., 8}

A ∗8+k B = ¬(A ∗8 B) .

Wir wollen hier den wichtigsten zweiwertigen Verknüpfungen einen Namen geben.

17


18/227


Definition 2.2.6 • Die UND-Verknüpfung (Konjuktion) zweier Aussagen a und bist eine Aussage, die genau dann wahr ist, wenn beide Aussagen wahr sind. Wirschreiben a

∧b und lesen “a und b”.

• Die ODER-Verknüpfung (Disjuktion) zweier Aussagen a und b ist eine Aussage, diegenau dann wahr ist, wenn mindestens eine der Aussagen wahr sind. Wir schreibena ∨ b und lesen “a oder b”.

• Das ausschließende Oder (eXclusive OR) zweier Aussagen a und b ist eine Aussage,die genau dann wahr ist, wenn entweder a oder b (aber nicht a und b) wahr ist.Wir schreiben a xor b und lesen “entweder a oder b”.

Die Wahrheitstabelle dieser Verknüpfungen ist die folgende:

a b a ∧ b a ∨ b a xor b1 1 1 1 0

1 0 0 1 10 1 0 1 1

0 0 0 0 0

In der Umgangssprache benutzen wir meistens das Wort “oder” im ausschließenden Sinn,während in der Mathematik häufiger das einschließende oder ∨ verwendet wird.

Definition 2.2.7 Die WENN-DANN-Verknüpfung (Subjunktion) a −→ b, die “wenna, dann b” gelesen wird, und die GENAU-DANN-WENN-Verknüpfung (Bijunktion)a

←→ b, die “a genau dann, wenn b” gelesen wird, von zwei Aussagen sind durch

folgende Wahrheitstabellen definiert:

a b a −→ b a ←→ b1 1 1 11 0 0 00 1 1 00 0 1 1

Definition 2.2.8 • Ist die verknüpfte Aussage a → b wahr, so spricht man voneinem logischen Schluß (Implikation) und schreibt

a ⇒ b.

Wir sagen dann “aus a folgt b”, “a impliziert b”, “wenn a, dann b”, “a ist hinreichendf ̈ur b” oder b ist notwendig f ̈ur a.

• Wenn die verknüpfte Aussage a ←→ b wahr ist, dann spricht man von Äquivalenzund schreibt

a ⇔ b.

Mithilfe der Äquivalenz lassen sich die Rechenregeln f ̈ur andere Verknüpfungen formulieren.

18


19/227


Satz 2.2.9 Für die UND- sowie die ODER-Verknüpfung gelten das Kommutativgesetz

a ∧ b ⇔ b ∧ aa ∨ b ⇔ b ∨ a,

das Assoziativgesetz:

a ∧ (b ∧ c) ⇔ (a ∧ b) ∧ ca ∨ (b ∨ c) ⇔ (a ∨ b) ∨ c

und das Distributivgesetz:

a ∧ (b ∨ c) ⇔ (a ∧ b) ∨ (a ∧ c)a ∨ (b ∧ c) ⇔ (a ∨ b) ∧ (a ∨ c)

Beweis. Wir können den Wahrheitsgehalt dieser Aussagen mittels Wahrheitstabellenüberprüfen.Die GENAU-DANN-WENN-Verknüpfung zweier Aussagen ist genau dann wahr, wennentweder beide Aussagen wahr sind oder wenn beide Aussagen falsch sind. Somit m üssenwir prüfen, ob die Einträge in der Wahrheitstabelle f ̈ur den Ausdruck auf der rechten Seitedes Äquivalenzpfeils gleich der Tabelle f ̈ur den Ausdruck auf der linken Seite ist.Wir zeigen hier exemplarisch das erste Distributivgesetz:

a b c b ∨ c a ∧ (b ∨ c)1 1 1 1 11 1 0 1 11 0 1 1 11 0 0 0 00 1 1 1 00 1 0 1 00 0 1 1 00 0 0 0 0

a b c a ∧ b a ∧ c (a ∧ b) ∨ (a ∧ c)1 1 1 1 1 11 1 0 1 0 11 0 1 0 1 11 0 0 0 0 00 1 1 0 0 00 1 0 0 0 00 0 1 0 0 00 0 0 0 0 0

Konvention: Die Verneinung ¬ bindet stärker als ∧ und ∨. Das heißt, der Ausdruck ¬a∧bist gleichbedeutend mit (¬a) ∧ b und nicht mit ¬(a ∧ b).Einen Zusammenhang zwischen Verneinung und der UND und ODER- Verknüpfung lieferndie De Morganschen Gesetze.

Satz 2.2.10 Es gelten die de Morganschen Gesetze:

¬(a ∧ b) ⇔ ¬a ∨ ¬b¬(a ∨ b) ⇔ ¬a ∧ ¬b,

19


20/227

KAPITEL 2. GRUNDLAGEN DER MATHEMATISCHEN LOGIK 2.3. BEWEISARTEN

Beweis. Der Beweis funktioniert genauso wie der zu Satz 2.2.9. Wir zeigen hier die Wahr-heitstabellen zur zweiten Regel.

a b a

∨b

¬(a

∨b)

1 1 1 01 0 1 00 1 1 00 0 0 1

a b

¬a

¬b

¬a

∧ ¬b

1 1 0 0 01 0 0 1 00 1 1 0 00 0 1 1 1

Definition 2.2.11 Eine Tautologie ist ein logischer Ausdruck, der immer wahr ist. EineKontradiktion ist ein logischer Ausdruck, der immer falsch ist.

Beispiel 2.2.12 •

a∨ ¬

a ist eine Tautologie.

• Die Verwendung des Äquivalenzpfeils ⇔ in den letzten zwei Sätzen besagt geradedass die verknüpfte Aussage wahr ist, und daher ist zum Beispiel ¬(a ∧ b) ←→¬a ∨ ¬b eine Tautologie.

2.3. Beweisarten

Satz 2.3.1 Für zwei beliebige Aussagen a, b gilt:

a) (a −→ b) ←→ (¬b −→ ¬a) ist eine Tautologieb) (a −→ b) ←→ ¬(a ∧ ¬b) ist eine Tautologie

Beweis.

a b a −→ b0 0 11 0 00 1 1

1 1 1

a b ¬a ¬b ¬b −→ ¬a0 0 1 1 11 0 0 1 00 1 1 0 1

1 1 0 0 1

a b ¬b a ∧ ¬b ¬(a ∧ ¬b)0 0 1 0 11 0 1 1 00 1 0 0 1

1 1 0 0 1

Satz 2.3.2

(a −→ b) ∧ (b −→ a) ←→ (a ←→ b) ist eine Tautologie.• direkter Beweis a ⇒ b• indirekter Beweis ¬b ⇒ ¬a• Beweis durch Widerspruch: ¬b ∧ a ist eine Kontradiktion.

20


21/227

KAPITEL 2. GRUNDLAGEN DER MATHEMATISCHEN LOGIK 2.3. BEWEISARTEN

Beispiel 2.3.3 Seien x,y > 0 reelle Zahlen. Wir betrachten die Aussagen

a : x2 > y2 b : x > y

und wollen zeigen, dass aus Aussage a die Aussage b folgt.

Wir dürfen dabei folgende Rechenregeln verwenden, wobei x, y, z reelle Zahlen sind:

i) die Rechengesetze der Addition und Multiplikation in den reellen Zahlen

ii) Wenn z > 0 dann gilt: x < y ⇒ x · z < y · ziii) x < y ⇒ x + z < y + ziv) x < y und y < z impliziert x < z.

direkter Beweis

x2 > y2 iii)⇒ x2 − y2 > 0 i)⇒ (x − y)(x + y) > 0

ii)⇒ (x − y)(x + y) 1x + y

> 0 · 1x + y

i)⇒ x − y > 0iii)⇒ x > y

indirekter Beweis Zunächst müssen die Aussage a und b negiert werden

¬a : x2

≤ y2

¬b : x

≤ y

Nun gilt

x ≤ y ii)⇒ xx ≤ xy und xy ≤ yy iv)⇒ x2 ≤ y2

Beweis durch Widerspruch

21


22/227

3. Grundlagen der Mengenlehre

In diesem Kapitel ist das Ziel zu lernen, mit Mengen zu jonglieren und auch komplizierteMengen formal und kompakt aufzuschreiben. Die Symbole, die wir daf ̈ur verwenden, kannman fast wie eine Programmiersprache verstehen. Ganz genau wie bei Programmiersprachenmuss man diese Symbole erst einmal mühsam lesen und schreiben lernen, bevor man wirklichin der Lage ist, von der formalen, knappen Schreibweise zu profitieren. Deshalb ist es indiesem Kapitel besonders wichtig darauf zu achten, die Symbole schlicht und ergreifendauswendig zu lernen und darauf zu vertrauen, dass dies einem später die Arbeit mitkomplexerer Mathematik sehr erleichtert.

3.1. Notation und Operationen auf Mengen

Eine Menge wurde im Jahr 1895 in Halle von Georg Cantor(1845-1918), dem Begr ünderder Mengenlehre so definiert:

Definition 3.1.1 Eine Menge ist eine Zusammenfassung von bestimmten und wohlun-terschiedenen Objekten unserer Anschauung oder unseren Denkens zu einem Ganzen.Die Objekte einer Menge heißen Elemente.

Bemerkung 3.1.2 Formal korrekt wird die Mengenlehre durch ein System von 10Axiomen, die Zermelo-Fraenkel-Axiome, begründet. Uns soll hier aber die einfachereDefinition von Cantor genügen.

Um leichter mit Mengen arbeiten zu können, hat man sich auf einen Satz von Begriffenund Symbolen geeinigt:

Notation 3.1.3 • Wir bezeichnen Mengen mit einfachen Großbuchstaben.

• Wenn a ein Element der Menge M ist, schreiben wir a ∈ M .• Wenn a kein Element der Menge M ist, schreiben wir a /∈ M , dies entspricht der

Negation ¬(a ∈ M ).

Notation 3.1.4 Die Elemente einer Menge werden zusammengefasst mit geschweiftenKlammern. Dabei haben wir verschiedene Möglichkeiten Mengen anzugeben:

• durch direktes Hinschreiben der Elemente, z. B. M = {1, 3, 5}.

22


23/227

K AP ITEL 3. GRUNDLAGEN DER MENGE NL EHRE 3.1. NOTATION UND OPE RATIONE N AUF MENGE N

• durch die Angabe von Eigenschaften, z. B. M = {n ∈ N | n 0} die rationalen Zahlen.• R die reellen Zahlen.

All diese Regeln f ̈ur Mengen sind in vielen Programmiersprachen bereits implementiert.Wir werden zum Beispiel gegen Ende des Programmierkurses ein C++-Objekt mit demNamen set (englisch f ̈ur Menge) kennenlernen. Fügt man dort ein neues Element in einebestehende Menge ein und dieses Element liegt bereits in der Menge, wird das Einf ̈ugenabgebrochen. Dieses Verhalten folgt der Regel nach der jedes Element nur einmal in einerMenge enthalten sein darf.Mengen und die nun folgenden Operationen auf Mengen spielen insbesondere in dertheoretischen Informatik und z.B. f ̈ur Datenbanksysteme eine sehr große Rolle. Es istsinnvoll mit den Kurzschreibweisen zunächst stur auswendig zu lernen, um sie anschließendimmer zu verwenden, wenn sich etwas durch Mengen ausdrücken lässt. Das Umsetzender natürlichen Sprache in die Mengenschreibweise ähnelt sehr stark dem Programmieren,spart Zeit beim Schreiben und ermöglicht (mit etwas Übung) das Erfassen der Elementeeiner Menge auf einen Blick.

Definition 3.1.6 Die Anzahl der Elemente einer Menge nennt man ihre Mächtigkeit(oder Kardinalität) und schreibt #M (oder |M |).Eine endliche Menge M ist eine Menge mit endlicher Mächtigkeit #M


24/227


• Wenn A ⊆ B und B ⊆ A, dann sind A und B gleich, d. h. sie enthalten diesselbenElemente und wir schreiben A = B .

• Ist A eine echte Teilmenge von B, d. h. ist A

⊆ B und A

= B , dann schreiben

wir A B.

Der zweite Punkt ist zum Beweisen von Mengengleichheiten besonders wichtig. Um zuzeigen, dass zwei Mengen gleich sind, muss gezeigt werden, dass sie jeweils Teilmenge deranderen sind. Man sagt es müssen beide Inklusionen A ⊆ B und B ⊆ A gezeigt werden.

Beispiel 3.1.8 • Für alle Mengen A gilt ∅ ⊆ A und A ⊆ A.• {2, 5} {2, 3, 4, 5}

• N Z Q R

Proposition 3.1.9 Seien A, B Mengen. Wenn A ⊆ B , dann gilt #A ≤ #B.

Beweis. Da jedes Element aus A auch in B liegt, muss B mindestens so viele Elementewie A besitzen.

Definition 3.1.10 Die Menge P (A) = {M | M ⊂ A} heißt Potenzmenge von A.

Die Potenzmenge ist also die Menge aller Teilmengen einer vorgegebenen Menge A. Aufgrundvon Beispiel 3.1.8 ist immer die leere Menge und die Menge A selbst ein Element derPotenzmenge.

Proposition 3.1.11 Sei A eine Menge mit n


25/227


Die wichtigsten Operationen um aus zwei Mengen eine neue Menge zu bilden sind Durch-schnitt und Vereinigung.

Definition 3.1.13 Seien A, B Mengen.

• Die Menge A ∩ B = {x | x ∈ A ∧ x ∈ B} nennt man den Durchschnitt von Aund B .

• Wenn A ∩ B = ∅, dann nennt man A und B disjunkt,• Die Menge A ∪ B = {x | x ∈ A ∨ x ∈ B} nennt man die Vereinigung von A und

B.

Bemerkung 3.1.14 Zur Veranschaulichung dieser Mengenoperationen sind sogenannte

Venn -Diagramme gut geeignet.

Der Durchschnitt zweier Mengen A und B:

A B

Die Vereinigung zweier Mengen A und B :

A B

Beispiel 3.1.15 Seien A = {1, 2, 3, 4} und B = {3, 4, 5}, dann ist A ∩ B = {1, 2, 3, 4, 5}und A ∪ B = {3, 4}.

Aus der Definition von Durchschnitt und Vereinigung mithilfe der logischen Verknüpfungen∧ und ∨ folgen direkt einige Rechengesetze f ̈ur Mengen.

Satz 3.1.16 Seien A, B,C Mengen. Es gelten die Kommutativgesetze

A ∪ B = B ∪ AA ∩ B = B ∩ A,

die Assoziativgesetze

A ∪ (B ∪ C ) = (A ∪ B) ∪ C A ∩ (B ∩ C ) = (A ∩ B) ∩ C,

und die Distributivgesetze

A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ).

25


26/227


Beweis. Der Beweis dieser Regeln folgt direkt aus den entsprechenden Regeln f ̈ur ∧ und ∨(s. Satz 2.2.9). Wir zeigen hier exemplarisch das Kommutativgesetz f ̈ur die Vereinigung.Um die Gleichheit von Mengen zu beweisen müssen wir die zwei Inklusionen A ∪B ⊆ B ∪Aund B

∪A

⊆ A

∪B zeigen.

Um A ∪ B ⊆ B ∪ A zu zeigen, betrachten wir ein beliebiges Element aus A ∪ B und zeigen,dass es auch in B ∪ A enthalten ist.

x ∈ A ∪ B Def. von ∪⇒ x ∈ A ∨ x ∈ B Kommutativität von ∨⇒ x ∈ B ∨ x ∈ A Def. von ∪⇒ x ∈ B ∪ A

Analog können wir B ∪ A ⊆ A ∪ B beweisen, woraus die Gleichheit der beiden Mengenfolgt.

Bemerkung 3.1.17 Wir veranschaulichen die Distributivgesetze mithilfe von Venn -Diagrammen.

A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )

A B

C

A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )

A B

C

Notation 3.1.18 Für den Durchschnitt und die Vereinigung mehrerer Mengen, verwen-den wir folgende Bezeichnungen:

∪ni=1Ai = A1 ∪ A2 ∪ · · · ∪ An = {x | ∃i ∈ {1, 2, . . . , n} so dass x ∈ Ai}∩ni=1Ai = A1 ∩ A2 ∩ · · · ∩ An = {x | ∀i ∈ {1, 2, . . . , n} gilt x ∈ Ai}

Definition 3.1.19 Seien A und B Mengen.

• Die Menge A\B = {x | x ∈ A ∧ x /∈ B} nennt man die Differenz zwischen A undB. Man spricht auch:

”A ohne B“.

• Wenn B ⊆ A, dann nennen wir A\B = Bc das Komplement von B (in A).

26


27/227


Bemerkung 3.1.20 Wir veranschaulichen die Differenz und Komplement mithilfe vonVenn -Diagrammen.A

\B

A B

Ac = M

\A

M

A B

Satz 3.1.21 Seien A und B die Teilmengen einer Menge M sind. Dann gelten die de

Morgan’schen Gesetze

(A ∪ B)c = Ac ∩ Bc(A ∩ B)c = Ac ∪ Bc.

Dabei sind immer die Komplemente in M gemeint.

Beweis. Wir beweisen hier die erste Regel (A ∪ B)c = Ac ∩ Bc. Der zweite Beweis istanalog.Wir zeigen zunächst, dass (A ∪ B)c ⊆ Ac ∩ Bc. Da immer gilt, dass x ∈ M , verzichten wirzur besseren Lesbarkeit der Umformungen darauf dies in jeder Zeile zu schreiben.

x ∈ (A ∪ B)c ⇒ x /∈ A ∪ B Definition des Komplements⇒ ¬(x ∈ A ∪ B) Definition von /∈⇒ ¬(x ∈ A ∨ x ∈ B) Definition der Vereinigung⇒ ¬(x ∈ A) ∧ ¬(x ∈ B) De Morgansche Regel f ̈ur logische Operatoren⇒ x /∈ A ∧ x /∈ B Definition von /∈⇒ x ∈ Ac ∧ x ∈ Bc Definition des Komplements⇒ x ∈ Ac ∩ Bc Definition des Durchschnitts

Analog wird die umgekehrte Inklusion Ac ∩ Bc ⊆ (A ∪ B)c bewiesen.

Bemerkung 3.1.22 Wir veranschaulichen die de Morgan’schen Gesetze mithilfe vonVenn -Diagrammen.(A ∪ B)c = Ac ∩ Bc

M

A B

(A ∩ B)c = Ac ∪ Bc

M

A B

27


28/227

KAPITEL 3. GRUNDLAGEN DER MENGENLEHRE 3.2. ABBILDUNGEN ZWISCHEN MENGEN

Bei der Schreibung von Mengen mithilfe von geschweiften Klammern ist es wichtig, dassdie Reihenfolge der Elemente keine Rolle spielt. Oft aber ist auch die Reihenfolge vonElementen relevant. Daf ̈ur verwenden wir dann runde Klammern.

Definition 3.1.23 Seien A, B Mengen und a ∈ A, b ∈ B.• Man bezeichnet mit (a, b) ein geordnetes Paar (Tupel). Zwei geordnete Paare

(a, b) und (a, b) sind genau dann gleich, wenn a = a und b = b gilt.

• Die Menge aller geordneten Paare (a, b) nennt man das kartesische Produkt vonA und B und schreibt A × B = {(a, b) | a ∈ A ∧ b ∈ B}. Man spricht: “A kreuz B”.

• A1 × A2 × ·· · × An = {(a1, · · · , an) | a1 ∈ A1, · · · , an ∈ An} ist das n-fachekartesische Produkt und besteht aus allen n-Tupeln (a1, · · · , an).

• Wir bezeichnen mit An = A

×A

× · · · ×A das n-fache kartesische Produkt der

Menge A mit sich selbst.

Beispiel 3.1.24 • {1} × {1, 2} = {(1, 1), (1, 2)}• {2, 4} × {1, 3} = {(2, 1), (2, 3), (4, 1), (4, 3)}• {1, 3} × {2, 4} = {(1, 2), (1, 4), (3, 2), (3, 4)}• R2 ist die Menge aller Punkte der Ebene.

Aus der Definition eines geordneten Paares folgt, dass (1, 2) = (2, 1) ist und daher gilt auchf ̈ur die Mengen {2, 4} × {1, 3} = {1, 3} × {2, 4}.

3.2. Abbildungen zwischen Mengen

Neben dem Begriff der Menge ist der Begriff der Abbildung von grundlegender Bedeutungf ̈ur die gesamte Mathematik. Unter diesem Aspekt betrachtet zeichnen sich die verschiede-nen Teilgebiete der Mathematik lediglich dadurch aus, daß sie sich dem Studium jeweilsbesonderer Abbildungen widmen bzw. gewisse Abbildungen auf bestimmte Eigenschaftenhin untersuchen.

Abbildung zwischen Mengen werden benutzt, um Elemente aus verschiedenen Mengeneinander zuzuordnen. Diese sind wichtig um mehr Informationen über eine Menge zuerhalten.

Definition 3.2.1 Seien A, B nichtleere Mengen. Eine Abbildung f von einer MengeA in eine Menge B ist eine Vorschrift, die jedem x ∈ A genau ein f (x) ∈ B zuordnet.Wir schreiben:

f : A → Ba →

f (a)

28


29/227


und sagen “a wird auf f (a) abgebildet”.In Bezug auf die Abbildung f heißt A die Definitionsmenge und B die Wertemengevon f .

Folgendes ist zu beachten:

• Zur Definition einer Abbildung gehört neben der Zuordnungsvorschrift ganz wesentlichdie Nennung der Definitionsmenge (Ausgangsmenge) und auch der Wertemenge(Zielmenge). So stellen

f : Z → N0, n → n2g : R → R, x → x2

ganz unterschiedliche Abbildungen dar, obwohl die Zuordnungsvorschrift – nämlichzu quadrieren – die gleiche ist, wenn man von den unterschiedlichen Variablennamen

n und x absieht, die man auch hätte gleich wählen können.• Jedem a ∈ A wird ein b ∈ B zugeordent, die Umkehrung gilt im allgemeinen jedoch

nicht, d.h. es kann durchaus vorkommen, dass es Elemente b ∈ B gibt, denen keinoder auch zwei verschiedene Elemente zugeordnet werden.

Um eine Abbildung zu definieren, kann man explizit die Zuordnung angeben, welchesElement aus A auf welches Element aus B abgebildet wird. Dies ist aber nur f ̈ur endlicheMengen möglich und auch da mühsam. Alternativ kann man Abbildung durch eine odermehrere Formeln definieren.

Beispiel 3.2.2

•f : N → N

n → n2

ist eine wohldefinierte Abbildung.

• Der ASCII-Code ordnet den Zahlen von 0 bis 127 bestimmte Steuerzeichen zu.

f : {0, 1, 2, . . . , 127} → {0, 1, 2, . . . , a , b , . . . , A , B , . . . , %, ?, . . . }48 → 061

→ =

... ...

Wir nennen eine Abbildungsvorschrift wohldefiniert, wenn dadurch wirklich eine Abbil-dung definiert wird.

Beispiel 3.2.3 Um zu sehen, was genau wohldefiniert bedeutet, ist es am besten sicheinige Beispiele nicht wohldefinierter Abbildungsvorschriften anzuschauen.

29


30/227


• Die Abbildungsvorschrift

f : {1, 3, 5} → {2, 3}1 → 23 → 25 → 31 → 3

ist nicht wohldefiniert, da dem Element 1 ∈ {1, 3, 5} zwei verschiedene Elementezugeordnet werden.


f : {1, 3, 5} → {2, 3}1 → 23 → 2

ist nicht wohldefiniert, da dem Element 5 ∈ {1, 3, 5} kein Element zugeordnet wird.• Die Abbildungsvorschrift

f : {1, 3, 5} → {2, 3}1

→ 2

3 → 25 → 5

ist nicht wohldefiniert, da dem Element 5 ein Element zugeordnet wird, das nichtin der Menge {2, 3} liegt.


f : N → N

n → n2 wenn

n eine Primzahl ist,

n → 3n wenn n eine gerade Zahl ist.

ist nicht wohldefiniert, da zum einen die Zahl 2, die eine Primzahl ist und gerade auf verschiedene Zahlen abgebildet wird (Aus der Vorschrift folgt einerseits 2 → 22 = 4,da 2 eine Primzahl ist, andererseits gilt 2 → 3 · 2 = 6, da 2 gerade ist). Außerdemgibt es keine Vorschrift f ̈ur ungerade Zahlen, die nicht prim sind.

30


31/227


Definition 3.2.4 Seien A, B Mengen.

• Die Abbildung idA : A → A, a → a heißt Identität.• Sei f : A → B eine Abbildung. Dann heißt die Menge

f (A) = {b ∈ B | ∃a ∈ A so dass giltf (a) = b} ⊆ B

das Bild von f .

• Sei f : A → B eine Abbildung und M ⊆ B . Dann heißt die Menge

f −1(M ) = {a ∈ A | f (a) ∈ M } ⊆ A

das Urbild der Menge M unter f .

Beispiel 3.2.5 Wir betrachten folgende Abbildung

f : {1, 2, 3} → {4, 5, 6}1 → 42 → 43 → 5

Dann ist das Bild f ({1, 2, 3}) = {4, 5} und wir berechnen die Urbilder f −1({4}) = {1, 2},f −1({5}) = {3} und f −1({6}) = ∅.

Eigenschaften von Abbildungen, die eine besondere Rolle spielen geben wir einen Namenund versuchen sie genau zu charakterisieren.

Definition 3.2.6 Seien A, B Mengen und sei f : A → B, a → f (b) eine Abbildung.• f heißt genau dann injektiv, wenn f ̈ur alle a, a ∈ A gilt: wenn f (a) = f (a), dann

ist a = a.

• f heißt genau dann surjektiv, wenn f ̈ur alle b ∈ B ein a ∈ A existiert, so dass giltf (a) = b.

• f heißt genau dann bijektiv, wenn f injektiv und surjektiv ist.

Bemerkung 3.2.7 Um besser zu verstehen, was diese Begriffe bedeuten, ist es g ünstigsie auf verschiedene Art und Weisen umzuformulieren.

In der Definition von injektiv steht eine Aussage der Form “x ⇒ y”, diese ist genau dannrichtig, wenn ¬y ⇒ ¬x richtig ist (s. Satz 2.3.1). Somit lautet eine alternative Definition

31


32/227


von Injektivität: f heißt genau dann injektiv, wenn f ̈ur a, a ∈ A gilt: wenn a = a, dannist f (a) = f (a).Oder noch anders formuliert: bei einer injektiven Abbildung hat jedes Element b ∈ Bhöchstens ein Urbild in A, d. h. #f −1({b}) = 0 oder #f −1({b}) = 1. Denn hätte bzwei Urbilder a, a ∈ A, d. h f (a) = f (a) = b, dann müssen diese ja gleich sein a = a.Also hat b höchstens ein Urbild.

Beim genauen Angucken der Definition des Bildes einer Abbildung sieht man, dass f genau dann surjektiv ist, wenn f (A) = B gilt.Das wiederum bedeutet, dass bei einer surjektiven Abbildung jedes Element b ∈ Bmindestens ein Urbild in A hat.

Somit hat bei einer bijektiven Abbildung jedes Element b ∈ B genau ein Urbild in A.

Schränkt man die Wertemenge B einer Abbildung f : A → B auf f (A) ein, dann erhältman eine neue Abbildung f̃ : A → f (A), die surjektiv ist. Die Eigenschaften injektivund surjektiv hängen also nicht nur von der Abbildungsvorschrift ab, sondern auch ganzwesentlich von der Definitions- und Wertemenge.

Beispiel 3.2.8 Die Abbildung

f : {1, 2} → {4, 5, 6}1 → 42 → 6

ist injektiv, aber nicht surjektiv, da 5 kein Urbild hat.Die Abbildung

f : {1, 2, 3} → {4, 5}1 → 42 → 53 → 5

ist surjektiv, aber nicht injektiv, da 5 zwei Urbilder hat.

Proposition 3.2.9 Seien A, B Mengen mit endlich vielen Elementen, #A = n und#B = m und sei f : A → B eine Abbildung. Dann gilt:Wenn f injektiv ist, dann ist n ≤ m.Wenn f surjektiv ist, dann ist n ≥ m.

Beweis. Die Methode diese Aussagen zu beweisen wird als Schubfachprinzip bezeichnet.Daf ̈ur können wir uns anschaulich die Menge A als Menge von n Kugeln vorstellen und

32


33/227


34/227


Beweis. (i) Angenommen g(f (a)) = g(f (a)), dann folgt aus der Injektivität von g, dassf (a) = f (a), aus der Injektivität von f , folgt dann wiederum, dass a = a. Und somitist auch (g ◦ f ) injektiv.

(ii) Da f sujektiv ist, gilt f (A) = B, da g surjektiv ist, folgt g(B) = C . Also istg(f (A)) = C und (g ◦ f ) ist surjektiv.

(iii) Folgt direkt aus (i) und (ii)

Satz 3.2.13 Seien A, B nichtleere Mengen und f : A → B eine Abbildung. Dann gilt:a) f ist genau dann injektiv, wenn f eine Linksinverse hat, d. h. wenn es eine

Abbildung g : B → A gibt, f ̈ur die gilt g ◦ f = idA .b) f ist genau dann surjektiv, wenn f eine Rechtsinverse hat, d. h. wenn es eine

Abbildung g : B → A gibt, f ̈ur die gilt f ◦ g = idB .c) f ist genau dann bijektiv, wenn f eine Inverse hat, d. h. wenn es eine Abbildung

g : B → A gibt, f ̈ur die gilt f ◦ g = idB und g ◦ f = idA .

Beweis. Alle Aussagen sind Äquivalenzen, das heißt es müssen immer beide Implikationengezeigt werden.

a) Wir zeigen zunächst die Implikation: “Wenn f injektiv ist, dann gibt es eine Abbildungg : B → A, f ̈ur die g ◦ f = idA gilt”.Wir nehmen also an f sei injektiv und definieren eine Abbildung g durch

g : B → Ab → a ∈ f −1({b}) wenn b ∈ f (A)b → a beliebig wenn b /∈ f (A)

Diese Abbildung ist wohldefiniert, da die Menge f −1({b}) aus nur einem Elementbesteht, da f injektiv ist. Wenn b /∈ f (A), dann ist f −1({b}) leer und wir können einbeliebiges Element wählen auf das b abgebildet wird.

Nun können wir prüfen, dass die so definierte Abbildung die Eigenschaft g ◦ f = idAhat. Sei also a ∈ A ein beliebiges Element, dann ist g(f (a)) = g(b) = a, da b = f (a)ein Element aus dem Bild f (A) ist und f −

1

({b}) = {a} das Urbild ist.Im zweiten Schritt zeigen wir die Implikation “Wenn es eine Abbildung g : B → A,f ̈ur die g ◦ f = idA gilt gibt, dann ist f injektiv.”Diesen Teil des Beweises f ̈uhren wir per Widerspruch, dass heißt wir nehmen an esgebe diese Abbildung g mit der geforderten Eigenschaft, aber f ist nicht injektiv.

Wenn f nicht injektiv ist, dann gibt es Elemente a, a ∈ A, die ungleich sind a = a,aber f ̈ur die f (a) = f (a) gilt.

Da a = a, ist auch idA(a) = idA(a).Andererseits gilt aber (g

◦f )(a) = g(f (a)) = g(f (a)) = (g

◦f )(a). Da nach Annahme

g ◦ f = idA gilt erhalten wir daraus a = a im Widerspruch zur vorherigen Zeile.

34


35/227


b) “⇒”: Angenommen f ist surjektiv, dann ist f −1(b) nicht leer wie auch immer b ∈ Bvorgegeben ist. Für jedes b ∈ B läßt sich ein a ∈ f −1(b) auswählen, welches dazuverwendet werden kann, die Funktion h : B → A durch die Setzung h(b) := a zudefinieren. Aus der Definition von h folgt dann unmittelbar die behauptete Eigenschaftf

h(b)

= b. Auch hier ist h nicht eindeutig festgelegt, sondern es gibt alternativeDefinitionsmöglichkeiten, wenn f nicht injektiv ist.

“⇐”: Angenommen es sei eine derartige Funktion h vorhanden. Ist b ∈ B beliebigaber fest vorgegeben, so gilt f

h(b)

= b. Damit wird h(b) ∈ A auf b abgebildet. Da

b beliebig, läßt sich somit zu jedem b ∈ B ein Element aus A finden – nämlich h(b) –welches auf b abgebildet wird, d.h. f ist surjektiv.

c) folgt direkt aus a) und b)

Definition 3.2.14 Seien A, B Mengen und f : A → B eine bijektive Abbildung. Dannheißt die Abbildung f −

1

: B → A, f (a) → a Umkehrabbildung von f .Die Umkehrabbildung entspricht der Abbildung g aus Satz 3.2.13 und erf ̈ullt somitf ◦ f −1 = idB und f −1 ◦ f = idA.

Achtung! Es ist wichtig die Umkehrabbildung nicht mit dem Urbild zu verwechseln,obwohl daf ̈ur die gleiche Notation verwendet wird. Das Urbild einer Menge unter einerAbbildung f : A → B ist eine Menge und kann f ̈ur alle Abbildungen f und alle TeilmengenM ⊆ B bestimmt werden.Die Umkehrabbildung hingegen kann nur von bijektiven Abbildungen f : A → B bestimmtwerden und sie ordnet dann einem Element b

∈ B, das eindeutig bestimmte Element

a ∈ f −1({b}) zu.Definition 3.2.15 Seien A, B Mengen und f : A → B eine Abbildung und A ⊆ A,dann definiert

f |A : A → Ba → f (a)

eine Abbildung die Einschränkung von A auf A.

Proposition 3.2.16 Seien A ⊆ A, B Mengen und f : A → B eine Abbildung. Danngilt:

i) Ist f injektiv, dann ist auch f |A injektiv.ii) Die Abbildung g : A → f (A), a → f (a) ist surjektiv.

Beweis. i) Wenn f ̈ur alle a1, a2 ∈ A aus a1 = a2 folgt, dass f (a1) = f (a2) gilt. Dann giltdas ebenfalls f ̈ur alle a1, a2 ∈ A ⊆ A.ii) Per Definition ist f (A) das Bild der Abbildung f . Da f ̈ur alle Elemente a ∈ A giltf (a) = g(a) per definition von g, ist also auch f (A) das Bild von g und damit ist g

surjektiv.

35


36/227

KAPITEL 3. GRUNDLAGEN DER MENGENLEHRE 3.3. RELATIONEN

3.3. Relationen

Relationen sind ein Mittel um Beziehungen zwischen Elementen einer Menge herzustellen,die wichtige zusätzliche Informationen liefern.

Definition 3.3.1 (Relation)Es seien A und B zwei nichtleere Mengen. Eine (binäre) Relation R zwischen denMengen A und B ist eine Teilmenge des kartesischen Produkts A × B, d. h.

R ⊂ A × B = {(a, b) | a ∈ A, b ∈ B} .

Für (a, b) ∈ R schreibt man auch aRb, d.h. a steht in Relation R zu b. Ist A = B sospricht auch von einer Relation auf bzw. in der Menge A.

Definition 3.3.2 (Eigenschaften von Relationen)Eine Relation R ⊂ A × A auf einer Menge A heißt

• reflexiv genau dann, wenn f ̈ur alle a ∈ A gilt, dass (a, a) ∈ R.• symmetrisch genau dann wenn gilt: (a, b) ∈ R ⇒ (b, a) ∈ R.• antisymmetrisch genau dann, wenn aus (a, b) ∈ R ∧ (b, a) ∈ R folgt, dass a = b.• transitiv genau dann, wenn gilt: (a, b) ∈ R ∧ (b, c) ∈ R ⇒ (a, c) ∈ R.

Bemerkung 3.3.3 Die Definition von antisymmetrisch ist von der Art A ⇒ B undsomit genau dann richtig, wenn ¬B ⇒= A richtig ist (s. Satz 2.3.1). Somit kann dieseDefinition mithilfe der De Morganschen Gesetze (s. Satz 2.2.10) umformuliert werden zu:Eine Relation R ⊂ A × A auf einer Menge A heißt antisymmetrisch genau dann, wennaus a = b folgt, dass (a, b) /∈ R ∨ (b, a) /∈ R.

Definition 3.3.4 (Äquivalenzrelation)Eine Relation R

⊂ A

×A heißt Äquivalenzrelation auf A, wenn sie reflexiv, symme-

trisch und transitiv ist. Anstatt (a, b) ∈ R schreibt man im Falle von Äquivalenzrelationenhäufiger a ∼ b, d.h. a ist äquivalent zu b.

Definition 3.3.5 (Äquivalenzklasse und Quotientenmenge)Es sei ∼ eine Äquivalenzrelation auf A. Für a ∈ A heißt die Teilmenge von A

[a] := {x ∈ A : a ∼ x } ⊂ A

Äquivalenzklasse von a. Die Elemente von [a] nennt man die zu a äquivalenten

Elemente.

36


37/227


Die Menge aller Äquivalenzklassen einer Äquivalenzrelation heißt Quotientenmenge

A/∼ := {[a] | a ∈ A}.

Es gibt eine kanonische surjektive Abbildung

π : A → A/∼, a → [a].

Eine Äquivalenzklasse enthält alle Elemente, die bezüglich eines bestimmten Aspekts,der durch die Äquivalenzrelation definiert wird, als gleich betrachtet werden kann. DieQuotientenmenge enthält dann all diese Äquivalenzklassen.

Beispiel 3.3.6 Sei A =

{Schüler einer Schule

}, dann ist “ a

∼ b := a ist in der selben

Schulklasse wie b”, eine Äquivalenzrelation und die Menge der Schulklassen ist dieQuotientenmenge bezüglich dieser Relation. Will man zum Beispiel einen Stundenplanentwerfen, dann ist es hilfreich nicht jeden Schüler einzeln zu betrachten, sondern denStundenplan f ̈ur jede Schulklasse zu erstellen.

Äquivalenzrelationen sind ein wichtiges Hilfsmittel um aus einer bekannten Menge eineneue Menge konstruieren zu können, die dann bestimmte gewünschte Eigenschaften hat.Wir werden dies in Abschnitt 5 mehrfach benutzen um Zahlenmengen zu konstruieren.

Satz 3.3.7 Es sei

∼ eine Äquivalenzrelation auf A. Dann bildet die Menge der

Äquivalenzklassen eine Partition von A. Das bedeutet, dass zwei Äquivalenzklassenentweder gleich oder disjunkt sind und außerdem gilt ∪a∈A[a] = A.

Beweis. Um zu beweisen, dass zwei Äquivalenzklassen entweder gleich oder disjunkt sind,zeigen wir dass sie gleich sind, sobald ihr Durchschnitt nicht leer ist.Wir betrachten zwei Äquivalenzklassen [a] und [a] in deren Durchschnitt ein Element cliegt, das heißt c ∈ [a] ∩ [a]. Dies ist gleichbedeutend mit c ∼ a und c ∼ a.Wir wollen nun zeigen, dass [a] ⊆ [a] gilt:Sei x ∈ [a], d. h. x ∼ a. Aufgrund der Symmetrie der Relation folgt aus c ∼ a auch a ∼ c.Aufgrund der Transitivität folgt aus x ∼ a und a ∼ c dass auch x ∼ c. Und somit wiederaufgrund der Transitivität folgt aus x ∼ c und c ∼ a die Beziehung x ∼ a. Damit liegtnun x ∈ [a] und wir haben gezeigt, dass [a] ⊆ [a] gilt.Auf analoge Weise (wir tauschen die Rollen von a und a) folgern wir [a] ⊆ [a], worausfolgt, dass die Äquivalenzklassen gleich sind.

Im nächsten Schritt wollen wir zeigen, dass ∪a∈A[a] = A gilt. Zunächst bemerken wir, dassÄquivalenzklassen [a] immer einer Teilmenge von A sind und damit auch ihre Vereinigung.Das heißt es gilt ∪a∈A[a] ⊆ A.Für die umgekehrte Inklusion müssen wir zeigen, dass jedes Element a ∈ A in einerÄquivalenzklasse liegt. Aufgrund der Reflexivität einer Äquivalenzrelation ist aber jederElement zu sich selbst äquivalent a ∼ a und somit liegt a ∈ [a], woraus wir A ⊆ ∪a∈A[a]folgern und damit die Gleichheit beider Mengen.

37


38/227


Neben Äquivalenzrelationen sind Ordnungsrelationen wichtige und häufig benutzte Rela-tionen.

Definition 3.3.8 (Ordnungsrelation)Eine Ordnungsrelation oder kurz eine Ordnung in der Menge A ist eine reflexive ,antisymmetrische und transitive Relation in A.

Definition 3.3.9 (Vergleichbarkeit zweier Elemente)Zwei Elemente a, b ∈ A heißen vergleichbar bezüglich der Ordnung in A, wennentweder a b oder b a gilt.

Definition 3.3.10 (Totale und partielle Ordnung)Eine Ordnung in der Menge A heißt total, wenn je zwei Elemente aus A vergleichbarsind bezüglich . Ist die Vergleichbarkeit nicht f ̈ur alle Elementpaare gegeben, so sprichtman zur Abgrenzung gegenüber totalen Ordnungen von einer partiellen Ordnungoder Teilordnung.

Beispiel 3.3.11 “≤” definiert auf den reellen Zahlen eine Totalordnung. Diese Relationist reflexiv, da f ̈ur jedes Element a ≤ a gilt. Sie ist antisymmetrisch, da f ̈ur zweiunterschiedliche Elemente a

= b entweder a

≤ b oder b

≤ a gilt, woraus auch die

Vergleichbarkeit zweier Elemente folgt. Die Transitivität gilt, da aus a ≤ b, b ≤ c folgt,dass a ≤ c ist.

“⊆” definiert auf der Potenzmenge P (A) einer Menge A eine partielle Ordnung. Schonwenn A die Mächtigkeit 2 hat, also A = {a, b}, dann hat A die Teilmengen {a} und {b},die nicht vergleichbar sind, da weder {a} ⊆ {b} noch {b} ⊆ {a} gilt.

38


39/227

4. Algebraische Strukturen

Nachdem wir nun mit Mengen und Abbildungen zwischen ihnen hantieren können, wollenwir nun Mengen betrachten mit denen man auch rechnen kann.

4.1. Gruppen

Definition 4.1.1 Sei G eine Menge mit einer Verknüpfung ◦, d. h.

◦ : G × G → G(g, h) → g ◦ h.

(G, ◦) heißt Gruppe, wenn gilt:i) Es existiert genau ein Element e ∈ G, das f ̈ur alle g ∈ G g ◦ e = e ◦ g = g erf ̈ullt.

e heißt neutrales Element.

ii) Zu jedem g ∈ G gibt es genau ein Element g−1 ∈ G, so dass g ◦ g−1 = g−1 ◦ g = egilt. g−1 heißt das zu g inverse Element.

iii) Für alle g1, g2, g3 ∈ G gilt: g1 ◦ (g2 ◦ g3) = (g1 ◦ g2) ◦ g3. (Assoziativgesetz)Gilt außerdem

iv) Für alle g1, g2 ∈ G : g2 ◦ g1 = g1 ◦ g2Dann heißt die Gruppe abelsch oder kommutativ.

Bemerkung 4.1.2 In der Definition einer Gruppe können die Forderungen i) und ii)durch die (auf dem ersten Blick) schwächeren Forderungen

i’) Es existiert ein linksneutrales Element Element e ∈ G, d. h. das f ̈ur alle g ∈ G gilt:e ◦ g = g erf ̈ullt,

ii’) Zu jedem g ∈ G gibt es ein linksinverses Element g−1 ∈ G, d. h. es gilt g−1 ◦ g = e,ersetzt werden. Dabei ist zu beachten, dass es hier nicht die Eindeutigkeit des Linksneu-tralen und Linksinversen gefordert wird. Es ist möglich durch einfache Rechnungen ausden Bedingungen i’),ii’) und iii) zu folgern, dass dann auch i),ii) und iii) gelten.Der Vorteil an der schwächeren Definition ist nun, dass es bei einem konkreten Beispielgenügt die schwächeren Eigenschaften nachzuweisen um zu beweisen, dass es sich umeine Gruppe handelt.

39


40/227

KAPITEL 4. ALGEBRAISCHE STRUKTUREN 4.1. GRUPPEN

Proposition 4.1.3 Sei G, ◦ eine Gruppe und g , h ∈ G, dann gilt:i) (g−1)−1 = g und

ii) (g ◦ h)−1 = h−1 ◦ g−1.

Beweis. i) Wir müssen zeigen, dass g ein zu g−1 inverses Element ist. Aber dies giltaufgrund der Definition von g−1 als zu g inverses Element: g ◦ g−1 = e. Aufgrund derEindeutigkeit des Inversen ist daher (g−1)−1 = g.

ii) Wir müssen zeigen, dass h−1 ◦ g−1 ein zu (g ◦ h) inverses Element ist. Dies ist derFall, da aufgrund des Assoziativgesetzes gilt:

(h−1 ◦ g−1) ◦ (g ◦ h) = h−1 ◦ (g−1 ◦ g) ◦ h = h−1 ◦ e ◦ h = h−1 ◦ h = e.

Beispiel 4.1.4 • (Z, +) ist eine Gruppe• (Q\{0}, ·) ist eine Gruppe• Sei M eine Menge, dann definieren wir die Menge der bijektiven Abbildungen von

M in sich selbst

Bij(M ) := {f : M → M | f ist bijektiv}

Die Menge Bij(M ) zusammen mit der Hintereinanderausf ̈uhrung von Abbildungen

als Verknüpfung ist eine Gruppe.– Das neutrale Element der Gruppe ist die Identität idM .

– Zu einer Abbildung f ∈ Bij(M ) gibt es eine eindeutig bestimmte Umkehrab-bildung f −1 ∈ Bij(M ), diese ist das zu f inverse Element in B ij(M ), dennes gilt f ◦ f −1 = f −1 ◦ f = idM .

– Das Assoziativgesetz gilt, da per Definition der Hintereinanderausf ̈uhrunggilt:

f ◦ (g ◦ h)(m) = f (g ◦ h)(m) = f (g(h(m)))und (f ◦ g) ◦ h(m) = (f ◦ g)h(m) = f (g(h(m))).

– Diese Gruppe ist nicht abelsch, wenn M mehr als 2 Elemente hat. Als Beispielbetrachten wir M = {1, 2, 3} und die bijektiven Abbildungen

f :M → M g : M → M 1 → 1 1 → 22 → 3 2 → 33 → 2 3 → 1

40


41/227

KAPITEL 4. ALGEBRAISCHE STRUKTUREN 4.1. GRUPPEN

Wir rechnen nach, dass (f ◦ g)(1) = f (g(1)) = f (2) = 3 gilt, aber(g ◦ f )(1) = g(f (1)) = g(1) = 2. Anschaulich können wir uns die Menge M alsEckpunkte eines gleichseitigen Dreiecks vorstellen, dann ist f eine Spiegelung

und g eine Drehung um 120 Grad.

g ◦ f = “ Drehen um 120◦” ◦ “Spiegeln”:

2

1

3 3

1

2 2

3

1

f =Spiegeln g =Drehen

f ◦ g = “Spiegeln” ◦ “ Drehen um 120◦”:

2

1

3 1

3

2 1

2

3

g=Drehen f =Spiegeln

Definition 4.1.5 Sei (G, ◦) eine Gruppe und H ⊆ G eine Teilmenge. H heißt Unter-gruppe von G, wenn H mit der von G geerbten Verknüpfung ◦ eine Gruppe (H, ◦)definiert.

Wichtig um zu zeigen, dass eine Teilmenge Untergruppe ist, ist neben den Gruppen axiomenauch die Abgeschlossenheit der Verknüpfung. Das heißt, dass f ̈ur g1, g2 ∈ H auch g1◦g2 ∈ H liegt.

Proposition 4.1.6 Sei (G, ◦) eine Gruppe und H ⊆ G eine Teilmenge, so dass gilt:

g1, g2 ∈ H ⇒ g−11 ◦ g2 ∈ H,

dann ist H eine Untergruppe von G.

Beweis. Wir müssen zeigen, dass alle Gruppenaxiome erf ̈ullt sind.

i) Sei g1 = g2 = g, wobei g ein beliebiges Element in H ist. Dann ist auch g−1 ◦ g ∈ H

und somit das neutrale Element e.

ii) Sei g ∈ H . Wir zeigen, dass auch g−1 ∈ H . Daf ̈ur setzen wir g1 = g und g2 = e (vondem wir ja schon wissen, dass es enthalten ist) und somit ist g−1 ◦ e = g−1 ∈ H .

iii) Das Assoziativgesetz überträgt sich sich direkt, da alle Element in H ja auch in Gliegen.

iv) Außerdem müssen wir noch zeigen, dass f ̈ur zwei Elemente g1, g2 ∈ H auch g1 ◦ g2 inH liegt (dies nennt man Abgeschlossenheit der Verknüpfung). Dies folgt, da wir jabereits wissen, dass g−11 ∈ H und somit auch (g−11 )−1 ◦ g2 = g1 ◦ g2 ∈ H.

41


42/227

KAPITEL 4. ALGEBRAISCHE STRUKTUREN 4.2. GRUPPENHOMOMORPHISMEN

Beispiel 4.1.7 • (Z, +) ist Untergruppe von (Q, +)• (R>0, ·) ist Untergruppe von (R\{0}, ·)• ({1, −1}, ·) ist Untergruppe von (R\{0}, ·)

4.2. Gruppenhomomorphismen

Besitzt eine Menge eine zusätzliche “Struktur”, wie in unserem Fall eine Verknüpfung,dann spielen Abbildungen eine besondere Rolle, die diese Struktur erhalten.

Definition 4.2.1 S

Date post:	07-Jul-2018
Category:	Documents
Upload:	lukas-bomml
View:	220 times
Download:	1 times

Skript IMI1 AK

Documents