Endliche Menge

Menge mit endlich vielen Elementen
(Weitergeleitet von Endlich viele)

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

eine endliche Menge mit vier Elementen. Die leere Menge hat gemäß ihrer Definition keine Elemente, d. h. die Anzahl der Elemente ist , sie gilt daher auch als endliche Menge. Die Mächtigkeit oder Kardinalität, geschrieben für eine Menge , einer endlichen Menge wird mit einer natürlichen Zahl (unter Einbeziehung der Null) identifiziert. Beispielsweise schreibt man dann , um auszudrücken, dass aus vier Elementen besteht.

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

Definition

Bearbeiten
 
Die durch die roten Pfeile angedeutete Bijektion   zeigt   und somit die Endlichkeit von  

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

 

zwischen   und der Menge   aller natürlichen Zahlen kleiner als   existiert.

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

So ist zum Beispiel die Menge

 

endlich, da eine Bijektion zur Menge

 

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

 .[1]

Für die Menge aller natürlichen Zahlen

 

existiert hingegen keine solche Bijektion auf eine endliche Menge, die Menge   ist daher unendlich.

Grundlegende Eigenschaften endlicher Mengen

Bearbeiten
  • Jede Teilmenge einer endlichen Menge   ist ebenfalls endlich.
  • Ist insbesondere   eine endliche Menge und   eine beliebige Menge, dann sind sowohl die Schnittmenge   als auch die Differenzmenge   endliche Mengen, denn beides sind Teilmengen von  .
  • Sind   endliche Mengen, so ist auch ihre Vereinigungsmenge   endlich. Für ihre Mächtigkeit gilt
         .
    Sind   und   endlich und disjunkt, also   so hat man
         .
  • 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   unendlich und   endlich, so ist   unendlich.
  • Die Potenzmenge   einer endlichen Menge   hat eine höhere Mächtigkeit als die Menge selbst, ist aber immer noch endlich; es gilt  .
  • Das kartesische Produkt   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   haben. Für endliche Mengen   gilt  . Allgemeiner ist ein kartesisches Produkt endlich vieler endlicher Mengen wieder eine endliche Menge.

Dedekind-Endlichkeit

Bearbeiten

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

Eine Menge   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   zu keiner echten Teilmenge gleichmächtig ist, dann ist auch   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   zwischen der Menge   und einer echten Teilmenge   von   eine Bijektion   zwischen   und einer echten Teilmenge   gewinnen kann.)

Umgekehrt ist jede Dedekind-endliche Menge   auch endlich, denn wäre   unendlich, so könnte man mit Hilfe des Auswahlaxioms eine Folge   von paarweise verschiedenen Elementen   finden. Die Abbildung

      für        
    für    

ist wohldefiniert, denn, wenn  , dann gibt es ein   mit   und dieses ist eindeutig. Sie zeigt, dass   zur echten Teilmenge   gleichmächtig und damit nicht Dedekind-endlich ist – im Widerspruch zur Voraussetzung.

Erblich endliche Mengen

Bearbeiten

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

In der abstrakten Mengenlehre werden die natürlichen Zahlen als erblich endliche Mengen eingeführt:

 

Damit sind die natürlichen Zahlen selbst endliche Mengen, sogar erblich endlich, und es gilt   für jede natürliche Zahl  , 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   an Stelle von   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   hat, wenn sie zu   gleichmächtig ist.

Durchschnitte, Vereinigungen und Produkte erblich endlicher Mengen sind wieder erblich endlich. Die Menge aller erblich endlichen Mengen ist genau die Stufe   der Von-Neumann-Hierarchie der Zermelo-Fraenkel-Mengenlehre.

Weitere Endlichkeitsbegriffe

Bearbeiten

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.

Einzelnachweise und Anmerkungen

Bearbeiten
  1. Es muss also eine Vergleichsoperation   geben, die in der Lage ist,   resp.   festzustellen.

Literatur

Bearbeiten