Endliche Menge
# 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 gemäß ihrer Definition keine Elemente, d. h. die Anzahl der Elemente ist $0$, sie gilt daher auch als endliche Menge. Die Mächtigkeit oder Kardinalität, geschrieben $|M|$ für eine Menge $M$, einer endlichen Menge wird mit einer natürlichen Zahl (unter Einbeziehung der Null) identifiziert. Beispielsweise schreibt man dann $|M|=4$, um auszudrücken, dass $M$ aus vier Elementen besteht.

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

## Definition

Eine Menge $M$ heißt endlich, wenn es eine natürliche Zahl $n$ gibt, sodass eine Bijektion (eine Eins-zu-eins-Zuordnung)

    $f\colon M\rightarrow N_{n}\quad :=\{m\in \mathbb {N} _{0}\,\mid \,m<n\}\;=\;\{0,1,2,3,\dotsc ,n-1\}$

zwischen $M$ und der Menge $N_{n}$ aller natürlichen Zahlen kleiner als $n$ existiert.

Insbesondere ist die leere Menge $\emptyset :=\{\}$ endlich, da eine Bijektion zwischen $\emptyset$ und der leeren Menge $N_{0}$ (alle natürlichen Zahlen kleiner als $0$, solche existieren nicht) trivialerweise existiert.

So ist zum Beispiel die Menge

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

endlich, da eine Bijektion zur Menge

    $N_{4}\,=\,\{0,1,2,3\}$

existiert, siehe etwa nebenstehende Abbildung.

Bei dieser aufzählenden Mengennotation kommt es auf die Reihenfolge nicht an. Ferner wird ein mehrfach genanntes Element nur einmal mit einbezogen. Es ist also beispielsweise

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

Für die Menge aller natürlichen Zahlen

    $\mathbb {N} _{0}=\{0,1,2,3,\dotsc \}$

existiert hingegen keine solche Bijektion auf eine endliche Menge, die Menge $\mathbb {N} _{0}$ ist daher unendlich.

## Grundlegende Eigenschaften endlicher Mengen

* Jede Teilmenge einer endlichen Menge $A$ ist ebenfalls endlich.
* Ist insbesondere $A$ eine endliche Menge und $B$ eine beliebige Menge, dann sind sowohl die Schnittmenge $A\cap B$ als auch die Differenzmenge $A\setminus B$ endliche Mengen, denn beides sind Teilmengen von $A$.
* Sind $A,B$ endliche Mengen, so ist auch ihre Vereinigungsmenge $A\cup B$ endlich. Für ihre Mächtigkeit gilt  $|A\cup B|=|A|+|B|-|A\cap B|$. Sind $A$ und $B$ endlich und disjunkt, also $A\cap B=\emptyset ,$ so hat man  $|A\cup B|=|A|+|B|=|A\,{\dot {\cup }}\,B|$.
* Allgemein ist eine Vereinigung endlich vieler endlicher Mengen wieder eine endliche Menge. Ihre Mächtigkeit ist durch das Prinzip von Inklusion und Exklusion gegeben.
* Ist $A$ unendlich und $B$ endlich, so ist $A\setminus B$ unendlich.
* Die Potenzmenge ${\mathcal {P}}(A):=\{U\mid U\subseteq A\}$ einer endlichen Menge $A$ hat eine höhere Mächtigkeit als die Menge selbst, ist aber immer noch endlich; es gilt $|{\mathcal {P}}(A)|=2^{|A|}$.
* Das kartesische Produkt $A\times B$ 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|$. Allgemeiner ist ein kartesisches Produkt endlich vieler endlicher Mengen wieder eine endliche Menge.

## 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:

* Die leere Menge ist zu keiner echten Teilmenge gleichmächtig.
* 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 Menge $A$ auch endlich, denn wäre $A$ unendlich, so könnte man mit Hilfe des Auswahlaxioms eine Folge $F:=(a_{0},a_{1},a_{2},\dotsc )=\left(a_{n}\right)_{n\in \mathbb {N} _{0}}$ von paarweise verschiedenen Elementen $a_{n}\in A$ finden. Die Abbildung

    $f\colon A\rightarrow A\setminus \{a_{0}\},\quad a\mapsto {\begin{cases}\\\\\end{cases}}$ $a_{n+1}$ für $a\in F,$ $a_{n}=a$ $a$ für $a\not \in F$

ist wohldefiniert, denn, wenn $a\in F$, dann gibt es ein $n\in \mathbb {N} _{0}$ mit $a_{n}=a$ und dieses ist eindeutig. Sie zeigt, dass $A$ zur echten Teilmenge $A\setminus \{a_{0}\}$ gleichmächtig und damit nicht Dedekind-endlich ist – im Widerspruch zur Voraussetzung.

## Erblich endliche Mengen

Eine Menge $A$ heißt erblich endlich, wenn die 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 $\{\mathbb {N} _{0}\}$ eine endliche Menge, denn sie enthält als einziges Element $\mathbb {N} _{0}$, aber das Element $\mathbb {N} _{0}$ selbst ist nicht endlich.

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

    ${\begin{aligned}0&:=\emptyset \\1&:=\{\emptyset \}=\{0\}\\2&:=\{\emptyset ,\{\emptyset \}\}=\{0,1\}\\3&:=\{\emptyset ,\{\emptyset \},\{\emptyset ,\{\emptyset \}\}\,\}=\{0,1,2\}\\&\vdots \\n&:=\{0,1,\dotsc ,n-1\}=N_{n}\end{aligned}}$

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 oben in der Einleitung bei der Definition der Gleichmächtigkeit die Menge $\{0,1,\dotsc ,n-1\}$ an Stelle von $\{1,2,\dotsc ,n\}$ gewählt wurde. Letzteres wäre zwar auch richtig gewesen, aber die getroffene Wahl passt besser zur Definition der natürlichen Zahlen, wonach eine Menge die Mächtigkeit $n$ hat, wenn sie zu $n:=N_{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_{\omega }$ der Von-Neumann-Hierarchie der Zermelo-Fraenkel-Mengenlehre.

## Weitere Endlichkeitsbegriffe

Die Endlichkeit einer Menge lässt sich auch ordnungstheoretisch fassen. Hier ist insbesondere das auf Alfred Tarski zurückgehende Konzept der Tarski-Endlichkeit zu nennen.

## Einzelnachweise und Anmerkungen

* ↑ Es muss also eine Vergleichsoperation $\equiv$ geben, die in der Lage ist, $6\equiv 6$ resp. $6\not \equiv 4$ festzustellen.
