WikiDer > Teilbestellung

Schematische Darstellung einer Teilordnung

In dem Ordnungstheorie, eine Unterregion der Mathematik, ist ein Teilbestellung oder Teilbestellung auf einen Sammlung ein Beziehung auf dieser Sammlung, normalerweise als "${displaystyle leq }$", die angibt, welche der Elemente als aufeinanderfolgend verglichen werden können. In einer Teilreihenfolge werden nicht unbedingt alle Elemente verglichen, aber es kann Paare von Elementen geben, bei denen nicht klar ist, welches der beiden Elemente in der Reihenfolge vor dem Sonstiges Im Extremfall ist nicht einmal ein Paar vergleichbar Eine Teilordnung ist eine Verallgemeinerung des Begriffs Gesamtbestellung, in welchem ​​von jedem Elementpaar bestimmt wird, welches von beiden der Nachfolger des anderen ist.

Definition

EIN zweisitzig Beziehung ${Anzeigestil R}$ auf einer Sammlung ${Anzeigestil V}$ heißt a Teilbestellung auf ${Anzeigestil V}$ wenn

• ${Anzeigestil R}$reflexiv ist, das ist ${displaystyle xRx}$.
• ${Anzeigestil R}$ ist antisymmetrisch, das heißt: wenn ${displaystyle xRy}$ und ${Anzeigestil yRx}$, als ${Anzeigestil x=y}$
• ${Anzeigestil R}$transitiv das heißt, wenn ${displaystyle xRy}$ und ${displaystyle yRz}$, dann ${displaystyle xRz}$

Die Sammlung ${Anzeigestil V}$ auf der eine Teilordnung definiert ist, heißt a teilweise bestelltes Set, in englischsprachigen wissenschaftlichen Publikationen oft auf . abgekürzt Poset (von teilweise bestelltes Set).

Terminologie und Notation; invers

Das Bestellverhältnis ${Anzeigestil R}$ wird normalerweise als "${displaystyle leq }$", und heißt dann "kleiner oder gleich". Es gibt eine zugehörige Ordnungsrelation "${displaystyle geq }$", "größer oder gleich", so dass ${displaystyle aleqb}$ dann und nur dann, wenn ${displaystyle bgeq a}$. Dies wird die Umkehrung der Teilordnung genannt."${displaystyle leq }$“ und ist selbst auch ein Teilauftrag.

Begriffsdefinitionen wie kleinstes, größtes, infimum, supremum, minimum, maximum erfolgen immer unter der Annahme eines Zusammenhangs mit der Terminologie und Notation von "${displaystyle leq }$". Wendet man dies auf eine Beziehung mit der Terminologie und Notation von "${displaystyle geq }$“ würde Verwirrung stiften, wahrscheinlich bedeutet dies, die Definitionen auf die Umkehrung anzuwenden.

Anstelle der Schreibweise "${displaystyle leq }$", gelesen als "kleiner oder gleich", für das Ordnungsverhältnis wird die neutrale Bezeichnung verwendet ${Anzeigestil a}$ ist ein Vorgänger von ${displaystyle b}$ wenn ${displaystyle aeq b, aleq b}$.

Beispiel

Auf der reale Nummern${displaystyle mathbb {R} }$ ist die Beziehung"${displaystyle geq }$" (größer oder gleich) eine Teilbestellung, immerhin:

• ${displaystyle xgeq x}$ für alle ${displaystyle xin mathbb {R} }$,
• ${displaystyle xgeq y}$ und ${displaystyle ygeq x}$ impliziert ${Anzeigestil x=y}$ für alle ${displaystyle x,yin mathbb {R}}$,
• ${displaystyle xgeq y}$ und ${displaystyle ygeq z}$ impliziert ${displaystyle xgeq z}$ für alle ${displaystyle x,y,satz mathbb {R} }$.

Teilmenge

wenn ${displaystyle Rsubset V^{2}}$ ist eine Teilordnung auf einer Menge ${Anzeigestil V,}$ und ${Anzeigestil W}$ ist eine Teilmenge von ${Anzeigestil V,}$ dann definiert das Beschränkung von ${Anzeigestil R}$ bis um ${Anzeigestil W}$

${displaystyle R|W={(a,b)in Rmid a,bin W}}$

eine Teilbestellung auf ${Anzeigestil W}$.

EIN Kette einer Bestellbeziehung ${Anzeigestil R}$ ist eine Teilmenge ${displaystyle Wsubset V}$ damit die Einschränkung ${Anzeigestil R|W}$ ist ein Gesamtauftrag.^[1]

EIN Anti-Kette ist eine Teilmenge ${displaystyle Wsubset V}$ damit die Einschränkung ${Anzeigestil R|W}$ enthält nur Schleifen, d.h.

${displaystyle R|W={(w,w)mid win W}}$^[1]

Strenge Teilordnung

Eine Teilordnung hat immer eine entsprechende Relation, die nicht reflexiv ist. Anstelle der Relation "größer gleich" gilt nur die Reihenfolge "größer als". Eine solche Ordnung wird als strikte Teilordnung bezeichnet.

Definition

EIN Zwei-Positionen-Endo-Beziehung "${Anzeigestil <}$"auf der Sammlung ${Anzeigestil X}$ heißt a strikte Teilordnung, wenn "${Anzeigestil <}$" ist asymmetrisch und transitiv. (Asymmetrie bedeutet nicht beides ${Anzeigestil x$ und ${Anzeigestil y$ kann wahr sein, also wenn ${Anzeigestil x$, dann nicht ${Anzeigestil y$.)

Beachten Sie, dass eine strikte Teilordnung keine Teilordnung ist. Einige Autoren nennen eine partielle Ordnung, wie hier erwähnt, eine schwache partielle Ordnung.

Außerdem impliziert Asymmetrie Irreflexivität. Eine strikte Teilordnung kann auch als irreflexive, transitive zweistellige Endo-Relation definiert werden, da Irreflexivität und Transitivität zusammen eine Asymmetrie implizieren.

Da ist ein Einzelkorrespondenz zwischen allen Teilaufträgen auf a Sammlung${Anzeigestil X}$ und alle strengen Teilordnungen am selben Set ${Anzeigestil X}$, die man erhält, indem man jede Teilordnung auf ihre reflexive Reduktion. Von jeder Teilbestellung auf ${Anzeigestil X}$ ist seine reflexive Reduktion eine strikte Teilordnung auf orde ${Anzeigestil X}$. Darüber hinaus bildet die Umkehrung dieser Eins-zu-Eins-Korrespondenz strenge Teilordnungen auf ihre reflexartiger Verschluss. Der reflexive Abschluss einer strikten Teilordnung auf ${Anzeigestil X}$ ist eine Teilbestellung auf ${Anzeigestil X}$.

Die strikte Teilordnungsrelation wird normalerweise als "${Anzeigestil <}$“, und heißt dann „kleiner als“. Die Umkehrung wird dann notiert „${Anzeigestil >}$" und heißt "größer als". Es ist selbst auch eine strenge Teilordnung, und die reflexive Reduktion von "${displaystyle geq }$".

des Vierer"${displaystyle leq }$", "${Anzeigestil <}$", "${displaystyle geq }$" und "${Anzeigestil >}$", wie aus dem Vorstehenden ersichtlich ist, folgt jedes eindeutig den anderen drei. Nach Einführung eines der vier ist es daher möglich, die anderen Symbole und die zugehörigen Begriffe zu verwenden, ohne sie explizit zu definieren. Wird eine Ordnungsbeziehung mit a anderes Symbol, zum Beispiel ${Anzeigestil R}$, dann wird die Bedeutung von Begriffen wie "kleiner" als die der Notation "${displaystyle leq }$" oder "${Anzeigestil <}$".

Für zwei Elemente ${Anzeigestil a}$ und ${displaystyle b}$ Es gibt vier Möglichkeiten: gleich, kleiner, größer und unvergleichbar. An einer Gesamtbestellung letzteres kommt nicht vor.

Manchmal statt "${Anzeigestil a}$ ist kleiner als ${displaystyle b}$"gut gesagt"${Anzeigestil a}$ tritt ein ${displaystyle b}$" oder "${Anzeigestil a}$ ist ein Vorgänger von ${displaystyle b}$".

Gitter

Hasse-Diagramm des Sammlung von allen Teiler von 60, teilweise nach Teilbarkeit geordnet

sehen Raster (Mathematik) für den Hauptartikel zu diesem Thema.

Eine partielle Ordnung, in der jedes Argumentpaar eine Gemeinsamkeit hat infimum und ein gemeinsames höchste hat, heißt a Bar.

Lexikographische Reihenfolge

Die lexikographische Ordnung/Ordnung/Ordnung ${displaystyle leq }$ auf dem kartesischen Produkt ${Anzeigestil A imes B}$ von zwei teilweise geordneten Sets ${Anzeigestil A}$ und ${Anzeigestil B}$ ist definiert als

${displaystyle (a,b)leq (a',b')}$ dann und nur dann, wenn ${displaystyle a$ oder ${Anzeigestil (a=a'}$ und ${displaystyle bleq b')}$.

Das Ergebnis ist eine Teilordnung. wenn ${Anzeigestil A}$ und ${Anzeigestil B}$total bestellt sind, ist die lexikographische Ordnung auch eine Gesamtordnung.

Die lexikographische Ordnung kann analog auch für mehr als zwei Mengen definiert werden. Das Konzept kann auch für die Ordnung einer Teilmenge eines kartesischen Produkts verwendet werden, da die Ordnung des kartesischen Produkts die Ordnung der Teilmenge impliziert.

EIN Datumsformat wenn 2020-03-21 lexikografisch ist (genauer: die lexikografische Reihenfolge entspricht der chronologisch). Ein Datumsformat wie der 21. März 2020 ist bis auf die Formatreihenfolge ebenfalls möglich. Ein Zeitformat wie 12:27 Uhr ist nicht einmal das (weil es früher als 13:27 Uhr ist), es sei denn, es wird eine Stundenreihenfolge mit 12 unter 1 verwendet. Mit einem alten Jahr Stil wo das Jahr in der Mitte eines Monats inkrementiert wurde, war das Datumsformat selbst mit solchen Vorbehalten nicht lexikografisch.

Der Begriff lexikographische Ordnung leitet sich aus der Anordnung von Wörtern und Phrasen ab (alphabetischer Reihenfolge) basierend auf der Reihenfolge der Buchstaben im Alphabet. Eine einfache Variante davon besteht darin, sich den Abstand aller zu sortierenden Texte bis auf die gleiche Länge vorzustellen und dann lexikographisch mit dem Leerzeichen als erstem Zeichen des Zeichensatzes zu sortieren. Bei einem Text mit Teilen, die als 3.1.1, 3.2.1.5 usw. nummeriert sind.^[2], ist die übliche Reihenfolge dieser Teile gleich.

Manchmal gibt es im Wesentlichen eine lexikografische Reihenfolge, aber die Teile sind in einer anderen Reihenfolge aufgeführt, beispielsweise mit einem Datum in der Form 11. März 2020 statt März 2020.11.

Geordneter Vektorraum

EIN Vektorraum${Anzeigestil V}$ über den Körper ${displaystyle mathbb {R} }$ der reellen Zahlen heißt geordnet, wenn sie mit einer Teilordnung versehen ist ${displaystyle leq }$ die die Vektorraumoperationen wie folgt respektiert:^[3]Für alle ${displaystyle u,v,win V}$ mit ${displaystyle uleq v}$ und ${ Anzeigestil Lambda in Mathbb {R} , Lambda geq 0}$, gilt

1. ${displaystyle u wleq v w}$
2. ${displaystyle lambda uleq lambda v}$

Die mit der natürlichen Ordnung versehenen reellen Zahlen selbst bilden einen geordneten Vektorraum, aber auch jeden Vektorraum, der aus reellwertigen Funktionen auf einem gegebenen Gebiet besteht. Für Funktionen ${displaystyle f}$ und ${displaystyle g}$ gilt dann ${displaystyle fleq g}$ wie für alle ${Anzeigestil x}$ in der Domäne ${Anzeigestil f(x)leq g(x).}$

Abweichende Verwendung des Ausdrucks "unvergleichbar"

Manchmal wird der Ausdruck "unvergleichbar" im allgemeinen Sprachgebrauch etwas verwirrend in einem anderen Sinne als dem obigen "unvergleichbar" verwendet, um anzuzeigen, dass von zwei Größen die eine viel größer ist als die andere.

Siehe auch

• Gesamtbestellung