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

Übungsaufgaben

Aufgabe

Zeige, dass die Menge der Untergruppen einer Gruppe ${}G$ mit der Inklusion, dem Durchschnitt von Untergruppen und der erzeugten Untergruppe einen Verband bildet.

Aufgabe

Es sei ${}G$ eine Gruppe, ${}{\mathfrak {P}}\,(G)$ der zugehörige Teilmengenverband und ${}V$ der zugehörige Untergruppenverband. Zeige, dass die natürliche Inklusion ${}V\subseteq {\mathfrak {P}}\,(G)$ ordnungstreu ist, aber nicht mit den Verbandsverknüpfungen verträglich sein muss.

Die folgende Aussage setzt eine gewisse Kenntnis in Galoistheorie voraus.

Aufgabe

Es sei ${}K\subseteq L$ eine Galoiserweiterung. Es sei ${}V$ der Verband der Zwischenkörper der Erweiterung und sei ${}W$ der Verband der Untergruppen der Galoisgruppe ${}\operatorname {Gal} \,(L{|}K)$. Zeige, dass durch die Galoiskorrespondenz eine bijektive antimonotone Abbildung zwischen den Verbänden ${}V$ und ${}W$ gegeben ist.

Aufgabe

Es sei ${}(V_{i},\leq _{i})$, ${}i\in I$, eine Familie von Verbänden. Zeige, dass die Produktmenge ${}\prod _{i\in I}V_{i}$ mit der Produktordnung ebenfalls ein Verband ist.

Kommentar:

Dies ist eher eine Frage zum Umgang mit Produktmengen als mit Verbänden, bei „jedem“ Konzept fragt man sich, wie sich das bei Produktmengen verhält. Bei Produktmengen sind zwei Spezialfälle besonders wichtig und helfen einem, sich der Sache anzunähern, nämlich das Produkt von zwei Mengen und ein vielfaches Produkt, wo die Faktoren alle gleich sind. Letztere Situation liegt in Aufgabe 9.7 vor, man kann auch damit starten, das ist vielleicht vertrauter. Dort sind die einzelnen Verbände stets die total geordneten reellen Zahlen.

Wir wissen bereits, dass eine Produktmenge von geordneten Mengen wieder eine geordnete Menge ist, siehe Aufgabe 7.7. Ein Element in der Produktmenge hat die Form ${}x_{i}$, ${}i\in I$, jedem ${}i$ aus der Indexmenge wird ein Element ${}x_{i}\in V_{i}$ zugeordnet. Die Ordnungsrelation besagt

${}(x_{i})_{i\in I}\leq (y_{i})_{i\in I}\,$

genau dann, wenn

${}x_{i}\leq _{i}y_{i}\,$

für alle ${}i$ ist. Das einzige, was bei einem Verband hinzukommt, ist die Existenz eines Infimums und eines Supremums. Es muss also ein Infimum von ${}(x_{i})_{i\in I}$ und ${}(y_{i})_{i\in I}$ angegeben werden. Zu jedem einzelnen ${}i$ gibt es das Infimum ${}x_{i}\sqcap y_{i}\in V_{i}$. Aus diesen bastelt man sich das Infimum der beiden Elemente und muss dann noch die Infimumseigenschaft nachweisen.

 

Aufgabe

Es sei ${}S$ eine Menge und ${}(T,\leq )$ eine total geordnete Menge. Zeige, dass die Abbildungsmenge

${}M=\operatorname {Abb} \,{\left(S,T\right)}\,$

in natürlicher Weise ein Verband ist.

Aufgabe

Wir versehen die zweielementige Menge ${}\{0,1\}$ mit der Ordnung ${}0<1$. Es sei ${}S$ eine Menge. Zeige, dass die Verbandsstruktur auf der Abbildungsmenge ${}\operatorname {Abb} \,{\left(S,\{0,1\}\right)}$ im Sinne von Aufgabe 9.5 als Verband isomorph zum Teilmengenverband ${}{\mathfrak {P}}\,(S)$ ist. Was sind die „atomaren Funktionen“?

Aufgabe *

Zeige, dass auf der Funktionenmenge ${}M=\operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}$ Infima und Suprema existieren und dass somit ${}M$ ein Verband ist. Skizziere das Infimum von der Sinusfunktion und der Kosinusfunktion.

Es sei ${}(M,1,\cdot )$ ein kommutatives Monoid. Man sagt, dass das Element ${}a$ das Element ${}b$ teilt, wenn es ein ${}c\in M$ mit ${}a\cdot c=b$ gibt.

Aufgabe

Es sei ${}M$ ein kommutatives Monoid. Zeige, dass die Teilbarkeit in ${}M$ eine reflexive und transitive Relation, aber im Allgemeinen keine Ordnungsrelation ist.

Aufgabe

Es sei ${}S$ eine Menge und ${}M={\mathfrak {P}}\,(S)$ die zugehörige Potenzmenge, die wir als kommutatives Monoid mit dem Durchschnitt als Verknüpfung auffassen. Es seien ${}A,B\in {\mathfrak {P}}\,(S)$. Zeige, dass folgende Eigenschaften äquivalent sind.

1. Es ist ${}B\subseteq A$.
2. Es ist ${}B=B\cap A$.
3. Es ist ${}A$ ein Teiler (im monoidtheoretischen Sinn) von ${}B$.

In einem Verband gilt stets ${}x\sqcap x=x$ für jedes ${}x$. Diese Eigenschaft nennt man Idempotenz, sie tritt in einem Ring ebenfalls auf, aber typischerweise nur für gewisse Elemente.

Aufgabe

Bestimme für einen Körper ${}K$ die idempotenten Elemente, also Elemente ${}e\in K$ mit ${}e^{2}=e$. Bestimme die linearen Projektionen ${}\varphi \colon K\rightarrow K$.

Aufgabe

Man gebe ein Beispiel für einen kommutativen Ring ${}R$ mit einem von ${}0$ und ${}1$ verschiedenen Element ${}e\in R$ mit ${}e^{2}=e$.

Aufgabe

1. Bestimme die idempotenten Elemente im Ring ${}\operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}$ aller Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$.
2. Bestimme die idempotenten Elemente im Ring ${}C^{0}(\mathbb {R} ,\mathbb {R} )$ aller stetigen Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$.

Aufgabe

Man gebe Beispiele für nichttriviale reelle ${}2\times 2$- Matrizen ${}M$ mit ${}M^{2}=M$.

Aufgabe

Betrachte eine endliche geordnete Menge mit einem kleinsten Element ${}0$ und einem größten Element ${}1$, das darüber hinaus aus Elementen ${}x_{1},\ldots ,x_{n}$ mit ${}0<x_{i}<1$ besteht, und für die es untereinander keine Größerbeziehung gibt. Ist dies ein Verband? Ist er komplementär? Ist er distributiv?

Aufgabe

Zeige, dass in einem booleschen Verband ${}V$ die Gleichheit ${}\neg \neg x=x$ für alle ${}x\in V$ gilt.

Kommentar:

In einem booleschen Verband wissen wir nach Lemma 9.16  (1), das zu jedem Element ${}x\in M$ es genau ein Element ${}y\in M$ mit ${}x\sqcap y=0$ und ${}x\sqcup y=1$ gibt, und dieses wird mit ${}\neg x$ bezeichnet. Hier schlägt dann das Prinzip „Gleichheit wegen Eindeutigkeit“ zu, d.h. man zeigt

${}\neg (\neg x)=x\,$

darüber, indem man zeigt, dass ${}x$ diejenige Eigenschaft erfüllt, die für ${}\neg (\neg x)$ charakteristisch ist. Dieses Argumentationsschema wird beispielsweise auch bei Aufgabe 5.2 verwendet. Also: ${}\neg (\neg x)$ ist dasjenige Element, das die Eigenschaften

${}\neg (\neg x)\sqcap (\neg x)=0\,$

und

${}\neg (\neg x)\sqcup (\neg x)=1\,.$

Es ist aber auch

${}x\sqcap (\neg x)=0\,$

und

${}x\sqcup (\neg x)=1\,.$

Deshalb erfüllen ${}x$ und ${}\neg (\neg x))$ die beiden gleichen Eigenschaften, durch diese Eigenschaften ist aber das Element bereits eindeutig bestimmt. Also ist

${}x=\neg (\neg x))\,.$

 

Aufgabe

Zeige, dass in einem booleschen Verband ${}V$ die Gleichheiten ${}\neg 0=1$ und ${}\neg 1=0$ gelten.

Aufgabe *

Zeige, dass in einem booleschen Verband ${}V$ die Gleichheit ${}\neg (x\sqcap y)=\neg x\sqcup \neg y$ für alle ${}x,y\in V$ gilt.

Aufgabe

Es sei ${}(M,\preccurlyeq )$ eine geordnete Menge mit einem kleinsten Element ${}0$ und mit der Eigenschaft, dass zu je zwei Elementen das Infimum ${}x\sqcap y$ existiert. Zeige, dass die folgenden Eigenschaften gelten.

1. Wenn ${}a\in M$ ein Atom ist, so ist ${}a\sqcap x=0$ oder ${}a\sqcap x=a$ für alle ${}x$.
2. Wenn ${}a$ und ${}b$ verschiedene Atome sind, so ist ${}a\sqcap b=0$.
3. Es sei ${}M$ endlich. Dann gibt es zu jedem ${}x\in M\setminus \{0\}$ ein Atom ${}a$ mit ${}a\preccurlyeq x$.

Aufgabe

Bestimme die möglichen Anzahlen eines endlichen booleschen Verbandes.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei ${}(\mathbb {N} ,{|})$ der Teilerverband auf den natürlichen Zahlen ${}\mathbb {N}$ im Sinne von Beispiel 9.3 und ${}V$ der Untergruppenverband von ${}\mathbb {Z}$ im Sinne von Beispiel 9.5. Zeige, dass diese beiden Verbände isomorph zueinander sind.

Aufgabe (2 Punkte)

Zeige, dass ein total geordneter beschränkter komplementärer Verband gleich ${}\{0\}$ oder gleich ${}\{0,1\}$ ist.

Aufgabe (3 Punkte)

Zeige, dass in einem booleschen Verband ${}V$ die Gleichheit ${}\neg (x\sqcup y)=\neg x\sqcap \neg y$ für alle ${}x,y\in V$ gilt.

Aufgabe (5 (1+2+2) Punkte)

Es sei ${}n\in \mathbb {N} _{+}$ eine positive natürliche Zahl und sei ${}V$ die Menge aller Teiler von ${}n$, versehen mit dem größten gemeinsamen Teiler als Infimum und dem kleinsten gemeinsamen Vielfachen als Supremum.

1. Zeige, dass ${}V$ ein beschränkter Verband ist.
2. Charakterisiere die Zahlen ${}n$, für die ein komplementärer Verband vorliegt.
3. Charakterisiere die Zahlen ${}n$, für die ein distributiver Verband vorliegt.

Aufgabe (3 Punkte)

Es seien ${}m,n\in \mathbb {N}$ und sei

${}V=\{0,1,\ldots ,m\}\times \{0,1,\ldots ,n\}\,$

mit der Produktordnung versehen, sodass ein Verband vorliegt. Für welche ${}m,n$ liegt ein beschränkter Verband, ein komplementärer Verband, ein distributiver Verband vor?