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

Die durch die roten Pfeile angedeutete Bijektion $f$ zeigt $|M|=|M_{4}|$ und somit die Endlichkeit von $M$

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:

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 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.

Literatur

• Paul R. Halmos: Naive Mengenlehre (= Moderne Mathematik in elementarer Darstellung. Bd. 6). 5. Auflage. Vandenhoeck & Ruprecht, Göttingen 1994, ISBN 3-525-40527-8.
• Oliver Deiser: Einführung in die Mengenlehre. Die Mengenlehre Georg Cantors und ihre Axiomatisierung durch Ernst Zermelo. 3., korrigierte Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-01444-4, doi:10.1007/978-3-642-01445-1.