Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 7



Übungsaufgaben

Aufgabe *

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.


Aufgabe

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.


Aufgabe

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).

  1. Zeige, dass eine totale Ordnung auf ergibt und beschreibe exemplarisch diese Ordnung.
  2. 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).
  3. Erfüllt die Menge die Dedekind-Peano-Axiome?


Aufgabe

Es sei eine endliche total geordnete Menge. Definiere für ein geeignetes eine ordnungstreue bijektive Abbildung

wobei mit der natürlichen Ordnung versehen sei.


Aufgabe

Es sei eine Teilmenge. Zeige, dass die Teilmenge

mit der induzierten Ordnung versehen ist.


Aufgabe *

Es sei eine endliche Menge. Betrachte die Relation auf der Potenzmenge , die durch

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?


Aufgabe

Zeige, dass die Produktordnung auf in der Tat eine Ordnung ist.


Aufgabe

Es sei eine total geordnete Menge. Zeige durch Induktion, dass jede nichtleere endliche Teilmenge ein eindeutiges Maximum besitzt.


Aufgabe *

Zeige durch Induktion, dass jede nichtleere Teilmenge ein kleinstes Element besitzt.


Aufgabe

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.


Aufgabe

Zeige, dass die natürliche Ordnung auf den ganzen Zahlen keine Wohlordnung ist.


Aufgabe

Definiere eine Wohlordnung auf der Menge der ganzen Zahlen .


Aufgabe

Es sei eine total geordnete Menge, die sowohl nach unten als auch nach oben wohlgeordnet ist. Zeige, dass endlich ist.


Aufgabe

Beweise das Lemma von Dickson, das besagt, dass eine nichtleere Teilmenge nur endlich viele minimale Elemente besitzt.


Aufgabe

Wir betrachten mit der Produktordnung. Bestimme die minimalen und die maximalen Elemente des Einheitskreises, versehen mit der induzierten Ordnung.


Aufgabe

Besitzt die Menge der natürlichen Zahlen in eine obere Schranke? Wie sieht das in anderen angeordneten Körpern aus?


Aufgabe *

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

gegebene Abbildung

als eine Hintereinanderschaltung von geeigneten und .


Aufgabe *

Zeige, dass für natürliche Zahlen die folgenden Teilbarkeitsbeziehungen gelten.

  1. Für jede natürliche Zahl gilt und .
  2. Für jede natürliche Zahl gilt .
  3. Gilt und , so gilt auch .
  4. Gilt und , so gilt auch .
  5. Gilt , so gilt auch für jede natürliche Zahl .
  6. Gilt und , so gilt auch für beliebige natürliche Zahlen .


Aufgabe

Bringe die Teilbarkeit einer natürlichen Zahl durch eine natürliche Zahl mit dem Begriff der Produktmenge in Zusammenhang.


Aufgabe

Skizziere ein Teilerdiagramm für die Menge der echten natürlichen Teiler von (dabei gelte als echter Teiler, nicht). Was sind die maximalen, die minimalen Elemente, gibt es ein größtes und ein kleinstes Element, was sind die total geordneten Teilmengen?


Aufgabe *

Es sei . Zeige, dass das Produkt von aufeinanderfolgenden natürlichen Zahlen von geteilt wird.


Aufgabe

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.


Aufgabe

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.


Aufgabe

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 (2 Punkte)

Bestimme auf der dreielementigen Menge sämtliche Ordnungen.


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)

  1. Es sei eine endliche geordnete Menge mit einem einzigen maximalen Element . Zeige, dass das größte Element von ist.
  2. 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) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)