Mengen, Relationen und Abbildungen – Mathe Studium 1. Semester Arbeitsblatt Lösungen zum Herunterladen als PDF

← Zurück zu den Aufgaben

1. Lösung zu Aufgabe 1

   a) \(A\cup B=\{1,2,3,4,5\}\), \(A\cap B=\{3,4\}\), \(A\setminus B=\{1,2\}\), \(B\setminus A=\{5\}\).
   b) \(B\cup C=\{1,3,4,5,6\}\), also \(A\cap(B\cup C)=\{1,3,4\}\). \(A\cap B=\{3,4\}\), \(A\cap C=\{1\}\), Vereinigung \(\{1,3,4\}\). Das Distributivgesetz ist bestätigt.
   c) \(\overline{A\cup B}=\{6\}\). \(\bar A=\{5,6\}\), \(\bar B=\{1,2,6\}\), \(\bar A\cap\bar B=\{6\}\). De Morgan ist bestätigt.
   d) Im Schnitt \(A\cap B\) liegen \(3,4\); nur in \(A\): \(2\); in \(A\cap C\) ohne \(B\): \(1\); in \(B\cap C\) ohne \(A\): \(5\); nur in \(C\): \(6\). Alle Elemente liegen in mindestens einer Menge.

2. Lösung zu Aufgabe 2

   a) \(\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\): \(8=2^3\) Elemente.
   b) \(\{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}\): \(2\cdot3=6\) Paare.
   c) \(\mathcal P(\{1\})=\{\emptyset,\{1\}\}\) hat \(2\) Elemente, also hat \(\mathcal P(\mathcal P(\{1\}))=\{\emptyset,\{\emptyset\},\{\{1\}\},\{\emptyset,\{1\}\}\}\) genau \(4\) Elemente.
   d) Für jedes der \(n\) Elemente entscheidet man unabhängig „gehört dazu“ oder „gehört nicht dazu“. Das ergibt \(2\cdot2\cdots2=2^n\) Möglichkeiten (alternativ: Induktion über \(n\)).

3. Lösung zu Aufgabe 3

   a) \(x\in A\setminus(B\cup C)\iff x\in A\wedge\neg(x\in B\vee x\in C)\iff x\in A\wedge x\notin B\wedge x\notin C\iff(x\in A\wedge x\notin B)\wedge(x\in A\wedge x\notin C)\iff x\in(A\setminus B)\cap(A\setminus C)\). \(\square\)
   b) \(x\in A\cap(B\cup C)\iff x\in A\wedge(x\in B\vee x\in C)\iff(x\in A\wedge x\in B)\vee(x\in A\wedge x\in C)\iff x\in(A\cap B)\cup(A\cap C)\), mit dem Distributivgesetz der Logik. \(\square\)
   c) „\(\Rightarrow\)“: \(A\cap B\subseteq A\) gilt immer. Ist \(x\in A\), so wegen \(A\subseteq B\) auch \(x\in B\), also \(x\in A\cap B\). „\(\Leftarrow\)“: Ist \(x\in A=A\cap B\), so \(x\in B\). \(\square\)

4. Lösung zu Aufgabe 4

   a) Reflexiv (alle \((a,a)\) enthalten), symmetrisch (zu \((1,2)\) gehört \((2,1)\)), transitiv (geprüft für alle Paare), nicht antisymmetrisch (\(1\sim2\), \(2\sim1\), \(1\ne2\)). Äquivalenzrelation mit Klassen \(\{1,2\}\), \(\{3\}\).
   b) Reflexiv, antisymmetrisch und transitiv, aber nicht symmetrisch (\(1\le2\), nicht \(2\le1\)): eine Ordnungsrelation.
   c) Nicht reflexiv (\((1,1)\notin R_3\)), nicht symmetrisch, antisymmetrisch (keine Paare in beiden Richtungen), nicht transitiv (\((1,2),(2,3)\in R_3\), aber \((1,3)\notin R_3\)).
   d) Reflexiv (\(0\) ist gerade), symmetrisch (\(-(a-b)\) gerade), transitiv (Summe gerader Zahlen ist gerade), nicht antisymmetrisch: Äquivalenzrelation mit den Klassen gerade und ungerade Zahlen.

5. Lösung zu Aufgabe 5

   a) Vier Klassen \([0],[1],[2],[3]\) nach dem Rest bei Division durch \(4\). \(-7=4\cdot(-2)+1\), also \(-7\in[1]\).
   b) Zwei Punkte sind äquivalent, wenn sie gleich weit vom Ursprung entfernt sind. Die Klassen sind die Kreise um \(0\) mit Radius \(r>0\) und der Ursprung selbst.
   c) Zahlen sind äquivalent, wenn sie denselben Nachkommaanteil haben. Jede Klasse enthält genau eine Zahl aus \([0,1)\); dieses Intervall ist ein Vertretersystem. Anschaulich wickelt man die Zahlengerade auf einen Kreis vom Umfang \(1\).

6. Lösung zu Aufgabe 6

   a) Aus \(3x_1-1=3x_2-1\) folgt \(x_1=x_2\): injektiv. \(y=3x-1\iff x=\frac{y+1}3\): surjektiv. Bijektiv mit \(f^{-1}(y)=\frac{y+1}3\).
   b) \(g(-1)=g(1)\): nicht injektiv; \(-1\) hat kein Urbild: nicht surjektiv. \(\tilde g\) ist bijektiv mit \(\tilde g^{-1}(y)=\sqrt y\).
   c) \(n_1+1=n_2+1\Rightarrow n_1=n_2\): injektiv. \(1\) hat kein Urbild in \(\mathbb N\): nicht surjektiv.
   d) \(k(0)=k(1)=0\): nicht injektiv. Zu \(m\in\mathbb Z\) ist \(k(2m)=m\): surjektiv.

7. Lösung zu Aufgabe 7

   a) Zwei Personen dürfen nicht dieselbe Nummer haben, sonst könnte man sie nicht unterscheiden. Surjektiv ist \(m\) nicht: \(400\) Personen können höchstens \(400\) der \(900\,000\) sechsstelligen Zahlen belegen.
   b) \(400\) Personen werden auf \(366\) Tage verteilt. Wäre \(g\) injektiv, bräuchte man mindestens \(400\) verschiedene Tage. Also haben mindestens zwei Personen am selben Tag Geburtstag.
   c) Möglich ist es: Dazu müsste jeder der \(366\) Tage, auch der 29. Februar, mindestens einmal vorkommen. Das ist bei \(400\) Personen unwahrscheinlich, aber nicht ausgeschlossen.
   d) Die Klassen sind die Fasern \(g^{-1}(\{d\})\) der belegten Tage, also höchstens \(366\) Klassen.

8. Lösung zu Aufgabe 8

   a) \(|L\cup A|=65+50-25=90\).
   b) \(|L\setminus A|=65-25=40\).
   c) \(|L\cup A\cup P|=65+50+30-25-12-10+5=103\).
   d) \(120-103=17\). Im Venn-Diagramm: nur L: \(65-25-12+5=33\), nur A: \(50-25-10+5=20\), nur P: \(30-12-10+5=13\), L und A ohne P: \(20\), L und P ohne A: \(7\), A und P ohne L: \(5\), alle drei: \(5\). Summe \(103\).

9. Lösung zu Aufgabe 9

   a) Symmetrisch: ja, die Linien fahren in beide Richtungen. Transitiv: nein, \(A\to C\) und \(C\to D\), aber nicht \(A\to D\) (Umstieg in C nötig).
   b) Reflexiv nach Definition; symmetrisch, da man jede Fahrt rückwärts fahren kann; transitiv, da man zwei Fahrten aneinanderhängen kann.
   c) \(\{A,B,C,D\}\) und \(\{E,F\}\): die zusammenhängenden Teile des Netzes.
   d) Dann ist alles verbunden: Es gibt nur noch eine Klasse \(\{A,B,C,D,E,F\}\).

10. Lösung zu Aufgabe 10

    a) \(9+100=109=4\cdot24+13\): \(13\) Uhr.
    b) \(1000=142\cdot7+6\). Sechs Tage nach Montag: Sonntag.
    c) \(1009=42\cdot24+1\): \(1\) Uhr nachts.
    d) Ist \(a\equiv a'\) und \(b\equiv b'\pmod{24}\), so \(a+b-(a'+b')=(a-a')+(b-b')\) ein Vielfaches von \(24\). Die Summenklasse hängt also nicht von der Wahl der Vertreter ab: Die Addition ist wohldefiniert.

11. Lösung zu Aufgabe 11

    a) Jede der vier Personen hat drei Möglichkeiten: \(3^4=81\).
    b) Nein: Nach dem Schubfachprinzip müssen zwei der vier Personen in derselben Gruppe landen.
    c) Ohne Gruppe I: \(2^4=16\) Verteilungen. Inklusion und Exklusion: \(3\cdot16-3\cdot1+0=45\) Verteilungen lassen mindestens eine Gruppe leer (\(3\) Verteilungen lassen zwei Gruppen leer).
    d) \(81-45=36\). Kontrolle: Eine Gruppe bekommt zwei Personen (\(3\) Wahlen der Gruppe, \(\binom42=6\) Paare), die übrigen zwei werden auf zwei Gruppen verteilt (\(2\) Arten): \(3\cdot6\cdot2=36\).

12. Lösung zu Aufgabe 12

    a) Reflexiv: \(a=1\cdot a\). Antisymmetrisch: Aus \(b=ka\), \(a=lb\) mit \(k,l\in\mathbb N\) folgt \(kl=1\), also \(k=l=1\). Transitiv: Aus \(b=ka\), \(c=lb\) folgt \(c=(kl)a\).
    b) Nicht total: \(4\nmid9\) und \(9\nmid4\).
    c) Untere Schranken von \(12\) und \(18\): \(1,2,3,6\); die größte ist \(6=\operatorname{ggT}(12,18)\). Obere Schranke von \(4\) und \(9\): nur \(36=\operatorname{kgV}(4,9)\).
    d) \(27\) Paare (zum Beispiel \(1\mid b\) für \(8\) Werte \(b\)). Das Diagramm zeigt nur direkte Teilbarkeiten; die übrigen folgen durch Transitivität (etwa \(2\mid12\) über \(2\mid4\mid12\)).

13. Lösung zu Aufgabe 13

    a) \(7\cdot15=105=4\cdot26+1\). Also ist \(g^{-1}(y)=15y\bmod26\), denn \(15\cdot7x\equiv x\). Mit Umkehrabbildung ist \(g\) bijektiv.
    b) \((g\circ f)(x)=7(x+3)=7x+21\), \((f\circ g)(x)=7x+3\) (jeweils mod \(26\)). Verschieden: Die Verkettung ist nicht kommutativ.
    c) \(g(f(2))=7\cdot5=35\equiv9\) (J). \(f(g(2))=14+3=17\) (R).
    d) \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\): \(y\mapsto15y-3\equiv15(y-21)\). Für \(y=18\): \(15\cdot(-3)=-45\equiv7\) (H). Probe: \(7\cdot(7+3)=70\equiv18\).

14. Lösung zu Aufgabe 14

    a) Nicht injektiv (\(N(18)=N(19)=1\)); surjektiv, da jede Note vorkommt.
    b) \(N^{-1}(\{1,2\})=\{15,\dots,20\}\) mit \(6\) Elementen; \(N^{-1}(\{5\})=\{0,\dots,9\}\) mit \(10\) Elementen.
    c) Die fünf Klassen sind die Punktebereiche \(\{0..9\}\), \(\{10,11\}\), \(\{12,13,14\}\), \(\{15,16,17\}\), \(\{18,19,20\}\): genau die Fasern \(N^{-1}(\{k\})\).
    d) \(V=\{2\}\): \(N^{-1}(V)=\{15,16,17\}\), \(N(\{15,16,17\})=\{2\}=V\). \(U=\{16\}\): \(N(U)=\{2\}\), \(N^{-1}(\{2\})=\{15,16,17\}\ne U\).

15. Lösung zu Aufgabe 15

    a) Ist \(y\in f(U_1\cap U_2)\), so \(y=f(x)\) mit \(x\in U_1\) und \(x\in U_2\). Dann \(y\in f(U_1)\) und \(y\in f(U_2)\). \(\square\)
    b) \(U_1\cap U_2=\emptyset\), also \(f(U_1\cap U_2)=\emptyset\). Aber \(f(U_1)=f(U_2)=\{1\}\), der Schnitt ist \(\{1\}\).
    c) Sei \(y\in f(U_1)\cap f(U_2)\), also \(y=f(x_1)=f(x_2)\) mit \(x_i\in U_i\). Injektivität liefert \(x_1=x_2\in U_1\cap U_2\), also \(y\in f(U_1\cap U_2)\). \(\square\)
    d) \(x\in f^{-1}(V_1\cap V_2)\iff f(x)\in V_1\wedge f(x)\in V_2\iff x\in f^{-1}(V_1)\cap f^{-1}(V_2)\). \(\square\)
    e) Ja: \(y\in f(U_1\cup U_2)\iff\exists x\in U_1\cup U_2:y=f(x)\iff y\in f(U_1)\vee y\in f(U_2)\).

16. Lösung zu Aufgabe 16

    a) \(0,-1,1,-2,2,-3,3\). Gerade \(n\) treffen genau die Zahlen \(\ge0\), ungerade genau die negativen, jeweils injektiv; also bijektiv mit \(z^{-1}(k)=2k\) für \(k\ge0\) und \(z^{-1}(k)=-2k-1\) für \(k<0\).
    b) \(0\), \(1\), \(2\), \(\frac{3\cdot4}2+1=7\), \(\frac{3\cdot4}2+0=6\).
    c) Auf der Diagonale \(m+n=k\) liegen \(k+1\) Punkte. Vorher wurden \(1+2+\dots+k=\frac{k(k+1)}2\) Punkte nummeriert; innerhalb der Diagonale zählt \(n\) weiter. So erhält jeder Punkt genau eine Nummer.
    d) Jede rationale Zahl ist \(\pm\frac pq\) mit \(p\in\mathbb N_0\), \(q\in\mathbb N\). Die Paare \((p,q)\) sind abzählbar, ebenso ihre Vorzeichenvarianten. Lässt man doppelte Darstellungen weg, bleibt eine unendliche Teilmenge einer abzählbaren Menge, also abzählbar.

17. Lösung zu Aufgabe 17

    a) \(u(n)=n+1\) ist injektiv, und \(1\) liegt nicht im Bild. Der neue Gast bekommt Zimmer \(1\).
    b) \(u\) ist injektiv, die Bewohner belegen genau die geraden Zimmer. Gast \(b_k\) bekommt Zimmer \(2k-1\); das ist injektiv, und alle Zimmer sind wieder belegt.
    c) Nein, ungerade Zahlen haben kein Urbild. Gerade das ist der freie Platz für die neuen Gäste.
    d) \(n\mapsto2n\) ist eine Bijektion von \(\mathbb N\) auf die geraden Zahlen. Bei einer endlichen Menge mit \(n\) Elementen hat eine echte Teilmenge weniger als \(n\) Elemente, und injektive Abbildungen in eine kleinere Menge gibt es nach dem Schubfachprinzip nicht.

18. Lösung zu Aufgabe 18

    a) \(ab=ba\): reflexiv. Aus \(ad=bc\) folgt \(cb=da\): symmetrisch.
    b) Aus \(ad=bc\) und \(cf=de\) folgt \(adf=bcf=bde\), also \(d(af-be)=0\). Wegen \(d\ne0\) ist \(af=be\), also \((a,b)\sim(e,f)\). \(\square\)
    c) Zum Beispiel \((4,6)\), \((-2,-3)\), \((20,30)\), \((-6,-9)\): alle \((2k,3k)\) mit \(k\ne0\).
    d) Sei \((a,b)\sim(a',b')\), also \(ab'=a'b\). Zu zeigen: \((ad+bc)b'd=(a'd+b'c)bd\). Links \(ab'd^2+bb'cd\), rechts \(a'bd^2+bb'cd\); wegen \(ab'=a'b\) gleich. Für den zweiten Summanden analog. \(\square\)

19. Lösung zu Aufgabe 19

    a) Aus \(f(x_1)=f(x_2)\) folgt \(g(f(x_1))=g(f(x_2))\) und wegen der Injektivität von \(g\circ f\) dann \(x_1=x_2\). \(\square\)
    b) Zu \(c\in C\) gibt es \(a\) mit \(g(f(a))=c\). Dann ist \(b=f(a)\) ein Urbild von \(c\) unter \(g\). \(\square\)
    c) \(A=C=\{1\}\), \(B=\{1,2\}\), \(f(1)=1\), \(g(1)=g(2)=1\). Dann ist \(g\circ f=\mathrm{id}\), aber \(g\) nicht injektiv.
    d) Nach a) ist \(f\) injektiv, nach b) (mit \(f\circ h\)) surjektiv. Außerdem \(g=g\circ(f\circ h)=(g\circ f)\circ h=h\). \(\square\)

20. Lösung zu Aufgabe 20

    a) \(1\in f(1)\), \(2\notin f(2)\), \(3\in f(3)\). Also \(D=\{2\}\). Die Bilder sind \(\{1,2\},\emptyset,\{1,3\}\); \(\{2\}\) kommt nicht vor.
    b) Wäre \(D=f(d)\), dann gälte: \(d\in D\iff d\notin f(d)\iff d\notin D\). Widerspruch. Also ist keine Abbildung \(M\to\mathcal P(M)\) surjektiv. \(\square\)
    c) Eine Bijektion \(\mathbb N\to\mathcal P(\mathbb N)\) wäre insbesondere surjektiv – das ist nach b) unmöglich.
    d) Man bildet \(\mathbb N\), \(\mathcal P(\mathbb N)\), \(\mathcal P(\mathcal P(\mathbb N))\), … Jede Stufe ist echt mächtiger als die vorige, die Folge bricht nie ab.