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

Die Pausenaufgabe

Aufgabe Referenznummer erstellen

Wir betrachten auf dem weißen Teil des angegebenen Labyrinths die Äquivalenzrelation, die dadurch festgelegt ist, dass zwei Punkte als äquivalent gelten, wenn man durch eine stetige Bewegung (also ohne Sprünge) von einem Punkt zum anderen Punkt gelangen kann. Bestimme, welche der markierten Punkte zueinander äquivalent sind. Skizziere die Äquivalenzklassen des Labyrinths durch verschiedene Farben.

Übungsaufgaben

Aufgabe Referenznummer erstellen

Es sei ${}M$ die Menge der Menschen und ${}R$ die Verwandtschaftsrelation darauf, die wir großzügig als transitiv interpretieren. Wie viele Äquivalenzklassen gibt es?

Aufgabe Referenznummer erstellen

In der Klasse ${}7c$ herrscht ein rigides Cliquensystem, jeder Schüler und jede Schülerin gehört genau einer Clique an. Es gibt die „Borussen-Bande“ (Heinz Ngolo, Mustafa Müller, Veronika Zaitsev, Bernd Buxtehude, Paola Rodrigues und Peter Dembele), die „Eisfreunde Sonne“ (Lucy Sonnenschein, Fred Feuerstein, Natascha Schleckmaul, Frodo Gletscherzunge) die „Nutty Nerds“ (Gabi Hochster, Primo von Hinten), das „Anarcho-Syndikat“ (Anna-Lena Müller, Annegret Maier, Ann-Kathrin Schmitt, Anabelle Belami, Antoine de la Playa, Arndt MacDermott), die „Lucky Loosers“ (Yogi Nanging, Manfred Trutzenburg, Roberta Falstaff, Dörte Waterkant), die „Cauchy-Zwillinge“ (Carmen Cauchy, Conchita Cauchy), sowie fünf weitere Einzelpersonen, die für sich jeweils eine Clique bilden. Die Zugehörigkeit zur gleichen Clique definiert eine Äquivalenzrelation in der Klasse ${}7c$.

1. Bestimme ${}[{\text{Natascha Schleckmaul}}]$.
2. Bestimme ${}[{\text{Ann-Kathrin Schmitt}}]\cap [{\text{Roberta Falstaff}}]$.
3. Bestimme ${}\{{\text{Ann-Kathrin Schmitt}}\}\cap \{{\text{Anabelle Belami}}\}$.
4. Bestimme ${}[{\text{Ann-Kathrin Schmitt}}]\cap [{\text{Anabelle Belami}}]$.
5. Wie viele Äquivalenzklassen gibt es in der Klasse?
6. Wie viele Elemente besitzt die Quotientenmenge zu dieser Äquivalenzrelation?
7. Um das Klima in der Klasse zu verbessern, ruft Frau Maier-Sengupta ein Treffen zusammen, zu dem jede Clique einen Repräsentanten schickt. Wie viele Möglichkeiten für ein solches Treffen gibt es? Wie viele Möglichkeiten gibt es, wenn die fünf Einzelpersonen zusammen eine neue Clique bilden und Antoine de la Playa das Anarcho-Syndikat verlässt und sich den Eisfreunden Sonne anschließt?

Aufgabe Referenznummer erstellen

Es finden ein Gipfeltreffen von ${}n$ Staaten statt, wobei jeder Staat entweder den Präsidenten(-in) oder den Vizepräsidenten hinschickt. Das Gastgeberland ist jedenfalls mit dem Präsidenten vertreten. Wie viele Möglichkeiten für das Gipfeltreffen (also Kombinationsmöglichkeiten an Repräsentanten) gibt es?

Aufgabe Referenznummer erstellen

Es sei ${}K$ ein Körper und ${}V$ ein ${}K$- Vektorraum. Zeige, dass die Relation auf ${}V$, die durch

$v\sim w,{\text{ falls es ein }}\lambda \in K,\lambda \neq 0,{\text{ mit }}v=\lambda w{\text{ gibt }}$

eine Äquivalenzrelation ist. Was sind die Äquivalenzklassen?

Aufgabe Referenznummer erstellen

Es sei ${}K$ ein Körper und ${}n\in \mathbb {N} _{+}$.

1. Wir betrachten auf dem ${}K^{n}$ die Relation ${}R$, die durch ${}vRw$ gegeben ist, falls es eine lineare Abbildung ${}\varphi \colon K^{n}\rightarrow K^{n}$ mit ${}\varphi (v)=w$ gibt. Welche Eigenschaften einer Äquivalenzrelation sind erfüllt, welche nicht?
2. Wir betrachten auf dem ${}K^{n}$ die Relation ${}S$, die durch ${}vSw$ gegeben ist, falls es eine bijektive lineare Abbildung ${}\varphi \colon K^{n}\rightarrow K^{n}$ mit ${}\varphi (v)=w$ gibt. Welche Eigenschaften einer Äquivalenzrelation sind erfüllt, welche nicht?

Aufgabe Referenznummer erstellen

Es sei ${}K$ ein Körper und ${}n\in \mathbb {N} _{+}$. Wir betrachten auf dem ${}K^{n}$ die Äquivalenzrelation ${}\sim$, die durch ${}v\sim w$ gegeben ist, falls es eine bijektive lineare Abbildung ${}\varphi \colon K^{n}\rightarrow K^{n}$ mit ${}\varphi (v)=w$ gibt. Bestimme die Äquivalenzklassen zu dieser Äquivalenzrelation.

Aufgabe Referenznummer erstellen

Es sei ${}V=K^{n}$ ein Vektorraum und ${}m\in \mathbb {N}$. Betrachte auf der Produktmenge ${}V^{m}$ die folgende Relation.

$(v_{1},\ldots ,v_{m})\sim (w_{1},\ldots ,w_{m}),{\text{ falls }}\langle v_{1},\ldots ,v_{m}\rangle =\langle w_{1},\ldots ,w_{m}\rangle .$

Die beiden Vektorentupel stehen also in Relation zueinander, wenn sie den gleichen Untervektorraum erzeugen. Zeige, dass dies eine Äquivalenzrelation ist. Man gebe eine Bijektion zwischen der zugehörigen Quotientenmenge und der Menge der Untervektorräume von ${}V$, die durch ${}m$ Vektoren erzeugt werden können.

Aufgabe Referenznummer erstellen

Es sei ${}V\subseteq K^{n}$ ein Untervektorraum und ${}\sim$ die zugehörige Äquivalenzrelation im Sinne von Aufgabe 10.15.

1. Zeige, dass die affinen Unterräume der Form ${}P+V$ die Äquivalenzklassen sind.
2. Es sei ${}W\subseteq K^{n}$ ein weiterer Untervektorraum mit

   ${}V\cap W=\{0\}\,$

   und derart, dass man jeden Vektor ${}u\in K^{n}$ in der Form ${}u=v+w$ mit ${}v\in V$ und ${}w\in W$ schreiben kann. Zeige, dass ${}W$ ein Repräsentantensystem

   für die Äquivalenzrelation ist.

Aufgabe Referenznummer erstellen

Es sei ${}F$ ein Faden. Man versuche, sich die folgenden Äquivalenzrelationen auf ${}F$ und die zugehörige Identifizierungsabbildungen vorzustellen (möglichst geometrisch).

1. Die beiden Endpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
2. Es seien zwei Punkte ${}P,Q\in F$ fixiert. Diese beiden Punkte seien zueinander äquivalent, ansonsten seien die Punkte nur zu sich selbst äquivalent.
3. Es seien ${}n$ Punkte ${}P_{1},P_{2},\ldots ,P_{n}\in F$ fixiert. Diese Punkte seien untereinander äquivalent, ansonsten seien die Punkte nur zu sich selbst äquivalent.
4. Auf dem Faden seien abwechselnd ${}3$ rote Punkte und ${}3$ blaue Punkte markiert. Die roten Punkte sollen untereinander äquivalent sein und die blauen Punkte sollen untereinander äquivalent sein, ansonsten seien die Punkte nur zu sich selbst äquivalent.
5. Es sei ${}M$ der Mittelpunkt des Fadens. Zwei Punkte seien zueinander äquivalent, wenn sie zu ${}M$ den gleichen (gestreckter) Abstand haben.
6. Der Faden wird in ${}2$ (oder $3,4,5,\ldots$) gleichlange Teile unterteilt, die Länge eines Teiles sei ${}s$. Zwei Punkte sind zueinander äquivalent, wenn ihr Abstand ein Vielfaches von ${}s$ ist.

Aufgabe Referenznummer erstellen

Es sei ${}B$ ein Blatt Papier (oder ein Taschentuch). Man versuche, sich die folgenden Äquivalenzrelationen auf ${}B$ und die zugehörige Identifizierungsabbildungen vorzustellen (möglichst geometrisch).

1. Die vier Eckpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
2. Alle Randpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
3. Jeder Punkt des linken Randes ist äquivalent zu seinem horizontal gegenüber liegenden Punkt am rechten Rand, ansonsten sind die Punkte nur zu sich selbst äquivalent.
4. Jeder Punkt des linken Randes ist äquivalent zu seinem horizontal gegenüber liegenden Punkt am rechten Rand und jeder Punkt des oberen Randes ist äquivalent zu seinem vertikal gegenüber liegenden Punkt, ansonsten sind die Punkte nur zu sich selbst äquivalent.
5. Jeder Punkt des Randes ist äquivalent zu seinem punktsymmetrisch (bezüglich des Mittelpunktes des Blattes) gegenüber liegenden Punkt, ansonsten sind die Punkte nur zu sich selbst äquivalent.
6. Es sei ${}K$ ein Kreis (d.h. eine Kreislinie) auf dem Blatt. Alle Kreispunkte seien untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
7. Es gebe zwei Punkte ${}P\neq Q$, die untereinander äquivalent seien, ansonsten sind die Punkte nur zu sich selbst äquivalent.
8. Es sei ${}H$ die horizontale Halbierungsgerade des Blattes. Zwei Punkte sind genau dann äquivalent, wenn sie achsensymmetrisch zu ${}H$ sind.

Aufgabe Referenznummer erstellen

Es sei ${}K$ ein angeordneter Körper und

$K\longrightarrow K_{\geq 0},\,x\longmapsto \vert {x}\vert ,$

die Betragsabbildung. Zeige, dass man diese Abbildung als Quotientenabbildung zur Äquivalenzrelation ${}\sim$ auf ${}K$ auffassen kann, für die ${}x\sim y$ bei ${}x=\pm y$ gilt.

Aufgabe Aufgabe 11.13 ändern

Es sei

$f\colon M\longrightarrow N$

eine surjektive Abbildung mit der zugehörigen Äquivalenzrelation ${}\sim$ auf ${}M$ im Sinne von Lemma 10.10. Es sei ${}Q$ die Quotientenmenge zu ${}\sim$ mit der kanonischen Projektion ${}p\colon M\rightarrow Q$. Zeige, dass es eine bijektive Abbildung

$\psi \colon Q\longrightarrow N$

mit

${}f=\psi \circ p\,$

gibt.

Kommentar:

Die Konstruktion der Abbildung ${}\psi$ aus der Abbildung ${}f$, die in Lemma 11.13 durchgeführt wurde, ist eine schöne Idee, um jede Abbildung in eine injektive Abbildung umzuwandeln: ist ${}f$ nicht injektiv, dann existieren ${}x,y\in M$ mit ${}x\neq y$, sodass ${}f(x)=f(y)$. Aber ${}x$ und ${}y$ sind "gleich" in der Quotientenmenge ${}Q$ (d.h. ${}[x]=[y]$). Somit ist ${}\psi$ immer eine injektive Abbildung (siehe auch Bemerkung 11.14). Durch diese Konstruktion sieht man also die Wichtigkeit von Äquivalenzrelationen und Quotientenmengen.

Wenn ${}f$ weiterhin eine surjektive Abbildung ist, dann ist ${}\psi$ ebenfalls surjektiv und somit bijektiv: für jedes ${}z\in N$ existiert ein ${}x\in M$ mit ${}f(x)=z$ und folglich gilt ${}\psi ([x])=f(x)=z$.

Diese Aufgabe ist ein sehr nützliches Werkzeug zum Nachweis der Bijektivität, insbesondere wenn ${}M$ und ${}N$ dieselbe algebraische Struktur (z. B. Gruppe, Ring, Vektorraum) haben und ${}f$ ein Homomorphismus ist; siehe Vorlesung 12.

 

Aufgabe Referenznummer erstellen

Es sei

$\varphi \colon K^{n}\longrightarrow K^{m}$

eine surjektive lineare Abbildung mit dem Kern ${}U\subseteq K^{n}$. Es sei ${}\sim$ die Äquivalenzrelation auf ${}K^{n}$ zu diesem Untervektorraum im Sinne von Aufgabe 10.15 und sei

$p\colon K^{n}\longrightarrow K^{n}/\sim$

die zugehörige Quotientenabbildung. Zeige, dass es nach Lemma 11.13 eine Abbildung

$\psi \colon K^{n}/\sim \longrightarrow K^{m}$

mit

${}\varphi =\psi \circ p\,$

gibt. Zeige, dass ${}\psi$ bijektiv ist.

Aufgabe Referenznummer erstellen

Beschreibe typische Äquivalenzklassen zur Äquivalenzrelation ${}\sim$ auf ${}\mathbb {Z} \times \mathbb {Z}$, die durch die Additionsabbildung

$+\colon \mathbb {Z} \times \mathbb {Z} \longrightarrow \mathbb {Z} ,\,(x,y)\longmapsto x+y,$

im Sinne von Lemma 10.10 gegeben ist.

Aufgabe Referenznummer erstellen

Beschreibe typische Äquivalenzklassen zur Äquivalenzrelation ${}\sim$ auf ${}\mathbb {N} \times \mathbb {N}$, die durch die Multiplikationsabbildung

$\cdot \colon \mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(x,y)\longmapsto x\cdot y,$

im Sinne von Lemma 10.10 gegeben ist. Wie sieht die Äquivalenzklasse zu ${}(6,20)$ aus? Markiere in ${}\mathbb {N} \times \mathbb {N}$ mit unterschiedlichen Farben unterschiedliche Äquivalenzklassen. Gibt es Äquivalenzklassen, die nur aus einem Element bestehen? Gibt es Äquivalenzklassen, die aus unendlich vielen Elementen bestehen? Welche Äquivalenzklassen bestehen aus zwei Elementen?

Aufgabe Referenznummer erstellen

Die Schüler und Schülerinnen der Klasse 3b werden für den Schwimmunterricht in die vier Leistungsklassen ${}A,B,C,D$ eingeteilt. Wenn der Schwimmunterricht im Freibad stattfindet, so schwimmen die Leistungsklassen ${}A$ und ${}B$ im großen Becken und die Leistungsklassen ${}C$ und ${}D$ im kleinen Becken. Wenn der Schwimmunterricht im Hallenbad stattfindet, so schwimmt die Leistungsklasse ${}A$ auf den Bahnen ${}1$ und ${}2$, die Leistungsklassen ${}B$ und ${}C$ auf den Bahnen ${}3$ bis ${}6$ und die Leistungsklasse ${}D$ macht Trockenübungen. Erläutere diese Situation mit Hilfe von Lemma 11.13.

Aufgabe * Referenznummer erstellen

Wir betrachten auf ${}\mathbb {N} _{+}$ die Relation ${}\sim$, die durch

${}m\sim n\,$

festgelegt ist, falls ${}m$ eine Potenz von ${}n$ und ${}n$ eine Potenz von ${}m$ teilt.

1. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.
2. Bestimme, welche der folgenden Elemente zueinander äquivalent sind, welche nicht.

   $100,\,1000,\,9,\,125,\,500,\,27,\,10,\,210.$

3. Es sei ${}Q$ die Quotientenmenge zu dieser Äquivalenzrelation und es sei ${}\mathbb {P}$ die Menge der Primzahlen mit der Potenzmenge ${}{\mathfrak {P}}\,({\mathbb {P} })$. Zeige, dass es eine natürliche Abbildung

   $\varphi \colon \mathbb {N} _{+}\longrightarrow {\mathfrak {P}}\,({\mathbb {P} })$

   gibt, die zu einer injektiven Abbildung

   ${\tilde {\varphi }}\colon Q\longrightarrow {\mathfrak {P}}\,({\mathbb {P} })$

   führt. Ist ${}{\tilde {\varphi }}$ surjektiv?

4. Wie sieht ein besonders einfaches Repräsentantensystem für die Äquivalenzrelation aus?

Aufgabe Referenznummer erstellen

Es sei ${}D$ eine vierelementige und ${}W$ eine zweielementige Menge. Bestimme die Äquivalenzklassen zur Äquivalenzrelation aus Aufgabe 10.31 in dieser Situation. Man gebe für jede Äquivalenzklasse einen Repräsentanten an und bestimme die Anzahl der Repräsentanten pro Klasse.

Es seien ${}\sim _{1}$ und ${}\sim _{2}$ Äquivalenzrelationen auf der Menge ${}M$. Man sagt, dass ${}\sim _{1}$ eine Verfeinerung von ${}\sim _{2}$ ist, wenn aus ${}x\sim _{1}y$ stets ${}x\sim _{2}y$ folgt.

Aufgabe Referenznummer erstellen

Wir betrachten auf der Menge aller höheren Säugetiere die Äquivalenzrelationen, die durch „gehören zur gleichen Gattung“, „gehören zur gleichen Familie“, „gehören zur gleichen Art“, „gehören zur gleichen Klasse“, „gehören zur gleichen Ordnung“ gegeben sind. Welche Äquivalenzrelation ist eine Verfeinerung von welcher Äquivalenzrelation? Man gebe für je zwei dieser Äquivalenzrelationen Tiere an, die bezüglich der einen Relation äquivalent sind, aber nicht bezüglich der anderen. Wie viele Äquivalenzklassen besitzt die Äquivalenzrelation zur Ordnung?

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine Menge und seien ${}\sim _{1}$ und ${}\sim _{2}$ Äquivalenzrelationen auf ${}M$ mit den zugehörigen kanonischen Abbildungen

$p_{1}\colon M\longrightarrow Q_{1}$

und

$p_{2}\colon M\longrightarrow Q_{2}.$

Zeige, dass die folgenden Aussagen äquivalent sind.

1. ${}\sim _{1}$ ist eine Verfeinerung von ${}\sim _{2}$.
2. Für die Äquivalenzklassen zu jedem Element ${}x\in M$ gilt ${}[x]_{1}\subseteq [x]_{2}$.
3. Es ist (als Teilmengen von ${}M\times M$)

   ${}\sim _{1}\subseteq \sim _{2}\,.$

4. Es gibt eine Abbildung

   $\psi \colon Q_{1}\longrightarrow Q_{2}$

   mit ${}\psi \circ p_{1}=p_{2}$.

Aufgabe Referenznummer erstellen

Es sei ${}M\times N$ eine Produktmenge. Zeige, dass die Gleichheit in der ersten Komponente eine Äquivalenzrelation ${}\sim$ auf ${}M\times N$ ist. Zeige, dass man jede Äquivalenzklasse mit ${}N$ und die Quotientenmenge ${}M\times N/\sim$ mit ${}M$ identifizieren kann.

Kommentar:

Wie im Kommentar zu Aufgabe 9.4 erwähnt, fragt man sich bei jedem Konzept, wie sich das bei Produktmengen verhält. Bei der Äquivalenzrelation hat man dieselbe Frage. Es sei also ${}(M_{i},\sim _{i}),\ i\in I$, eine Familie der Mengen, wobei ${}\sim _{i}$ eine Äquivalenzrelation auf ${}M_{i}$ ist. Man betrachtet die Relation ${}\sim$, die auf dem Produktmenge ${}\prod _{i\in I}M_{i}$ durch

$(x_{i})_{i\in I}\sim (y_{i})_{i\in I}{\text{ genau dann, wenn }}x_{i}\sim _{i}y_{i}{\text{ für alle }}i\in I$

definiert wird. Natürlich fragt man sich, ob ${}\sim$ eine Äquivalenzrelation ist, und wenn ja, was dann die Äquivalenzklassen ${}[(x_{i})_{i\in I}]$ sind und wie die Quotientenmenge ${}\prod _{i\in I}M_{i}/\sim$ aussieht. Dies sind keine schwierigen Fragen. Per Definition sieht man leicht, dass ${}\sim$ tatsächlich eine Äquivalenzrelation ist und es gilt

$[(x_{i})_{i\in I}]=\prod _{i\in I}[x_{i}].$

Für die letzte Frage betrachtet man die Abbildung

$f\colon \prod _{i\in I}M_{i}\longrightarrow \prod _{i\in I}(M_{i}/\sim _{i}),\,(x_{i})_{i\in I}\longmapsto ([x_{i}])_{i\in I},$

die offensichtlich surjektiv ist. Es ist klar, dass ${}\sim$ genau die durch ${}f$ definierte Äquivalenzrelation im Sinne von Lemma 10.10 ist. Nach Aufgabe 11.13 ist die Abbildung

$\psi \colon \prod _{i\in I}M_{i}/\sim \longrightarrow \prod _{i\in I}(M_{i}/\sim _{i})$

bijektiv. Daher kann man die Quotientenmenge ${}\prod _{i\in I}M_{i}/\sim$ mit der Produktmenge ${}\prod _{i\in I}(M_{i}/\sim _{i})$ identifizieren.

Diese Aufgabe ist ein Spezialfall der obigen Beobachtung, wobei ${}\sim _{1}$ die Gleichheit auf ${}M$ und ${}\sim _{2}$ die Allrelation auf ${}N$ (siehe Beispiel 10.3) ist.

 

Aufgabe Referenznummer erstellen

Es sei ${}D$ eine Schulklasse und

${}W=\{1,2,3,4,5,6\}\,$

die Menge der Schulnoten. Das Ergebnis einer Klausur ist eine Abbildung ${}f\colon D\rightarrow W$, wobei jedem Schüler ${}x\in D$ seine in der Klausur erzielte Note ${}f(x)$ zugeordnet wird. Die zugehörige Notenverteilung ist die Abbildung, die jeder Note ${}w\in W$ zuordnet, wie oft diese Note in der Klausur vergeben wurde. Die in Aufgabe 11.23 besprochene Abbildung

$\Psi \colon \operatorname {Abb} \,{\left(D,W\right)}\longrightarrow \operatorname {Abb} \,{\left(W,\mathbb {N} \right)},\,f\longmapsto {\left(w\mapsto {\#\left(f^{-1}(w)\right)}\right)},$

ordnet also dem Klausurergebnis die Notenverteilung zu. Es sei nun

$\varphi \colon \operatorname {Abb} \,{\left(D,W\right)}\longrightarrow \mathbb {Q}$

die Abbildung, die jedem Klausurergebnis die Durchschnittsnote zuordnet.

1. Erstelle eine Formel für die Durchschnittsnote zu einem Klausurergebnis ${}f$.
2. Erstelle eine Formel für die Durchschnittsnote zu einer Notenverteilung ${}h\colon W\rightarrow \mathbb {N}$.
3. Zeige, dass man die Durchschnittsnote zum Klausurergebnis ${}f$ allein aus der zugehörigen Notenverteilung ${}\Psi (f)$ berechnen kann.
4. Zeige, dass es eine Abbildung

   ${\tilde {\varphi }}\colon \operatorname {Abb} \,{\left(W,\mathbb {N} \right)}\longrightarrow \mathbb {Q}$

   mit

   ${}\varphi ={\tilde {\varphi }}\circ \Psi \,$

   gibt.

5. Aus welchen Notenverteilungen ist das Klausurergebnis rekonstruierbar?
6. Was ist eine sinnvolle Antwort auf die Frage „Wie ist die Klausur ausgefallen“?

Aufgabe Referenznummer erstellen

Es seien ${}D$ und ${}W$ Mengen, wobei ${}D$ endlich sei. Es sei ${}\sim$ die Äquivalenzrelation auf ${}\operatorname {Abb} \,{\left(D,W\right)}$ aus Aufgabe 10.19 und sei

$\Psi \colon \operatorname {Abb} \,{\left(D,W\right)}\longrightarrow \operatorname {Abb} \,{\left(W,\mathbb {N} \right)},\,f\longmapsto {\left(w\mapsto {\#\left(f^{-1}(w)\right)}\right)},$

die in Aufgabe 11.23 besprochene Abbildung.

1. Es sei ${}\pi \colon D\rightarrow D$ eine bijektive Abbildung und ${}f\colon D\rightarrow W$ eine Abbildung. Zeige

   ${}\Psi (f)=\Psi (f\circ \pi )\,.$

2. Es seien ${}f,g\colon D\rightarrow W$. Zeige ${}f\sim g$ genau dann, wenn ${}\Psi (f)=\Psi (g)$ ist.
3. Zeige, dass es eine injektive Abbildung

   ${\tilde {\Psi }}\colon \operatorname {Abb} \,{\left(D,W\right)}/\sim \!\longrightarrow \operatorname {Abb} \,{\left(W,\mathbb {N} \right)}$

   mit ${}\Psi ={\tilde {\Psi }}\circ p$ gibt, wobei ${}p$ die kanonische Projektion in die Quotientenmenge bezeichnet.

Aufgabe * Referenznummer erstellen

Es sei ${}M$ eine Menge und ${}\preccurlyeq$ eine Relation auf ${}M$, die reflexiv und transitiv sei.

1. Zeige, dass auf ${}M$ durch ${}x\sim y$, falls ${}x\preccurlyeq y$ und ${}y\preccurlyeq x$ ist, eine Äquivalenzrelation definiert wird.
2. Es sei ${}Q$ die Quotientenmenge zu ${}M$ zur Äquivalenzrelation aus (1). Zeige, dass durch ${}[x]\leq [y]$, falls ${}x\preccurlyeq y$, eine wohldefinierte Relation auf ${}Q$ gegeben ist.
3. Zeige, dass die Relation auf ${}Q$ aus (2) eine Ordnungsrelation ist.

Aufgaben zum Abgeben

Aufgabe (2 Punkte)Referenznummer erstellen

Es sei ${}R$ eine Relation zwischen den Mengen ${}M$ und ${}N$. Wir definieren auf ${}M$ die Relation ${}S$ durch ${}aSb$, wenn für alle ${}x\in N$ die Beziehung ${}aRx$ genau dann gilt, wenn ${}bRx$ gilt. Zeige, dass ${}S$ eine Äquivalenzrelation auf ${}M$ ist.

Aufgabe (3 Punkte)Referenznummer erstellen

Betrachte die Schachfiguren Turm, Läufer, Pferd und Esel zusammen mit ihren erlaubten Zügen auf einem ${}8\times 8$-Schachbrett. Ein Esel darf dabei pro Zug einen Doppelschritt nach vorne, nach hinten, nach rechts oder nach links machen. Jede dieser Figuren definiert eine Äquivalenzrelation auf den ${}64$ Feldern, indem zwei Felder als äquivalent angesehen werden, wenn das eine Feld von dem anderen Feld aus mit dieser Figur in endlich vielen Zügen erreichbar ist. Beschreibe für jede dieser Schachfiguren die zugehörige Äquivalenzrelation und ihre Äquivalenzklassen. Wie sieht es auf einem ${}3\times 3$-Schachbrett aus?

Aufgabe (1 Punkt)Referenznummer erstellen

Im Portemonnaie befinden sich vier ${}2$-Euro-Münzen, sechs ${}1$-Euro-Münzen, drei ${}50$-Cent-Münzen, zwei ${}20$-Cent-Münzen, eine ${}10$-Cent-Münze, keine ${}5$-Cent-Münze, fünf ${}2$-Cent-Münzen und acht ${}1$-Cent-Münzen. Wir betrachten auf dieser Münzmenge diejenige Äquivalenzrelation, bei der zwei Münzen als äquivalent gelten, wenn sie den gleichen Münzwert haben. Wie viele Äquivalenzklassen gibt es? Wie viele Elemente besitzen die einzigen Äquivalenzklassen? Wie viele Elemente besitzt die Quotientenmenge?

Aufgabe (3 Punkte)Referenznummer erstellen

Es seien ${}\sim _{1}$ und ${}\sim _{2}$ Äquivalenzrelationen auf der Menge ${}M$ mit den zugehörigen kanonischen Abbildungen

$p_{1}\colon M\longrightarrow Q_{1}$

und

$p_{2}\colon M\longrightarrow Q_{2}.$

Es sei ${}\sim$ der Durchschnitt der beiden Äquivalenzrelationen mit der zugehörigen kanonischen Projektion

$p\colon M\longrightarrow Q.$

Zeige, dass es eine injektive Abbildung

$\psi \colon Q\longrightarrow Q_{1}\times Q_{2}$

mit ${}\psi \circ p=p_{1}\times p_{2}$ gibt.

Aufgabe (4 Punkte)Referenznummer erstellen

Wir betrachten auf der Menge der Geraden in der Ebene ${}\mathbb {Q} ^{2}$ die Äquivalenzrelation, die durch die Parallelität von Geraden gegeben ist. Zeige, dass die folgende Menge ein Repräsentantensystem ist: die ${}x$-Achse und diejenigen Geraden, die durch den Nullpunkt und einen Punkt der Form ${}(x,1)$ mit ${}x\in \mathbb {Q}$ verlaufen.

Aufgabe (5 Punkte)Referenznummer erstellen

Es sei ${}D$ eine fünfelementige und ${}W$ eine dreielementige Menge. Bestimme die Äquivalenzklassen zur Äquivalenzrelation aus Aufgabe 10.31 in dieser Situation. Man gebe für jede Äquivalenzklasse einen Repräsentanten an und bestimme die Anzahl der Repräsentanten pro Klasse.