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

Übungsaufgaben

Aufgabe

In der Planung für einen Laufwettbewerb wurden die folgenden Bahnen vergeben.

${}k$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
${}F(k)$	${}N$	${}C$	${}Z$	${}G$	${}R$	${}D$	${}M$	${}S$

Leider wurden ${}C$ und ${}R$ des Dopings überführt und dürfen nicht teilnehmen. In dieser Situation möchte man auf die Außenbahnen ${}7$ und ${}8$ verzichten. Erstelle aus der Nummerierung ${}F$ eine möglichst einfache neue Nummerierung (also eine bijektive Abbildung) für die neue Situation.

Aufgabe

Es seien ${}k$ und ${}n$ natürliche Zahlen. Zeige, dass die (Nachfolger-)Abbildung

\{k,\ldots ,n\}\longrightarrow \{k^{\prime },\ldots ,n^{\prime }\},\,i\longmapsto i^{\prime },

bijektiv ist.

Aufgabe

Zeige durch Induktion nach ${}n$ , dass jede Teilmenge ${}T$ von ${}{\{1,\ldots ,n\}}$ endlich ist.

Kommentar:

Der Sachverhalt ist „klar“. Es geht aber darum im Sinne der Vorlesung zu zeigen, wie man zu der beliebigen Teilemenge

{}T\subseteq {\{1,\ldots ,n\}}\,

einer bijektive Abbildung

\varphi \colon \{1,\ldots ,k\}\longrightarrow T

angibt bzw. deren Existenz nachweist. Dies ist also eine Übung in Induktion, Definition von Abbildungen und zum Konzept bijektiv. Man kann es auch nicht als eine grundlegende mengentheoretische Aussage sehen, sondern als eine durchaus praktische Aussage über das nummerieren. Die Gesamtmenge ${}{\{1,\ldots ,n\}}$ liegt ja in einer durchnummerierten Form vor, jetzt hat man da aber einige Elemente davon rausgeschmissen (wie in Aufgabe 1.1) bzw. eine Teilmenge ist noch übrig, und dafür möchte man eine neue Nummerierung aufstellen. Die praktische Idee ist natürlich, die fehlenden Elemente zu überspringen und „intern“ weiter zu zählen. Diese Idee ist klar, es ist aber nicht klar, wie man daraus eine schlüssige Definition für die neue Abbildungsnummerierung ${}\varphi$ macht.

Es ist nicht so einfach, einen geschlossenen Term für ${}\varphi (j)$ anzugeben, zumal nicht klar ist, in welchem Bereich ${}j$ wandert, da ja eben das ${}k$ noch nicht bekannt ist. (Beispiel: Sei ${}n=1000000$ und ${}T$ die Menge der Primzahlen unterhalb von ${}n$ . Was ist ${}k$ ? Was ist ${}\varphi (9876)$ ?)

Deshalb wird die Existenz von ${}k$ und die Existenz von ${}\varphi$ durch Induktion über ${}n$ bewiesen! Die Gesamtaufgabe, die Angabe eines ${}\varphi$ , ist ziemlich schwierig, es ist aber relativ einfach, den Übergang zu verstehen, wenn man ${}n$ um eins erhöht. Im eben erwähnten Beispiel geht man so vor. Wenn man schon eine Bijektion zwischen ${}\{1,\ldots ,k\}$ und den Primzahlen ${}\leq 1000000$ hat, so kriegt man daraus auch leicht eine Bijektion zwischen ${}\{1,\ldots ,\ell \}$ und den Primzahlen ${}\leq 1000001$ durch eine Fallunterscheidung: Wenn diese neue Zahl, also die ${}1000001$ , keine Primzahl ist, so kann man die alte Nummerierung direkt übernehmen. Wenn es eine Primzahl ist, so ist ${}\ell =k+1$ und ergänzt die alte Nummerierung durch ${}\varphi (k+1)=1000001$ . Aus dieser Beobachtung sollte man nun den allgemeinen Induktionsschluss formulieren können.

Diskutieren und Fragen

Aufgabe

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und es sei ${}T\subseteq M$ eine Teilmenge. Zeige, dass ${}T$ ebenfalls eine endliche Menge ist, und dass für ihre Anzahl ${}k$ die Abschätzung

{}k\leq m\,

gilt. Zeige ferner, dass ${}T$ genau dann eine echte Teilmenge ist, wenn

{}k<m\,

ist.

Aufgabe *

Es sei ${}M$ eine endliche Menge mit ${}n$ Elementen und sei ${}w$ ein Element, das nicht zu ${}M$ gehöre. Zeige, dass dann die Vereinigung ${}M\cup \{w\}$ genau ${}n'$ Elemente besitzt.

Aufgabe *

Es seien ${}k,n$ natürliche Zahlen. Zeige, dass die Abbildung

\{1,\ldots ,k\}\longrightarrow \{1+n,\ldots ,k+n\},\,i\longmapsto i+n,

bijektiv ist.

Aufgabe

Zeige, dass die Menge ${}\{1,\ldots ,n\}$ endlich mit ${}n$ Elementen ist. Zeige ferner, dass für jedes ${}k\in \mathbb {N}$ die Menge

{}\{k+1,\ldots ,k+n\}={\left\{x\in \mathbb {N} \mid x\geq k+1{\text{ und }}x\leq k+n\right\}}\,

ebenfalls eine endliche Menge mit ${}n$ Elementen ist.

Aufgabe

Es seien ${}S$ und ${}T$ endliche Mengen und es gebe eine injektive Abbildung ${}\psi \colon S\rightarrow T$ . Zeige ${}{\#\left(S\right)}\leq {\#\left(T\right)}$ .

Aufgabe

Es seien ${}S$ und ${}T$ endliche Mengen. Es gebe zwei injektive Abbildungen ${}\psi \colon S\rightarrow T$ und ${}\varphi \colon T\rightarrow S$ . Zeige, dass dann die beiden Mengen die gleiche Anzahl besitzen.

Aufgabe *

Zwei Personen wollen ihre Körpergröße vergleichen. Sie können sich direkt vergleichen, indem sie sich Rücken an Rücken hinstellen, oder, indem sie ein Maßband (Zollstock) nehmen und ihre Größe damit jeweils messen. Welche Analogien zu diesen Methoden gibt es, wenn man zwei endliche Mengen vergleichen möchte?

Aufgabe

Es seien ${}S$ und ${}T$ endliche Teilmengen einer Menge ${}M$ . Zeige, dass dann auch die Vereinigung ${}S\cup T$ endlich ist.

Aufgabe

In der Klasse gibt es vier Reihen mit je acht Sitzplätzen, die alle besetzt sind. Vorne stehen Frau Maier-Sengupta und Herr Lutz. Frau Maier Sengupta zählt die Kinder durch, wobei sie reihenweise von (zuerst) links nach rechts und (dann) von vorne nach hinten durchzählt. Herr Lutz zählt die Kinder von rechts hinten nach links vorne, wobei er zuerst die ganz rechts sitzenden Kinder durchzählt u.s.w.

Welche Nummer bekommt dasjenige Kind, das von Frau Maier-Sengupta die Nummer ${}23$ bekommt, von Herrn Lutz?
Welche Nummer bekommt dasjenige Kind, das von Herrn Lutz die Nummer ${}18$ bekommt, von Frau Maier-Sengupta?
Welche Nummer bekommt das Kind, das in der dritten Reihe von vorne auf dem sechsten Stuhl von links sitzt, von den beiden Lehrkräften?

Aufgabe *

Es seien ${}M$ und ${}N$ Mengen und seien ${}A\subseteq M$ und ${}B\subseteq N$ Teilmengen. Zeige die Gleichheit

{}{\left(A\times N\right)}\cap {\left(M\times B\right)}=A\times B\,.

Aufgabe

Es seien ${}M$ und ${}N$ Mengen und seien ${}A_{1},A_{2}\subseteq M$ und ${}B_{1},B_{2}\subseteq N$ Teilmengen. Zeige die Gleichheit

{}{\left(A_{1}\times B_{1}\right)}\cap {\left(A_{2}\times B_{2}\right)}={\left(A_{1}\cap A_{2}\right)}\times {\left(B_{1}\cap B_{2}\right)}\,.

Aufgabe

Es seien ${}A$ und ${}B$ disjunkte Mengen und ${}C$ eine weitere Menge. Zeige die Gleichheit

{}C\times (A\uplus B)=(C\times A)\uplus (C\times B)\,.

Aufgabe *

Es sei ${}a\in \mathbb {N} _{+}$ . Zeige, wie man ${}a^{10}$ mit vier Multiplikationen berechnen kann.

Aufgabe

Es seien ${}M,N,L$ Mengen. Stifte eine Bijektion zwischen

\operatorname {Abb} \,{\left(M\times N,L\right)}\,\,{\text{  und }}\,\,\operatorname {Abb} \,{\left(M,\operatorname {Abb} \,{\left(N,L\right)}\right)}.

Kommentar:

Seien ${}M,N,L$ Mengen. Stifte eine Bijektion zwischen

\operatorname {Abb} \,{\left(M\times N,L\right)}\,\,{\text{  und }}\,\,\operatorname {Abb} \,{\left(M,\operatorname {Abb} \,{\left(N,L\right)}\right)}.

Das sieht schon ganz schön verschachtelt aus. Es gibt drei Menge, es taucht die Produktmenge auf und Abbildungsmengen, wobei rechts sogar eine verschachtelte Abbildungsmenge steht, also eine Abbildungsmenge zwischen zwei Mengen, bei der die zweite Menge selbst eine Abbildungsmenge ist. Aufgabe 1.21 ist von einer ähnlichen Komplexität.

Es ist zwar nur nach einer Bijektion gefragt, man hat aber eigentlich nur eine Chance, wenn man eine natürliche Bijektion mit einer inhaltlichen Bedeutung findet. Wie geht man so etwas an? Am Besten nimmt man sich ein Objekt links her, also eine Abbildung von ${}M\times N$ nach ${}L$ , und überlegt sich, was für ein Objekt man diesem rechts zuordnet. Dem Objekt gibt man erst mal einen Namen

f\colon M\times N\longrightarrow L.

Dazu wollen wir eine Abbildung

M\longrightarrow \operatorname {Abb} \,{\left(N,L\right)}

assoziieren. Dies bedeutet wiederum, dass jedem ${}x\in M$ ein Wert zugeordnet werden soll, doch der Wert ist in diesem Fall eine Abbildung ${}g$ bzw. ${}g_{x}$ , da es ja von ${}x$ abhängt, von ${}N$ nach ${}L$ . Dieses ${}g_{x}$ soll somit jedem ${}y\in N$ ein Element aus ${}L$ zuordnen. Wir haben ja aber das ${}f$ zur Verfügung, das jedem Paar ${}(x,y)$ etwas aus ${}L$ zuordnet. Deshalb ist die einzige sinnvolle Idee, dem ${}f$ die Abbildung

x\longmapsto (y\mapsto f(x,y))

zuzuordnen.

Jetzt muss man dies noch sinnvoll aufschreiben. Nennen wir die Gesamtzuordnung ${}\Psi$ , also

\Psi \colon \operatorname {Abb} \,{\left(M\times N,L\right)}\longrightarrow \operatorname {Abb} \,{\left(M,\operatorname {Abb} \,{\left(N,L\right)}\right)},\,f\longmapsto \Psi (f),

wobei ${}\Psi (f)$ eben definiert wird durch

{}((\psi (f))(x))(y):=f(x,y)\,.

Man muss jetzt noch zeigen, dass diese Gesamtzuordnung bijektiv ist, etwa dadurch, dass man mit einer ähnlichen Überlegung eine Umkehrabbildung angibt.

Diskutieren und Fragen

Aufgabe

Es seien ${}D$ und ${}W$ Mengen, wobei ${}D$ endlich sei. Wir betrachten die 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)}.

Einer Abbildung ${}f\colon D\rightarrow W$ wird also die Abbildung zugeordnet, die jedem Wert ${}w\in W$ die Anzahl seiner Urbilder zuordnet. Finde möglichst viele Interpretationen für diese Situation.