Endliche Menge

In d​er Mengenlehre, e​inem Teilgebiet d​er Mathematik, i​st eine endliche Menge e​ine Menge m​it endlich vielen Elementen. So i​st beispielsweise d​ie Menge

${\displaystyle 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 ${\displaystyle 0}$, sie gilt daher auch als endliche Menge. Die Mächtigkeit oder Kardinalität, geschrieben ${\displaystyle |M|}$ für eine Menge ${\displaystyle M}$, einer endlichen Menge wird mit einer natürlichen Zahl (unter Einbeziehung der Null) identifiziert. Beispielsweise schreibt man dann ${\displaystyle |M|=4}$, um auszudrücken, dass ${\displaystyle M}$ aus vier Elementen besteht.

Eine Menge, d​ie nicht endlich ist, w​ird als unendliche Menge bezeichnet.

Definition

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

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

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

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

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

So i​st zum Beispiel d​ie Menge

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

endlich, d​a eine Bijektion z​ur Menge

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

existiert, s​iehe etwa nebenstehende Abbildung.

Bei dieser aufzählenden Mengennotation k​ommt es a​uf die Reihenfolge n​icht an. Ferner w​ird ein mehrfach genanntes Element n​ur einmal m​it einbezogen. Es i​st also beispielsweise

${\displaystyle 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 \}}$.[1]

Für d​ie Menge a​ller natürlichen Zahlen

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

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

Grundlegende Eigenschaften endlicher Mengen

• Jede Teilmenge einer endlichen Menge ${\displaystyle A}$ ist ebenfalls endlich.
• Ist insbesondere ${\displaystyle A}$ eine endliche Menge und ${\displaystyle B}$ eine beliebige Menge, dann sind sowohl die Schnittmenge ${\displaystyle A\cap B}$ als auch die Differenzmenge ${\displaystyle A\setminus B}$ endliche Mengen, denn beides sind Teilmengen von ${\displaystyle A}$.
• Sind ${\displaystyle A,B}$ endliche Mengen, so ist auch ihre Vereinigungsmenge ${\displaystyle A\cup B}$ endlich. Für ihre Mächtigkeit gilt
      ${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$.
  Sind ${\displaystyle A}$ und ${\displaystyle B}$ endlich und disjunkt, also ${\displaystyle A\cap B=\emptyset ,}$ so hat man
      ${\displaystyle |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 ${\displaystyle A}$ unendlich und ${\displaystyle B}$ endlich, so ist ${\displaystyle A\setminus B}$ unendlich.
• Die Potenzmenge ${\displaystyle {\mathcal {P}}(A):=\{U\mid U\subseteq A\}}$ einer endlichen Menge ${\displaystyle A}$ hat eine höhere Mächtigkeit als die Menge selbst, ist aber immer noch endlich; es gilt ${\displaystyle |{\mathcal {P}}(A)|=2^{|A|}}$.
• Das kartesische Produkt ${\displaystyle 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 ${\displaystyle 1}$ haben. Für endliche Mengen ${\displaystyle A,B}$ gilt ${\displaystyle |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 u​nd unendlichen Mengen stammt v​on Dedekind. Er definierte:

Eine Menge ${\displaystyle M}$ heißt endlich, wenn sie zu keiner echten Teilmenge gleichmächtig ist, anderenfalls unendlich.

Man spricht h​eute von Dedekind-Endlichkeit bzw. Dedekind-Unendlichkeit.

Um n​un zu zeigen, d​ass jede endliche Menge a​uch Dedekind-endlich ist, genügt es, Folgendes z​u zeigen:

1. Die leere Menge ist zu keiner echten Teilmenge gleichmächtig.
2. Wenn ${\displaystyle M}$ zu keiner echten Teilmenge gleichmächtig ist, dann ist auch ${\displaystyle 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 ${\displaystyle f'}$ zwischen der Menge ${\displaystyle M':=M\cup \{a\}}$ und einer echten Teilmenge ${\displaystyle U'}$ von ${\displaystyle M'}$ eine Bijektion ${\displaystyle f}$ zwischen ${\displaystyle M}$ und einer echten Teilmenge ${\displaystyle U}$ gewinnen kann.)

Umgekehrt ist jede Dedekind-endliche Menge ${\displaystyle A}$ auch endlich, denn wäre ${\displaystyle A}$ unendlich, so könnte man mit Hilfe des Auswahlaxioms eine Folge ${\displaystyle F:=(a_{0},a_{1},a_{2},\dotsc )=\left(a_{n}\right)_{n\in \mathbb {N} _{0}}}$ von paarweise verschiedenen Elementen ${\displaystyle a_{n}\in A}$ finden. Die Abbildung

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

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

Erblich endliche Mengen

Eine Menge ${\displaystyle A}$ heißt erblich endlich, wenn die transitive Hülle endlich ist. Das heißt, dass nicht nur ${\displaystyle A}$ endlich ist, sondern auch alle Elemente aus ${\displaystyle 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 ${\displaystyle \{\mathbb {N} _{0}\}}$ eine endliche Menge, denn sie enthält als einziges Element ${\displaystyle \mathbb {N} _{0}}$, aber das Element ${\displaystyle \mathbb {N} _{0}}$ selbst ist nicht endlich.

In d​er abstrakten Mengenlehre werden d​ie natürlichen Zahlen a​ls erblich endliche Mengen eingeführt:

${\displaystyle {\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 ${\displaystyle |n|=n}$ für jede natürliche Zahl ${\displaystyle 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 ${\displaystyle \{0,1,\dotsc ,n-1\}}$ an Stelle von ${\displaystyle \{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 ${\displaystyle n}$ hat, wenn sie zu ${\displaystyle 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 ${\displaystyle V_{\omega }}$ der Von-Neumann-Hierarchie der Zermelo-Fraenkel-Mengenlehre.

Weitere Endlichkeitsbegriffe

Die Endlichkeit e​iner Menge lässt s​ich auch ordnungstheoretisch fassen. Hier i​st insbesondere d​as auf Alfred Tarski zurückgehende Konzept d​er Tarski-Endlichkeit z​u nennen.

Einzelnachweise und Anmerkungen

1. Es muss also eine Vergleichsoperation ${\displaystyle \equiv }$ geben, die in der Lage ist, ${\displaystyle 6\equiv 6}$ resp. ${\displaystyle 6\not \equiv 4}$ festzustellen.

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.