Schwache Ordnung

transitive  binäre Relationen v T e
Symmetrisch Antisymmetrisch Verbunden Gut begründet Hat sich angeschlossen Hat trifft Reflexiv Irreflexiv Asymmetrisch Total, Semiconnex Antireflexiv​ Äquivalenzrelation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Vorbestellung (Quasibestellung) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Teilordnung ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Gesamtvorbestellung ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Gesamtbestellung ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Vorbestellung ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Wohl-Quasi-Ordnung ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Gut bestellt ✗ Y Y Y ✗ ✗ Y ✗ ✗ Gitter ✗ Y ✗ ✗ Y Y Y ✗ ✗ Verbindungshalbgitter ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Treff-Halbgitter ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strenge Teilordnung ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strenge schwache Ordnung ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strikte Gesamtbestellung ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetrisch Antisymmetrisch Verbunden Gut begründet Hat sich angeschlossen Hat trifft Reflexiv Irreflexiv Asymmetrisch Definitionen, für alle und${\displaystyle a,b}$${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ und }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ oder }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{existiert}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{nicht }}bRa\end{aligned}}}$
YEin Sternchen (*) bedeutet, dass die Eigenschaft der Spalte für den Eintrag der Zeile (ganz links) immer gilt, während ein Kreuz (✗) anzeigt, dass die Eigenschaft im Allgemeinen nicht garantiert ist (sie kann gelten oder auch nicht). Beispielsweise wird in der Spalte „Symmetrisch“ durch ein Sternchen (*) und in der Spalte „Antisymmetrisch“ durch ein Kreuz (✗) angezeigt , dass jede Äquivalenzrelation symmetrisch, aber nicht notwendigerweise antisymmetrisch ist.Y Alle Definitionen fordern stillschweigend, dass die homogene Relation transitiv ist : für alle wenn und dann. Die Definition eines Begriffs kann zusätzliche Eigenschaften erfordern, die in dieser Tabelle nicht aufgeführt sind. ${\displaystyle R}$${\displaystyle a,b,c,}$${\displaystyle aRb}$${\displaystyle bRc}$${\displaystyle aRc.}$

In der Ordnungstheorie ist eine schwache Ordnung eine mathematische Formalisierung des intuitiven Begriffs einer Rangfolge einer Menge , deren Elemente teilweise gleichrangig sein können . Schwache Ordnungen sind eine Verallgemeinerung total geordneter Mengen (Rangfolgen ohne Gleichrangigkeit) und werden ihrerseits durch (streng) partiell geordnete Mengen und Präordnungen verallgemeinert . ^{[ 1 ]}

Es gibt mehrere gängige Methoden zur Formalisierung schwacher Ordnungen, die sich zwar voneinander unterscheiden, aber kryptomorph sind (ohne Informationsverlust ineinander überführbar): Sie können als strikte schwache Ordnungen (streng partiell geordnete Mengen, in denen Unvergleichbarkeit eine transitive Relation ist ), als totale Präordnungen (transitive binäre Relationen, in denen zwischen jedem Elementpaar mindestens eine der beiden möglichen Relationen existiert) oder als geordnete Partitionen ( Partitionen der Elemente in disjunkte Teilmengen mit einer totalen Ordnung auf den Teilmengen) axiomatisiert werden. In vielen Fällen ist auch eine andere Darstellungsform möglich , die sogenannte Präferenzanordnung basierend auf einer Nutzenfunktion .

Schwache Ordnungen werden anhand der geordneten Bell-Zahlen gezählt . Sie werden in der Informatik als Teil von Partitionsverfeinerungsalgorithmen und in der C++-Standardbibliothek verwendet . ^{[ 2 ]}

Im Pferderennsport hat die Verwendung von Zielfotos einige, aber nicht alle Gleichstände (oder, wie sie in diesem Zusammenhang genannt werden, tote Rennen ) eliminiert . Daher kann das Ergebnis eines Pferderennens durch eine schwache Rangfolge modelliert werden. ^{[ 3 ]} In einem Beispiel vom Maryland Hunt Cup Steeplechase 2007 war The Bruce der klare Sieger, aber zwei Pferde, Bug River und Lear Charm, teilten sich den zweiten Platz, während die übrigen Pferde weiter hinten lagen; drei Pferde erreichten das Ziel nicht. ^{[ 4 ]} In der schwachen Rangfolge, die dieses Ergebnis beschreibt, wäre The Bruce Erster, Bug River und Lear Charm würden nach The Bruce, aber vor allen anderen Pferden, die das Ziel erreichten, platziert, und die drei Pferde, die das Ziel nicht erreichten, würden als Letzte in der Rangfolge, aber gleichauf miteinander, platziert.

Die Punkte der euklidischen Ebene lassen sich nach ihrem Abstand vom Ursprung ordnen . Dies ist ein weiteres Beispiel für eine schwache Ordnung mit unendlich vielen Elementen, unendlich vielen Teilmengen gebundener Elemente (den Mengen von Punkten, die auf einem gemeinsamen Kreis um den Ursprung liegen) und unendlich vielen Punkten innerhalb dieser Teilmengen. Obwohl diese Ordnung ein kleinstes Element besitzt (den Ursprung selbst), hat sie weder ein zweitkleinstes noch ein größtes Element.

Meinungsumfragen bei politischen Wahlen liefern ein Beispiel für eine Rangordnung, die schwachen Ordnungen ähnelt, sich aber mathematisch besser auf andere Weise modellieren lässt. In den Ergebnissen einer Umfrage kann ein Kandidat deutlich vor dem anderen liegen, oder die beiden Kandidaten können statistisch gleichauf sein. Das bedeutet nicht, dass ihre Umfrageergebnisse identisch sind, sondern dass sie innerhalb der Fehlermarge des jeweils anderen liegen. Wenn jedoch Kandidat A statistisch gleichauf mit B und Kandidat B ebenfalls statistisch gleichauf mit B liegt, kann Kandidat A dennoch deutlich besser abschneiden als B. In diesem Fall ist die Gleichstand-Relation also nicht transitiv . Aufgrund dieser Möglichkeit lassen sich Rangordnungen dieser Art besser als Semiordnungen denn als schwache Ordnungen modellieren. ^{[ 5 ]}${\displaystyle x}$${\displaystyle y,}$${\displaystyle y}$${\displaystyle z,}$${\displaystyle x}$${\displaystyle z,}$

Sei im Folgenden eine homogene binäre Relation auf einer Menge (d. h. ist eine Teilmenge von ). Wie üblich schreiben wir und sagen, dass genau dann gilt , wenn wahr ist .${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S\times S}$${\displaystyle x<y}$${\displaystyle x<y}$${\displaystyle (x,y)\in \,<.\,}$

Vorbemerkungen zur Unvergleichbarkeit und Transitivität der Unvergleichbarkeit

Zwei Elemente und von heißen unvergleichbar bezüglich , wenn weder noch wahr ist. ^{[ 1 ]} Eine strikte partielle Ordnung ist genau dann eine strikte schwache Ordnung, wenn die Unvergleichbarkeit bezüglich eine Äquivalenzrelation ist . Die Unvergleichbarkeit bezüglich ist stets eine homogene symmetrische Relation auf . Sie ist genau dann reflexiv , wenn irreflexiv ist (d. h., dass immer falsch ist), was hier vorausgesetzt wird, sodass Transitivität die einzige Eigenschaft ist, die diese „Unvergleichbarkeitsrelation“ benötigt, um eine Äquivalenzrelation zu sein . ${\displaystyle x}$${\displaystyle y}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle x<y}$${\displaystyle y<x}$${\displaystyle \,<\,}$${\displaystyle \,<\,}$${\displaystyle \,<\,}$${\displaystyle S.}$${\displaystyle \,<\,}$${\displaystyle x<x}$

Definiere außerdem eine induzierte homogene Relation auf , indem du erklärst, dass , wobei wichtig ist, dass diese Definition nicht notwendigerweise dasselbe ist wie: genau dann, wenn . Zwei Elemente sind bezüglich unvergleichbar, genau dann, wenn sie bezüglich äquivalent sind (oder weniger umständlich: -äquivalent ), was per Definition bedeutet, dass beide wahr sind. Die Relation „sind unvergleichbar bezüglich “ ist somit identisch mit (d. h. gleich) der Relation „sind -äquivalent“ (insbesondere ist die erstere transitiv genau dann, wenn die letztere transitiv ist). Wenn irreflexiv ist, dann ist die Eigenschaft, die als „ Transitivität der Unvergleichbarkeit “ (unten definiert) bekannt ist , genau die notwendige und hinreichende Bedingung, um zu garantieren, dass die Relation „sind -äquivalent“ tatsächlich eine Äquivalenzrelation auf bildet. In diesem Fall erlaubt sie es, je zwei Elemente, die erfüllen , als ein einziges Objekt zu identifizieren (genauer gesagt, sie werden in ihrer gemeinsamen Äquivalenzklasse identifiziert ). ${\displaystyle \,\lesssim \,}$${\displaystyle S}$$${\displaystyle x\lesssim y{\text{ ist wahr }}\quad {\text{ genau dann, wenn }}\quad y<x{\text{ falsch ist}}}$$${\displaystyle x\lesssim y}$${\displaystyle x<y{\text{ oder }}x=y.}$${\displaystyle x,y\in S}$${\displaystyle \,<\,}$${\displaystyle x{\text{ und }}y}$${\displaystyle \,\lesssim \,}$${\displaystyle \,\lesssim }$${\displaystyle x\lesssim y{\text{ und }}y\lesssim x}$${\displaystyle \,<}$${\displaystyle \,\lesssim }$${\displaystyle \,<\,}$${\displaystyle \,\lesssim }$${\displaystyle S.}$${\displaystyle x,y\in S}$${\displaystyle x\lesssim y{\text{ und }}y\lesssim x}$

Definition

Eine strikte schwache Ordnung auf einer Menge ist eine strikte partielle Ordnung auf , für die die durch induzierte Unvergleichbarkeitsrelation auf eine transitive Relation ist . ^{[ 1 ]} Explizit ist eine strikte schwache Ordnung auf eine homogene Relation auf , die alle vier der folgenden Eigenschaften besitzt: ${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$

1. Irreflexivität : Dennes ist nicht wahr, dass${\displaystyle x\in S,}$${\displaystyle x<x.}$
   • Diese Bedingung gilt genau dann, wenn die induzierte Relation auf reflexiv ist , wobei definiert ist durch die Aussage, dass wahr ist, genau dann, wenn falsch ist .${\displaystyle \,\lesssim \,}$${\displaystyle S}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y}$${\displaystyle y<x}$
2. Transitivität : Für alle Wenn -Dann-Bedingungen gilt:${\displaystyle x,y,z\in S,}$${\displaystyle x<y{\text{ und }}y<z}$${\displaystyle x<z.}$
3. Asymmetrie : Für alleWennwahr, dannist falsch.${\displaystyle x,y\in S,}$${\displaystyle x<y}$${\displaystyle y<x}$
4. Transitivität der Unvergleichbarkeit :Wennunvergleichbar mit A ist(d. h. weder Anoch Awahr ist) und wennA unvergleichbar mit A ist,dannist A unvergleichbar mit A.${\displaystyle x,y,z\in S,}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x<y}$${\displaystyle y<x}$${\displaystyle y}$${\displaystyle z,}$${\displaystyle x}$${\displaystyle z.}$
   • Zwei Elemente sind bezüglich unvergleichbar genau dann, wenn sie bezüglich der induzierten Relation äquivalent sind (was per Definition bedeutet, dass beide wahr sind), wobei wie zuvor gilt, dass genau dann als wahr erklärt wird, wenn falsch ist. Diese Bedingung ist also genau dann erfüllt, wenn die durch " sind äquivalent bezüglich " definierte symmetrische Relation auf eine transitive Relation ist, d. h., wenn -äquivalent und auch -äquivalent sind , dann sind notwendigerweise auch -äquivalent. Dies lässt sich auch wie folgt ausdrücken: Wenn und auch, dann notwendigerweise${\displaystyle x{\text{ und }}y}$${\displaystyle \,<\,}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y{\text{ und }}y\lesssim x}$${\displaystyle x\lesssim y}$${\displaystyle y<x}$${\displaystyle S}$${\displaystyle x{\text{ und }}y}$${\displaystyle \,\lesssim \,}$${\displaystyle x{\text{ und }}y}$${\displaystyle \,\lesssim }$${\displaystyle y{\text{ und }}z}$${\displaystyle \,\lesssim }$${\displaystyle x{\text{ und }}z}$${\displaystyle \,\lesssim }$${\displaystyle x\lesssim y{\text{ und }}y\lesssim x}$${\displaystyle y\lesssim z{\text{ und }}z\lesssim y}$${\displaystyle x\lesssim z{\text{ und }}z\lesssim x.}$

Die Eigenschaften (1), (2) und (3) definieren eine strikte partielle Ordnung. Allerdings enthält diese Liste Redundanz, da Asymmetrie (3) Irreflexivität (1) impliziert und Irreflexivität (1) und Transitivität (2) zusammen Asymmetrie (3) implizieren. ^{[ 6 ]} Die Unvergleichbarkeitsrelation ist stets symmetrisch und genau dann reflexiv , wenn sie eine irreflexive Relation ist (was durch die obige Definition vorausgesetzt wird). Folglich ist eine strikte partielle Ordnung genau dann eine strikte schwache Ordnung, wenn ihre induzierte Unvergleichbarkeitsrelation eine Äquivalenzrelation ist. In diesem Fall partitionieren ihre Äquivalenzklassen die Menge aller , und darüber hinaus lässt sich die Menge dieser Äquivalenzklassen durch eine binäre Relation strikt total ordnen , die auch mit bezeichnet wird und für alle definiert ist durch: ${\displaystyle \,<\,}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle {\mathcal {P}}}$${\displaystyle \,<,}$${\displaystyle A,B\in {\mathcal {P}}}$

${\displaystyle A<B{\text{ genau dann, wenn }}a<b}$für einige (oder gleichbedeutend für alle) Vertreter${\displaystyle a\in A{\text{ und }}b\in B.}$

Umgekehrt führt jede strikte totale Ordnung auf einer Partition zu einer strikten schwachen Ordnung auf , die durch definiert ist, genau dann, wenn es Mengen in dieser Partition gibt, sodass${\displaystyle {\mathcal {P}}}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle a<b}$${\displaystyle A,B\in {\mathcal {P}}}$${\displaystyle a\in A,b\in B,{\text{ und }}A<B.}$

Nicht jede partielle Ordnung erfüllt das Transitivitätsgesetz der Unvergleichbarkeit. Betrachten wir beispielsweise die partielle Ordnung in der durch die Relation definierten Menge. Die Paare sind unvergleichbar, aber und sind relational. Daher bildet die Unvergleichbarkeit keine Äquivalenzrelation, und dieses Beispiel ist keine strikt schwache Ordnung. ${\displaystyle \{a,b,c\}}$${\displaystyle b<c.}$${\displaystyle a,b{\text{ und }}a,c}$${\displaystyle b}$${\displaystyle c}$

Für die Transitivität der Unvergleichbarkeit ist jede der folgenden Bedingungen notwendig und für strikte partielle Ordnungen auch hinreichend :

• Wenn dann für alle entweder oder beides.${\displaystyle x<y}$${\displaystyle z,}$${\displaystyle x<z{\text{ oder }}z<y}$
• Wenn unvergleichbar ist mit , dann gilt für alle entweder ( ) oder ( ) oder ( ist unvergleichbar mit und ist unvergleichbar mit ).${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x<z{\text{ und }}y<z}$${\displaystyle z<x{\text{ und }}z<y}$${\displaystyle z}$${\displaystyle x}$${\displaystyle z}$${\displaystyle y}$

Streng schwache Ordnungen sind eng mit totalen Präordnungen oder (nicht-strengen) schwachen Ordnungen verwandt , und dieselben mathematischen Konzepte, die sich mit strengen schwachen Ordnungen modellieren lassen, können ebenso gut mit totalen Präordnungen modelliert werden. Eine totale Präordnung oder schwache Ordnung ist eine Präordnung, in der je zwei Elemente vergleichbar sind. ^{[ 7 ]} Eine totale Präordnung erfüllt die folgenden Eigenschaften: ${\displaystyle \,\lesssim \,}$

• Transitivität : Für alle Wenn -Dann-Bedingungen gilt:${\displaystyle x,y,{\text{ and }}z,}$${\displaystyle x\lesssim y{\text{ and }}y\lesssim z}$${\displaystyle x\lesssim z.}$
• Starke Verbundenheit : Für alle${\displaystyle x{\text{ and }}y,}$${\displaystyle x\lesssim y{\text{ or }}y\lesssim x.}$
  • Dies impliziert Reflexivität : für alle${\displaystyle x,}$${\displaystyle x\lesssim x.}$

Eine totale Ordnung ist eine totale Präordnung, die antisymmetrisch ist, also gleichzeitig auch eine partielle Ordnung . Totale Präordnungen werden manchmal auch Präferenzrelationen genannt .

Das Komplement einer strikten schwachen Ordnung ist eine totale Präordnung und umgekehrt. Es erscheint jedoch natürlicher, strikte schwache Ordnungen und totale Präordnungen so zu verknüpfen, dass die Reihenfolge der Elemente erhalten bleibt, anstatt umgekehrt zu werden. Daher betrachten wir die Umkehrung des Komplements: Für eine strikte schwache Ordnung definieren wir eine totale Präordnung, indem wir setzen, dass sie immer dann gilt, wenn nicht der Fall ist, dass . Umgekehrt definieren wir eine strikte schwache Ordnung < aus einer totalen Präordnung, indem wir setzen, dass sie immer dann gilt, wenn nicht der Fall ist ^{[ 8 ].}${\displaystyle \,<,}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y}$${\displaystyle y<x.}$${\displaystyle \,\lesssim ,}$${\displaystyle x<y}$${\displaystyle y\lesssim x.}$

Zu jeder Präordnung gehört eine entsprechende Äquivalenzrelation, in der zwei Elemente als äquivalent definiert sind, wenn … Im Falle einer totalen Präordnung ist die zugehörige partielle Ordnung auf der Menge der Äquivalenzklassen eine totale Ordnung. Zwei Elemente sind in einer totalen Präordnung genau dann äquivalent, wenn sie in der zugehörigen strikten schwachen Ordnung unvergleichbar sind. ${\displaystyle x}$${\displaystyle y}$${\displaystyle x\lesssim y{\text{ and }}y\lesssim x.}$

Eine Partition einer Menge ist eine Familie nichtleerer, disjunkter Teilmengen, deren Vereinigung die Menge der Teilmengen ist . Eine Partition, zusammen mit einer Totalordnung der Partitionsmengen, ergibt eine Struktur, die von Richard P. Stanley als geordnete Partition ^{[ 9 ]} und von Theodore Motzkin als Liste von Mengen ^{[ 10 ]} bezeichnet wird . Eine geordnete Partition einer endlichen Menge lässt sich als endliche Folge der in der Partition enthaltenen Mengen schreiben : Beispielsweise sind die drei geordneten Partitionen der Menge 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 1 ...${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \{a,b\}}$$${\displaystyle \{a\},\{b\},}$$$${\displaystyle \{b\},\{a\},\;{\text{ and }}}$$$${\displaystyle \{a,b\}.}$$

In einer strikten schwachen Ordnung liefern die Äquivalenzklassen der Unvergleichbarkeit eine Mengenpartition, in der die Mengen eine totale Ordnung von ihren Elementen erben, was zu einer geordneten Partition führt. Umgekehrt führt jede geordnete Partition zu einer strikten schwachen Ordnung, in der zwei Elemente unvergleichbar sind, wenn sie derselben Menge in der Partition angehören, und andernfalls die Ordnung der sie enthaltenden Mengen erben.

Für Mengen mit hinreichend kleiner Kardinalität ist eine vierte Axiomatisierung möglich, die auf reellwertigen Funktionen basiert. Ist eine beliebige Menge , so induziert eine reellwertige Funktion auf eine strikte schwache Ordnung auf durch . Die zugehörige totale Präordnung ist gegeben durch und die zugehörige Äquivalenz durch . ${\displaystyle X}$${\displaystyle f:X\to \mathbb {R} }$${\displaystyle X}$${\displaystyle X}$$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a)\leq f(b)}$${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a)=f(b).}$

Die Relationen bleiben unverändert, wenn durch eine zusammengesetzte Funktion ersetzt wird , wobei eine streng monoton steigende , reellwertige Funktion ist, die mindestens im Wertebereich von definiert ist. So definiert beispielsweise eine Nutzenfunktion eine Präferenzrelation . In diesem Kontext werden schwache Ordnungen auch als Präferenzanordnungen bezeichnet . ^{[ 11 ]}${\displaystyle f}$${\displaystyle g\circ f}$${\displaystyle g}$${\displaystyle f.}$

Ist endlich oder abzählbar, so lässt sich jede schwache Ordnung auf durch eine Funktion darstellen. ^{[ 12 ]} Es gibt jedoch strikte schwache Ordnungen, denen keine reelle Funktion entspricht. Beispielsweise existiert keine solche Funktion für die lexikographische Ordnung auf . Während also in den meisten Präferenzrelationsmodellen die Relation bis auf ordnungserhaltende Transformationen eine Nutzenfunktion definiert, existiert keine solche Funktion für lexikographische Präferenzen . ${\displaystyle X}$${\displaystyle X}$${\displaystyle \mathbb {R} ^{n}.}$

Allgemeiner gilt: Ist eine Menge, eine Menge mit einer strikten schwachen Ordnung und eine Funktion, so induziert eine Funktion eine strikte schwache Ordnung auf durch . Wie zuvor ist die zugehörige totale Vorordnung durch und die zugehörige Äquivalenz durch gegeben. Es wird hier nicht vorausgesetzt, dass eine injektive Funktion ist ; daher kann eine Klasse von zwei äquivalenten Elementen auf eine größere Klasse äquivalenter Elemente auf induzieren. Ebenso wird nicht vorausgesetzt, dass eine surjektive Funktion ist ; daher kann eine Klasse äquivalenter Elemente auf eine kleinere oder leere Klasse auf induzieren. Die Funktion induziert jedoch eine injektive Funktion, die die Partition auf auf diejenige auf abbildet . Daher ist im Fall endlicher Partitionen die Anzahl der Klassen in kleiner oder gleich der Anzahl der Klassen auf .${\displaystyle X}$${\displaystyle Y}$${\displaystyle \,<,\,}$${\displaystyle f:X\to Y}$${\displaystyle f}$${\displaystyle X}$$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a){}\lesssim {}f(b),}$${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a){}\sim {}f(b).}$${\displaystyle f}$${\displaystyle Y}$${\displaystyle X.}$${\displaystyle f}$${\displaystyle Y}$${\displaystyle X.}$${\displaystyle f}$${\displaystyle X}$${\displaystyle Y.}$${\displaystyle X}$${\displaystyle Y.}$

Halbordnungen verallgemeinern strikte schwache Ordnungen, setzen aber keine Transitivität der Unvergleichbarkeit voraus. ^{[ 13 ]} Eine strikte schwache Ordnung, die trichotom ist, wird als strikte totale Ordnung bezeichnet . ^{[ 14 ]} Die totale Präordnung, die die Inverse ihres Komplements ist, ist in diesem Fall eine totale Ordnung .

Für eine strikte schwache Ordnung ist eine weitere zugehörige reflexive Relation ihr reflexiver Abschluss , eine (nicht-strikte) partielle Ordnung. Die beiden zugehörigen reflexiven Relationen unterscheiden sich hinsichtlich verschiedener und , für die weder noch gilt : In der totalen Präordnung, die einer strikten schwachen Ordnung entspricht, erhalten wir und , während wir in der durch den reflexiven Abschluss gegebenen partiellen Ordnung weder noch erhalten. Für strikte totale Ordnungen sind diese beiden zugehörigen reflexiven Relationen identisch: die entsprechende (nicht-strikte) totale Ordnung. ^{[ 14 ]} Der reflexive Abschluss einer strikten schwachen Ordnung ist eine Art von Serien-Parallel-Partialordnung . ${\displaystyle \,<\,}$${\displaystyle \,\leq .}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a<b}$${\displaystyle b<a}$${\displaystyle a\lesssim b}$${\displaystyle b\lesssim a,}$${\displaystyle a\leq b}$${\displaystyle b\leq a.}$

Die Anzahl der verschiedenen schwachen Ordnungen (dargestellt entweder als strikte schwache Ordnungen oder als totale Präordnungen) auf einer -elementigen Menge wird durch die folgende Folge gegeben (Folge A000670 in der OEIS ): ${\displaystyle n}$

Beachten Sie, dass S ( n , k ) sich auf Stirling-Zahlen zweiter Art bezieht .

Diese Zahlen werden auch Fubini-Zahlen oder geordnete Bell-Zahlen genannt .

Beispielsweise gibt es für eine Menge von drei markierten Elementen eine schwache Ordnung, in der alle drei Elemente gleich groß sind. Es gibt drei Möglichkeiten, die Elemente in eine Menge mit einem Element und eine Gruppe mit zwei gleich großen Elementen zu unterteilen. Jede dieser Unterteilungen liefert zwei schwache Ordnungen (eine, in der die Menge mit einem Element kleiner ist als die Gruppe mit zwei Elementen, und eine, in der diese Reihenfolge umgekehrt ist). Insgesamt ergeben sich also sechs schwache Ordnungen dieser Art. Außerdem gibt es genau eine Möglichkeit, die Menge in drei Mengen mit einem Element zu unterteilen, die auf sechs verschiedene Arten vollständig geordnet werden können. Somit existieren insgesamt 13 verschiedene schwache Ordnungen für drei Elemente.

Anders als bei partiellen Ordnungen ist die Familie schwacher Ordnungen auf einer gegebenen endlichen Menge im Allgemeinen nicht durch Schritte verbunden, die einer gegebenen Ordnung eine einzelne Ordnungsrelation hinzufügen oder entfernen. Beispielsweise unterscheidet sich bei drei Elementen die Ordnung, in der alle drei Elemente gleich groß sind, in mindestens zwei Paaren von jeder anderen schwachen Ordnung auf derselben Menge, weder in der strikten schwachen Ordnung noch in der totalen Präordnungsaxiomatisierung. Es ist jedoch eine andere Art von Schritt möglich, bei der die schwachen Ordnungen auf einer Menge stärker miteinander verbunden sind. Eine Dichotomie ist eine schwache Ordnung mit zwei Äquivalenzklassen. Eine Dichotomie ist mit einer gegebenen schwachen Ordnung kompatibel , wenn je zwei Elemente, die in der Ordnung in Beziehung stehen, entweder auf dieselbe Weise in Beziehung stehen oder in der Dichotomie gleich groß sind. Alternativ kann eine Dichotomie als Dedekind-Schnitt einer schwachen Ordnung definiert werden . Eine schwache Ordnung kann dann durch ihre Menge kompatibler Dichotomien charakterisiert werden. Für eine endliche Menge markierter Elemente lassen sich alle Paare schwacher Ordnungen durch eine Folge von Schritten miteinander verbinden, die jeweils eine Dichotomie zu dieser Menge von Dichotomien hinzufügen oder daraus entfernen. Darüber hinaus bildet der ungerichtete Graph , dessen Knoten die schwachen Ordnungen und dessen Kanten diese Schritte darstellen, einen partiellen Würfel . ^{[ 15 ]}

Geometrisch lassen sich die Gesamtordnungen einer gegebenen endlichen Menge als die Eckpunkte eines Permutoeders darstellen , und die Dichotomien auf derselben Menge als die Flächen des Permutoeders. In dieser geometrischen Darstellung entsprechen die schwachen Ordnungen der Menge den Flächen aller Dimensionen des Permutoeders (einschließlich des Permutoeders selbst, jedoch nicht der leeren Menge, als Fläche). Die Kodimension einer Fläche gibt die Anzahl der Äquivalenzklassen in der zugehörigen schwachen Ordnung an. ^{[ 16 ]} In dieser geometrischen Darstellung ist der partielle Kubus der Züge auf schwachen Ordnungen der Graph, der die Überdeckungsrelation des Flächenverbandes des Permutoeders beschreibt.

Beispielsweise ist das Permutoeder mit drei Elementen ein reguläres Sechseck. Das Flächengitter des Sechsecks (wobei das Sechseck selbst als Fläche, aber nicht die leere Menge, mitgezählt wird) hat dreizehn Elemente: ein Sechseck, sechs Kanten und sechs Ecken. Dies entspricht einer vollständig gebundenen schwachen Ordnung, sechs schwachen Ordnungen mit einer Bindung und sechs Gesamtordnungen. Der Graph der Züge dieser 13 schwachen Ordnungen ist in der Abbildung dargestellt. ${\displaystyle n=3,}$

Wie bereits erwähnt, finden schwache Ordnungen Anwendung in der Nutzentheorie. ^{[ 12 ]} In der linearen Programmierung und anderen kombinatorischen Optimierungsproblemen wird die Priorisierung von Lösungen oder Basen häufig durch eine schwache Ordnung beschrieben, die durch eine reellwertige Zielfunktion bestimmt wird . Das Phänomen von Gleichständen in diesen Ordnungen wird als „Degeneriertheit“ bezeichnet. Um Probleme aufgrund von Degeneriertheit zu vermeiden, wurden verschiedene Regeln zur Auflösung von Gleichständen verwendet, um diese schwache Ordnung zu einer totalen Ordnung zu verfeinern. ^{[ 17 ]}

Schwache Ordnungen finden auch in der Informatik Anwendung , beispielsweise in partitionsverfeinernden Algorithmen für die lexikographische Breitensuche und die lexikographische topologische Ordnung . In diesen Algorithmen wird eine schwache Ordnung der Knoten eines Graphen (dargestellt als eine Familie von Mengen, die die Knoten partitionieren , zusammen mit einer doppelt verketteten Liste, die eine totale Ordnung der Mengen liefert) im Verlauf des Algorithmus schrittweise verfeinert, bis schließlich eine totale Ordnung als Ausgabe des Algorithmus entsteht. ^{[ 18 ]}

In der Standardbibliothek der Programmiersprache C++ sortieren die Datentypen Menge und Multimenge ihre Eingabe durch eine Vergleichsfunktion, die zum Zeitpunkt der Template-Instanziierung festgelegt wird und von der angenommen wird, dass sie eine strikte schwache Ordnung implementiert. ^{[ 2 ]}

• Vergleichbarkeit  – Eigenschaft von Elementen, die durch Ungleichungen miteinander verbunden sind
• Vorordnung  – Reflexive und transitive binäre Relation
• Schwache Komponente  – Partition der Knoten eines gerichteten Graphen – die äquivalenten Teilmengen in der feinsten schwachen Ordnung, die mit einer gegebenen Relation konsistent ist