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

Übungsaufgaben

Aufgabe *

Es sei $M$ eine Menge und $\preccurlyeq$ eine Ordnung auf $M$. Zeige durch Induktion über $n\ge 2$ die Aussage: Wenn für Elemente $a_1,\dots ,a_n\in M$ die Beziehungen

$a_1\preccurlyeq a_2\preccurlyeq \dots \preccurlyeq a_{n-1}\preccurlyeq a_n$

und

$a_n\preccurlyeq a_1$

gelten, dann sind alle $a_1,\dots ,a_n$ gleich.

Aufgabe

Es sei $A$ eine endliche total geordnete Menge. Es sei $I=\{1,2,\dots ,n\}$ eine endliche Indexmenge. Definiere auf der Produktmenge

$A^I=\underset{n\text{-mal}}{\underbrace{A\times \cdots \times A}}$

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. $A$ das deutsche Alphabet ist, dann ist $A\cup \{␣\}$ eine geordnete Menge mit der offensichtlichen totalen Ordnung:

  $␣$ < a < ä < b < c < $\cdots$ < 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 $W_1$ und $W_2$ (z.B. $W_1$ = "Vorlesung" und $W_2$ = "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. $W_1$ = "Vorlesung" und $W_2$ = "Vorlesen$␣$"). Dann definiert man $W_1<W_2$ (d.h. $W_1$ kommt vor $W_2$ in einem Wörterbuch, das beide Wörter enthält) wenn an der ersten Stelle von vorne gelesen, wo sich $W_1$ und $W_2$ unterscheiden, der Buchstabe von $W_1$ an dieser Stelle kleiner als der Buchstaben von $W_2$ 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 $A$ erweitert werden: Für $x,y\in A^n$ mit $x=(a_1,\dots ,a_n),y=(b_1,\dots ,b_n)$ definiert man $x\le y$ falls $x=y$ oder ein $j\in \{1,\dots ,n\}$ existiert mit

$a_1=b_1,a_2=b_2,\dots ,a_{j-1}=b_{j-1},a_j<b_j.$

Man überprüft leicht, dass dies eine Ordnung auf $A^n$ ist. Die Linearität sieht man so: wenn $x\ne y$, dann existiert ein $j\in \{1,\dots ,n\}$ mit $a_j\ne b_j$. Da $A$ eine total geordnete Menge ist, gilt entweder $a_j<b_j$ oder $b_j<a_j$. Somit ist entweder $x<y$ oder $y<x$.

 

Aufgabe

Wir definieren auf ${\mathbb{N}}_{+}$ eine neue Relation $R$ durch folgende Vorschrift: Für zwei Zahlen  $n,m\in {\mathbb{N}}_{+}$  mit  $n=2^{k}t$  und  $m=2^{\ell }u$  mit $t,u$ ungerade sei

$nRm\text{ falls }t<u\text{ gilt oder falls zugleich }t=u\text{ und }k\le \ell \text{ gilt}$

(rechts wird auf die natürliche Ordnung in $\mathbb{N}$ Bezug genommen).

1. Zeige, dass $R$ eine totale Ordnung auf ${\mathbb{N}}_{+}$ ergibt und beschreibe exemplarisch diese Ordnung.
2. Zeige, dass es zu jedem  $n\in {\mathbb{N}}_{+}$  ein wohldefiniertes Element $n^{\star }\in {\mathbb{N}}_{+}$, $n^{\star }\ne n$, derart gibt, dass $nR{n}^{\star }$ gilt und dass es zwischen $n$ und $n^{\star }$ keine weiteren Elemente gibt (diese Formulierung ist zu präzisieren).
3. Erfüllt die Menge $({\mathbb{N}}_{+},1,\star )$ die Dedekind-Peano-Axiome?

Aufgabe

Es sei $(M,\le )$ eine endliche total geordnete Menge. Definiere für ein geeignetes  $n\in \mathbb{N}$  eine ordnungstreue bijektive Abbildung

$\{1,\dots ,n\}⟶M,$

wobei $\{1,\dots ,n\}$ mit der natürlichen Ordnung versehen sei.

Aufgabe

Es sei  $T\subseteq M$  eine Teilmenge. Zeige, dass die Teilmenge

$𝔓(T)\subseteq 𝔓(M)$

mit der induzierten Ordnung versehen ist.

Aufgabe *

Es sei $M$ eine endliche Menge. Betrachte die Relation auf der Potenzmenge $𝔓(M)$, die durch

$S\preccurlyeq T,\text{ falls }\mathrm{\#}\left(S\right)\le \mathrm{\#}\left(T\right),$

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?

Aufgabe

Zeige, dass die Produktordnung auf $\prod _{i\in I}(M_i,{\le }_i)$ in der Tat eine Ordnung ist.

Aufgabe

Es sei $(I,\preccurlyeq )$ eine total geordnete Menge. Zeige durch Induktion, dass jede nichtleere endliche Teilmenge $T\subseteq I$ ein eindeutiges Maximum besitzt.

Aufgabe *

Zeige durch Induktion, dass jede nichtleere Teilmenge  $T\subseteq \mathbb{N}$  ein kleinstes Element besitzt.

Aufgabe

Es sei $M$ eine Menge und $I$ die Menge der echten Teilmengen von $M$, also

$I=\{T\subseteq M\mid T\ne \mathrm{\varnothing }\text{ und }T\ne M\}.$

Diese Menge ist durch die Inklusion eine geordnete Menge. Bestimme die minimalen und die maximalen Elemente von $I$.

Eine totale Ordnung $\preccurlyeq$ auf einer Menge $M$ heißt Wohlordnung, wenn jede nichtleere Teilmenge  $T\subseteq M$  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 $\mathbb{Z}$.

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 $\mathbb{Z}$ ist jedoch die Konstruktion einer expliziten Wohlordnung möglich. Der Grund ist, dass $\mathbb{Z}$ und $\mathbb{N}$ die gleiche Mächtigkeit haben und dass $\mathbb{N}$ bekanntermaßen wohlgeordnet ist (siehe Aufgabe 7.9). Um eine Wohlordnung auf $\mathbb{Z}$ zu definieren, reicht es also aus, eine Nummerierung von $\mathbb{Z}$ (d.h. eine Bijektion $\phi :\mathbb{N}\to \mathbb{Z}$) zu konstruieren. Eine solche Nummerierung ist

$0,-1,1,-2,2,-3,3,\dots$

und die entsprechende Wohlordnung auf $\mathbb{Z}$ definiert man so: $a\prec b$ falls $|a|<|b|$ oder $|a|=|b|$ und $a<0<b$.

 

Aufgabe

Es sei $(M,\preccurlyeq )$ eine total geordnete Menge, die sowohl nach unten als auch nach oben wohlgeordnet ist. Zeige, dass $M$ endlich ist.

Aufgabe

Beweise das Lemma von Dickson, das besagt, dass eine nichtleere Teilmenge  $T\subseteq {\mathbb{N}}^r$  nur endlich viele minimale Elemente besitzt.

Kommentar:

Zuerst soll man sich klar machen, welche Ordnung auf ${\mathbb{N}}^r$ 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 ${\mathbb{N}}^r$, die wir hier betrachten, ist die Produktordnung (das ist auch die Ordnung in Beispiel 7.12, wenn man dort

$X=\{1,\dots ,r\}$

und $\mathbb{N}$ statt $ℝ$ nimmt): Für $a=(a_1,\dots ,a_r),b=(b_1,\dots ,b_r)\in {\mathbb{N}}^r$ definiert man $a\le b$, wenn

$a_1\le b_1,a_2\le b_2,\dots ,a_r\le b_r.$

Diese ist klar eine Ordnung auf ${\mathbb{N}}^r$, jedoch keine totale Ordnung für $r\ge 2$. Eine Motivation für die Produktordnung kommt aus der Teilbarkeitsrelation innerhalb eines Polynomrings: das Mononom $x_1^{a_1}\cdots x_r^{a_r}$ teilt das Mononom $x_1^{b_1}\cdots x_r^{b_r}$ genau dann, wenn $a\le b$.

Aus dem Induktionsprinzip folgt, dass die natürlichen Zahlen wohlgeordnet sind, d.h. jede nichtleere Teilmenge  $T\subseteq \mathbb{N}$  besitzt ein kleinstes Element (siehe Aufgabe 7.9). Also gilt das Lemma von Dickson für $r=1$. Für $r>1$ ist es eine natürliche Idee, Induktion über $r$ zu verwenden. Der Einfachheit halber betrachten wir nur den Fall $r=2$. Es empfiehlt sich, die Sache geometrisch in der Ebene  ${\mathbb{N}}^2\subseteq {ℝ}^2$  vorzustellen. Die minimalen Elemente von  $T\subseteq {\mathbb{N}}^2$  sind dann die Randpunkte mit ganzzahligen Koordinaten, wenn man $T$ 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  $T\subseteq {\mathbb{N}}^2$  existieren, die unendlich viele minimale Elemente

$t_1=(a_1,b_1),t_2=(a_2,b_2),\dots ,t_n=(a_n,b_n),\dots$

besitzt. Die Minimalität der Elemente $t_i$ bedeutet, dass man nicht $t_i$ und $t_j$ für $i\ne j$ vergleichen kann. Also gilt entweder $a_i<a_j$ und $b_i>b_j$ oder $a_i>a_j$ und $b_i<b_j$. Um die Induktionsvoraussetzung anzuwenden, betrachtet man die Mengen

$A_1=\{a_1,a_2,\dots ,a_n,\dots ,\},B_1=\{b_1,b_2,\dots ,b_n,\dots ,\}\subseteq \mathbb{N}.$

Da $\mathbb{N}$ wohlgeordnet ist, besitzt $A_1$ ein kleinstes Element, das man ohne Einschränkung als $a_1$ annehmen kann. Dann ist es klar, dass $b_1$ das größte Element von $B_1$ ist. Nun betrachtet man die Mengen

$A_2=\{a_2,a_3,\dots ,a_n,\dots ,\},B_2=\{b_2,b_3,\dots ,b_n,\dots ,\}\subseteq \mathbb{N}.$

Wie oben kann man annehmen, dass $a_2$ das kleinste Element von $A_2$ ist. Dies folgt, dass $b_2$ das größte Element von $B_2$ ist. Wenn man diesen Prozess fortsetzt, kann man davon ausgehen, dass

$a_1<a_2<\cdots <a_n<\cdots ,b_1>b_2>\cdots >b_n>\cdots .$

Die zweite Bedingung impliziert jedoch, dass die Menge $B_1=\{b_1,b_2,\dots ,b_n,\dots ,\}$ kein kleinstes Element besitzt, ein Widerspruch.

Das Lemma von Dickson spielt eine Rolle beim Beweis des Hilbertschen Basissatzes, der besagt, dass der Polynomring $k[x_1,\dots ,x_n]$ über einem Körper $k$ noethersch ist, d.h. jedes Ideal von $k[x_1,\dots ,x_n]$ ein endliches Erzeugendensystem besitzt.

 

Aufgabe

Wir betrachten ${ℝ}^2$ mit der Produktordnung. Bestimme die minimalen und die maximalen Elemente des Einheitskreises, versehen mit der induzierten Ordnung.

Aufgabe

Besitzt die Menge $\mathbb{N}$ der natürlichen Zahlen in $ℝ$ eine obere Schranke? Wie sieht das in anderen angeordneten Körpern aus?

Aufgabe *

Zu  $n\in \mathbb{N}$  sei

$[n]=\{0,1,2,\dots ,n\}.$

Zu jedem $n\in \mathbb{N}$ und jedem $0\le k\le n$ seien die Abbildungen

$D_k:[n]⟶[n+1]$

durch

$D_k(j)=\{\begin{array}{c}j,\text{ falls }j<k,\\ j+1\text{ sonst},\end{array}$

und die Abbildungen

$S_k:[n+1]⟶[n]$

durch

$S_k(j)=\{\begin{array}{c}j,\text{ falls }j\le k,\\ j-1\text{ sonst},\end{array}$

definiert.

a) Erstelle eine Wertetabelle für

$D_3:[4]⟶[5].$

b) Erstelle eine Wertetabelle für

$S_3:[6]⟶[5].$

c) Beschreibe die durch die Wertetabelle

$j$	$0$	$1$	$2$	$3$	$4$	$5$
$\phi (j)$	$0$	$2$	$2$	$4$	$5$	$5$

gegebene Abbildung

$\phi :[5]⟶[5]$

als eine Hintereinanderschaltung von geeigneten $D_k$ und $S_i$.

Aufgabe *

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

1. Für jede natürliche Zahl $a$ gilt $1\mid a$ und $a\mid a$.
2. Für jede natürliche Zahl $a$ gilt $a\mid 0$.
3. Gilt $a\mid b$ und $b\mid c$, so gilt auch $a\mid c$.
4. Gilt $a\mid b$ und $c\mid d$, so gilt auch $ac\mid bd$.
5. Gilt $a\mid b$, so gilt auch $ac\mid bc$ für jede natürliche Zahl $c$.
6. Gilt $a\mid b$ und $a\mid c$, so gilt auch $a\mid (rb+sc)$ für beliebige natürliche Zahlen $r,s$.

Aufgabe

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

Aufgabe

Skizziere ein Teilerdiagramm für die Menge $M$ der echten natürlichen Teiler von $100$ (dabei gelte $1$ als echter Teiler, $100$ 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  $n\in {\mathbb{N}}_{+}$.  Zeige, dass das Produkt von $n$ aufeinanderfolgenden natürlichen Zahlen von $n!$ geteilt wird.

Aufgabe

Es sei $({\mathbb{N}}_{+},\mid )$ die Menge der positiven natürlichen Zahlen mit der Teilbarkeitsrelation und $({\mathbb{N}}_{+},\le )$ die gleiche Menge mit der natürlichen Ordnungsstruktur. Zeige, dass die identische Abbildung

$({\mathbb{N}}_{+},\mid )⟶({\mathbb{N}}_{+},\le )$

ordnungstreu, aber nicht ordnungsvolltreu ist.

Aufgabe

Es sei $M$ die Menge aller unendlichen Teilmengen von ${\mathbb{N}}_{+}$, versehen mit der Inklusion als Ordnung, und es sei $[0,1[$ das rechtsseitig offene reelle Einheitsintervall mit der Kleinergleich-Relation als Ordnung. Zeige, dass die Abbildung

$\mathrm{\Psi }:M⟶[0,1[,T⟼\sum _{n\in ̸T}{\left(\frac{1}{2}\right)}^n,$

eine bijektive, ordnungstreue Abbildung ist, deren Umkehrabbildung nicht ordnungstreu ist.

Aufgabe

Es sei ${ℝ}^{\mathbb{N}}$ die Menge aller reellen Folgen, versehen mit der Produktordnung und sei  $T\subseteq {ℝ}^{\mathbb{N}}$  die Teilmenge aller konvergenten Folgen. Zeige, dass die Abbildung

$T⟶ℝ,{\left(x_n\right)}_{n\in \mathbb{N}}⟼\underset{n\to \mathrm{\infty }}{lim}{x}_n,$

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  $M=\{a,b,c\}$  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 $(M,\le )$ eine geordnete Menge und $𝔓(M)$ die Potenzmenge von $M$. Zeige, dass die Abbildung

$M⟶𝔓(M),x⟼\{y\in M\mid y\le x\},$

ordnungsvolltreu und injektiv ist, wobei die Potenzmenge mit der Inklusion versehen ist.

Aufgabe (4 Punkte)

Zeige, dass es keine Abbildung

$\phi :\mathbb{N}⟶\mathbb{N}$

gibt, die die folgende Eigenschaft erfüllt: Es ist  $k\ge n$  genau dann, wenn  $\phi (k)\le \phi (n)$. 

Aufgabe (3 (2+1) Punkte)

1. Es sei $M$ eine endliche geordnete Menge mit einem einzigen maximalen Element $m$. Zeige, dass $m$ das größte Element von $M$ ist.
2. Man gebe ein Beispiel für eine geordnete Menge mit genau einem maximalen Element, das aber nicht das größte Element ist.