Endliche Menge

In der Mengenlehre, einem Teilgebiet der Mathematik, ist eine endliche Menge eine Menge mit endlich vielen Elementen. So ist beispielsweise die Menge

$M\,=\,\{4,6,2,8\}$

eine endliche Menge mit vier Elementen. Die leere Menge hat per definitionem keine Elemente, d.h. die Anzahl der Elemente (Kardinalität oder Mächtigkeit) ist 0, sie gilt daher auch als endliche Menge. Die Kardinalität einer endlichen Menge wird mit einer natürlichen Zahl (unter Einbeziehung der Null) identifiziert. Man schreibt dafür auch | M | = n, wobei die natürliche Zahl n die Anzahl der Elemente der Menge M bezeichnet.

Eine Menge, die nicht endlich ist, wird als unendliche Menge bezeichnet.

Definition

Die durch die roten Pfeile angedeutete Bijektion f zeigt | M | = | M₄ | und somit die Endlichkeit von M

Eine Menge M heißt endlich, wenn es eine natürliche Zahl n gibt, sodass eine Bijektion

$f\colon M\rightarrow\{0,\ldots,n-1\}$

zwischen M und der Menge aller natürlichen Zahlen kleiner als n, {m | m < n} = {0,1,2,3,...,n − 1}, existiert.

Insbesondere ist also für n = 0 die leere Menge endlich, da eine Bijektion zwischen der leeren Menge und der leeren Menge (alle natürlichen Zahlen kleiner als 0, solche existieren nicht) existiert.

So ist zum Beispiel die Menge

$M\,=\,\{4,6,2,8\}$

endlich, da eine Bijektion zur Menge

$M_4\,=\,\{0,1,2,3\}$

existiert, siehe etwa nebenstehende Abbildung.

Für die Menge aller natürlichen Zahlen

$\N=\{0,1,2,3,\ldots\}$

existiert hingegen keine solche Bijektion auf eine endliche Menge, die Menge $\N$ ist daher unendlich.

Grundlegende Eigenschaften endlicher Mengen

• Jede Teilmenge einer endlichen Menge A ist ebenfalls endlich.
• Sind A,B endliche Mengen, so sind auch ihre Vereinigungsmenge $A \cup B$, ihre Schnittmenge $A\cap B$ und ihre Differenzmenge $A\setminus B$ endlich. Die Differenzmenge $A\setminus B$ ist sogar endlich, wenn lediglich A endlich ist.
• Für die Kardinalität der Vereinigungsmenge $A \cup B$ gilt $|A\cup B| = |A| + |B| - |A\cap B|$, sind A und B disjunkt, so hat man $|A\cup B| = |A| + |B|$.
• Die Potenzmenge einer endlichen Menge hat eine höhere Mächtigkeit als die Menge selbst, ist aber immer noch endlich, es gilt | P(A) | = 2 ^{| A |} .
• Das kartesische Produkt endlicher Mengen ist endlich. Seine Mächtigkeit ist höher als die aller beteiligter Faktoren, wenn kein Faktor leer ist und mindestens zwei Faktoren eine Mächtigkeit größer 1 haben. Für endliche Mengen A,B gilt $|A\times B| = |A| \cdot |B|$

Dedekind-Endlichkeit

Eine andere Unterscheidung zwischen endlichen und unendlichen Mengen stammt von Dedekind. Er definierte:

• Eine Menge M heißt endlich, wenn sie zu keiner echten Teilmenge gleichmächtig ist, anderenfalls unendlich.

Man spricht heute von Dedekind-Endlichkeit bzw. Dedekind-Unendlichkeit

Um nun zu zeigen, dass jede endliche Menge auch Dedekind-endlich ist, genügt es, Folgendes zu zeigen:

1. Die leere Menge ist zu keiner echten Teilmenge gleichmächtig.
2. Wenn M zu keiner echten Teilmenge gleichmächtig ist, dann ist auch $M \cup \{a\}$ zu keiner echten Teilmenge (von sich selbst) gleichmächtig.

(Punkt 1 ist klar, da die leere Menge keine echten Teilmengen hat. Zu Punkt 2 muss man zeigen, dass man aus einer Bijektion f' zwischen der Menge M' := $M \cup \{a\}$ und einer echten Teilmenge U' von M' eine Bijektion f zwischen M und einer echten Teilmenge U gewinnen kann.)

Umgekehrt ist jede Dedekind-endliche A Menge auch endlich, denn wäre A unendlich, so könnte man mit Hilfe des Auswahlaxioms eine Folge $a_0, a_1, a_2, \ldots$ von paarweise verschiedenen Elementen $a_n\in A$ finden. Die Abbildung

$f:A\rightarrow A\setminus \{a_0\},\quad a\mapsto \begin{cases} a_{n+1} &, \mbox{ falls } a=a_n \mbox{ für ein }n\\ a &, \mbox{ sonst}\end{cases}$

zeigt dann, dass A zur echten Teilmenge $A\setminus \{a_0\}$ gleichmächtig und daher nicht Dedekind-endlich ist. Widerspruch!

Erblich endliche Mengen

Eine Menge A heißt erblich endlich, wenn die $\in$-transitive Hülle endlich ist. Das heißt, dass nicht nur A endlich ist sondern auch alle Elemente aus A endliche Mengen sind, und deren Elemente ebenfalls endliche Mengen sind, und so weiter.

Nach Definition sind alle erblich-endlichen Mengen endlich. Die Umkehrung gilt nicht, so ist etwa $\{\N\}$ eine endliche Menge, denn sie enthält als einziges Element $\N$, aber das Element $\N$ selbst ist nicht endlich.

In der abstrakten Mengenlehre werden die natürlichen Zahlen als erblich endliche Mengen eingeführt:

$\begin{align} 0 &:= \emptyset\\ 1 &:= \{\emptyset\} = \{0\}\\ 2 &:= \{\emptyset, \{\emptyset\} \} = \{0,1\}\\ 3 &:= \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\} \} \,\} = \{0,1,2\}\\ &\ldots\\ n &:= \{0,1,\ldots n-1\} \end{align}$

Damit sind die natürlichen Zahlen selbst endliche Mengen, sogar erblich endlich, und es gilt | n | = n für jede natürliche Zahl n, wobei hier die senkrechten Striche nicht für die Betragsfunktion stehen, sondern für die Mächtigkeit. Das ist der Grund, warum wir oben in der Einleitung von einer Gleichmächtigkeit zu $\{0,1,\ldots,n-1\}$ an Stelle von $\{1,2,\ldots n\}$ gesprochen haben. Letzteres wäre zwar auch richtig gewesen, aber die getroffene Wahl passt besser zur Definition der natürlichen Zahlen. Danach hat eine Menge die Mächtigkeit n, wenn sie zu n gleichmächtig ist.

Durchschnitte, Vereinigungen und Produkte erblich endlicher Mengen sind wieder erblich endlich. Die Menge aller erblich endlichen Mengen ist genau die Stufe V_ω der von-Neumann-Hierarchie der Zermelo-Fraenkel-Mengenlehre.

Literatur

• Paul R. Halmos: Naive Mengenlehre, Vandenhoeck & Ruprecht 1994, ISBN 978-3525405277.
• Oliver Deiser: Einführung in die Mengenlehre, Springer Berlin 2004, ISBN 978-3540204015.