05 Elemente und Mengen

0:00 ...

Auf das Video Klicken zum Abspielen & Im Video ziehen zum Vor-/Zurückspielen

Timestamps

Daten werden geladen...

Elemente und Mengen - Aufgabe 1 (von 5)

Für eine Menge $M$ definiert man die Menge all ihrer Teilmengen als ihre Potenzmenge $\begin{array}{r} 𝒫 (M) = {A : A \subseteq M} . \end{array}$ Im Falle einer endlichen Menge $M = a 1, a 2, . . ., a$ gibt es dabei eine schöne Formel für die Anzahl der Elemente in $𝒫 (M)$ , also die Anzahl der Teilmengen von $M$ .
Experimentieren Sie zunächst mit ein paar kleinen Mengen und versuchen Sie, die Formel zu erkennen.

Falls zum Beipiel $M = 1$ ist, dann hat die Potenzmenge offenbar die Form $\begin{array}{r} 𝒫 (M) = {\emptyset, {1}}, \end{array}$ bei $M = {1,2}$ ist $\begin{array}{r} 𝒫 (M) = {\emptyset, {1}, {2}, {1, 2}} \end{array}$ und bei $M (1,2, 3)$ gilt $\begin{array}{r} M = {\emptyset, {1}, {2}, {1, 2}, {1, 3}, {2, 3}, {1, 2,3}} . \end{array}$ Bei einem Element ergeben sich zwei Teilmengen, bei zwei Elementen vier und bei drei Elementen acht. Welche Formel vermuten Sie?

Offenbar scheint die Anzahl der Teilmengen einer $n$ - elementigen Menge genau gleich $2^{n}$ zu sein. Das stimmt sogar für den Fall $n = 0$ , also die leere Menge $\emptyset$ . In diesem Fall hat die Potenzmenge $P (\emptyset) = {\emptyset}$ genau ein Element $(= 2^{0})$ . Versuchen Sie, diese Aussage nun allgemein für jedes $n \in ℕ$ zu beweisen.

Die Potenzmenge $P (M)$ einer $n$ - elementigen Menge $M$ hat $2^{n}$ Elemente. Der Beweis geht mit vollständiger Induktion nach $n$ .
Den Induktionsanfang haben wir schon mit den Beispielen erledigt.
Induktionsschritt $n ⟶ n + 1 :$ Im Falle $M = {a_{1}, . . ., a_{n + 1}}$ ist $\begin{array}{r} M = {a_{1}, . . ., a_{" n "}} \cup {a_{" n + 1 "}} . \end{array}$ Die Teilmengen von $M$ sind dann zunächst alle Tellmengen von ${a_{1}, . . ., a_{n}}$ , nach Induktionsvoraussetzung sind das $2^{n}$ Stück. Nun ist klar, dass wir die restlichen Teilmengen erhalten, wenn wir zu jeder dieser $2^{n}$ Teilmengen das Element $a_{n + 1}$ hinzufügen. Das ergibt nochmals $2^{n}$ Teilmengen, insgesamt also $2^{n} + 2^{n} = 2^{n + 1}$ . Teilmengen. Das war zu zeigen.

Elemente und Mengen - Aufgabe 2 (von 5)

Im Falle von $n$ Mengen $A_{1} . . ., A_{n}$ heißt die Konstruktion $\begin{array}{r} \prod_{k = 1}^{n} A_{k} \end{array}$ nicht aus Zufall das Produkt von Mengen. Denken Sie ein wenig nach über den Ursprung dieser Bezeichnung. Machen Sie dazu ein paar kleine Experimente mir zwei oder drei kleinen Mengen.

Probieren wir es mit den Mengen $A = {1}, B = {1, 2}$ und $C = {1, 2, 3} . A$ hat ein Element, $B$ zwei Elemente und $C$ hat drei. Das Produkt $A \times B \times C$ hat die Gestalt $\begin{array}{r} A \times B \times C = {(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3)} \end{array}$ und damit 6 Elemente.
Wir erkennen, dass $6 = 1 \cdot 2 \cdot 3$ ist und vermuten jetzt ganz allgemein, dass im Falle endlicher Mengen die Anzahl der Elemente des Produktes gleich dem Produkt der Elementzahlen der einzelnen "Faktoren" ist. Bezeichnet man die Anzahl der Elemente einer endlichen Menge $A$ mit $# A$ , so kann man diesen komplizierten deutschen Satz kurz schreiben als $\begin{array}{r} # (\prod_{k = 1}^{n} A_{k}) = \prod_{k = 1}^{n} # A_{k} . \end{array}$ Versuchen Sie, diese Vermutung zu beweisen.

Hinweis: Durch die Beispiele erscheint die Aussage ziemlich selbstverständlich. Damit wollen wir uns aber nicht begnügen. Versuchen Sie in Ihrer Argumentation so exakt wie möglich zu sein.

Ich gebe hier als Beispiel einen sehr formalen Beweis, wie er in der Mathematik an der Hochschule manchmal vorkommt. Bestimmt haben Sie ihn nicht wörtlich genauso konstruiert. Aber prüfen Sie einmal, ob Ihr Gedankengang sich darin wiederfinden lässt und versuchen Sie, sich an die manchmal etwas abstrakt anmu- tenden Formeln zu gewöhnen. $\begin{array}{r} # (\prod_{k = 1}^{n} A_{k}) = \prod_{k = 1}^{n} # A_{k} . \end{array}$ Die Aussage wird formal am besten mit vollständiger Induktion nach der Anzahl $n$ der Mengen $A_{k}$ bewiesen.
Induktionsanfang: Die Aussage stimmt klarerweise für $n = 1$ . In diesem Fall ist es aber auch sinnvoll, sie für $n = 2$ zu prüfen. Da $\begin{array}{r} A_{1} \times A_{2} = {(a_{1}, a_{2}) : a_{1} \in A_{1} u n d a \in A_{2}}, \end{array}$ ist klar, dass wir jedes Element des Produkts $A_{1} \times A_{2}$ , "erwischen", wenn wir zu jedem Element in $A_{1}$ ein Paar mit jedem Element von $A_{2}$ bilden. Das ergibt dann natürlich $# A_{1} \cdot # A_{2}$ Paare - für den Induktionsanfang reicht das.
Induktionsschritt $n ⟶ n + 1 :$ Ganz offenbar haben die Mengen $\begin{array}{r} \prod_{k = 1}^{n + 1} A_{k} = A_{1} \times A_{2} \times . . . \times A_{n + 1} \end{array}$ und $\begin{array}{r} (\prod_{k = 1}^{n} A_{k}) \times A_{n + 1} = (A_{1} \times A_{2} \times . . . \times A_{n}) \times A_{n + 1} \end{array}$ die gleiche Anzahl von Elementen. Es gibt nämlich eine natürliche Abbildung $φ$ zwischen diesen beiden Mengen: $\begin{array}{r} φ : \prod_{k = 1}^{n + 1} A_{k} \to (\prod_{k = 1}^{n} A_{k}) \times A_{n + 1} \end{array}$ $\begin{array}{r} (a_{1}, a_{2}, . . ., a_{n + 1}) \mapsto ((a_{1}, a_{2}, . . ., a_{n}), a_{n + 1}) \end{array}$ Da es offenbar egal ist, ob wir in einem $(n + 1)$ -Tupel die ersten $n$ Komponenten durch Klammern zusammenfassen oder nicht, erkennen wir diese Abbildung sofort als bijektiv. Die Mengen haben also tatsächlich die gleiche Elementzahl.
Beachten Sie, dass das Ziel der Abbildung $φ$ ein Produkt aus nur zwei Mengen ist. Wegen des Induktionsanfangs $(n = 2)$ können wir daher festhalten, dass $\begin{array}{r} # (\prod_{k = 1}^{n + 1} A_{k}) = # ((\prod_{k = 1}^{n} A_{k}) \times A_{n + 1}) = # (\prod_{k = 1}^{n} A_{k}) \cdot # A_{n + 1} \end{array}$ ist. Wegen der Induktionsvoraussetzung ist schließlich $\begin{array}{r} # (\prod_{k = 1}^{n} A_{k}) \cdot # A_{n + 1} \underset{I n d V}{\underset{⏟}{(\prod_{k = 1}^{n} # A_{k})}} \cdot # A_{n + 1} = \prod_{k = 1}^{n + 1} # A_{k} . \end{array}$ Das war zu zeigen.
Zugegeben: Ein etwas technischer Beweis, sieht aber viel komplizierter aus, als er eigentlich ist. Wir haben bei dieser Gelegenheit gleich ein spezielles Abzählprinzip gezeigt, das auch in der Wahrscheinlichkeitsrechnung und der Statistik eine wichtige Rolle spielt.

Elemente und Mengen - Aufgabe 3 (von 5)

Betrachten Sie die Menge $\begin{array}{r} M = {1, 2, 3, 4} . \end{array}$ Bestimmen Sie die kleinste Äquivalenzrelation auf $M$ , welche die Elemente $(1,4)$ und $(2,4)$ enthält.

Nun ja, die Äquivalenzrelation muss wegen der Reflexivität zunächst alle Elemente der Form $(a, a)$ enthalten. Wegen der Symmetrie müssen dann auch die "Spiegelbilder" $(4,1)$ und $(4,2)$ der beiden vorgegebenen Elemente enthalten sein. Die Transitivität verlangt dann abschließend noch (wegen $(1,4)$ und $(4,2)$ ), dass auch $(1,2)$ enthalten ist - klarerweise dann auch $(2,1)$ . Nun sind wir fertig $\begin{array}{r} ℛ_{e} = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1) . (1,4), (4,1), (2,4), (4.2)} . \end{array}$ Offenbar sind in dieser Menge alle Elemente äquivalent zueinander, nur die $3$ steht isoliert da. In den folgenden Kapiteln werden wir sehen, welch wundersame Dinge man mit Äquivalenzrelationen konstruieren kann.

Elemente und Mengen - Aufgabe 4 (von 5)

Im vorigen Kapitel haben wir die Ordnung $\leq$ auf der Menge $ℕ$ definiert. Eine solche Ordnung ergibt auch eine Relation auf $ℕ^{2} = ℕ \times ℕ$ : $\begin{array}{r} (a, b) \in ℛ ⟺ a \leq b . \end{array}$ Man kann nun ganz allgemein Ordnungsrelationen (auf beliebigen Mengen) defnieren. Das geht ganz ähnlich wie bei den Äquivalenzrelationen. Eine Ordnungsrelation ist auch reflexiv und transitiv: Es gilt stets $a \leq a$ und aus $a \leq b$ und $b \leq c$ folgt $a \leq c$ .
Erinnern Sie sich noch an eine weitere Bedingung, sie steht im Zusammenhang mit der Symmetrie einer Relation? Versuchen Sie, hier für Ordnungsrelationen auch eine präzise logische Regel zu finden.
In der Frage der Symmetrie sind Ordnungsrelationen das genaue Gegenteil von Aquivalenzrelationen: Falls $a \leq b$ und $b \leq a$ gilt, dann muss zwangsläufig $a = b$ gelten. Man nennt, diese Bedingung auch Antisymmetrie: $\begin{array}{r} a \leq b u n d b \leq a ⟹ a = b . \end{array}$ Es ist bemerkenswert, dass sich die zwei wichtigsten Relationen in der Mathematik nur in diesem einen Punkt unterscheiden, wenn auch gewaltig. Dazu gleich eine interessante Frage: Wieviele Relationen auf einer Menge $M$ gibt es, welche sowohl Äquivalenz- als auch Ordnungsrelation sind? Jonglieren Sie ein wenig mit den Begriffen und Regeln.

Es gibt genau eine solche Relation, nämlich die Identität: $\begin{array}{r} (a, b) \in ℛ ⟺ a = b . \end{array}$ Klarerweise sind die Bedingungen sowohl von Äquivalenz- als auch Ordnungsrelationen erfüllt. Es kann aber keine weiteren Relationen $ℛ$ dieser Art geben, da sich Symmetrie und Antisymmetrie gegenseitig ausschließen, falls irgendein $(a, b)$ mit $a \neq b$ in $ℛ$ liegen sollte.

Elemente und Mengen - Aufgabe 5 (von 5)

Bleiben wir zum Abschluss bet den natürlichen Zahlen. Die Addition und die Multiplikation können auch als Abbildungen zwischen zwei Mengen aufgefasst werden, so wie es zum Beispiel in der Informatik bei Datentypen oder der funktionalen Programmierung verwendet wird. Überlegen Sie sich, wie das gehen kann.
Beide Operationen sind Abbildungen von $ℕ \times ℕ$ in die Menge $ℕ$ : $\begin{array}{r} a d d : ℕ \times ℕ \to ℕ \end{array}$ $\begin{array}{r} (a, b) \mapsto a + b . \end{array}$ und $\begin{array}{r} m u l t : ℕ \times ℕ \to ℕ \end{array}$ $\begin{array}{r} (a, b) \mapsto a \cdot b . \end{array}$ Bestimmen Sie das Urbild der Menge ${2, 4} \in ℕ$ bei den beiden Abbildungen. $\begin{array}{r} a d d^{- 1} ({3, 4}) = {(0,3) (1,2) (2,1) (3,0) (0,4) (1,3) (2,2) (3,1) (4,0)}, \end{array}$ $\begin{array}{r} m u l t^{- 1} ({3, 4}) = {(1, 3) (3, 1) (1, 4) (2, 2) (4,1)} . \end{array}$ Finden Sie mittels der Abbildung mult eine Bedingung für eine Zahl $n \in ℕ$ , welche äquivalent dazu ist, dass $n$ eine Primzahl ist.

Die Eigenschaft einer natürlichen Zahl $n \geq 2$ , nur durch $1$ und sich selbst tellbar zu sein, ist äquivalent dazu, dass $\begin{array}{r} # (m u l t^{- 1} ({n})) = 2 \end{array}$ ist, das Urbild bei der Multiplikation also aus genau zwei Elementen besteht, nämlich $(1, n)$ und $(n, 1)$ .
Gratuliere, Sie sind durch! Viel Vergnügen beim nächsten Kapitel.