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

Die Pausenaufgabe

Aufgabe

Ist das Reimen von Wörtern eine Äquivalenzrelation?

Übungsaufgaben

Aufgabe

Es sei ${}M$ die Menge der Leute im Kurs. Bestimme für die folgenden, durch eine Eigenschaft festgelegten Äquivalenzrelationen auf ${}M$, wer zu wem äquivalent ist.

1. Hat im gleichen Monat Geburtstag.
2. Hat das gleiche Zweitfach (neben Mathematik).
3. Wohnt in der gleichen Stadt.

Aufgabe

Wir betrachten die folgende Menge, deren Elemente gewisse Zahlenmengen sind.

${}M=\{\{2,5,7\},\,\{2,3,4\},\,\{2,5,7,8\},\,\{2,7\},\,\{4,10,14\},\,\{3\},\,\{8,9\},\,\{12,15,23\}\}\,.$

Zeige, dass für Elemente ${}S,T\in M$ durch ${}S\sim T$, falls ${}S$ und ${}T$ die gleiche Anzahl an Elementen haben, eine Äquivalenzrelation auf ${}M$ gegeben ist. Welche Elemente sind zueinander äquivalent, welche nicht?

Aufgabe

Wir betrachten auf der Menge der Tiere die Äquivalenzrelation, bei der zwei Tiere als äquivalent angesehen werden, wenn sie die gleiche Anzahl an Gliedmaßen besitzen. Welche der folgenden Tiere sind zueinander in diesem Sinne äquivalent?

Ein Elefant, eine Schlange, eine Forelle, ein Delphin, eine Blindschleiche, ein Schimpanse, ein Tausendfüßer, ein Wenigfüßer, ein Eichhörnchen, ein Erdferkel, eine Ameise, ein Raptor, ein Tetrapode, ein Mensch, ein Pinguin.

Aufgabe

In der Biologie werden die Lebewesen mittels verschiedener (mehr oder weniger feiner) Einteilungen klassifiziert. Wie nennt man die Rangstufen, zu denen der Mensch gehört? Man gebe für jede Rangstufe ein Lebewesen an, das sich bezüglich dieser Rangstufe vom Menschen unterscheidet, aber bezüglich der darüberliegenden Rangstufe mit dem Menschen übereinstimmt.

Aufgabe

Wir sagen, dass Tage zueinander äquivalent sind, wenn sie auf den gleichen Wochentag fallen. Welche der folgenden Tage sind zueinander äquivalent, welche nicht?

1. Der ${}11.11.1877$,
2. Der ${}7.11.1877$,
3. Der ${}14.11.1877$,
4. Der ${}13.11.1877$,
5. Der ${}30.10.1877$,
6. Der ${}2.12.1877$,
7. Der ${}6.1.1878$,
8. Der ${}20.11.1877$,
9. Der ${}23.10.1877$,
10. Der ${}6.12.1877$.

Kommentar:

Hier fragen manche: Muss man dazu nicht wissen, welcher Wochentag der ${}11.11.1877$ war. Es ist in der Mathematik häufig sinnvoll, Objekte direkt miteinander zu vergleichen, nicht über ein drittes Vergleichsobjekt.

 

Aufgabe

Betrachte die zweielementige Menge ${}M=\{a,b\}$.

1. Bestimme alle Relationen auf ${}M$.
2. Welche dieser Relationen sind symmetrisch, reflexiv, transitiv?
3. Bei welchen Relationen handelt es sich um Äquivalenzrelationen?

Aufgabe

Es seien ${}p$ und ${}q$ zwei nichtäquivalente Aussagen. Welche der folgenden zusammengesetzten Aussagen sind zueinander äquivalent, welche nicht?

$p,\,q,\,p\wedge q,\,p\vee q,\,p\rightarrow q,\,p\rightarrow (q\rightarrow p),\,\neg p\vee q,\,p\vee \neg p.$

Aufgabe *

Seien ${}M$ und ${}N$ Mengen und sei ${}f\colon M\rightarrow N$ eine Abbildung. Zeige, dass durch die Festlegung

${}x\sim y\,,$

wenn

${}f(x)=f(y)\,,$

eine Äquivalenzrelation auf ${}M$ definiert wird.

Aufgabe

Zeige, dass die folgende Relation eine Äquivalenzrelation auf ${}\mathbb {Z}$ ist:

$x\sim y,{\text{ falls }}5{\text{ teilt }}x-y.$

Welche Zahlen sind bei dieser Relation äquivalent zueinander?

Kommentar:

Dies ist eine besonders wichtige und typische Aufgabe zu Äquivalenzrelationen. Die Sache hat natürlich nichts mit der ${}5$ zu tun, man könnte genausso gut jede andere natürliche Zahl nehmen (wobei bei ${}0$ und bei ${}1$ gewisse Besonderheiten auftreten). Die Aufgabe ist ein Vorgriff auf Lemma 12.4, auch Aufgabe 10.15 ist ähnlich.

Also, zwei Zahlen stehen in Relation, wenn ihre Differenz von ${}5$ geteilt wird, also ein Vielfaches der ${}5$ ist. Somit stehen etwa ${}3$ und ${}8$ oder ${}3$ und ${}13$ in Relation zueinander, ${}3$ und ${}7$ aber nicht. Bei Nachweis, dass eine Äquivalenzrelation vorliegt, muss man einfach die definierenden Eigenschaften durchgehen und die gegebene Teilbarkeit richtig formulieren. Die einzig sinnvolle Formulierung ist

$5{\text{ teilt }}(x-y){\text{ genau dann wenn, es gibt }}a\in \mathbb {Z} {\text{ mit }}x-y=5a,$

mit der man konsequent arbeiten soll.

Die Reflexivität beruht einfach auf

${}x-x=0=5\cdot 0\,.$

Die beiden anderen Eigenschaften einer Äquivalenzrelation sind bedingt formuliert. Wenn (für die Transitivität) ${}x\sim y$ und ${}y\sim z$ ist, dann muss auch ${}x\sim z$ sein. Die beiden Bedingungen bedeutet im vorliegenden Fall, dass es einerseits ein ${}a$ und andererseits ein ${}b$ mit

${}x-y=5a\,$

beziehungsweise

${}y-z=5b\,$

gibt. Dann ist direkt (Distributivgesetz)

${}x-z=(x-y)+(y-z)=5a+5b=5(a+b)\,.$

 

Aufgabe

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. Zeige, dass ein Punkt außerhalb des äußeren Kreises und ein Punkt des inneren Kreises zueinander äquivalent sind.

Aufgabe

Wir betrachten die Produktmenge ${}M=\mathbb {Z} \times \mathbb {Z}$. Wir fixieren wie in Beispiel 10.15 die Sprünge

$\pm (2,0)\,\,{\text{ und }}\,\,\pm (3,3),$

und sagen, dass zwei Punkte ${}P=(a,b),\,Q=(c,d)\in M$ äquivalent sind, wenn man ausgehend von ${}P$ den Punkt ${}Q$ mit einer Folge von diesen Sprüngen aus erreichen kann.

1. Zeige, dass die Punkte ${}P=(4,-3)$ und ${}P=(3,6)$ zueinander äquivalent sind.
2. Zeige, dass die Punkte ${}P=(4,-3)$ und ${}P=(3,7)$ nicht zueinander äquivalent sind.

Kommentar:

Dies ist eine zweidimensionale Version von Aufgabe 10.10 bzw. der Division mit Rest. Es geht um die von den beiden Sprüngen erzeugte Untergruppe der Gruppe ${}\mathbb {Z} \times \mathbb {Z}$. Für diese Untergruppen gibt es keine so einfache Charakterisierung wie Satz 8.4.

Die beiden Teile sind wesentlich verschieden, aber bei beiden Teilen geht es nur um die Differenz der beiden Vektoren, im zweiten Teil also um

${}(4,-3)-(3,7)=(1,-10)\,.$

Bei Teil a) erhält man mit etwas probieren eine Lösung. Bei Teil b) muss man zeigen, dass es definitiv nicht möglich ist, ${}(1,-10)$ in der Form

$x(2,0)+y(3,3)$

darzustellen. Dies kann allgemein schwierig sein, ist hier aber direkt klar, wenn man die zweite Komponente betrachtet.

 

Aufgabe

Die Äquatorflöhe leben auf den vollen Metern eines ${}40000$ Kilometer langen kreisrunden Bandes. Sie verfügen nur über einen Sprung, der sie sieben Meter nach vorne oder nach hinten bringt (und der beliebig oft wiederholt werden kann). Können sich alle Flöhe begegnen?

Aufgabe *

Zeige, dass die auf ${}\mathbb {Z} \times \mathbb {N} _{+}$ durch

$(a,b)\sim (c,d),{\text{ falls }}ad=bc,$

festgelegte Relation eine Äquivalenzrelation ist.

Aufgabe

Wir betrachten die rationalen Zahlen

${\frac {7}{3}},\,{\frac {5}{3}},\,3,\,{\frac {5}{2}},\,{\frac {4}{3}},\,4,\,{\frac {3}{4}},\,{\frac {1}{3}},\,{\frac {3}{2}},\,{\frac {5}{4}},\,-{\frac {1}{3}},\,{\frac {4}{5}}.$

1. Welche dieser Zahlen sind unter der Gaußklammeräquivalenzrelation („Vorkommaäquivalenzrelation“, siehe Beispiel 10.12) zueinander äquivalent?
2. Welche dieser Zahlen sind unter der Bruchanteiläquivalenzrelation („Nachkommaäquivalenzrelation“) zueinander äquivalent?

Aufgabe

Es sei ${}K$ ein Körper, ${}V$ ein ${}K$- Vektorraum und ${}U\subseteq V$ ein Untervektorraum. Wir betrachten die Relation auf ${}V$, die durch

$v_{1}\sim v_{2}{\text{ genau dann, wenn }}v_{1}-v_{2}\in U$

definiert ist. Zeige, dass diese Relation eine Äquivalenzrelation ist.

Aufgabe

Es sei ${}K$ ein Körper und ${}n\in \mathbb {N}$. Wir betrachten die folgende Relation auf ${}\operatorname {Mat} _{n}(K)$.

$M\sim N,{\text{ falls es eine invertierbare Matrix }}B{\text{ gibt mit }}M=BNB^{-1}.$

Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.

Aufgabe *

Es sei ${}G$ eine Gruppe. Betrachte die Relation ${}\sim$ auf ${}G$, die durch

$x\sim y{\text{ genau dann, wenn }}x=y{\text{ oder }}x=y^{-1}$

erklärt ist. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.

Aufgabe

Es sei ${}M$ eine Menge und ${}(R_{i})_{i\in I}$ eine Familie von Äquivalenzrelationen auf ${}M$. Zeige, dass durch den Durchschnitt ${}R:=\bigcap _{i\in I}R_{i}$ wieder eine Äquivalenzrelation auf ${}M$ definiert ist. Gilt dies auch für ${}\bigcup _{i\in I}R_{i}$?

Aufgabe

Es seien ${}D$ und ${}W$ Mengen. Wir betrachten auf der Abbildungsmenge ${}\operatorname {Abb} \,{\left(D,W\right)}$ diejenige Relation, bei der die Abbildungen

$f,g\colon D\longrightarrow W$

in Relation stehen, wenn es eine bijektive Abbildung

$\pi \colon D\longrightarrow D$

mit

${}f=g\circ \pi \,$

gibt. Zeige, dass dies eine Äquivalenzrelation ist.

Aufgabe

Es seien ${}D$ und ${}W$ Mengen. Wir betrachten auf der Abbildungsmenge ${}\operatorname {Abb} \,{\left(D,W\right)}$ diejenige Relation, bei der die Abbildungen

$f,g\colon D\longrightarrow W$

in Relation stehen, wenn es eine bijektive Abbildung

$\rho \colon W\longrightarrow W$

mit

${}f=\rho \circ g\,$

gibt. Zeige, dass dies eine Äquivalenzrelation ist.

Bei den folgenden Aufgaben überlege man sich auch, was die Äquivalenzrelationen für die Graphen der Funktionen bedeuten.

Aufgabe

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

${}\operatorname {Abb} \,{\left(K,K\right)}={\left\{f:K\rightarrow K\mid f{\text{ Funktion}}\right\}}\,$

die Menge der Abbildungen von ${}K$ nach ${}K$. Wir betrachten die Relation auf ${}\operatorname {Abb} \,{\left(K,K\right)}$, die durch ${}f\sim g$, falls es ein ${}d\in K$ mit

${}f=g+d\,$

gibt. Zeige, dass es sich dabei um eine Äquivalenzrelation handelt.

Aufgabe

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

${}\operatorname {Abb} \,{\left(K,K\right)}={\left\{f:K\rightarrow K\mid f{\text{ Funktion}}\right\}}\,$

die Menge der Abbildungen von ${}K$ nach ${}K$. Wir betrachten die Relation auf ${}\operatorname {Abb} \,{\left(K,K\right)}$, die durch ${}f\sim g$, falls es ein ${}c\in K$ mit

${}f(x)=g(x+c)\,$

für alle ${}x\in K$ gibt. Zeige, dass es sich dabei um eine Äquivalenzrelation handelt.

Aufgabe

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

${}\operatorname {Abb} \,{\left(K,K\right)}={\left\{f:K\rightarrow K\mid f{\text{ Funktion}}\right\}}\,$

die Menge der Abbildungen von ${}K$ nach ${}K$. Wir betrachten die Relation auf ${}\operatorname {Abb} \,{\left(K,K\right)}$, die durch ${}f\sim g$, falls es ein ${}c,d\in K$ mit

${}f(x)=g(x+c)+d\,$

für alle ${}x\in K$ gibt. Zeige, dass es sich dabei um eine Äquivalenzrelation handelt.

Aufgabe

Wir betrachten auf der Menge der quadratischen Polynome über dem Körper ${}K$ die Äquivalenzrelation aus Aufgabe 10.22. Finde für jedes quadratische Polynom einen besonders einfachen Repräsentanten.

Aufgabe *

Wir betrachten auf der Menge ${}C$ aller stetigen Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$ die folgende Relation: Es ist ${}f\sim g$, falls es eine nullstellenfreie stetige Funktion ${}\alpha \colon \mathbb {R} \rightarrow \mathbb {R}$ mit

${}f=g\cdot \alpha \,$

gibt.

1. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.
2. Zeige, dass aus ${}f\sim g$ folgt, dass die Nullstellenmenge von ${}f$ und von ${}g$ übereinstimmen.
3. Zeige, dass die beiden Funktionen

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

   und

   ${}g(x)=x^{2}\,$

   nicht zueinander äquivalent sind.

Aufgabe *

Es sei ${}M$ die Menge der zweimal stetig differenzierbaren Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$. Definiere auf ${}M$ eine Relation durch

$f\sim g{\text{ falls }}f(0)=g(0),\,f'(0)=g'(0){\text{ und }}f^{\prime \prime }(1)=g^{\prime \prime }(1).$

a) Zeige, dass dies eine Äquivalenzrelation ist.

b) Finde für jede Äquivalenzklasse dieser Äquivalenzrelation einen polynomialen Vertreter.

c) Zeige, dass diese Äquivalenzrelation mit der Addition von Funktionen verträglich ist.

d) Zeige, dass diese Äquivalenzrelation nicht mit der Multiplikation von Funktionen verträglich ist.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Zeige, dass die folgenden Äquivalenzrelationen auf der Menge der natürlichen Zahlen ${}\mathbb {N}$ übereinstimmen.

1. Die Einerziffer in der Zifferndarstellung zur Basis ${}7$ von ${}a$ und ${}b$ ist gleich.
2. Die Differenz ${}a-b$ ist ein Vielfaches der ${}7$.
3. ${}a$ und ${}b$ haben bei der Division durch ${}7$ den gleichen Rest.

Aufgabe (2 Punkte)

Wir betrachten für je zwei Teilmengen ${}A,B\subseteq \mathbb {N}$ die symmetrische Differenz

${}A\triangle B:=(A\setminus B)\cup (B\setminus A)\,.$

Wir setzen ${}A\sim B$, falls ${}A\triangle B$ endlich ist. Zeige, dass dadurch eine Äquivalenzrelation auf ${}{\mathfrak {P}}\,(\mathbb {N} )$ definiert wird.

Aufgabe (4 Punkte)

Alle Springmäuse leben in ${}\mathbb {Z} ^{2}$ und verfügen über zwei Sprünge, nämlich den Sprung ${}\pm (3,4)$ und den Sprung ${}\pm (5,2)$. Wie viele Springmaus-Populationen gibt es? Die Springmäuse Albert, Beate, Erich, Heinz, Sabine und Frida sitzen in den Positionen

$(14,11),\,(13,15),\,(17,12),\,(15,19),\,(16,16){\mbox{ und }}(12,20).$

Welche Springmäuse können sich begegnen?

Aufgabe (3 Punkte)

Es seien ${}M_{1}$ und ${}M_{2}$ Mengen und ${}\sim _{1}$ sei eine Äquivalenzrelation auf ${}M_{1}$ und ${}\sim _{2}$ sei eine Äquivalenzrelation auf ${}M_{2}$. Betrachte die Relation ${}\sim$ auf der Produktmenge ${}M_{1}\times M_{2}$, die durch

$(a_{1},a_{2})\sim (b_{1},b_{2}),{\text{ falls }}a_{1}\sim _{1}b_{1}{\text{ und }}a_{2}\sim _{2}b_{2}{\text{ gilt}},$

definiert ist. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.

Zeige ferner, dass auf ${}M_{1}\times M_{2}$ die durch

$(a_{1},a_{2})\sim (b_{1},b_{2}),{\text{ falls }}a_{1}\sim _{1}b_{1}{\text{ oder }}a_{2}\sim _{2}b_{2}{\text{ gilt}},$

definierte Relation keine Äquivalenzrelation ist.

Aufgabe (2 Punkte)

Seien ${}M$ und ${}N$ Mengen und sei ${}f\colon M\rightarrow N$ eine Abbildung. Es sei ${}\sim$ eine Äquivalenzrelation auf ${}N$. Zeige, dass durch ${}x\equiv x'$, falls ${}f(x)\sim f(x')$ gilt, eine Äquivalenzrelation auf ${}M$ definiert wird.

Aufgabe (3 Punkte)

Es seien ${}D$ und ${}W$ Mengen. Wir betrachten auf der Abbildungsmenge ${}\operatorname {Abb} \,{\left(D,W\right)}$ diejenige Relation, bei der die Abbildungen

$f,g\colon D\longrightarrow W$

in Relation stehen, wenn es bijektive Abbildungen

$\pi \colon D\longrightarrow D$

und

$\rho \colon W\longrightarrow W$

mit

${}f=\rho \circ g\circ \pi \,$

gibt. Zeige, dass dies eine Äquivalenzrelation ist.