Endliche Menge - Finite set

In der Mathematik (insbesondere der Mengenlehre ) ist eine endliche Menge eine Menge , die eine endliche Anzahl von Elementen hat . Informell ist eine endliche Menge eine Menge, die man im Prinzip zählen und zu Ende zählen könnte. Beispielsweise,

ist eine endliche Menge mit fünf Elementen. Die Anzahl der Elemente einer endlichen Menge ist eine natürliche Zahl (eine nicht negative ganze Zahl ) und wird als Kardinalität der Menge bezeichnet. Eine nicht endliche Menge heißt unendlich . Zum Beispiel ist die Menge aller positiven ganzen Zahlen unendlich:

Finite Mengen sind besonders wichtig in der Kombinatorik , dem mathematischen Studium des Zählens . Viele Argumente mit endlichen Mengen beruhen auf dem Schubladenprinzip , das besagt, dass es keine injektive Funktion von einer größeren endlichen Menge zu einer kleineren endlichen Menge geben kann.

Definition und Terminologie

Formal ein Satz S heißt endlich , wenn es eine gibt bijection

für eine natürliche Zahl n . Die Zahl n ist die Kardinalität der Menge, bezeichnet als | S | . Die leere Menge {} oder ∅ gilt als endlich, mit Kardinalität Null.

Wenn eine Menge endlich ist, können ihre Elemente – auf viele Arten – in einer Folge geschrieben werden :

In der Kombinatorik wird eine endliche Menge mit n Elementen manchmal als n- Menge und eine Teilmenge mit k Elementen als k- Teilmenge bezeichnet . Zum Beispiel ist die Menge {5,6,7} eine 3-Menge – eine endliche Menge mit drei Elementen – und {6,7} ist eine 2-Teilmenge davon.

(Diejenigen, die mit der in der Mengenlehre üblichen Definition der natürlichen Zahlen selbst, der sogenannten von-Neumann-Konstruktion , vertraut sind , ziehen es vielleicht vor, die Existenz der Bijektion zu verwenden , die äquivalent ist.)

Grundeigenschaften

Jede echte Teilmenge einer endlichen Menge S ist endlich und hat weniger Elemente als S selbst. Folglich kann es keine Bijektion zwischen einer endlichen Menge S und einer echten Teilmenge von S geben . Jede Menge mit dieser Eigenschaft heißt Dedekind-finite . Unter Verwendung der Standard- ZFC- Axiome für die Mengenlehre ist jede Dedekind-endliche Menge auch endlich, aber diese Implikation kann nicht in ZF (Zermelo-Fraenkel-Axiome ohne das Auswahlaxiom ) allein bewiesen werden . Das Axiom der abzählbaren Wahl , eine schwache Version des Wahlaxioms, reicht aus, um diese Äquivalenz zu beweisen.

Jede injektive Funktion zwischen zwei endlichen Mengen derselben Kardinalität ist auch eine surjektive Funktion (eine Surjektion). Ebenso ist jede Surjektion zwischen zwei endlichen Mengen derselben Kardinalität ebenfalls eine Injektion.

Die Vereinigung zweier endlicher Mengen ist endlich, mit

Tatsächlich gilt nach dem Einschluss-Ausschluss-Prinzip :

Allgemeiner gesagt ist die Vereinigung einer endlichen Anzahl endlicher Mengen endlich. Das kartesische Produkt endlicher Mengen ist ebenfalls endlich, mit:

Ebenso ist das kartesische Produkt endlich vieler endlicher Mengen endlich. Eine endliche Menge mit n Elementen hat 2 n verschiedene Teilmengen. Das heißt, die Potenzmenge einer endlichen Menge ist endlich mit der Kardinalität 2 n .

Jede Teilmenge einer endlichen Menge ist endlich. Die Menge der Werte einer Funktion, wenn sie auf Elemente einer endlichen Menge angewendet wird, ist endlich.

Alle endlichen Mengen sind abzählbar , aber nicht alle abzählbaren Mengen sind endlich. (Einige Autoren verwenden jedoch "abzählbar", um "abzählbar unendlich" zu bedeuten, betrachten also endliche Mengen nicht als abzählbar.)

Das freie Halbgitter über einer endlichen Menge ist die Menge ihrer nichtleeren Teilmengen, wobei die Join-Operation durch die Mengenvereinigung gegeben ist.

Notwendige und hinreichende Bedingungen für Endlichkeit

In der Zermelo-Fraenkel-Mengentheorie ohne das Auswahlaxiom (ZF) sind die folgenden Bedingungen alle äquivalent:

  1. S ist eine endliche Menge. Das heißt, S kann in eine Eins-zu-Eins-Entsprechung mit der Menge dieser natürlichen Zahlen gebracht werden, die kleiner als eine bestimmte natürliche Zahl sind.
  2. ( Kazimierz Kuratowski ) S hat alle Eigenschaften, die durch mathematische Induktion bewiesen werden können, beginnend mit der leeren Menge und Hinzufügen eines neuen Elements nach dem anderen. (Siehe unten für die mengentheoretische Formulierung der Kuratowski-Endlichkeit.)
  3. ( Paul Stäckel ) S kann eine Gesamtordnung gegeben werden, die sowohl vorwärts als auch rückwärts wohlgeordnet ist. Das heißt, jede nichtleere Teilmenge von S hat sowohl ein kleinstes als auch ein größtes Element in der Teilmenge.
  4. Jede Eins-zu-Eins-Funktion von P ( P ( S )) in sich selbst ist auf . Das heißt, die Potenzmenge der Potenzmenge von S ist Dedekind-endlich (siehe unten).
  5. Jede surjektive Funktion von P ( P ( S )) auf sich selbst ist eins zu eins.
  6. ( Alfred Tarski ) Jede nichtleere Familie von Teilmengen von S hat ein minimales Element bezüglich der Inklusion. (Äquivalent hat jede nichtleere Familie von Teilmengen von S ein maximales Element in Bezug auf die Inklusion.)
  7. S kann wohlgeordnet sein und zwei beliebige Wohlordnungen darauf sind ordnungsisomorph . Mit anderen Worten, die Well-Ordnungen auf S haben genau einen Ordertyp .

Wird auch das Auswahlaxiom angenommen (das abzählbare Auswahlaxiom ist ausreichend), dann sind die folgenden Bedingungen alle äquivalent:

  1. S ist eine endliche Menge.
  2. ( Richard Dedekind ) Jede Eins-zu-eins-Funktion von S in sich selbst ist auf.
  3. Jede surjektive Funktion von S auf sich selbst ist eins zu eins.
  4. S ist leer oder jede Teilordnung von S enthält ein maximales Element .

Grundlegende Fragen

Georg Cantor leitete seine Mengenlehre ein, um eine mathematische Behandlung unendlicher Mengen zu ermöglichen. Somit liegt die Unterscheidung zwischen Endlichem und Unendlichem im Kern der Mengenlehre. Bestimmte Fundamentalisten, die strengen Finitisten , lehnen die Existenz unendlicher Mengen ab und empfehlen daher eine Mathematik, die ausschließlich auf endlichen Mengen basiert. Mainstream-Mathematiker halten den strikten Finitismus für zu eng, erkennen aber seine relative Konsistenz an: Das Universum der erblich endlichen Mengen bildet ein Modell der Zermelo-Fraenkel-Mengentheorie, wobei das Axiom der Unendlichkeit durch seine Negation ersetzt wird.

Selbst für Mathematiker, die unendliche Mengen annehmen, kann die formale Unterscheidung zwischen Endlichem und Unendlichem in bestimmten wichtigen Zusammenhängen eine heikle Angelegenheit bleiben. Die Schwierigkeit ergibt sich aus den Unvollständigkeitssätzen von Gödel . Man kann die Theorie der erblich endlichen Mengen innerhalb der Peano-Arithmetik interpretieren (und sicherlich auch umgekehrt), so dass die Unvollständigkeit der Theorie der Peano-Arithmetik die der Theorie der erblich endlichen Mengen impliziert. Insbesondere existiert eine Fülle sogenannter Nicht-Standard-Modelle beider Theorien. Ein scheinbares Paradoxon ist, dass es Nichtstandardmodelle der Theorie erblich endlicher Mengen gibt, die unendliche Mengen enthalten, aber diese unendlichen Mengen erscheinen innerhalb des Modells endlich. (Dies kann passieren, wenn dem Modell die Mengen oder Funktionen fehlen, die notwendig sind, um die Unendlichkeit dieser Mengen zu bezeugen.) Aufgrund der Unvollständigkeitssätze kann kein Prädikat erster Ordnung oder auch kein rekursives Schema von Prädikaten erster Ordnung den Standard charakterisieren Teil all dieser Modelle. Zumindest aus Sicht der Logik erster Ordnung kann man also nur hoffen, die Endlichkeit näherungsweise beschreiben zu können.

Allgemeiner gesagt können informelle Begriffe wie Menge und insbesondere endliche Menge Interpretationen über eine Reihe formaler Systeme erfahren, die sich in ihrer Axiomatik und ihrem logischen Apparat unterscheiden. Zu den bekanntesten axiomatischen Mengentheorien gehören die Zermelo-Fraenkel-Mengentheorie (ZF), die Zermelo-Fraenkel-Mengentheorie mit dem Auswahlaxiom (ZFC), die Von Neumann-Bernays-Gödel-Mengentheorie (NBG), die nicht fundierte Mengenlehre , Bertrand Russell ‚s Art Theorie und alle die Theorien ihrer verschiedenen Modelle. Man kann auch zwischen klassischer Logik erster Ordnung, verschiedenen Logiken höherer Ordnung und intuitionistischer Logik wählen .

Ein Formalist könnte die Bedeutung der Menge von System zu System variieren. Einige Arten von Platonikern könnten bestimmte formale Systeme als Annäherung an eine zugrunde liegende Realität betrachten.

Mengentheoretische Definitionen der Endlichkeit

In Kontexten, in denen der Begriff der natürlichen Zahl logisch vor jedem Begriff der Menge steht, kann man eine Menge S als endlich definieren, wenn S eine Bijektion zu einer Menge natürlicher Zahlen der Form zulässt . Mathematiker entscheiden sich typischerweise dafür, Zahlenbegriffe in der Mengentheorie zu begründen , zum Beispiel könnten sie natürliche Zahlen durch die Ordnungstypen endlicher wohlgeordneter Mengen modellieren . Ein solcher Ansatz erfordert eine strukturelle Definition der Endlichkeit, die nicht von natürlichen Zahlen abhängt.

Verschiedene Eigenschaften, die die endlichen Mengen unter allen Mengen in der Theorie ZFC aussondern, erweisen sich in schwächeren Systemen wie ZF oder intuitionistischen Mengentheorien als logisch inäquivalent. Zwei Definitionen sind in der Literatur prominent vertreten, eine von Richard Dedekind , die andere von Kazimierz Kuratowski . (Kuratowskis ist die oben verwendete Definition.)

Eine Menge S heißt Dedekind unendlich, wenn es eine injektive, nicht surjektive Funktion gibt . Eine solche Funktion weist eine Bijektion zwischen S und einer echten Teilmenge von S auf , nämlich dem Bild von f . Gegeben eine unendliche Menge S von Dedekind , eine Funktion f und ein Element x , das nicht im Bild von f ist , können wir eine unendliche Folge von verschiedenen Elementen von S bilden , nämlich . Umgekehrt können wir bei einer gegebenen Folge in S, die aus verschiedenen Elementen besteht , eine Funktion f definieren, so dass sich auf Elementen in der Folge und f ansonsten wie die Identitätsfunktion verhält. Die unendlichen Mengen von Dedekind enthalten also Teilmengen, die den natürlichen Zahlen bijektiv entsprechen. Dedekind endlich bedeutet natürlich, dass jede injektive Selbstabbildung auch surjektiv ist.

Die Kuratowski-Endlichkeit wird wie folgt definiert. Bei einer gegebenen Menge S verleiht die binäre Operation von union der Potenzmenge P ( S ) die Struktur eines Halbgitters . Schreiben Sie K ( S ) für das Unterhalbgitter, das durch die leere Menge und die Singletons erzeugt wird, nennen Sie die Menge S Kuratowski endlich, wenn S selbst zu K ( S ) gehört. Intuitiv besteht K ( S ) aus den endlichen Teilmengen von S . Entscheidend ist, dass man keine Induktion, Rekursion oder Definition natürlicher Zahlen braucht, um zu definieren , indem man K ( S ) erhält, indem man einfach den Durchschnitt aller Teilsemilattices nimmt, die die leere Menge und die Singletons enthalten .

Leser, die mit Halbgittern und anderen Begriffen der abstrakten Algebra nicht vertraut sind, bevorzugen möglicherweise eine ganz elementare Formulierung. Kuratowski endlich bedeutet, dass S in der Menge K ( S ) liegt, die wie folgt konstruiert wird. Schreiben Sie M für die Menge aller Teilmengen X von P ( S ), so dass:

  • X enthält die leere Menge;
  • Für jeden Satz T in P ( S ), wenn X enthält T dann X auch die Vereinigung enthält T mit jedem Singleton.

Dann kann K ( S ) als der Schnittpunkt von M definiert werden .

In ZF bedeutet Kuratowski endlich, dass Dedekind endlich ist, aber nicht umgekehrt. Im Sprachgebrauch einer populären pädagogischen Formulierung kann man, wenn das Axiom der Wahl stark versagt, eine unendliche Sockenfamilie haben, ohne dass man eine Socke aus mehr als nur endlich vielen Paaren auswählen kann. Damit wäre die Menge solcher Socken Dedekind endlich: Es kann keine unendliche Folge von Socken geben, weil eine solche Folge eine Auswahl einer Socke für unendlich viele Paare ermöglichen würde, indem man die erste Socke in der Folge wählt. Die Endlichkeit von Kuratowski würde jedoch für den gleichen Sockensatz versagen.

Andere Konzepte der Endlichkeit

In der ZF-Mengentheorie ohne Auswahlaxiom sind die folgenden Begriffe der Endlichkeit für eine Menge S verschieden. Sie sind in streng absteigender Reihenfolge der Stärke angeordnet, dh wenn eine Menge S ein Kriterium in der Liste erfüllt, dann erfüllt sie alle der folgenden Kriterien. In Abwesenheit des Auswahlaxioms sind die umgekehrten Implikationen alle unbeweisbar, aber wenn das Auswahlaxiom angenommen wird, sind alle diese Konzepte äquivalent. (Beachten Sie, dass für keine dieser Definitionen zuerst die Menge endlicher Ordnungszahlen definiert werden muss; sie sind alle reine "mengentheoretische" Definitionen in Bezug auf die Gleichheits- und Zugehörigkeitsbeziehungen, die ω nicht beinhalten.)

  • Ich-endlich . Jede nichtleere Menge von Teilmengen von S hat ein ⊆-maximales Element. (Dies entspricht der Forderung nach einem ⊆-minimalen Element. Es entspricht auch dem numerischen Standardkonzept der Endlichkeit.)
  • Ia-endlich . Für jede Zerlegung von S in zwei Mengen ist mindestens eine der beiden Mengen I-endlich.
  • II-endlich . Jede nichtleere ⊆-monotone Menge von Teilmengen von S hat ein ⊆-maximales Element.
  • III-endlich . Die Potenzmenge P ( S ) ist Dedekind-endlich.
  • IV-endlich . S ist Dedekind endlich.
  • V-endlich . ∣ S ∣ = 0 oder 2⋅∣ S ∣ > ∣ S |.
  • VI-endlich . ∣ S ∣ = 0 oder ∣ S ∣ = 1 oder ∣ S ∣ 2 > ∣ S ∣.
  • VII-endlich . S ist I-endlich oder nicht gut geordnet.

Die Vorwärtsimplikationen (von stark zu schwach) sind Theoreme innerhalb von ZF. Gegenbeispiele zu den umgekehrten Implikationen (von schwach nach stark) in ZF mit Urelementen werden mit Hilfe der Modelltheorie gefunden .

Die meisten dieser Endlichkeitsdefinitionen und ihre Namen werden Tarski 1954 von Howard & Rubin 1998 , p. 278. Die Definitionen I, II, III, IV und V wurden jedoch in Tarski 1924 , S. 49, 93, zusammen mit Beweisen (oder Verweisen auf Beweise) für die Vorwärtsimplikationen präsentiert. Damals war die Modelltheorie noch nicht weit genug fortgeschritten, um Gegenbeispiele zu finden.

Jede der Eigenschaften I-endlich bis IV-endlich ist ein Begriff der Kleinheit in dem Sinne, dass jede Teilmenge einer Menge mit einer solchen Eigenschaft auch die Eigenschaft besitzt. Dies gilt nicht für V-endlich bis VII-endlich, da sie abzählbar unendliche Teilmengen haben können.

Siehe auch

Anmerkungen

Verweise

Externe Links