Mengenlehre Und Logik

Transcript

Mengenlehre und Logik Handout 1 zum Mathematik-Brückenkurs Carl Hammann, µFSR, TU Dresden Version vom 30. September 2015, Fehler und Verbesserungsvorschläge bitte an [email protected] 1.1 Aussagen Mathematik und Logik sind eng miteinander verwandt, denn in beiden Wissenschaften ist und sehr daran gelegen, dass alle Begriffe eine klare und scharf umrissene Bedeutung haben. Logik hat Aussagen zum Gegenstand. Wir geben eine umgangssprachliche Definition. Definition 1.1 (Aussage). Eine Aussage ist ein Ausdruck aus natürlicher Sprache und (mathematischer oder anderer) Notation, für den man sinnvoll entscheiden kann, ob er wahr oder falsch ist. Aufgabe 1.1. Welche der folgenden Ausdrücke sind Aussagen? Begründe! Wenn der Ausdruck eine Aussage ist, entscheide, ob sie wahr oder falsch ist! 1. 1 + 1 = 2 2. In Dresden ist das Wetter gut. 3. Ich mag Mathematik. 4. Johann Sebastian Bach. 5. Pferde sind Paarhufer. 6. Dieser Satz ist eine Aussage. 7. Dieser Satz ist keine Aussage. 8. Dieser Satz ist eine wahre Aussage. 9. Dieser Satz ist eine falsche Aussage. 1 1.2 Logische Junktoren Logische Junktoren konstruieren aus gegebenen Aussagen eine neue Aussage. Definition 1.2 (logischer Junktor, Wahrheitstabelle). Für zwei Aussagen a und b sind die logischen Junktoren definiert durch folgende Tabelle: a 0 0 1 1 b 0 1 0 1 a 0 0 1 1 b 0 1 0 1 Negation ¬a 1 1 0 0 Implikation a⇒b 1 1 0 1 Disjunktion (Oder) a∨b 0 1 1 1 Äquivalenz a⇔b 1 0 0 1 Konjunktion (Und) a∧b 0 0 0 1 exklusives Oder a⊕b 0 1 1 0 Tabelle 1: Wahrheitstabelle der logischen Junktoren Die Tabelle nennt man eine Wahrheitstabelle. Sie ist folgendermaßen zu verstehen: Die Eins steht für „wahr“, die Null für „falsch“. Im Kopf rechts neben dem Doppelstrich stehen zusammengesetzte Aussagen, links neben dem Doppelstrich stehen die Teilaussagen. In jeder Zeile steht unter der zusammengesetzten Aussage ihr Wahrheitswert in Abhängigkeit von den Wahrheitswerten ihrer Teilaussagen. Definition 1.3 (Präzedenz der logischen Junktoren). Um Klammern zu sparen, versehen wir die logischen Operatoren mit einer Präzedenzreihenfolge: ¬ ∧, ∨, ⊕ ⇒, ⇔ Junktoren, die hier weiter oben stehen, binden stärker als die, die weiter unten stehen. Das bedeutet, dass z.B. der Ausdruck ¬ a ∧ b ⇒ c und der Ausdruck ((¬ a) ∧ b) ⇒ c das Selbe bedeuten sollen. Aufgabe 1.2. Stelle die Wahrheitstabellen für folgende Aussagen auf: a ⇒ b, b ⇒ a, ¬ a ∨ b, ¬b ⇒ ¬ a, a ⇔ b, ( a ⇒ b) ∧ (b ⇒ a), a ⊕ b, ( a ∨ b) ∧ ¬( a ∧ b). Was fällt dir auf? Formuliere die gefundenen logischen Sachverhalte in natürlicher Sprache und gib Beispiele. Aufgabe 1.3. Beweise die De Morgan’schen Regeln: ¬( a ∨ b) = ¬ a ∧ ¬b und ¬( a ∧ b) = ¬ a ∨ ¬b für Aussagen a und b. Was bedeuten sie in natürlicher Sprache? 2 Aufgabe 1.4. Gibt es eine zusammengesetzte Aussage mit Teilaussagen a, b und c (jede mindestens einmal!), die genau die Junktoren ∧ und ∨ benutzt (jeden mindestens einmal!), und bei der Klammersetzung den Wahrheitswert nicht verändert? Begründe! 1.3 Quantoren Man möchte auch Aussagen wie „Es gibt eine Zahl, die größer ist als 5“ oder „Alle nichttrivialen Nullstellen der Riemann’schen Zetafunktion haben Realteil 1/2“ formal logisch aufschreiben können. Definition 1.4 (Quantor, Individuenbereich). Der Allquantor ∀ und der Existenzquantor ∃ werden wie folgt verwendet, um Aussagen zu bilden: Für eine Aussage A( x ), die von x abhängt (z.B. „x ist blau“), werden folgende neue Aussagen erklärt: Schreibweise ∃ x : A( x ) ∃!x : A( x ) ∀ x : A( x ) @x : A( x ) Sprechweise „Es gibt (mindestens) ein x, sodass A( x ) gilt.“ „Es gibt genau ein x, sodass A( x ) gilt.“ „Für alle x gilt A( x ).“ „Es gibt kein x, sodass A( x ) gilt.“ Tabelle 2: die Quantoren Die Gesamtheit aller Gegenstände x, über die man die Aussagen mit Quantoren bildet, wird Individuenbereich oder Diskursuniversum genannt. Wenn nichts weiter gesagt ist, nehmen wir als Individuenbereich schlicht alle Objekte der Welt und unseres Denkens. Man kann insbesondere Aussagen mit mehreren Quantoren schreiben: Sei der Individuenbereich die Gesamtheit aller Menschen. Bezeichne L( a, b) die Aussage „a liebt b.“. Dann kann man die Aussage „Jeder Mensch liebt (mindestens) einen Menschen“ als ∀ a∃b : L( a, b) schreiben. Hier ist zu beachten, dass die Reihenfolge der Quantoren wichtig ist: ∃b∀ a : L( a, b) bedeutet nämlich „Es gibt (mindestens) einen Menschen, den alle Menschen lieben“. Aufgabe 1.5. Sei der Individuenbereich die Gesamtheit aller Menschen. Schreibe die folgenden Aussagen mit Quantoren, wobei du nur die Aussagen K ( x, y, z) für „z ist ein Kind von x und y“ und M( x ) für „x ist männlich“ verwendest! Für die Zwecke dieser Aufgabe (und nur dafür) nehmen wir an, dass jeder Mensch entweder männlich oder nicht männlich, was weiblich sei, ist. 1. a ist ein Einzelkind. 2. a ist ein Cousin von b. 3. a hat genau eine Schwester. 3 4. Niemand ist sein eigener Vater. Aufgabe 1.6. Schreibe die Aussagen ∃!x : A( x ) und @x : A( x ), wobei du nur die Quantoren ∃ und ∀ verwendest! Aufgabe 1.7. Verneine die Aussagen ∀ x : A( x ) und ∃ x : A( x )! Welches Prinzip fällt dir auf? Kann man es auch auf eine Aussage wie ∀ x ∃y, z : B( x, y, z) anwenden? Wie verhalten sich die Quantoren @ und ∃!? Aufgabe 1.8. Gib jeweils beispielhafte Aussagen A( x ) und B( x ) (und einen Individuenbereich) an, die belegen, dass im Allgemeinen (∀ x : A( x ) ∨ B( x )) 6= (∀ x : A( x )) ∨ (∀ x : B( x )) und (∃ x : A( x ) ∧ B( x )) 6= (∃ x : A( x )) ∧ (∃ x : B( x ))! 1.4 Was ist eine Menge? Wir betreiben hier die sog. naive Mengenlehre. Unter einer „Menge“ verstehen wir jede Zusammenfassung M von wohlunterschiedenen Objecten m unserer Anschauung oder unseres Denkens (welche die „Elemente“ von M genannt werden) zu einem Ganzen. – Georg Cantor Schreibweisen: • Mengen schreiben wir mit den geschwungenen Klammern „{“ und „}“ begrenzt. • Wir können die Elemente einer Menge aufzählen, wie in {13, Γ, grün, ∞} oder auch {1, 2, 4, 8, 16, . . .}, wenn klar ist, wie die Aufzählung weitergehen soll. • Aussagen wie „3 ist Element der Menge M“ schreiben wir folgendermaßen: 3 ∈ M. Aussagen wie „5 ist nicht Element der Menge M“ schreiben wir folgendermaßen: 5 6∈ M. • Wir können Mengen auch in der Form { x | A( x )} schreiben, wobei A( x ) eine Aussage über x ist. Diese Schreibweise bedeutet, dass die Menge alle x enthalten soll, für die A( x ) wahr ist. Weiterhin scheiben wir für eine Menge M auch { x ∈ M | A( x )} und meinen damit die Menge { x | x ∈ M ∧ A( x )}. Bemerkungen: • Extensionalität: Eine Menge ist allein durch ihre Elemente bestimmt. Reihenfolge oder Darstellung sind nicht entscheidend. • Menge enthält jedes ihrer Elemente genau einmal. • Weder der Begriff der Menge noch der Begriff des Elements sind streng formal definiert. Auch werden sie in den Axiomen der Zermelo-Fraenkel-Mengenlehre, die das Fundament der modernen Mathematik bildet, nicht definiert. Vielmehr ergeben sich die Bedeutungen durch die axiomatisch festgelegten Beziehungen zwischen den Begriffen. 4 Noch mehr Schreibweisen: Für eine Menge M und Aussagen A( x ), B( x ) schreiben wir Schreibweise ∀ x ∈ M : A( x ) ∃ x ∈ M : B( x ) Bedeutung ∀ x : x ∈ M ⇒ A( x ) ∃ x : x ∈ M ∧ B( x ) Sprechweise „Für alle x ∈ M gilt A( x ).“ „Es gibt ein x ∈ M, für das B( x ) gilt.“ Definition 1.5 (Obermenge und Untermenge). Seien A und B zwei Mengen. • A und B heißen gleich, geschrieben A = B genau dann, wenn ∀ x : x ∈ A ⇔ x ∈ B. • A heißt Teilmenge oder Untermenge von B, geschrieben A ⊆ B genau dann, wenn ∀ x : x ∈ A ⇒ x ∈ B. • A heißt Obermenge von B, geschrieben A ⊇ B, wenn B eine Untermenge von A ist. • A heißt echte Teilmenge oder echte Untermenge von B, geschrieben A ( B, falls (∀ x : x ∈ A ⇒ x ∈ B) ∧ (∃ x : x ∈ B ∧ x 6∈ A). • A heißt echte Obermenge von B, falls B eine echte Untermenge von A ist. Aufgabe 1.9. Seien A( x ), B( x ) Aussagen mit A( x ) ⇒ B( x ). Zeige, dass dann { x | A( x )} ⊆ { x | B( x )}! Aufgabe 1.10. Zeige, dass für zwei Mengen A und B gilt, dass A = B ⇔ ( A ⊆ B) ∧ ( B ⊆ A)! (Diese Eigenschaft wird oft verwendet, um zu zeigen, dass zwei Mengen gleich sind.) Aufgabe 1.11. Beweise, dass jede Menge eine Obermenge der leeren Menge ist! 1.5 Mengenkonstruktionen Wir wollen aus gegebenen Mengen neue Mengen konstruieren. Definition 1.6 (Schnittmenge, Vereinigungsmenge, Differenz, symmetrische Differenz). Seien A und B Mengen. Dann bezeichnet • A ∪ B die Vereinigungsmenge von A und B, die definiert ist durch ∀ x : ( x ∈ A) ∨ ( x ∈ B) ⇔ x ∈ ( A ∪ B) • A ∩ B die Schnittmenge von A und B, die definiert ist durch ∀ x : ( x ∈ A) ∧ ( x ∈ B) ⇔ x ∈ ( A ∩ B) • A \ B die Differenzmenge von A und B, die definiert ist durch ∀ x : ( x ∈ A) ∧ ( x 6∈ B) ⇔ x ∈ ( A \ B) • A4 B die symmetrische Differenz von A und B, die definiert ist durch ∀ x : ( x ∈ A) ⊕ ( x ∈ B) ⇔ x ∈ ( A4 B) 5 Aufgabe 1.12. Beweise, dass die symmetrische Differenz tatsächlich symmetrisch ist, d.h. dass für je zwei Mengen A und B gilt, dass A4 B = B4 A! Dazu kannst du entweder direkt anhand der Definition arbeiten oder die Aussage von Aufgabe 1.10 verwenden oder zuerst (z.B. mit einem Venn-Diagramm) beweisen, dass A4 B = ( A \ B) ∪ ( B \ A) und dann benutzen, dass für beliebige Mengen M und N die Aussage M ∪ N = N ∪ M in offensichtlicher Weise gilt. Definition 1.7 (Potenzmenge). Sei A eine Menge, dann ist die Potenzmenge P( A) von A definiert als die Menge aller Teilmengen von A. Aufgabe 1.13. Schreibe die Potenzmenge der Menge A := {∅, {∅}} auf! Gibt es eine Menge, deren Potenzmenge A ist? Aufgabe 1.14. Die Menge A habe n Elemente. Erkläre, warum P( A) dann 2n Elemente hat! Definition 1.8 (kartesisches Produkt). Seien A und B Mengen. Dann ist das kartesische Produkt A × B definiert als die Menge der Paare ( a, b), sodass a ∈ A und b ∈ B. Aufgabe 1.15. Seien A und B Mengen. Beweise A × B = ∅ ⇔ A = ∅ ∨ B = ∅! Aufgabe 1.16. Sei A eine Menge mit n Elementen und B eine Menge mit m Elementen. Wie viele Elemente hat A × B? Begründe! Aufgabe 1.17. Wir alle kennen aus der Schule das Distributivgesetz der Multiplikation und Addition reller Zahlen: Für a, b, c ∈ R gilt a · (b + c) = a · b + a · c. Für welche der bis jetzt definierten Mengenoperationen gelten auch Distributivgesetze? Wenn Distributivgesetze gelten, gibt sie an! Ebenso wissen wir, dass die Addition reller Zahlen monoton ist, das heißt, für Zahlen a, b, α, β ∈ R gilt a ≤ α ∧ b ≤ β ⇒ a + b ≤ α + β. Welche der bis jetzt definierten Mengenoperationen sind monoton (wobei man natürlich „≤“ mit „⊆“ ersetzen muss)? Du kannst dir, wenn du unsicher bist, mit Venn-Diagrammen helfen. 1.6 Gewitterwolken am Horizont Die Russel’sche Antinomie (1903): Enthält die Menge aller Mengen, die sich nicht selbst enthalten, sich selbst? Unsere naive Mengenlehre enthält Paradoxa. Man kann diese Probleme aber unter (sehr großem) Aufwand umgehen. Der erste Unvollständigkeitssatz von Gödel (1931): Jedes hinreichend mächtige, rekursiv aufzählbare formale System ist entweder widersprüchlich oder unvollständig. Das Konzept von Wahrheit ist nicht mit dem Konzept von Beweisbarkeit vereinbar. Diese beiden Aussaagen werden in der Stunde genauer diskuitert. 6