In der Mathematik, bestellen Sie besonders Theorie, ein teilweise bestellter Satz (oder poset) formalisiert und verallgemeinert das intuitive Konzept einer Einrichtung, sequencing, oder Einordnung der Elemente eines Satzes. Ein poset besteht aus einem Satz zusammen mit einer binären Beziehung, die anzeigt, dass, für bestimmte Paare von Elementen im Satz, eines der Elemente dem anderen vorangeht. Solch eine Beziehung wird eine teilweise Ordnung genannt, die Tatsache zu widerspiegeln, dass nicht jedes Paar von Elementen verbunden sein muss: Für einige Paare kann es sein, dass kein Element anderem im poset vorangeht.

So verallgemeinern teilweise Ordnungen die vertrauteren Gesamtbezüge, in denen jedes Paar verbunden ist. Ein begrenzter poset kann durch sein Diagramm von Hasse vergegenwärtigt werden, das die Einrichtungsbeziehung zeichnet.

Ein vertrautes wahres Beispiel eines teilweise bestellten Satzes ist eine Sammlung von durch genealogischen descendancy befohlenen Leuten. Einige Paare von Leuten ertragen die Beziehung des Nachkommen-Vorfahren, aber andere Paare ertragen keine solche Beziehung.

Formelle Definition

Eine teilweise Ordnung ist eine binäre Beziehung "" über einen Satz P, der reflexiv, antisymmetrisch, und, d. h., für den ganzen a, b, und c in P transitiv ist, haben wir das:

• ein  (reflexivity);
• wenn ein  b und b  dann = b (Antisymmetrie);
• wenn ein  b und b  c dann ein  c (transitivity).

Mit anderen Worten ist eine teilweise Ordnung eine antisymmetrische Vorordnung.

Ein Satz mit einer teilweisen Ordnung wird genannt ein teilweise bestellter Satz (hat auch einen poset genannt). Der Begriff hat befohlen, dass Satz manchmal auch für posets verwendet wird, so lange es vom Zusammenhang klar ist, dass keine anderen Arten von Ordnungen gemeint werden. Insbesondere völlig bestellte Sätze können auch "bestellte Sätze" besonders in Gebieten genannt werden, wo diese Strukturen üblicher sind als posets.

Für a, b, Elemente eines teilweise bestellten Satzes P, wenn ein  b oder b  a, dann sind a und b vergleichbar. Sonst sind sie unvergleichbar. Eine teilweise Ordnung, laut deren jedes Paar von Elementen vergleichbar ist, wird einen Gesamtbezug oder geradlinige Ordnung genannt; ein völlig bestellter Satz wird auch eine Kette (z.B, die natürlichen Zahlen mit ihrer Standardordnung) genannt. Ein poset, in dem keine zwei verschiedenen Elemente vergleichbar sind, wird eine Antikette genannt.

Beispiele

Standardbeispiele von posets, der in der Mathematik entsteht, schließen ein:

• Die reellen Zahlen, die durch den Standard weniger bestellt sind als oder die gleiche Beziehung  (ein völlig bestellter Satz ebenso).
• Der Satz von natürlichen Zahlen mit der Beziehung der Teilbarkeit ausgestattet.
• Der Scheitelpunkt-Satz eines geleiteten acyclic Graphen durch reachability bestellt.
• Der Satz von Teilmengen eines gegebenen Satzes (sein Macht-Satz) bestellt durch die Einschließung (sieh die Figur auf Spitzenrecht).
• Der Satz von Subräumen eines Vektorraums durch die Einschließung bestellt.
• Für einen teilweise bestellten Satz P, der Folge-Raum, der alle Folgen von Elementen von P enthält, wo Folge Folge b wenn jeder Artikel in einem Vorangehen dem entsprechenden Artikel in b vorangeht. Formell, wenn und nur wenn für den ganzen n in .
• Für einen Satz X und einen teilweise bestellten Satz P, der Funktionsraum, der alle Funktionen von X bis P, wo f  g wenn und nur wenn f (x)  g (x) für den ganzen x in X enthält.
• Ein Zaun, ein teilweise bestellter Satz, der durch eine Wechselfolge von Ordnungsbeziehungen &lt definiert ist; b > c < d...

Extrema

Es gibt mehrere Begriffe von "größten" und "kleinsten" Element in einem poset P namentlich:

• Größtes Element und kleinstes Element: Ein Element g in P ist ein größtes Element wenn für jedes Element in P, ein  g. Ein Element M in P ist kleinstes Element wenn für jedes Element in P, einer  M. Ein poset kann nur einen größten oder kleinstes Element haben.
• Maximale Elemente und minimale Elemente: Ein Element g in P ist ein maximales Element, wenn es kein Element in solchem P dass a> g gibt. Ähnlich ist eine Element-M in P ein minimales Element, wenn es kein Element in solchem P dass a gibt

In der Informatik werden Algorithmen, um geradlinige Erweiterungen von teilweisen Ordnungen (vertreten als die reachability Ordnungen von geleiteten acyclic Graphen) zu finden, das topologische Sortieren genannt.

In der Kategorie-Theorie

Jeder poset (und jede Vorordnung) können als eine Kategorie betrachtet werden, in der jeder Hom-Satz höchstens ein Element hat. Lassen Sie ausführlicher hom (x, y) = {(x, y)} wenn x ≤ y (und sonst der leere Satz) und (y, z) (x, y) = (x, z). Posets sind zu einander gleichwertig, wenn, und nur wenn sie isomorph sind. In einem poset ist das kleinste Element, wenn es besteht, ein anfänglicher Gegenstand, und das größte Element, wenn es besteht, ist ein Endgegenstand. Außerdem ist jeder vorbestellte Satz zu einem poset gleichwertig. Schließlich wird jede Unterkategorie eines poset Isomorphismus-geschlossen.

Ein functor von einer poset Kategorie (ein Diagramm, das durch eine poset Kategorie mit einem Inhaltsverzeichnis versehen ist), ist ein Ersatzdiagramm.

Teilweise Ordnungen in topologischen Räumen

Wenn P ein teilweise bestellter Satz ist, der auch die Struktur eines topologischen Raums gegeben worden ist, dann ist es üblich, um anzunehmen, dass das eine geschlossene Teilmenge des topologischen Produktraums ist. Unter dieser Annahme werden teilweise Ordnungsbeziehungen an Grenzen im Sinn dass wenn, und für alles ich dann gut benommen.

Zwischenraum

Für einen  b ist der geschlossene Zwischenraum [a, b] der Satz von Elementen x Zufriedenheit eines  x  b (d. h. ein  x und x  b). Es enthält mindestens die Elemente a und b.

Das Verwenden der entsprechenden strengen Beziehung"

Die halb offenen Zwischenräume [a, b) und (a, b] werden ähnlich definiert.

Ein poset ist lokal begrenzt, wenn jeder Zwischenraum begrenzt ist. Zum Beispiel sind die ganzen Zahlen unter ihrer natürlichen Einrichtung lokal begrenzt.

Dieses Konzept eines Zwischenraums in einer teilweisen Ordnung sollte mit der besonderen Klasse von teilweisen als die Zwischenraum-Ordnungen bekannten Ordnungen nicht verwirrt sein.

Siehe auch

• antimatroid, eine Formalisierung der Einrichtung auf einem Satz, der allgemeinere Familien der Einrichtung erlaubt als posets
• kausaler Satz
• Vergleichbarkeitsgraph
• geleitet setzt
• sortierter poset
• Halbgitter
• Gitter
• befohlene Gruppe
• Poset-Topologie, eine Art topologischer Raum, der von jedem poset definiert werden kann
• Halbordnung
• mit der Reihe parallele teilweise Ordnung
• strenge schwache Einrichtung - strenge teilweise Ordnung"

Links

• Folgen im OEIS:

:: Die Zahl von posets mit n hat Elemente etikettiert

:: Zahl von posets mit n unetikettierte Elemente