Endliche Menge

 

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 ist zum Beispiel die Menge

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

endlich, da eine Bijektion zur Menge

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

Für die Menge aller 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.

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

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

Eine Menge ${\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}$  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.

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 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}}}$ 

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.

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 }$  geben, die in der Lage ist, ${\displaystyle 6\equiv 6}$  resp. ${\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.