Endliche Menge

Aus AnthroWiki
Wechseln zu: Navigation, Suche

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

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

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

Definition

Die durch die roten Pfeile angedeutete Bijektion LaTeX: f zeigt LaTeX: |M|=|M_4| und somit die Endlichkeit von LaTeX: M

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

LaTeX: f\colon M\rightarrow\{0,\dotsc,n-1\}

zwischen LaTeX: M und der Menge aller natürlichen Zahlen kleiner als LaTeX: n,

LaTeX: M_n := \{m\in\N|m<n\}=\{0,1,2,3,\dotsc,n-1\},

existiert.

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

So ist zum Beispiel die Menge

LaTeX: M\,=\,\{4,6,2,8\}

endlich, da eine Bijektion zur Menge

LaTeX: M_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 gewertet. Es ist also beispielsweise

LaTeX: M\,=\,\{4,6,2,8\}\,=\,\{2,4,6,8\}\,=\,\{4,8,6,2,8\} .

Für die Menge aller natürlichen Zahlen

LaTeX: \N=\{0,1,2,3,\dotsc\}

existiert hingegen keine solche Bijektion auf eine endliche Menge, die Menge LaTeX: \N ist daher unendlich.

Grundlegende Eigenschaften endlicher Mengen

  • Jede Teilmenge einer endlichen Menge LaTeX: A ist ebenfalls endlich.
  • Ist insbesondere LaTeX: A eine endliche Menge und LaTeX: B eine beliebige Menge, dann sind sowohl die Schnittmenge LaTeX: A\cap B als auch die Differenzmenge LaTeX: A\setminus B endliche Mengen, denn beides sind Teilmengen von LaTeX: A.
  • Sind LaTeX: A,B endliche Mengen, so sind auch ihre Vereinigungsmenge LaTeX: A \cup B endlich. Für ihre Mächtigkeit gilt LaTeX: |A\cup B| = |A| + |B| - |A\cap B|; sind LaTeX: A und LaTeX: B disjunkt, so hat man LaTeX: |A\,\dot\cup\, B| = |A| + |B|. Allgemeiner ist eine Vereinigung endlich vieler endlicher Menge wieder eine endliche Menge. Ihre Mächtigkeit ist durch das Prinzip von Inklusion und Exklusion gegeben.
  • Ist LaTeX: A unendlich und LaTeX: B endlich, so ist LaTeX: A \setminus B unendlich.
  • Die Potenzmenge LaTeX: \mathcal{P}(A) einer endlichen Menge hat eine höhere Mächtigkeit als die Menge selbst, ist aber immer noch endlich; es gilt LaTeX: |\mathcal{P}(A)| = 2^{|A|}.
  • Das kartesische Produkt LaTeX: 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 LaTeX: 1 haben. Für endliche Mengen LaTeX: A,B gilt LaTeX: |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 LaTeX: 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 LaTeX: M zu keiner echten Teilmenge gleichmächtig ist, dann ist auch LaTeX: 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 LaTeX: f' zwischen der Menge LaTeX: M' := M \cup \{a\} und einer echten Teilmenge LaTeX: U' von LaTeX: M' eine Bijektion LaTeX: f zwischen LaTeX: M und einer echten Teilmenge LaTeX: U gewinnen kann.)

Umgekehrt ist jede Dedekind-endliche Menge LaTeX: A auch endlich, denn wäre LaTeX: A unendlich, so könnte man mit Hilfe des Auswahlaxioms eine Folge LaTeX: a_0, a_1, a_2, \dotsc von paarweise verschiedenen Elementen LaTeX: a_n\in A finden. Die Abbildung

LaTeX: f\colon A\rightarrow A\setminus \{a_0\},\quad a\mapsto \begin{cases} a_{n+1} &, \mbox{ falls } a=a_n \mbox{ für ein }n\\ a &, \mbox{ sonst}\end{cases}

zeigt dann, dass LaTeX: A zur echten Teilmenge LaTeX: A\setminus \{a_0\} gleichmächtig und daher nicht Dedekind-endlich ist. Widerspruch!

Siehe auch

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.


Dieser Artikel basiert (teilweise) auf dem Artikel Endliche Menge aus der freien Enzyklopädie Wikipedia und steht unter der Lizenz Creative Commons Attribution/Share Alike. In der Wikipedia ist eine Liste der Autoren verfügbar.