In der Mathematik und theoretischen Informatik ist die breiteste und abstrakteste Definition einer Enumeration eines Satzes eine genaue Auflistung von allen seinen Elementen (vielleicht mit der Wiederholung). Die Beschränkungen, die dem Typ der verwendeten Liste auferlegt sind, hängen vom Zweig der Mathematik und des Zusammenhangs ab, in dem arbeitet. In spezifischeren Einstellungen umfasst dieser Begriff der Enumeration die zwei verschiedenen Typen der Auflistung: Derjenige, wo es eine natürliche Einrichtung und diejenige gibt, wo die Einrichtung nebliger ist. Diese zwei verschiedenen Arten von Enumerationen entsprechen einem Verfahren, um alle Mitglieder des Satzes in einer bestimmten Folge oder einen Graf von Gegenständen einer angegebenen Art beziehungsweise zu verzeichnen. Während die zwei Arten der Enumeration häufig in den meisten natürlichen Situationen überlappen, können sie sehr verschiedene Bedeutungen in bestimmten Zusammenhängen annehmen.

Enumeration in combinatorics

In combinatorics bedeutet Enumeration, zu zählen, d. h., die genaue Zahl der Elemente von begrenzten Sätzen bestimmend, die gewöhnlich in unendliche Familien, wie die Familie von Sätzen jeder gruppiert sind, aus allen Versetzungen von einem begrenzten Satz bestehend. Dort gedeihen Teilbereiche in vielen Zweigen der Mathematik, die mit dem Aufzählen in diesem Sinn Gegenstände von speziellen Arten betroffen ist. Zum Beispiel in der Teilungsenumeration und Graph-Enumeration ist das Ziel, Teilungen oder Graphen aufzuzählen, die bestimmte Bedingungen entsprechen.

Enumeration in der Mengenlehre

In der Mengenlehre hat der Begriff der Enumeration einen breiteren Sinn und verlangt nicht, dass der Satz, der wird aufzählt begrenzt ist.

Enumeration als Auflistung

Wenn eine Enumeration in einem Zusammenhang der geordneten Liste verwendet wird, erlegen wir eine Art Einrichtungsstruktur-Voraussetzung an den Index-Satz auf. Während wir die Voraussetzungen an die Einrichtung ziemlich locker machen können, um große Allgemeinheit zu berücksichtigen, ist die natürlichste und allgemeine Vorbedingung, dass der Index untergegangen ist gut bestellt zu werden. Gemäß dieser Charakterisierung wird eine bestellte Enumeration definiert, um eine Surjektion mit einem gut bestellten Gebiet zu sein. Diese Definition ist im Sinn natürlich, dass ein gegebener gut bestellender auf dem Index-Satz eine einzigartige Weise zur Verfügung stellt, das folgende Element gegeben eine teilweise Enumeration zu verzeichnen.

Enumeration im zählbaren gegen den unzählbaren Zusammenhang

Der grösste Teil der üblichen Anwendung der Enumeration in der Mengenlehre kommt im Zusammenhang vor, wo unendliche Sätze in diejenigen getrennt werden, die zählbar sind und diejenigen, die nicht sind. In diesem Fall ist eine Enumeration bloß eine Enumeration mit dem Gebiet ω die Ordnungszahl der natürlichen Zahlen. Diese Definition kann auch wie folgt festgesetzt werden:

• Als ein surjective, der von (die natürlichen Zahlen) zu S kartografisch darstellt (d. h. ist jedes Element von S das Image von mindestens einer natürlicher Zahl). Diese Definition ist zu Fragen der Berechenbarkeit und elementaren Mengenlehre besonders passend.

Wir können es auch verschieden definieren, wenn wir mit begrenzten Sätzen arbeiten. In diesem Fall kann eine Enumeration wie folgt definiert werden:

• Als, von S bis ein anfängliches Segment der natürlichen Zahlen bijektiv kartografisch darzustellen. Diese Definition ist zu kombinatorischen Fragen und begrenzten Sätzen besonders passend; dann ist das anfängliche Segment {1,2..., n} für einen n, der der cardinality von S ist.

In der ersten Definition ändert es sich, ob kartografisch darzustellen, auch erforderlich ist, injective zu sein (d. h. jedes Element von S ist das Image von genau einer natürlicher Zahl), und/oder erlaubt, teilweise zu sein (d. h. kartografisch darzustellen, wird nur für einige natürliche Zahlen definiert). In einigen Anwendungen (besonders diejenigen, die mit der Berechenbarkeit des Satzes S betroffen sind), sind diese Unterschiede von wenig Wichtigkeit, weil einer nur mit der bloßen Existenz von etwas Enumeration betroffen wird, und eine Enumeration gemäß einer liberalen Definition allgemein andeuten wird, dass Enumerationen, die strengere Voraussetzungen auch befriedigen, bestehen.

Die Enumeration von begrenzten Sätzen verlangt offensichtlich, dass entweder non-injectivity oder Parteilichkeit, und in Zusammenhängen akzeptiert werden, wo begrenzte Sätze ein erscheinen können oder beide von diesen unvermeidlich da sind.

Beispiele

• Die natürlichen Zahlen sind enumerable nach der Funktion f (x) = x. In diesem Fall ist einfach die Identitätsfunktion.

• der Satz von ganzen Zahlen ist enumerable durch

::

ist eine Bijektion, da jede natürliche Zahl genau einer ganzer Zahl entspricht. Der folgende Tisch gibt die ersten paar Werte dieser Enumeration:

• Alle begrenzten Sätze sind enumerable. Lassen Sie S ein begrenzter Satz mit n Elementen sein und K = {1,2..., n} zu lassen. Wählen Sie jedes Element s in S aus und teilen Sie &fnof zu; (n) = s. Jetzt Satz S = S − {s} (wo − zeigt Satz-Unterschied an). Wählen Sie irgendwelche Element-s' &isin aus; S und teilt &fnof zu; (n − 1) = s. Setzen Sie diesen Prozess fort, bis alle Elemente des Satzes eine natürliche Zahl zugeteilt worden sind. Dann ist eine Enumeration von S.
• Die reellen Zahlen haben keine zählbare Enumeration, wie bewiesen, durch das diagonale Argument des Kantoren und den ersten uncountability Beweis des Kantoren.

Eigenschaften

• Dort besteht eine Enumeration für einen Satz (in diesem Sinn), wenn, und nur wenn der Satz zählbar ist.
• Wenn ein Satz enumerable ist, wird es eine unzählbare Unendlichkeit von verschiedenen Enumerationen haben, außer in den degenerierten Fällen des leeren Satzes oder (abhängig von genauer Definition) Sätze mit einem Element. Jedoch, wenn man verlangt, dass Enumerationen injective sind, und nur eine beschränkte Form der solcher Parteilichkeit dass wenn &fnof erlaubt; (n) wird dann &fnof definiert; (m) muss für die ganze M definiert werden veranlasst eine Gut-Ordnung  auf diesem Satz, der durch s  t wenn und nur wenn Minute e (s) &le definiert ist; Minute e (t). Obwohl die Ordnung wenig haben kann, um mit dem zu Grunde liegenden Satz zu tun, ist es nützlich, wenn eine Ordnung des Satzes notwendig ist.

Ordnungsenumeration

In der Mengenlehre gibt es einen allgemeineren Begriff einer Enumeration als die Charakterisierung, die das Gebiet der Schlagseite habenden Funktion verlangt, ein anfängliches Segment der Natürlichen Zahlen zu sein, wo das Gebiet der Aufzählen-Funktion jede Ordnungszahl annehmen kann. Laut dieser Definition ist eine Enumeration eines Satzes S jede Surjektion von einer Ordnungszahl α auf S. Die einschränkendere Version der Enumeration erwähnt ist vorher der spezielle Fall wo α ist eine begrenzte Ordnungszahl oder die erste Grenze Ordnungs-ω. diese mehr verallgemeinerte Version erweitert die oben erwähnte Definition, um transfinite Auflistungen zu umfassen.

Laut dieser Definition kann die erste unzählbare Ordnungszahl durch die Identitätsfunktion darauf aufgezählt werden, so dass diese zwei Begriffe nicht zusammenfallen. Mehr allgemein ist es ein Lehrsatz von ZF, dass jeder gut bestellte Satz unter dieser Charakterisierung aufgezählt werden kann, so dass es bis zum Wiederbeschriften mit der verallgemeinerten Schlagseite habenden Enumeration zusammenfällt. Wenn man auch das Axiom der Wahl annimmt, dann können alle Sätze aufgezählt werden, so dass es bis zum Wiederbeschriften mit der allgemeinsten Form von Enumerationen zusammenfällt.

Da Satz-Theoretiker mit unendlichen Sätzen willkürlich großen cardinalities arbeiten, neigt die Verzug-Definition unter dieser Gruppe von Mathematikern einer Enumeration eines Satzes dazu, irgendwelcher willkürlich α-sequence zu sein, genau alle seine Elemente verzeichnend. Tatsächlich, im Buch von Jech, das eine allgemeine Verweisung für Satz-Theoretiker ist, wird eine Enumeration definiert, um genau das zu sein. Deshalb, um Zweideutigkeit zu vermeiden, kann man den Begriff begrenzt enumerable oder denumerable gebrauchen, um einen der entsprechenden Typen von ausgezeichneten zählbaren Enumerationen anzuzeigen.

Enumeration als Vergleich von cardinalities

Formell ist die am meisten einschließliche Definition einer Enumeration eines Satzes S jede Surjektion von einem willkürlichen Index-Satz I auf S. In diesem breiten Zusammenhang kann jeder Satz S durch die Identitätsfunktion von S auf sich trivial aufgezählt werden. Wenn man das Axiom der Wahl nicht annimmt oder eine seiner Varianten, S keinen gut bestellend zu haben braucht. Selbst wenn man wirklich annimmt, dass das Axiom der Wahl, S keinen natürlich gut bestellend zu haben braucht.

Diese allgemeine Definition leiht deshalb sich zu einem Zählen-Begriff, wo wir uns für "wie viel" aber nicht "worin Ordnung interessieren." In der Praxis wird diese breite Bedeutung der Enumeration häufig verwendet, um die Verhältnisgrößen oder cardinalities von verschiedenen Sätzen zu vergleichen. Wenn man in der Zermelo-Fraenkel Mengenlehre ohne das Axiom der Wahl arbeitet, kann man die zusätzliche Beschränkung auferlegen wollen, von der eine Enumeration auch injective (ohne Wiederholung) seitdem in dieser Theorie, der Existenz einer Surjektion sein muss, brauche mir auf S nicht die Existenz einer Einspritzung von S in mich einzubeziehen.

Enumeration in der Berechenbarkeitstheorie

In der Berechenbarkeitstheorie denkt man häufig zählbare Enumerationen mit der zusätzlichen Voraussetzung, dass von zum aufgezählten Satz kartografisch darzustellen, berechenbar sein muss. Der Satz, der wird aufzählt, wird dann rekursiv enumerable (oder berechenbar enumerable auf der zeitgenössischeren Sprache) genannt, sich auf den Gebrauch der recursion Theorie in Formalisierungen dessen beziehend, was es für die Karte bedeutet, berechenbar zu sein.

In diesem Sinn ist eine Teilmenge von Natürlichen Zahlen berechenbar enumerable, wenn es die Reihe einer berechenbaren Funktion ist. In diesem Zusammenhang kann enumerable verwendet werden, um berechenbar enumerable zu bedeuten. Jedoch charakterisieren diese Definitionen verschiedene Klassen, da es unzählbar viele Teilmengen von Natürlichen Zahlen gibt, die durch eine willkürliche Funktion mit dem Gebiet &omega aufgezählt werden können; und nur zählbar viele berechenbare Funktionen. Ein spezifisches Beispiel eines Satzes mit einer Enumeration, aber nicht einer berechenbaren Enumeration ist die Ergänzung des hinkenden Satzes.

Außerdem illustriert diese Charakterisierung einen Platz, wo die Einrichtung der Auflistung wichtig ist. Dort besteht eine berechenbare Enumeration des hinkenden Satzes, aber nicht diejenige, die die Elemente in einer zunehmenden Einrichtung verzeichnet. Wenn es ein gäbe, dann würde der hinkende Satz entscheidbar sein, der nachweisbar falsch ist. Im Allgemeinen rekursiv enumerable zu sein, ist eine schwächere Bedingung als, ein entscheidbarer Satz zu sein.

Siehe auch

• Ordinalzahl
• Definition von Enumerative

Links

• Handbuch der Enumeration, Ein Textbuch auf den Wissenschaften der Enumeration durch C. J. Coffman an www.gutenberg.org