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

In der Grundmenge \(G=\{1,2,3,4,5,6\}\) seien \(A=\{1,2,3,4\}\), \(B=\{3,4,5\}\) und \(C=\{1,5,6\}\).

a) Bestimmen Sie \(A\cup B\), \(A\cap B\), \(A\setminus B\) und \(B\setminus A\).
b) Bestimmen Sie \(A\cap(B\cup C)\) und \((A\cap B)\cup(A\cap C)\). Welches Gesetz wird bestätigt?
c) Bestimmen Sie \(\overline{A\cup B}\) und \(\bar A\cap\bar B\).
d) Zeichnen Sie ein Venn-Diagramm mit allen sechs Elementen.

Bestimmen Sie die folgenden Mengen und ihre Mächtigkeiten.

a) \(\mathcal P(\{a,b,c\})\)
b) \(\{1,2\}\times\{x,y,z\}\)
c) \(\mathcal P(\mathcal P(\{1\}))\)
d) Begründen Sie allgemein \(|\mathcal P(M)|=2^n\) für \(|M|=n\).

Beweisen Sie für beliebige Mengen \(A,B,C\) mit einem Elementbeweis (zwei Inklusionen oder Äquivalenzkette).

a) \(A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)\)
b) \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\)
c) \(A\subseteq B\iff A\cap B=A\)

Prüfen Sie, ob die Relation reflexiv, symmetrisch, antisymmetrisch oder transitiv ist. Begründen Sie oder geben Sie ein Gegenbeispiel an.

a) Auf \(\{1,2,3\}\): \(R_1=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\)
b) Auf \(\mathbb R\): \(x\le y\)
c) Auf \(\{1,2,3\}\): \(R_3=\{(1,2),(2,3)\}\)
d) Auf \(\mathbb Z\): \(a\sim b\iff a-b\) ist gerade

Beschreiben Sie die Äquivalenzklassen der Äquivalenzrelationen.

a) Auf \(\mathbb Z\): \(a\sim b\iff4\mid a-b\). Wie viele Klassen gibt es? In welcher Klasse liegt \(-7\)?
b) Auf \(\mathbb R^2\): \((x,y)\sim(x',y')\iff x^2+y^2=x'^2+y'^2\).
c) Auf \(\mathbb R\): \(x\sim y\iff x-y\in\mathbb Z\). Geben Sie ein Vertretersystem an.

Untersuchen Sie die Abbildungen auf Injektivität, Surjektivität und Bijektivität. Geben Sie im bijektiven Fall die Umkehrabbildung an.

a) \(f:\mathbb R\to\mathbb R\), \(f(x)=3x-1\)
b) \(g:\mathbb R\to\mathbb R\), \(g(x)=x^2\), und \(\tilde g:[0,\infty)\to[0,\infty)\), \(\tilde g(x)=x^2\)
c) \(h:\mathbb N\to\mathbb N\), \(h(n)=n+1\) (mit \(\mathbb N=\{1,2,\dots\}\))
d) \(k:\mathbb Z\to\mathbb Z\), \(k(n)=\lfloor n/2\rfloor\)

An einer Hochschule beginnen in einem Studiengang \(400\) Erstsemester. Jede Person erhält eine Matrikelnummer. Wir betrachten die Abbildungen \(m\): Person \(\mapsto\) Matrikelnummer und \(g\): Person \(\mapsto\) Geburtstag (Tag und Monat, \(366\) Möglichkeiten).

a) Warum muss \(m\) injektiv sein? Ist \(m\) surjektiv auf die Menge aller sechsstelligen Zahlen?
b) Zeigen Sie mit dem Schubfachprinzip, dass \(g\) nicht injektiv sein kann.
c) Kann \(g\) surjektiv sein? Was müsste dafür gelten?
d) Die Relation „hat am selben Tag Geburtstag“ ist eine Äquivalenzrelation. Wie viele Klassen gibt es höchstens?

Von \(120\) Erstsemestern besuchen \(65\) das Tutorium zur Linearen Algebra (L), \(50\) das Tutorium zur Analysis (A) und \(25\) beide. Außerdem nehmen \(30\) am Programmierkurs (P) teil; davon besuchen \(12\) auch L, \(10\) auch A und \(5\) alle drei Angebote.

a) Wie viele besuchen mindestens eines der beiden Tutorien?
b) Wie viele besuchen nur das Tutorium zur Linearen Algebra (ohne Analysis)?
c) Wie viele nehmen an mindestens einem der drei Angebote teil?
d) Wie viele nehmen an keinem Angebot teil? Prüfen Sie mit einem Venn-Diagramm.

In einem kleinen Verkehrsverbund gibt es die Linien S1 (A – B – C), S2 (C – D) und einen Bus (E – F). Alle Linien fahren in beide Richtungen. Zwei Haltestellen stehen in der Relation \(x\to y\), wenn man ohne Umsteigen fahren kann, und in der Relation \(x\approx y\), wenn man mit beliebig vielen Umstiegen fahren kann (oder \(x=y\) ist).

a) Ist \(\to\) symmetrisch? Ist \(\to\) transitiv?
b) Zeigen Sie, dass \(\approx\) eine Äquivalenzrelation ist.
c) Bestimmen Sie die Äquivalenzklassen von \(\approx\).
d) Eine neue Buslinie verbindet D und E. Wie ändern sich die Klassen?

Uhrzeiten rechnet man modulo \(24\), Wochentage modulo \(7\). Zwei Zeitpunkte sind „gleich auf der Uhr“, wenn sich die Stunden um ein Vielfaches von \(24\) unterscheiden.

a) Es ist \(9\) Uhr. Welche Uhrzeit zeigt die Uhr in \(100\) Stunden?
b) Heute ist Montag. Welcher Wochentag ist in \(1000\) Tagen?
c) Welche Uhrzeit ist \(1000\) Stunden nach \(9\) Uhr?
d) Erklären Sie, warum man in \(\mathbb Z/24\mathbb Z\) Addition von Klassen definieren kann, obwohl verschiedene Vertreter gewählt werden können.

Vier Studierende sollen auf drei Tutoriumsgruppen verteilt werden. Eine Verteilung ist eine Abbildung \(f:\{1,2,3,4\}\to\{\mathrm I,\mathrm{II},\mathrm{III}\}\).

a) Wie viele Verteilungen gibt es insgesamt?
b) Gibt es eine injektive Verteilung? Begründen Sie.
c) Wie viele Verteilungen lassen eine bestimmte Gruppe leer? Wie viele lassen mindestens eine Gruppe leer?
d) Wie viele Verteilungen sind surjektiv, sodass jede Gruppe jemanden bekommt?

Auf der Menge \(T=\{1,2,3,4,6,9,12,18,36\}\) der Teiler von \(36\) betrachten wir die Teilbarkeitsrelation \(a\mid b\). Im Kurs ist ihr Hasse-Diagramm abgebildet.

a) Zeigen Sie, dass \(\mid\) eine Ordnungsrelation auf \(T\) ist.
b) Ist sie total? Geben Sie zwei unvergleichbare Elemente an.
c) Bestimmen Sie das größte gemeinsame untere Element von \(12\) und \(18\) sowie das kleinste gemeinsame obere Element von \(4\) und \(9\). Wie heißen diese Zahlen sonst?
d) Wie viele Paare \((a,b)\) mit \(a\ne b\) und \(a\mid b\) gibt es? Warum sind das mehr als die \(12\) Linien im Diagramm?

Buchstaben werden als Zahlen \(0\) bis \(25\) codiert. Zwei Verschlüsselungen sind die Verschiebung \(f(x)=x+3\bmod26\) und die Multiplikation \(g(x)=7x\bmod26\).

a) Zeigen Sie, dass \(g\) bijektiv ist, indem Sie \(7\cdot15\equiv1\pmod{26}\) nachrechnen und \(g^{-1}\) angeben.
b) Bestimmen Sie \(g\circ f\) und \(f\circ g\) als Formeln. Sind sie gleich?
c) Verschlüsseln Sie den Buchstaben C (\(=2\)) mit beiden Verkettungen.
d) Bestimmen Sie die Umkehrabbildung von \(g\circ f\) und entschlüsseln Sie \(18\).

In einer Übungsklausur werden \(0\) bis \(20\) Punkte vergeben (nur ganze Punkte). Die Notenabbildung \(N\) ordnet die Punkte so zu:

a) Ist \(N:\{0,\dots,20\}\to\{1,\dots,5\}\) injektiv bzw. surjektiv?
b) Bestimmen Sie die Urbilder \(N^{-1}(\{1,2\})\) und \(N^{-1}(\{5\})\) und ihre Mächtigkeiten.
c) Die Relation „bekommt dieselbe Note“ ist eine Äquivalenzrelation. Beschreiben Sie ihre Klassen.
d) Zeigen Sie an diesem Beispiel, dass \(N(N^{-1}(V))=V\) für surjektives \(N\) gilt, aber \(N^{-1}(N(U))\ne U\) möglich ist.

Sei \(f:A\to B\) eine Abbildung, \(U_1,U_2\subseteq A\) und \(V_1,V_2\subseteq B\). In dieser Aufgabe untersuchen Sie, welche Rechenregeln für Bilder und Urbilder gelten.

a) Beweisen Sie \(f(U_1\cap U_2)\subseteq f(U_1)\cap f(U_2)\).
b) Zeigen Sie mit \(f(x)=x^2\), \(U_1=\{-1\}\), \(U_2=\{1\}\), dass Gleichheit nicht gelten muss.
c) Beweisen Sie: Ist \(f\) injektiv, so gilt Gleichheit.
d) Beweisen Sie \(f^{-1}(V_1\cap V_2)=f^{-1}(V_1)\cap f^{-1}(V_2)\).
e) Gilt auch \(f(U_1\cup U_2)=f(U_1)\cup f(U_2)\)? Begründen Sie kurz.

Eine Menge ist abzählbar, wenn man ihre Elemente lückenlos durchnummerieren kann, also eine Bijektion zu \(\mathbb N_0=\{0,1,2,\dots\}\) existiert. Für \(\mathbb Z\) verwendet man \(z(n)=\frac n2\) für gerades \(n\) und \(z(n)=-\frac{n+1}2\) für ungerades \(n\). Für Paare natürlicher Zahlen verwendet man die Cantorsche Paarungsfunktion \(\pi(m,n)=\frac{(m+n)(m+n+1)}2+n\).

a) Berechnen Sie \(z(0),\dots,z(6)\) und zeigen Sie, dass \(z:\mathbb N_0\to\mathbb Z\) bijektiv ist.
b) Berechnen Sie \(\pi(0,0)\), \(\pi(1,0)\), \(\pi(0,1)\), \(\pi(2,1)\) und \(\pi(3,0)\).
c) Erklären Sie anhand einer Skizze der Gitterpunkte, warum \(\pi\) die Paare entlang der Diagonalen \(m+n=k\) durchnummeriert.
d) Folgern Sie, dass \(\mathbb Q\) abzählbar ist.

Ein Hotel hat die Zimmer \(1,2,3,\dots\), alle belegt. Die Hotelleitung darf Gäste umziehen lassen, aber jeder Gast muss danach wieder ein eigenes Zimmer haben. Mathematisch ist ein Umzugsplan eine injektive Abbildung \(u:\mathbb N\to\mathbb N\) (altes Zimmer \(\mapsto\) neues Zimmer).

a) Ein neuer Gast kommt an. Geben Sie einen Umzugsplan an, der Zimmer \(1\) frei macht.
b) Ein Bus mit unendlich vielen Gästen \(b_1,b_2,\dots\) kommt an. Zeigen Sie, dass \(u(n)=2n\) genügend Platz schafft, und weisen Sie den Neuen Zimmer zu.
c) Ist \(u(n)=2n\) surjektiv? Was bedeutet die Antwort für das Hotel?
d) Zeigen Sie, dass \(\mathbb N\) und die Menge der geraden Zahlen gleichmächtig sind, und erklären Sie, warum das bei endlichen Mengen unmöglich wäre.

Auf \(M=\mathbb Z\times(\mathbb Z\setminus\{0\})\) sei \((a,b)\sim(c,d)\iff ad=bc\). Man denkt bei \((a,b)\) an den Bruch \(\frac ab\).

a) Zeigen Sie, dass \(\sim\) reflexiv und symmetrisch ist.
b) Zeigen Sie die Transitivität. Wo wird \(d\ne0\) benötigt?
c) Welche Paare liegen in der Klasse von \((2,3)\)? Geben Sie vier an.
d) Zeigen Sie, dass die Addition \([(a,b)]+[(c,d)]=[(ad+bc,bd)]\) nicht von den Vertretern abhängt (Wohldefiniertheit).

Seien \(f:A\to B\) und \(g:B\to C\) Abbildungen.

a) Zeigen Sie: Ist \(g\circ f\) injektiv, so ist \(f\) injektiv.
b) Zeigen Sie: Ist \(g\circ f\) surjektiv, so ist \(g\) surjektiv.
c) Geben Sie ein Beispiel an, in dem \(g\circ f\) bijektiv, aber \(g\) nicht injektiv ist.
d) Folgern Sie: Gibt es \(g\) mit \(g\circ f=\mathrm{id}_A\) und \(h\) mit \(f\circ h=\mathrm{id}_B\), so ist \(f\) bijektiv und \(g=h\).

Georg Cantor bewies, dass keine Menge gleichmächtig zu ihrer Potenzmenge ist. Sei \(f:M\to\mathcal P(M)\) eine beliebige Abbildung und \(D=\{x\in M:x\notin f(x)\}\).

a) Bestimmen Sie \(D\) für \(M=\{1,2,3\}\) und \(f(1)=\{1,2\}\), \(f(2)=\emptyset\), \(f(3)=\{1,3\}\). Liegt \(D\) im Bild von \(f\)?
b) Beweisen Sie allgemein: \(D\) liegt nicht im Bild von \(f\). Nehmen Sie dazu \(D=f(d)\) an und fragen Sie, ob \(d\in D\) gilt.
c) Folgern Sie, dass \(\mathcal P(\mathbb N)\) nicht abzählbar ist.
d) Erklären Sie, warum es damit unendlich viele verschiedene Stufen von Unendlichkeit gibt.