Transcription

Diskrete Mathematik für InformatikerMarkus LohreyUniversität SiegenWintersemester 2014/2015Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20151 / 344

Organisatorisches zur VorlesungDie aktuelle Version der Folien finden Sie diskrete mathematik/folien.pdfLiteraturempfehlungen:Steger, Diskrete Strukturen 1. Kombinatorik, Graphentheorie,Algebra, SpringerDiekert, Kufleitner, Rosenberger, Elemente der diskreten Mathematik,De GruyterAigner, Diskrete Mathematik, ViewegDiestel, Graphentheorie, SpringerDie Übungen werden von Danny Hucke und Daniel König organisiert.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20152 / 344

Mengentheoretische GrundlagenNaive Definition (Mengen, Elemente, , 6 )Eine Menge ist die Zusammenfassung von bestimmten unterschiedlichenObjekten (die Elemente der Menge) zu einem neuen Ganzen.Wir schreiben x M, falls das Objekt x zur Menge M gehört.Wir schreiben x 6 M, falls das Objekt x nicht zur Menge M gehört.Falls x M und y M gilt, schreiben wir auch x, y M.Eine Menge, welche nur aus endlich vielen Objekten besteht (eine endlicheMenge), kann durch explizite Auflistung dieser Elemente spezifiziertwerden.Beispiel: M {2, 3, 5, 7}.Hierbei spielt die Reihnfolge der Auflistung keine Rolle:{2, 3, 5, 7} {7, 5, 3, 2}.Auch Mehrfachauflistungen spielen keine Rolle:{2, 3, 5, 7} {2, 2, 2, 3, 3, 5, 7}.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20153 / 344

Mengentheoretische GrundlagenEine besonders wichtige Menge ist die leere Menge {}, die keinerleiElemente enthält.In der Mathematik hat man es häufig auch mit unendlichen Mengen zutun (Mengen, die aus unendlich vielen Objekten bestehen).Solche Mengen können durch Angabe einer Eigenschaft, welche dieElemente der Menge auszeichnet, spezifiziert werden.Beispiele:N {0, 1, 2, 3, 4, 5, . . .} (Menge der natürlichen Zahlen)Z {. . . , 2, 1, 0, 1, 2, . . .} (Menge der ganzen Zahlen)Q { qp p Z, q Z, q 6 0} (Menge der ganzen Zahlen)P {n N n 2, n ist nur durch 1 und n teilbar}(Menge der Primzahlen)Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20154 / 344

Mengentheoretische GrundlagenUnser Mengenbegriff ist naiv in dem Sinne, dass es sich um keine formaleDefinition handelt.Dies mag schwierig zu vermeiden sein, ist doch der Mengenbegriff dasfundamentalste Konzept der Mathematik. Alle Objekte der Mathematikkönnen als Mengen aufgefasst werden.Wie sollte man also den Mengenbegriff in der Sprache der Mathematikformalisieren?Logiker haben zu Beginn des 20. Jahrhunderts eine formale Mengenlehreaufgestellt, indem sie eine Liste von Axiomen (Aussagen, deren Wahrheitnicht weiter hinterfragt wird) aufgestellt haben, welche grundlegendeEigenschaften der Elementbeziehung beschreibt. Dieses Liste vonAxiomen ist als ZFC (Zermelo-Frankel with Choice) bekannt.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20155 / 344

Mengentheoretische GrundlagenBeispiel: Eines der ZFC-Axiome besagt, dass zwei Mengen genau danngleich sind, wenn sie die gleichen Elemente haben. Etwas formaler:Für alle Mengen X und Y gilt: X und Y sind gleich, genau dann wenn füralle x gilt: x X genau dann, wenn x Y .Noch formaler: X Y : (X Y ( x : x X x Y ))Hierbei bedeutet “für alle” und “es existiert”.Bisher konnten Mathematiker kein schlüssiges mathematisches Argumentfinden, welche nicht mit den ZFC-Axiomen ableitbar ist.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20156 / 344

Mengentheoretische GrundlagenDie Notwendigkeit einer formalen Mengenlehre hat sich unter anderem ausdiversen Paradoxien entwickelt. Eines der bekanntesten hiervon ist Russel’sParadoxon:Elemente von Mengen können wieder Mengen sein. Also könnten wir dochdie Menge aller Mengen, welche sich nicht selbst als Element haben,definieren:Y {x x 6 x}Gilt nun Y Y ?Würde Y Y gelten, so würde Y die Eigenschaft, welche die MengeY definiert, erfüllen. Also müsste Y 6 Y gelten.Würde Y 6 Y gelten, so würde Y die Eigenschaft, welche die MengeY definiert, nicht erfüllen. Also müsste Y Y gelten.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20157 / 344

Mengentheoretische GrundlagenDefinition ( , (, Potenzmenge, , , \, disjunkt)Seien A und B zwei Mengen.A B bedeutet, dass jedes Element von A auch zu B gehört (A isteine Teilmenge von B); formal: a : a A a BA ( B bedeutet, dass A B und A 6 B gilt.2A {B B A} (Potenzmenge von A)A B {c c A und c B} (Schnitt von A und B)A B {c c A oder c B} (Vereinigung von A und B)A \ B {c A c 6 B} (Differenz von A und B)Zwei Mengen A und B sind disjunkt, falls A B gilt.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20158 / 344

Mengentheoretische GrundlagenBeispiele und einige einfache Aussagen: A und A A gilt für jede Menge A.Für alle Mengen A und B gilt A B genau dann, wenn A B undB A.N Z Q.{1, 2, 3} {4, 5, 6} , d. h. die beiden Mengen sind disjunkt.2{1,2} { , {1}, {2}, {1, 2}} und 2 { }Für alle Mengen A giltA und A A.Für alle Mengen A, B, und C gilt:A (B C ) (A B) (A C )A (B C ) (A B) (A C )A \ (B C ) (A \ B) (A \ C )A \ (B C ) (A \ B) (A \ C )Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/20159 / 344

Mengentheoretische GrundlagenWir beweisen beispielhaft die IdentitätA (B C ) (A B) (A C ).Hierzu zeigen wir:(1) Jedes Element von A (B C ) gehört auch zu (A B) (A C ).(2) Jedes Element von (A B) (A C ) gehört auch zu A (B C ).zu (1). Sei x A (B C ).Dann gilt also x A oder x (B C ).Fall 1: Es gilt x A.Dann gilt auch x (A B) sowie x (A C ) und damitx (A B) (A C ).Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201510 / 344

Mengentheoretische GrundlagenFall 2: Es gilt x (B C ), d. h. x B und x C .Wieder gilt x (A B) und x (A C ) und damit x (A B) (A C ).zu (2). Sei x (A B) (A C )Dann gilt x A B und x A C .Fall 1: x A.Dann gilt x A (B C ).Fall 2: x 6 A.Wegen x A B muss x B gelten, und wegen x A C muss x Cgelten.Also gilt x B C , d.h. x A (B C ).Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201511 / 344

Mengentheoretische GrundlagenDefinition (beliebige Vereinigung und Schnitt)Sei I eine Menge und für jedes i I sei Ai wiederum eine Menge. Danndefinieren wir:[Ai {a j I : a Aj }i I\i IAi {a j I : a Aj }Für Mengen A1 , A2 , . . . , An verwenden wir auch die Schreibweisen[Ai i 1Lohrey (Universität Siegen)[Ai undi {1,.,n}n\Ai i 1Diskrete Mathematik\Ai .i {1,.,n}Wintersem. 2014/201512 / 344

Mengentheoretische GrundlagenBeispiele:[{a} A für jede Menge Aa A\ε R\{0}{x R x π ε } {π}\n NEinfache Aussagen: \{m N m n} Aii I [i ILohrey (Universität Siegen)Ai B \(Ai B)i I[ B (Ai B)i IDiskrete MathematikWintersem. 2014/201513 / 344

Mengentheoretische GrundlagenEs wurde bereits erwähnt, dass alle Objekte der Mathematik als Mengenaufgefasst werden können.Hier ist ein konkretes Beispiel:Kuratowskis Definition des geordneten PaaresFür zwei Objekte x und y sei (x, y ) das geordnete Paar, bestehend aus xund y . Es zeichnet sich durch die Eigenschaft(x, y ) (x ′ , y ′ ) genau dann, wenn (x x ′ und y y ′ )aus. Kuratowski definierte das geordnete Paar als(x, y ) : {x, {x, y }}.Für Objekte x1 , x2 , . . . , xn (n 3) definieren wir dann das n-Tupel(x1 , x2 , . . . , xn ) : (x1 , (x2 , . . . , xn )).Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201514 / 344

Mengentheoretische GrundlagenDefinition (Kartesisches Produkt)Für zwei Mengen A und B istA B {(a, b) a A und b B}das kartesische Produkt von A und B.Allgemeiner: Für Mengen A1 , . . . , An (n 2) seinYi 1Ai A1 A2 · · · An {(a1 , . . . , an ) für alle 1 i n gilt ai Ai }Falls A1 A2 · · · An A schreiben wir auch An für diese Menge.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201515 / 344

Mengentheoretische GrundlagenBeispiele und einige einfache Aussagen:{1, 2, 3} {4, 5} {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}Für alle Mengen A, B, und C gilt:(A B) C (A C ) (B C )A (B C ) (A B) (A C )(A B) C (A C ) (B C )A (B C ) (A B) (A C )Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201516 / 344

Mengentheoretische GrundlagenDefinition (Relationen und Funktionen)Seien A und B Mengen.Eine Relation von A nach B ist eine Teilmenge R A B.Eine (binäre) Relation auf A ist eine Teilmenge R A A.Eine Funktion (oder Abbildung) von A (dem Definitionsbereich) nach B(dem Wertebereich) ist eine Relation f A B, so dass für alle a Agenau ein b B mit (a, b) f existiert. Wir schreiben dann auchf (a) b.Wir schreiben auch f : A B für eine Funktion f von A nach B.Beispiel: Hier sind zwei Relationen von {a, b, c} nach N:R {(a, 1), (b, 2), (c, 1)} und Q {(a, 1), (a, 2), (b, 2), (c, 1)}Dann ist R eine Funktion, Q hingegen ist keine Funktion.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201517 / 344

Mengentheoretische GrundlagenEine Relation R A A kann man sich graphisch veranschaulichen.Beispiel: Sei A {1, 2, 3, 4, 5} und R die RelationR {(1, 2), (2, 3), (3, 4), (4, 1), (2, 5), (5, 5)}.Diese Relation kann durch folgendes Diagram visualisiert werden.43512Solche Diagramme werden wir im Kapitel über Graphentheorie nochgenauer studieren.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201518 / 344

Mengentheoretische GrundlagenDefinitionFür Mengen A und B sei B A die Menge aller Funktionen von A nach B.Definition (Bild und Urbild einer Funktion)Sei f : A B eine Funktion.Für A′ A sei f (A′ ) {f (a) a A′ } das Bild von A′ unter f .Für B ′ B sei f 1 (B ′ ) {a A f (a) B ′ } das Urbild von B ′unter f .Beispiel: Sei f : (N N) Z definiert durch f ((n, m)) n m fürn, m N. Dann gilt:f ({(n, m) n m}) { a a N}f 1 ({0}) {(a, a) a N}Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201519 / 344

Mengentheoretische GrundlagenEinfache Aussagen:Für alle Funktionen f : A B und alle A1 , A2 A giltf (A1 A2 ) f (A1 ) f (A2 ).Für alle Funktionen f : A B und alle B1 , B2 B giltf 1 (B1 B2 ) f 1 (B1 ) f 1 (B2 ).f 1 (B1 B2 ) f 1 (B1 ) f 1 (B2 ).Im Allgemeinen gilt nicht f (A1 A2 ) f (A1 ) f (A2 ).Beispiel: Sei f (a) c und f (b) c. Dann giltf ({a} {b}) f ( ) und f ({a}) f ({b}) {c}.Für alle Funktionen f : A B und A′ A, B ′ B giltA′ f 1 (f (A′ )) und f (f 1 (B ′ )) B ′ .Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201520 / 344

Mengentheoretische GrundlagenDefinition (injektive/surjektive/bijektive Funktionen)Eine Funktion f : A B is injektiv, falls für alle a, b A gilt:Wenn a 6 b gilt, muss auch f (a) 6 f (b) gelten(verschiedene Elemente werden auf verschieden Elemente abgebildet).Eine Funktion f : A B is surjektiv, falls für alle b B ein a A mitf (a) b existiert (jedes Element aus B wird durch f getroffen).Äquivalent: f (A) B.Eine Funktion f : A B is bijektiv, falls sie injektiv und surjektiv ist.Wir sagen auch, dass f eine Bijektion ist.Eine Bijektion f : A B ist eine 1-zu-1 Zuordnung zwischen denElementen aus A und B.Definition (Permutation)Eine Permutation der Menge A ist eine Bijektion f : A A.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201521 / 344

Mengentheoretische GrundlagenBeispiele:Die Funktion f : Z (Z \ {0}) Q mit f ((a, b)) ba ist surjektiv(jede rationale Zahl ist Quotient zweier ganzer Zahlen) aber nichtinjektiv (z. B. f ((1, 2)) f ((2, 4)) 0.5).Die Funktion f : N N mit f (n) n 1 ist injektiv (ausn 1 m 1 folgt n m) aber nicht surjektiv (es gibt keinenatürliche Zahl m mit m 1 0).Die Funktion f : Z Z mit f (n) n 1 ist bijektiv (also einePermutation).Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201522 / 344

Mengentheoretische GrundlagenEinfache Aussagen:f : A B is surjektiv genau dann, wenn für alle b B das Urbildf 1 (b) nicht leer ist.f : A B is injektiv genau dann, wenn für alle b B das Urbildf 1 (b) höchstens ein Element enthält.f : A B is bijektiv genau dann, wenn für alle b B das Urbildf 1 (b) genau ein Element enthält.Wenn f : A B injektiv ist, dann gilt für alle A′ A und a A:Aus f (a) f (A′ ) folgt a A′ .Für nicht-injektive Funktionen ist dies im Allgemeinen falsch.Wenn f : A B injektiv ist, dann gilt für alle A1 , A2 A:f (A1 A2 ) f (A1 ) f (A2 ).Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201523 / 344

Mengentheoretische GrundlagenDefinition (Umkehrfunktion)Für eine bijektive Funktion f : A B kann man die Umkehrfunktionf 1 : B A definieren durch folgende Vorschrift:f 1 (b) a genau dann, wenn f (a) bBeachte: Wenn f : A B bijektiv dann gibt es für jedes b B genau einElement a mit f (a) b.Daher ist die obige Definition von f 1 eindeutig!Die Umkehrfunktion einer Bijektion ist wieder eine Bijektion.Beispiel: Für die Bijektion f : Z Z mit f (n) n 1 giltf 1 (n) n 1.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201524 / 344

Mengentheoretische GrundlagenBeachte: Die Notation f 1 für die Umkehrfunktion ist konsistent mit derNotation f 1 (A′ ) für das Urbild.Genauer: Ist f : A B eine Bijektion, und ist g f 1 dieUmkehrfunktion von f , so gilt für jede Teilmenge B ′ B:f 1 (B ′ ) g (B ′ ).In Worten: Das Urbild von B ′ unter f ist gleich dem Bild von B ′ unter derUmkehrfunktion von f .Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201525 / 344

Mengentheoretische GrundlagenMittels des Begriffs der Bijektion können wir definieren, wann zweiMengen gleich groß sind.Definition (gleich-mächtig)Zwei Mengen A und B sind gleich-mächtig, kurz A B , falls eineBijektion f : A B existiert.Man schreibt auch A B (A is höchstens so mächtig wie B), falls eineinjektive Funktion f : A B existiert.Den folgenden Satz beweisen wir später.Satz 1 (Satz von Cantor, Schröder und Bernstein)Für alle Mengen A und B gilt: A B genau dann, wenn ( A B und B A ).Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201526 / 344

Mengentheoretische GrundlagenIn anderen Worten: Es existiert eine Bijektion von A nach B genau dann,wenn injektive Funktionen von A nach B sowie B nach A existieren.Für endliche Mengen A und B gilt A B falls A und B im intuitivenSinne gleich viele Elemente haben.Der Begriff “gleich-mächtig” kann jedoch auch auf unendliche Mengenangewendet werden.Beispiel: Die Mengen N und Z sind gleich-mächtig.Wir definieren eine Bijektion f : Z N wie folgt, wobei m Z:( (2m 1) falls m 0f (m) 2mfalls m 0Übung: Zeigen Sie, dass f tatsächlich bijektiv ist.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201527 / 344

Mengentheoretische GrundlagenEbenso sind die Mengen N, N N und Q gleich-mächtig.Eine Bijektion zwischen N N und N ist die Cantorsche Paarungsfunktionp : N N N mit1p(n1 , n2 ) (n1 n2 1)(n1 n2 ) n2 .2Alternativ kann man die Gleichmächtigkeit von N und N N mittels desSatzes von Cantor, Schröder und Bernstein zeigen, indem man injektiveFunktionen i1 : N N N und i2 : N N N angibt, z. B.i1 (n) (n, 0) und i2 (n1 , n2 ) 2n1 3n2 .(Injektivität von i2 folgt aus Satz 45.)Man kann auch zeigen, dass die Mengen 2N und R (Menge der reellenZahlen) gleich-mächtig sind.Aber: Nicht alle unendlichen Mengen sind gleich-mächtig.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201528 / 344

Mengentheoretische GrundlagenSatz 2 (Cantor 1891)Für jede Menge A sind A und 2A nicht gleich-mächtig.Beweis (durch Widerspruch): Sei A eine beliebige Menge.Angenommen es gäbe eine surjektive Funktion f : A 2A .Definiere die MengeB {a A a 6 f (a)} A.Da f surjektiv ist, gibt es ein b A mit f (b) B.Dann gilt:b B b 6 f (b) b 6 B.Also gibt es keine surjektive (und somit auch keine bijektive) Abbildungf : A 2A .Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201529 / 344

Mengentheoretische GrundlagenDefinition (abzählbar-unendlich, abzählbar, überabzählbar)Eine Menge A ist abzählbar-unendlich, falls A N gilt.Eine Menge A ist abzählbar, falls A endlich oder abzählbar-unendlich ist.Eine Menge A ist überabzählbar, falls A unendlich aber nicht abzählbar ist.Beispiele:Die Mengen N, N N, Z und Q sind abzählbar-unendlich.Die Mengen 2N , R und C (Menge der komplexen Zahlen) sindüberabzählbar.Das eine Menge A abzählbar-unendlich ist, bedeutet, dass man dieElemente der Menge A auflisten kann alsa1 , a2 , a3 , a4 , . . .wobei in dieser Liste jedes Element von A genau einmal vorkommt.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201530 / 344

Mengentheoretische GrundlagenEs gibt in der Mengenlehre durchaus sehr schwierige Fragen.Z. B. hat Georg Cantor folgende Vermutung aufgestellt:Kontinuumshypothese (Cantor 1878)Für jede unendliche Teilmenge A 2N gilt A N oder A 2N .Diese Vermutung konnte lange Zeit weder bewiesen noch widerlegtwerden. Dies ist unvermeidbar:Die Verneinung der Kontinuumshypothese kann nicht aus demAxiomensystem ZFC hergeleitet werden (Gödel 1938).Die Kontinuumshypothese kann nicht aus dem Axiomensystem ZFChergeleitet werden (Cohen 1966).Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201531 / 344

Mengentheoretische GrundlagenFür eine Relation R A A und a, b A schreiben wir auch aRb für(a, b) R.Definition ((ir)reflexive/(anti)symmetrische/transitive Relationen)Sei A eine Menge und R A A eine Relation auf A.R ist reflexiv, falls aRa für alle a A gilt.R ist irreflexiv, falls kein a A mit aRa existiert.R ist symmetrisch, falls für alle a, b A gilt:Wenn aRb, dann auch bRa.R ist antisymmetrisch, falls für alle a, b A gilt:Wenn aRb und bRa, dann a b.R ist transitiv, falls für alle a, b, c A gilt:Wenn aRb und bRc, dann auch aRc.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201532 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Ist R irreflexiv?Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Ist R irreflexiv?Ja: Würde a R a gelten, so wäre 2a 43. Aber in Z gibt es einesolche Zahl a nicht.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Ist R irreflexiv?Ja: Würde a R a gelten, so wäre 2a 43. Aber in Z gibt es einesolche Zahl a nicht.Ist R symmetrisch?Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Ist R irreflexiv?Ja: Würde a R a gelten, so wäre 2a 43. Aber in Z gibt es einesolche Zahl a nicht.Ist R symmetrisch?Ja: Wenn a R b, dann a b 43. Dann gilt aber auch b a 43,d.h. b R a.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Ist R irreflexiv?Ja: Würde a R a gelten, so wäre 2a 43. Aber in Z gibt es einesolche Zahl a nicht.Ist R symmetrisch?Ja: Wenn a R b, dann a b 43. Dann gilt aber auch b a 43,d.h. b R a.Ist R antisymmetrisch?Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Ist R irreflexiv?Ja: Würde a R a gelten, so wäre 2a 43. Aber in Z gibt es einesolche Zahl a nicht.Ist R symmetrisch?Ja: Wenn a R b, dann a b 43. Dann gilt aber auch b a 43,d.h. b R a.Ist R antisymmetrisch?Nein: Es gilt z.B. 0 R 43 und 43 R 0 aber 0 6 43.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Ist R irreflexiv?Ja: Würde a R a gelten, so wäre 2a 43. Aber in Z gibt es einesolche Zahl a nicht.Ist R symmetrisch?Ja: Wenn a R b, dann a b 43. Dann gilt aber auch b a 43,d.h. b R a.Ist R antisymmetrisch?Nein: Es gilt z.B. 0 R 43 und 43 R 0 aber 0 6 43.Ist R transitiv?Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenBeispiel: Betrachte die RelationR {(a, b) Z Z a b 43}.Ist R reflexiv?Nein: Es gilt z.B. nicht 0 R 0.Ist R irreflexiv?Ja: Würde a R a gelten, so wäre 2a 43. Aber in Z gibt es einesolche Zahl a nicht.Ist R symmetrisch?Ja: Wenn a R b, dann a b 43. Dann gilt aber auch b a 43,d.h. b R a.Ist R antisymmetrisch?Nein: Es gilt z.B. 0 R 43 und 43 R 0 aber 0 6 43.Ist R transitiv?Nein: Es gilt z.B. 0 R 43 und 43 R 0 aber nicht 0 R 0.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201533 / 344

Mengentheoretische GrundlagenDefinition (partielle Ordnung)Eine Relation R A A ist eine partielle Ordnung (auf A), falls Rreflexiv, antisymmetrisch, und transitiv ist.Definition (lineare Ordnung)Eine partielle Ordnung R auf A ist eine lineare Ordnung (auf A), falls füralle a, b A gilt: aRb oder bRa.Beispiel 1 (Teilmengenbeziehung oder Inklusion): Sei A eine beliebigeMenge. Dann ist eine partielle Ordnung auf 2A .Falls A mindestens zwei Elemente enthält, ist jedoch keine lineareOrdnung auf 2A : Sei A {1, 2}. Dann gilt weder {1} {2} noch{2} {1}.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201534 / 344

Mengentheoretische GrundlagenBeispiel 2: Die Relation ist eine lineare Ordnung auf N, Z, Q und R.Beispiel 3 (Teilbarkeit): Wir definieren die binäre Relation auf denganzen Zahlen Z wie folgt, wobei a, b Z.a b genau dann, wenn q Z : q · a bDie Relation ist reflexiv und transitiv, sie ist jedoch nichtantisymmetrisch, denn für alle a Z gilt a a und a a.Betrachten wir jedoch als eine binäre Relation auf den natürlichen ZahlenN, so ist eine partielle Ordnung, aber keine lineare Ordnung: Es giltweder 2 3 noch 3 2.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201535 / 344

Mengentheoretische GrundlagenDefinition (Äquivalenzrelation)Eine Relation R A A ist eine Äquivalenzrelation (auf A), falls Rreflexiv, symmetrisch und transitiv ist.Beispiel 1: Für jede Menge A ist die RelationIdA {(a, a) a A}(die Identitätsrelation) reflexiv, symmetrisch, antisymmetrisch, undtransitiv. Insbesondere ist IdA eine Äquivalenzrelation.Beispiel 2: Sei f : A B eine Funktion. Dann ist{(a1 , a2 ) A A f (a1 ) f (a2 )}eine Äquivalenzrelation.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201536 / 344

Mengentheoretische GrundlagenBeispiel 3: Sei q Z \ {0} eine ganze Zahl. Auf der Menge Z definierenwir die Relation q {(a, b) a, b Z, q (a b)}.Sprechweise für a q b: a und b sind kongruent modulo q.Es gilt a q b genau dann, wenn eine ganze Zahl x Z mit a b x · qexistiert.Beachte: a q b genau dann, wenn a q b.Lemma 3Für jede Zahl q Z \ {0} ist q eine Äquivalenzrelation auf Z.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201537 / 344

Mengentheoretische GrundlagenBeweis: Sei q Z \ {0}.(1) q ist reflexiv, denn q (a a) (d. h. q 0) gilt für jede ganze Zahl a.(2) q ist symmetrisch: Gelte a q b, d. h. q (a b).Wegen (b a) (a b) gilt dann auch q (b a), d. h. b q a.(3) q ist transitiv: Seien a, b, c Z mit a q b und b q c.Also existieren ganze Zahlen p, s Z mita b qp und b c qs.Dann gilta c (a b) (b c) qp qs q(p s).Also gilt a q c.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201538 / 344

Mengentheoretische GrundlagenDefinition (Äquivalenzklassen)Sei R eine Äquivalenzrelation auf der Menge A und sei a A. Dann ist[a]R {b A aRb} die Äquivalenzklasse von a (bzgl. R).Beachte: Es gilt stets a [a]R (denn eine Aquivalenzrelation ist reflexiv).Eine Äquivalenzklasse kann also nie leer sein, und jedes Element von Agehört zu einer Äquivalenzklasse.Satz 4Sei R eine Äquivalenzrelation auf der Menge A und seien a, b A. Dannsind folgende drei Aussagen äquivalent:(1) aRb(2) [a]R [b]R(3) [a]R [b]R 6 .Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201539 / 344

Mengentheoretische GrundlagenBeweis (durch Ringschluss):(1) impliziert (2): Gelte aRb und damit auch bRa (R ist symmetrisch).Wir zeigen zunächst [a]R [b]R .Sei also c [a]R , d. h. es gilt aRc.bRa, aRc und R transitiv bRc, d. h. c [b]R .Analog kann man [b]R [a]R zeigen.(2) impliziert (3): Gelte [a]R [b]R .Dann gilt a [a]R [b]R und damit [a]R [b]R 6 .(3) impliziert (1): Gelte [a]R [b]R 6 .Also gibt es ein c mit c [a]R und c [b]R . aRc und bRc; und damit auch cRb (R ist symmetrisch). aRb, wegen R transitiv.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201540 / 344

Mengentheoretische GrundlagenBeispiele:Die Äquivalenzklassen der Identitätsrelation IdA sind dieeinelementigen Mengen {a} mit a A.Die Äquivalenzklassen der Relation {(a1 , a2 ) A A f (a1 ) f (a2 )}(für f : A B eine Funktion) sind die Urbilder f 1 (b) für b B.Die Äquivalenzklassen von q (für q N \ {0}) sind die Mengen{0 pq p Z}{1 pq p Z}.{(q 1) pq p Z}Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201541 / 344

Mengentheoretische GrundlagenSei R wieder eine Äquivalenzrelation auf der Menge A.Seien {Ai i I } die Menge aller Äquivalenzklassen von R, d. h.Für jedes a A gibt es ein i I mit [a]R AiFür alle i , j I mit i 6 j gilt Ai 6 Aj .Aufgrund von Satz 4 bildet {Ai i I } 2A eine Partition von A, d. h.Si I Ai A i I : Ai 6 . i , j I : i 6 j Ai Aj (verschiedene Ai sind disjunkt)Ist umgekehrt {Ai i I } eine Partition von A, so kann man eineÄquivalenzrelation R auf A definieren durch:R {(a, b) a, b A, i I : a, b Ai }Übung: Zeigen Sie, dass dies tatsächlich eine Äquivalenzrelation ist.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201542 / 344

Mengentheoretische GrundlagenDa eine Relation R A B eine Menge (von Paaren) ist, können wir dieOperationen und auch auf Relationen anwenden.Es gibt aber noch zwei weitere wichtige Operationen auf Mengen:Definition (R 1 , R S)Seien R A B und S B C binäre Relationen. Dann definieren wir:R 1 {(b, a) B A (a, b) R}R S {(a, c) A C b B : (a, b) R und (b, c) S}R 1 ist die Umkehrrelation von R.R S ist die Komposition (oder Verknüpfung) von R und S.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201543 / 344

Mengentheoretische GrundlagenBeispiel 1: SeiR {(a, 1), (b, 1), (b, 2)} und S {(1, x), (1, y ), (2, y )}Dann gilt:R 1 {(1, a), (1, b), (2, b)}R S {(a, x), (a, y ), (b, x), (b, y )}Beispiel 2: Sei R eine lineare Ordnung auf der Menge A. Dann giltR R 1 IdAR R 1 A ALohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201544 / 344

Mengentheoretische GrundlagenEin wichtiger Spezialfall der Komposition von Relationen ist dieKomposition von Funktionen:Wenn f : A B und g : B C Funktionen sind, dann ist f g : A Ceine Funktion und es gilt(f g )(a) g (f (a))für alle a A.Vorsicht: Manchmal wird die Funktion f g auch durch die Vorschrift(f g )(a) f (g (a)) definiert.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201545 / 344

Mengentheoretische GrundlagenBemerkungen: Sei R A A eine Relation auf A.R is reflexiv, genau dann, wenn IdA R.R is irreflexiv, genau dann, wenn IdA R .R ist symmetrisch, genau dann, wenn R 1 R.R is transitiv, genau dann, wenn R R R.R is antisymmetrisch, genau dann, wenn R R 1 IdA .Für alle binären Relationen R, S und T auf der Menge A gilt:R IdA IdA R R(R S) T R (S T )(R S) 1 S 1 R 1Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/201546 / 344

Mengentheoretische GrundlagenIst die Relation R A B eine Bijektion (also insbesondere eineFunktion) dann ist die Umkehrrelation R 1 genau dieUmkehrfunktion von R.Wenn f : A B und g : B C injektiv sind, dann ist auch f ginjektiv.Wenn f : A B und g : B C surjektiv sind, dann ist auch f gsurjektiv.Wenn f : A B und g : B C bijektiv sind, dann ist auch f gbijektiv.Konsequenz: Sei M eine Menge von Mengen. Dann ist Relation{(X , Y ) M M X Y }eine Äquivalenzrelation.Lohrey (Universität Siegen)Diskrete MathematikWintersem. 2014/2

Dies mag schwierig zu vermeiden sein, ist doch der Mengenbegriff das fundamentalste Konzept der Mathematik. Alle Objekte der Mathematik k onnen als Mengen aufgefasst werden. Wie sollte man also den Mengenbegriff in der Sprache der Mathematik formalisieren? Logiker habe