Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 7
- Übungsaufgaben
Es sei eine Menge und eine Ordnung auf . Zeige durch Induktion über die Aussage: Wenn für Elemente die Beziehung
und
gilt, dann sind alle gleich.
Es sei eine endliche total geordnete Menge. Es sei eine endliche Indexmenge. Definiere auf der Produktmenge
die „lexikographische Ordnung“, und zeige, dass es sich dabei ebenfalls um eine totale Ordnung handelt.
Kommentar:
Wie in Beispiel 7.5 erläutert, stammt der Name „lexikographische Ordnung“ von der Art und Weise, wie Wörter in einem Wörterbuch angeordnet sind. Wenn z.B. das deutsche Alphabet ist, dann ist eine geordnete Menge mit der offensichtlichen totalen Ordnung:
< a < ä < b < c < < x < y < z,
wobei das Leerzeichen bezeichnet. Diese Ordnung induziert die sogenannte „lexikographische Ordnung“ auf die Menge aller deutschen Wörter, die verwendet wird, um Wörter in einem Wörterbuch anzuordnen: wenn man zwei Wörter und (z.B. = "Vorlesung" und = "Vorlesen") vergleichen möchte, werden die Wörter zunächst als gleich lang angesehen, indem dem kürzeren Wort Leerzeichen hinzugefügt werden (z.B. = "Vorlesung" und = "Vorlesen"). Dann definiert man (d.h. kommt vor in einem Wörterbuch, das beide Wörter enthält) wenn an der ersten Stelle von vorne gelesen, wo sich und unterscheiden, der Buchstabe von an dieser Stelle kleiner als der Buchstaben von an dieser Stelle ist (also "Vorlesen" < "Vorlesung", da V = V, o = o, r = r, l = l, e = e, s = s, e < u).
Die obigen Überlegungen können direkt auf jede total geordnete Menge erweitert werden: Für mit definiert man falls oder ein existiert mit
Man überprüft leicht, dass dies eine Ordnung auf ist. Die Linearität sieht man so: wenn , dann existiert ein mit . Da eine total geordnete Menge ist, gilt entweder oder . Somit ist entweder oder .
Wir definieren auf eine neue Relation durch folgende Vorschrift: Für zwei Zahlen mit und mit ungerade sei
(rechts wird auf die natürliche Ordnung in Bezug genommen).
- Zeige, dass eine totale Ordnung auf ergibt und beschreibe exemplarisch diese Ordnung.
- Zeige, dass es zu jedem ein wohldefiniertes Element , , derart gibt, dass gilt und dass es zwischen und keine weiteren Elemente gibt (diese Formulierung ist zu präzisieren).
- Erfüllt die Menge die Dedekind-Peano-Axiome?
Es sei eine endliche total geordnete Menge. Definiere für ein geeignetes eine ordnungstreue bijektive Abbildung
wobei mit der natürlichen Ordnung versehen sei.
Es sei eine endliche Menge. Betrachte die Relation auf der Potenzmenge , die durch
gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?
Zeige, dass die Produktordnung auf in der Tat eine Ordnung ist.
Es sei eine total geordnete Menge. Zeige durch Induktion, dass jede nichtleere endliche Teilmenge ein eindeutiges Maximum besitzt.
Zeige durch Induktion, dass jede nichtleere Teilmenge ein kleinstes Element besitzt.
Es sei eine Menge und die Menge der echten Teilmengen von , also
Diese Menge ist durch die Inklusion eine geordnete Menge. Bestimme die minimalen und die maximalen Elemente von .
Eine totale Ordnung auf einer Menge heißt Wohlordnung, wenn jede nichtleere Teilmenge ein kleinstes Element besitzt.
Zeige, dass die natürliche Ordnung auf den ganzen Zahlen keine Wohlordnung ist.
Definiere eine Wohlordnung auf der Menge der ganzen Zahlen .
Kommentar:
Der Wohlordnungssatz besagt, dass jede Menge wohlgeordnet werden kann. Es ist aber im Allgemeinen schwierig, eine Wohlordnung zu konstruieren: bis heute ist keine explizite Wohlordnung auf den reellen Zahlen bekannt. Für "kleine" Mengen wie ist jedoch die Konstruktion einer expliziten Wohlordnung möglich. Der Grund ist, dass und die gleiche Mächtigkeit haben und dass bekanntermaßen wohlgeordnet ist (siehe Aufgabe 7.9). Um eine Wohlordnung auf zu definieren, reicht es also aus, eine Nummerierung von (d.h. eine Bijektion ) zu konstruieren. Eine solche Nummerierung ist
und die entsprechende Wohlordnung auf definiert man so: falls oder und .
Es sei eine total geordnete Menge, die sowohl nach unten als auch nach oben wohlgeordnet ist. Zeige, dass endlich ist.
Beweise das Lemma von Dickson, das besagt, dass eine nichtleere Teilmenge nur endlich viele minimale Elemente besitzt.
Kommentar:
Zuerst soll man sich klar machen, welche Ordnung auf berücksichtigt wird. Diese ist keine lexikographische Ordnung, die in Aufgabe 7.2 betrachtet wurde. Für die lexikographische Ordnung ist die Aussage des Lemmas von Dickson ganz trivial (wieso?) und nicht nützlich. Die Ordnung auf , die wir hier betrachten, ist die Produktordnung (das ist auch die Ordnung in Beispiel 7.12, wenn man dort
und statt nimmt): Für definiert man , wenn
Diese ist klar eine Ordnung auf , jedoch keine totale Ordnung für . Eine Motivation für die Produktordnung kommt aus der Teilbarkeitsrelation innerhalb eines Polynomrings: das Mononom teilt das Mononom genau dann, wenn .
Aus dem Induktionsprinzip folgt, dass die natürlichen Zahlen wohlgeordnet sind, d.h. jede nichtleere Teilmenge besitzt ein kleinstes Element (siehe Aufgabe 7.9). Also gilt das Lemma von Dickson für . Für ist es eine natürliche Idee, Induktion über zu verwenden. Der Einfachheit halber betrachten wir nur den Fall . Es empfiehlt sich, die Sache geometrisch in der Ebene vorzustellen. Die minimalen Elemente von sind dann die Randpunkte mit ganzzahligen Koordinaten, wenn man reell auffüllt (die konvexe Hülle nimmt). Die Aussage ist dann, dass es nur endlich viele solche Randpunkte gibt.
Wäre das Lemma falsch, würde eine Teilmenge existieren, die unendlich viele minimale Elemente
besitzt. Die Minimalität der Elemente bedeutet, dass man nicht und für vergleichen kann. Also gilt entweder und oder und . Um die Induktionsvoraussetzung anzuwenden, betrachtet man die Mengen
Da wohlgeordnet ist, besitzt ein kleinstes Element, das man ohne Einschränkung als annehmen kann. Dann ist es klar, dass das größte Element von ist. Nun betrachtet man die Mengen
Wie oben kann man annehmen, dass das kleinste Element von ist. Dies folgt, dass das größte Element von ist. Wenn man diesen Prozess fortsetzt, kann man davon ausgehen, dass
Die zweite Bedingung impliziert jedoch, dass die Menge kein kleinstes Element besitzt, ein Widerspruch.
Das Lemma von Dickson spielt eine Rolle beim Beweis des Hilbertschen Basissatzes, der besagt, dass der Polynomring über einem Körper noethersch ist, d.h. jedes Ideal von ein endliches Erzeugendensystem besitzt.
Wir betrachten mit der Produktordnung. Bestimme die minimalen und die maximalen Elemente des Einheitskreises, versehen mit der induzierten Ordnung.
Besitzt die Menge der natürlichen Zahlen in eine obere Schranke? Wie sieht das in anderen angeordneten Körpern aus?
Zu sei
Zu jedem und jedem seien die Abbildungen
durch
und die Abbildungen
durch
definiert.
a) Erstelle eine Wertetabelle für
b) Erstelle eine Wertetabelle für
c) Beschreibe die durch die Wertetabelle
als eine Hintereinanderschaltung von geeigneten und .
Zeige, dass für natürliche Zahlen die folgenden Teilbarkeitsbeziehungen gelten.
- Für jede natürliche Zahl gilt und .
- Für jede natürliche Zahl gilt .
- Gilt und , so gilt auch .
- Gilt und , so gilt auch .
- Gilt , so gilt auch für jede natürliche Zahl .
- Gilt und , so gilt auch für beliebige natürliche Zahlen .
Bringe die Teilbarkeit einer natürlichen Zahl durch eine natürliche Zahl mit dem Begriff der Produktmenge in Zusammenhang.
Es sei . Zeige, dass das Produkt von aufeinanderfolgenden natürlichen Zahlen von geteilt wird.
Es sei die Menge der positiven natürlichen Zahlen mit der Teilbarkeitsrelation und die gleiche Menge mit der natürlichen Ordnungsstruktur. Zeige, dass die identische Abbildung
ordnungstreu, aber nicht ordnungsvolltreu ist.
Es sei die Menge aller unendlichen Teilmengen von , versehen mit der Inklusion als Ordnung, und es sei das rechtsseitig offene reelle Einheitsintervall mit der Kleinergleich-Relation als Ordnung. Zeige, dass die Abbildung
eine bijektive, ordnungstreue Abbildung ist, deren Umkehrabbildung nicht ordnungstreu ist.
Es sei die Menge aller reellen Folgen, versehen mit der Produktordnung und sei die Teilmenge aller konvergenten Folgen. Zeige, dass die Abbildung
ordnungstreu, aber nicht ordnungsvolltreu ist.
- Aufgaben zum Abgeben
Aufgabe (1 Punkt)
Skizziere ein Inklusionsdiagramm für sämtliche Teilmengen einer dreielementigen Menge.
Aufgabe (3 Punkte)
Bestimme auf einer vierelementigen Menge sämtliche Ordnungen bis auf Isomorphie (die Rolle der Elemente darf also vertauscht werden).
Aufgabe (3 Punkte)
Es sei eine geordnete Menge und die Potenzmenge von . Zeige, dass die Abbildung
ordnungsvolltreu und injektiv ist, wobei die Potenzmenge mit der Inklusion versehen ist.
Aufgabe (4 Punkte)
Zeige, dass es keine Abbildung
gibt, die die folgende Eigenschaft erfüllt: Es ist genau dann, wenn .
Aufgabe (3 (2+1) Punkte)
- Es sei eine endliche geordnete Menge mit einem einzigen maximalen Element . Zeige, dass das größte Element von ist.
- Man gebe ein Beispiel für eine geordnete Menge mit genau einem maximalen Element, das aber nicht das größte Element ist.
<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> |
---|