Endliche Menge

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

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

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

Eine Menge ${\displaystyle M}${\displaystyle M} heißt endlich, wenn es eine natürliche Zahl ${\displaystyle n}${\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\}}${\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}${\displaystyle M} und der Menge ${\displaystyle N_{n}}${\displaystyle N_{n}} aller natürlichen Zahlen kleiner als ${\displaystyle n}${\displaystyle n} existiert.

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

So ist zum Beispiel die Menge

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

endlich, da eine Bijektion zur Menge

${\displaystyle N_{4},円=,円\{0,1,2,3\}}${\displaystyle 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

${\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 \}}${\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 die Menge aller natürlichen Zahlen

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

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

• Jede Teilmenge einer endlichen Menge ${\displaystyle A}${\displaystyle A} ist ebenfalls endlich.
• Ist insbesondere ${\displaystyle A}${\displaystyle A} eine endliche Menge und ${\displaystyle B}${\displaystyle B} eine beliebige Menge, dann sind sowohl die Schnittmenge ${\displaystyle A\cap B}${\displaystyle A\cap B} als auch die Differenzmenge ${\displaystyle A\setminus B}${\displaystyle A\setminus B} endliche Mengen, denn beides sind Teilmengen von ${\displaystyle A}${\displaystyle A}.
• Sind ${\displaystyle A,B}${\displaystyle A,B} endliche Mengen, so ist auch ihre Vereinigungsmenge ${\displaystyle A\cup B}${\displaystyle A\cup B} endlich. Für ihre Mächtigkeit gilt
      ${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}.
  Sind ${\displaystyle A}${\displaystyle A} und ${\displaystyle B}${\displaystyle B} endlich und disjunkt, also ${\displaystyle A\cap B=\emptyset ,}${\displaystyle A\cap B=\emptyset ,} so hat man
      ${\displaystyle |A\cup B|=|A|+|B|=|A,円{\dot {\cup }},円B|}${\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}${\displaystyle A} unendlich und ${\displaystyle B}${\displaystyle B} endlich, so ist ${\displaystyle A\setminus B}${\displaystyle A\setminus B} unendlich.
• Die Potenzmenge ${\displaystyle {\mathcal {P}}(A):=\{U\mid U\subseteq A\}}${\displaystyle {\mathcal {P}}(A):=\{U\mid U\subseteq A\}} einer endlichen Menge ${\displaystyle A}${\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|}}${\displaystyle |{\mathcal {P}}(A)|=2^{|A|}}.
• Das kartesische Produkt ${\displaystyle A\times B}${\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}${\displaystyle 1} haben. Für endliche Mengen ${\displaystyle A,B}${\displaystyle A,B} gilt ${\displaystyle |A\times B|=|A|\cdot |B|}${\displaystyle |A\times B|=|A|\cdot |B|}. Allgemeiner ist ein kartesisches Produkt endlich vieler endlicher Mengen wieder eine endliche Menge.

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

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

Umgekehrt ist jede Dedekind-endliche Menge ${\displaystyle A}${\displaystyle A} auch endlich, denn wäre ${\displaystyle A}${\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}}}${\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}${\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 f\colon A\rightarrow A\setminus \{a_{0}\},\quad a\mapsto {\begin{cases}\\\\\end{cases}}} ${\displaystyle a_{n+1}}${\displaystyle a_{n+1}}   für   ${\displaystyle a\in F,}${\displaystyle a\in F,}   ${\displaystyle a_{n}=a}${\displaystyle a_{n}=a}

${\displaystyle a}${\displaystyle a}   für   ${\displaystyle a\not \in F}${\displaystyle a\not \in F}

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

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

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

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.

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

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

• Mengenlehre