Ordnungstheorie - Order theory

Eine aktuelle Anleitung zu diesem Thema finden Sie unter Überblick über die Ordnungstheorie .

Die Ordnungstheorie ist ein Zweig der Mathematik, der den intuitiven Begriff der Ordnung anhand binärer Beziehungen untersucht . Es bietet einen formalen Rahmen für die Beschreibung von Aussagen wie "das ist weniger als das" oder "das geht davor". Dieser Artikel führt in das Feld ein und enthält grundlegende Definitionen. Eine Liste ordnungstheoretischer Begriffe finden Sie im Glossar zur Ordnungstheorie .

Hintergrund und Motivation

Aufträge gibt es überall in der Mathematik und verwandten Gebieten wie der Informatik . Die erste Reihenfolge, die in der Grundschule oft diskutiert wird , ist die Standardreihenfolge der natürlichen Zahlen, zB "2 ist kleiner als 3", "10 ist größer als 5" oder "Hat Tom weniger Kekse als Sally?". Dieses intuitive Konzept kann auf Ordnungen auf anderen Zahlenmengen , wie den ganzen Zahlen und den reellen Zahlen , erweitert werden . Die Idee, größer oder kleiner als eine andere Zahl zu sein, gehört zu den Grundintuitionen von Zahlensystemen (vergleiche mit Zahlensystemen ) im Allgemeinen (obwohl man sich meistens auch für die tatsächliche Differenz zweier Zahlen interessiert , die nicht durch die Ordnung gegeben ist ). Andere bekannte Beispiele für Ordnungen sind die alphabetische Reihenfolge von Wörtern in einem Wörterbuch und die genealogische Eigenschaft der linearen Abstammung innerhalb einer Gruppe von Personen.

Der Begriff der Ordnung ist sehr allgemein und geht über Kontexte hinaus, die ein unmittelbares, intuitives Gefühl für Abfolge oder relative Quantität haben. In anderen Kontexten können Ordnungen Vorstellungen von Eindämmung oder Spezialisierung erfassen. Abstrakt läuft diese Art der Ordnung auf die Teilmengenrelation hinaus , zB „ Kinderärzte sind Ärzte “ und „ Kreise sind nur Sonderfall- Ellipsen “.

Einige Ordnungen, wie "kleiner-als" bei natürlichen Zahlen und alphabetische Reihenfolge bei Wörtern, haben eine besondere Eigenschaft: Jedes Element kann mit jedem anderen Element verglichen werden, dh es ist kleiner (früher) als, größer (später) als, oder identisch mit. Bei vielen anderen Bestellungen jedoch nicht. Betrachten Sie zum Beispiel die Teilmengenordnung einer Sammlung von Mengen : Obwohl die Menge der Vögel und die Menge der Hunde beide Teilmengen der Menge der Tiere sind, bilden weder die Vögel noch die Hunde eine Teilmenge der anderen. Jene Ordnungen wie die "Teilmenge von"-Beziehungen, für die es unvergleichbare Elemente gibt, werden Teilordnungen genannt ; Ordnungen, bei denen jedes Elementpaar vergleichbar ist, sind Gesamtordnungen .

Die Ordnungstheorie erfasst die Intuition von Ordnungen, die aus solchen Beispielen in einem allgemeinen Kontext entsteht. Dies wird durch die Angabe von Eigenschaften erreicht, die eine Relation ≤ haben muss, um eine mathematische Ordnung zu sein. Dieser abstraktere Ansatz ist sehr sinnvoll, da man zahlreiche Theoreme im allgemeinen Rahmen ableiten kann, ohne sich auf die Details einer bestimmten Ordnung zu konzentrieren. Diese Erkenntnisse lassen sich dann ohne weiteres auf viele weniger abstrakte Anwendungen übertragen.

Angetrieben durch die breite praktische Verwendung von Ordnungen wurden zahlreiche Sonderarten geordneter Mengen definiert, von denen einige zu eigenen mathematischen Gebieten angewachsen sind. Darüber hinaus beschränkt sich die Ordnungstheorie nicht auf die verschiedenen Klassen von Ordnungsrelationen, sondern betrachtet auch entsprechende Funktionen zwischen ihnen. Ein einfaches Beispiel für eine ordnungstheoretische Eigenschaft für Funktionen stammt aus der Analysis, wo häufig monotone Funktionen gefunden werden.

Grundlegende Definitionen

In diesem Abschnitt werden geordnete Mengen eingeführt, indem auf den Konzepten der Mengentheorie , der Arithmetik und der binären Beziehungen aufgebaut wird .

Teilweise bestellte Sets

Aufträge sind spezielle binäre Beziehungen. Angenommen, P ist eine Menge und ≤ ist eine Relation auf P (»Relation auf einer Menge« bedeutet »Relation zwischen ihren Bewohnern«). Dann ist ≤ eine partielle Ordnung, wenn es reflexiv , antisymmetrisch und transitiv ist , d. h. wenn für alle a , b und c in P gilt:

a ≤ a (Reflexivität)
wenn a ≤ b und b ≤ a dann a = b (Antisymmetrie)
wenn ein ≤ b und b ≤ c dann a ≤ c (Transitivität).

Eine Menge mit einer teilweisen Ordnung wird als teilweise geordnete Menge , Poset oder einfach geordnete Menge bezeichnet, wenn die beabsichtigte Bedeutung klar ist. Wenn man diese Eigenschaften überprüft, sieht man sofort, dass die bekannten Ordnungen auf natürlichen Zahlen , ganzen Zahlen , rationalen Zahlen und reellen Zahlen alle Ordnungen im obigen Sinne sind. Diese Beispiele haben jedoch die zusätzliche Eigenschaft, dass zwei beliebige Elemente vergleichbar sind, d. h. für alle a und b in P gilt:

a ≤ b oder b ≤ a .

Eine Teilordnung mit dieser Eigenschaft wird als Gesamtordnung bezeichnet . Diese Ordnungen können auch als lineare Ordnungen oder Ketten bezeichnet werden . Während viele bekannte Ordnungen linear sind, liefert die Teilmengenordnung auf Mengen ein Beispiel, wo dies nicht der Fall ist. Ein weiteres Beispiel ist die Teilbarkeits- (oder "ist-ein- Faktor- von")-Relation |. Für zwei natürliche Zahlen n und m schreiben wir n | m wenn n m ohne Rest teilt . Man sieht leicht, dass dies eine Teilordnung ergibt. Die Identitätsrelation = auf jeder Menge ist auch eine Teilordnung, in der jeweils zwei verschiedene Elemente unvergleichbar sind. Es ist auch die einzige Relation, die sowohl eine Teilordnungs- als auch eine Äquivalenzrelation ist . Viele fortgeschrittene Eigenschaften von Posets sind vor allem für nichtlineare Ordnungen interessant.

Ein Poset visualisieren

Hasse-Diagramm der Menge aller Teiler von 60, teilweise geordnet nach Teilbarkeit

Hasse-Diagramme können die Elemente und Beziehungen einer Teilordnung visuell darstellen. Dies sind Diagrammzeichnungen, bei denen die Scheitelpunkte die Elemente des Poset sind und die Anordnungsbeziehung sowohl durch die Kanten als auch durch die relative Positionierung der Scheitelpunkte angezeigt wird . Ordnungen werden von unten nach oben gezeichnet: Wenn ein Element x kleiner als (vor) y ist, dann existiert ein nach oben gerichteter Pfad von x nach y . Es ist oft erforderlich, dass sich die Kanten verbindenden Elemente kreuzen, aber Elemente dürfen sich niemals innerhalb einer Kante befinden. Eine lehrreiche Übung besteht darin, das Hasse-Diagramm für die Menge der natürlichen Zahlen, die kleiner oder gleich 13 sind, geordnet nach | . zu zeichnen (das teilte Verhältnis).

Sogar einige unendliche Mengen können grafisch dargestellt werden, indem man eine Ellipse (...) auf eine endliche Unterordnung legt . Dies funktioniert gut für die natürlichen Zahlen, aber es schlägt fehl für die reellen Zahlen, wo es keinen unmittelbaren Nachfolger über 0 gibt; jedoch kann man sehr oft eine Intuition in Bezug auf Diagramme ähnlicher Art erhalten.

Besondere Elemente innerhalb einer Bestellung

In einer teilweise geordneten Menge können einige Elemente eine besondere Rolle spielen. Das einfachste Beispiel ist das kleinste Element eines Poset . Zum Beispiel ist 1 das kleinste Element der positiven ganzen Zahlen und die leere Menge ist die kleinste Menge unter der Teilmengenordnung. Formal ist ein Element m ein kleinstes Element, wenn:

m ≤ a , für alle Elemente a der Ordnung.

Die Notation 0 wird häufig für das kleinste Element gefunden, auch wenn keine Zahlen betroffen sind. In Zahlenreihenfolgen kann diese Notation jedoch unangemessen oder mehrdeutig sein, da die Zahl 0 nicht immer die kleinste ist. Ein Beispiel ist die obige Teilbarkeitsordnung |, wobei 1 das kleinste Element ist, da es alle anderen Zahlen teilt. Im Gegensatz dazu ist 0 die Zahl, die durch alle anderen Zahlen geteilt wird. Daher ist es das größte Element der Ordnung. Andere häufige Begriffe für die kleinsten und größten Elemente sind unten und oben oder Null und Einheit .

Kleinste und größte Elemente können ausbleiben, wie das Beispiel der reellen Zahlen zeigt. Aber wenn sie existieren, sind sie immer einzigartig. Betrachten Sie dagegen die Teilbarkeitsrelation | am Satz {2,3,4,5,6}. Obwohl diese Menge weder oben noch unten hat, haben die Elemente 2, 3 und 5 keine Elemente darunter, während 4, 5 und 6 keine darüber haben. Solche Elemente werden als minimal bzw. maximal bezeichnet. Formal ein Element m ist minimal , wenn:

a ≤ m impliziert a = m , für alle Elemente a der Ordnung.

Der Austausch von ≤ mit ≥ ergibt die Definition der Maximalität . Wie das Beispiel zeigt, kann es viele maximale Elemente geben und einige Elemente können sowohl maximal als auch minimal sein (zB 5 oben). Wenn es jedoch ein kleinstes Element gibt, ist es das einzige minimale Element der Reihenfolge. Auch hier gibt es in unendlichen Posets nicht immer maximale Elemente - die Menge aller endlichen Teilmengen einer gegebenen unendlichen Menge, geordnet nach Teilmengen-Inklusion, liefert eines von vielen Gegenbeispielen. Ein wichtiges Werkzeug, um die Existenz maximaler Elemente unter bestimmten Bedingungen sicherzustellen, ist das Lemma von Zorn .

Teilmengen von teilweise geordneten Mengen erben die Reihenfolge. Wir haben dies bereits angewendet, indem wir die Teilmenge {2,3,4,5,6} der natürlichen Zahlen mit der induzierten Teilbarkeitsordnung betrachtet haben. Nun gibt es auch Elemente eines Poset, die in Bezug auf eine Teilmenge des Ordens speziell sind. Dies führt zur Definition von Obergrenzen . Gegeben eine Teilmenge S eines Posets P ist eine obere Schranke von S ein Element b von P , das über allen Elementen von S liegt . Formal bedeutet dies, dass

s ≤ b , für alle s in S .

Untere Schranken werden wiederum durch Umkehren der Reihenfolge definiert. Beispielsweise ist -5 eine untere Grenze der natürlichen Zahlen als Teilmenge der ganzen Zahlen. Bei einer gegebenen Menge von Mengen ist eine obere Schranke für diese Mengen unter der Teilmengenordnung durch ihre Vereinigung gegeben . Tatsächlich ist diese obere Schranke etwas ganz Besonderes: Sie ist die kleinste Menge, die alle Mengen enthält. Damit haben wir die kleinste obere Schranke einer Menge von Mengen gefunden. Dieses Konzept wird auch Supremum oder Join genannt , und für eine Menge S schreibt man sup( S ) oder für ihre kleinste obere Schranke. Umgekehrt ist die größte untere Schranke als Infimum oder Meet bekannt und wird mit inf( S ) oder bezeichnet . Diese Konzepte spielen in vielen Anwendungen der Ordnungstheorie eine wichtige Rolle. Für zwei Elemente x und y schreibt man auch und für sup({ x , y }) bzw. inf({ x , y }).

1 ist beispielsweise das Infimum der positiven ganzen Zahlen als Teilmenge der ganzen Zahlen.

Betrachten Sie für ein weiteres Beispiel noch einmal die Beziehung | auf natürlichen Zahlen. Die kleinste obere Schranke zweier Zahlen ist die kleinste Zahl, die durch beide geteilt wird, dh das kleinste gemeinsame Vielfache der Zahlen. Größte untere Schranken wiederum werden durch den größten gemeinsamen Teiler gegeben .

Dualität

In den vorherigen Definitionen haben wir oft bemerkt, dass ein Konzept definiert werden kann, indem man einfach die Reihenfolge in einer früheren Definition umkehrt. Dies ist der Fall für "kleinste" und "größte", für "minimal" und "maximal", für "obere Grenze" und "untere Grenze" und so weiter. Dies ist eine allgemeine Situation in der Ordnungstheorie: Eine gegebene Ordnung kann invertiert werden, indem man einfach ihre Richtung ändert, indem man das Hasse-Diagramm bildhaft von oben nach unten dreht. Dies ergibt die sogenannte duale , inverse oder entgegengesetzte Ordnung .

Jede ordnungstheoretische Definition hat ihr Duales: Es ist der Begriff, den man erhält, wenn man die Definition auf die inverse Ordnung anwendet. Da alle Konzepte symmetrisch sind, bewahrt diese Operation die Theoreme der Teilordnungen. Für ein gegebenes mathematisches Ergebnis kann man einfach die Reihenfolge umkehren und alle Definitionen durch ihre Dualen ersetzen und man erhält einen anderen gültigen Satz. Dies ist wichtig und nützlich, da man zwei Sätze zum Preis von einem erhält. Einige weitere Details und Beispiele finden sich im Artikel zur Dualität in der Ordnungstheorie .

Aufbau neuer Aufträge

Es gibt viele Möglichkeiten, Aufträge aus gegebenen Aufträgen zu konstruieren. Die duale Ordnung ist ein Beispiel. Eine weitere wichtige Konstruktion ist das kartesische Produkt zweier teilgeordneter Mengen, zusammen mit der Produktreihenfolge auf Elementpaaren. Die Reihenfolge wird durch (definiert ein , x ) ≤ ( b , y ) , wenn (und nur wenn) ein ≤ b und x ≤ y . (Beachten Sie sorgfältig, dass das Relationssymbol ≤ in dieser Definition drei verschiedene Bedeutungen hat.) Die disjunkte Vereinigung zweier Posets ist ein weiteres typisches Beispiel für die Konstruktion von Ordnungen, bei der die Ordnung nur die (disjunkte) Vereinigung der ursprünglichen Ordnungen ist.

Jede partielle Ordnung ≤ ergibt sich eine so genannte strenge Ordnung <, durch Definieren eines < b , wenn a ≤ b und nicht b ≤ ein . Diese Transformation kann invertiert werden, indem a ≤ b gesetzt wird, falls a < b oder a = b . Die beiden Konzepte sind gleichwertig, obwohl unter bestimmten Umständen das eine bequemer zu handhaben ist als das andere.

Funktionen zwischen Aufträgen

Es ist sinnvoll, Funktionen zwischen teilgeordneten Mengen mit bestimmten zusätzlichen Eigenschaften zu betrachten, die sich auf die Ordnungsbeziehungen der beiden Mengen beziehen. Die grundlegendste Bedingung, die in diesem Zusammenhang auftritt, ist Monotonie . Eine Funktion f von einem poset P auf einen poset Q ist monotone oder ordnungserhaltend , wenn a ≤ b in P bedeutet f ( ein ) ≤ f ( b ) in Q (die Kenntnis nehmend, streng die beiden Beziehungen sind hier verschiedene seit sie gelten für verschiedene Sets.). Die Umkehrung dieser Implikation führt zu Funktionen, die Reihenfolge reflektierendes , dh Funktionen f , wie oben für die f ( a ) ≤ f ( b ) bedeutet , ein ≤ b . Auf der anderen Seite kann eine Funktion auch sein , um umkehr oder antitone , wenn a ≤ b bedeutet f ( ein ) ≥ f ( b ).

Eine Ordnungseinbettung ist eine Funktion f zwischen Ordnungen, die sowohl ordnungserhaltend als auch ordnungsreflektierend ist. Beispiele für diese Definitionen sind leicht zu finden. Zum Beispiel ist die Funktion, die eine natürliche Zahl auf ihren Nachfolger abbildet, in Bezug auf die natürliche Ordnung eindeutig monoton. Jede Funktion aus einer diskreten Ordnung, dh aus einer nach der Identitätsordnung "=" geordneten Menge, ist ebenfalls monoton. Die Abbildung jeder natürlichen Zahl auf die entsprechende reelle Zahl liefert ein Beispiel für eine Einbettung einer Ordnung. Das Set - Komplement auf einem Powerset ist ein Beispiel für eine Funktion antitone.

Eine wichtige Frage ist, wann zwei Ordnungen "im Wesentlichen gleich" sind, dh wenn sie bis hin zur Umbenennung von Elementen gleich sind. Ordnungsisomorphismen sind Funktionen, die eine solche Umbenennung definieren. Ein Ordnungsisomorphismus ist eine monotone bijektive Funktion, die eine monotone Inverse hat. Dies entspricht einer surjektiven Ordnungseinbettung. Daher ist das Bild f ( P ) einer Ordnungseinbettung immer isomorph zu P , was den Begriff "Einbettung" rechtfertigt.

Eine aufwendigere Art von Funktionen bieten sogenannte Galois-Verbindungen . Monotone Galois-Verbindungen können als Verallgemeinerung von Ordnungsisomorphismen angesehen werden, da sie aus einem Paar zweier Funktionen in umgekehrter Richtung bestehen, die "nicht ganz" invers zueinander sind, aber dennoch enge Beziehungen haben.

Eine weitere spezielle Art von Selbstabbildungen auf einem Poset sind Abschlussoperatoren , die nicht nur monoton, sondern auch idempotent sind , dh f ( x ) = f ( f ( x )), und extensiv (oder inflationär ), dh x ≤ f ( x ). Diese haben viele Anwendungen in allen Arten von "Verschlüssen", die in der Mathematik vorkommen.

Neben der Kompatibilität mit den bloßen Ordnungsbeziehungen können sich Funktionen zwischen Posets auch in Bezug auf spezielle Elemente und Konstruktionen gut verhalten. Wenn man zum Beispiel über Posets mit dem kleinsten Element spricht, kann es sinnvoll erscheinen, nur monotone Funktionen zu betrachten, die dieses Element beibehalten, dh die kleinste Elemente auf die kleinsten Elemente abbilden. Wenn binäre infima ∧ existiert, dann könnte eine vernünftige Eigenschaft sein, dass erfordern f ( x ∧ y ) = f ( x ) ∧ f ( y ) für alle x und y . Alle diese Eigenschaften und noch viele mehr können unter dem Etikett grenzerhaltende Funktionen zusammengefasst werden .

Schließlich kann man die Ansicht umkehren, indem man von Funktionen von Ordnungen zu Ordnungen von Funktionen wechselt . Tatsächlich können die Funktionen zwischen zwei Posets P und Q über die punktweise Ordnung geordnet werden . Für zwei Funktionen f und g , haben wir f ≤ g , wenn f ( x ) ≤ g ( x ) für alle Elemente x von P . Dies tritt beispielsweise in der Domänentheorie auf , wo Funktionsräume eine wichtige Rolle spielen.

Besondere Auftragsarten

Viele der in der Ordnungstheorie untersuchten Strukturen verwenden Ordnungsbeziehungen mit weiteren Eigenschaften. Tatsächlich sind sogar einige Beziehungen, die keine Teilaufträge sind, von besonderem Interesse. Hauptsächlich ist das Konzept einer Vorbestellung zu erwähnen. Eine Vorordnung ist eine Relation, die reflexiv und transitiv ist, aber nicht unbedingt antisymmetrisch. Jeder preorder induziert eine Äquivalenzbeziehung zwischen den Elementen, in denen ein äquivalent sind b , wenn a ≤ b und b ≤ a . Vorbestellungen können in Bestellungen umgewandelt werden, indem alle Elemente identifiziert werden, die in Bezug auf diese Beziehung äquivalent sind.

Aus numerischen Daten zu den Artikeln der Bestellung können mehrere Arten von Bestellungen definiert werden: Eine Gesamtbestellung ergibt sich aus dem Anhängen verschiedener reeller Zahlen an jeden Artikel und der Verwendung der numerischen Vergleiche zum Bestellen der Artikel; stattdessen erhält man eine strenge schwache Ordnung , wenn verschiedene Items gleiche numerische Scores haben dürfen . Das Erfordernis, dass zwei Bewertungen durch einen festen Schwellenwert getrennt werden, bevor sie verglichen werden können, führt zu dem Konzept einer Halbordnung , während erlaubt wird, dass der Schwellenwert auf einer Pro-Item-Basis variiert, eine Intervallreihenfolge erzeugt wird .

Eine zusätzliche einfache, aber nützliche Eigenschaft führt zu sogenannten wohlfundierten , für die alle nicht leeren Teilmengen ein minimales Element haben. Verallgemeinert man wohlgeordnete Ordnungen von linearen zu partiellen Ordnungen, so ist eine Menge gut partiell geordnet, wenn alle ihre nichtleeren Teilmengen eine endliche Anzahl minimaler Elemente haben.

Viele andere Arten von Aufträgen entstehen, wenn die Existenz von Infima und Suprema bestimmter Mengen garantiert ist. Konzentriert man sich auf diesen Aspekt, der üblicherweise als Vollständigkeit von Aufträgen bezeichnet wird, erhält man:

Man kann jedoch noch weiter gehen: Existieren alle endlichen nichtleeren Infima, dann kann ∧ als totale binäre Operation im Sinne der universellen Algebra angesehen werden . Somit stehen in einem Gitter zwei Operationen ∧ und ∨ zur Verfügung, und man kann neue Eigenschaften definieren, indem man Identitäten wie

x  ∧ ( y  ∨  z ) = ( x  ∧  y ) ∨ ( x  ∧  z ) für alle x , y , und z .

Diese Bedingung wird als Distributivität bezeichnet und führt zu Verteilungsgittern . Es gibt noch einige andere wichtige Distributivitätsgesetze, die im Artikel über Distributivität in der Ordnungstheorie diskutiert werden . Einige zusätzliche Ordnungsstrukturen, die oft über algebraische Operationen spezifiziert werden und Identitäten definieren, sind

die beide eine neue Operation ~ namens Negation einführen . Beide Strukturen spielen in der mathematischen Logik eine Rolle und insbesondere Boolesche Algebren haben große Anwendungen in der Informatik . Schließlich kombinieren verschiedene Strukturen in der Mathematik Ordnungen mit noch mehr algebraischen Operationen, wie im Fall von Quantalen , die die Definition einer Additionsoperation ermöglichen.

Viele andere wichtige Eigenschaften von Posen existieren. Zum Beispiel ist ein Poset lokal endlich, wenn jedes abgeschlossene Intervall [ a , b ] darin endlich ist . Lokal endliche Posets führen zu Inzidenzalgebren, die wiederum verwendet werden können, um die Euler-Charakteristik endlicher beschränkter Posets zu definieren .

Teilmengen geordneter Mengen

In einer geordneten Menge kann man basierend auf der gegebenen Reihenfolge viele Arten von speziellen Teilmengen definieren. Ein einfaches Beispiel sind obere Mengen ; dh Mengen, die alle Elemente enthalten, die in der Reihenfolge über ihnen stehen. Formal ist der obere Abschluss einer Menge S in einem Poset P gegeben durch die Menge { x in P | es gibt ein y in S mit y ≤ x }. Eine Menge, die ihrem oberen Abschluss gleich ist, wird obere Menge genannt. Untere Sätze werden dual definiert.

Kompliziertere untere Teilmengen sind Ideale , die die zusätzliche Eigenschaft haben, dass jeweils zwei ihrer Elemente eine obere Schranke innerhalb des Ideals haben. Ihre Duals werden durch Filter gegeben . Ein verwandtes Konzept ist das einer gerichteten Teilmenge , die wie ein Ideal obere Schranken endlicher Teilmengen enthält, aber keine untere Menge sein muss. Darüber hinaus wird es oft auf vorbestellte Sets verallgemeinert.

Eine Teilmenge, die – als Teilmenge – linear geordnet ist, wird Kette genannt . Der entgegengesetzte Begriff, die Antikette , ist eine Teilmenge, die keine zwei vergleichbaren Elemente enthält; dh das ist eine diskrete Ordnung.

Verwandte mathematische Gebiete

Obwohl die meisten mathematischen Bereichen verwenden Aufträge in die eine oder andere Art und Weise gibt es auch einige Theorien , die Beziehungen haben , die weit über die reine Anwendung gehen. Zusammen mit ihren wesentlichen Berührungspunkten mit der Ordnungstheorie sollen im Folgenden einige davon vorgestellt werden.

Universelle Algebra

Wie bereits erwähnt, sind die Methoden und Formalismen der universellen Algebra ein wichtiges Werkzeug für viele ordnungstheoretische Betrachtungen. Neben der Formalisierung von Ordnungen durch algebraische Strukturen , die bestimmten Identitäten genügen, kann man auch andere Verbindungen zur Algebra herstellen. Ein Beispiel ist die Korrespondenz zwischen Booleschen Algebren und Booleschen Ringen . Andere Probleme befassen sich mit der Existenz freier Konstruktionen , wie beispielsweise freier Gitter basierend auf einem gegebenen Satz von Generatoren. Darüber hinaus sind Abschlussoperatoren für das Studium der universellen Algebra wichtig.

Topologie

In der Topologie spielen Ordnungen eine sehr herausragende Rolle. Tatsächlich liefert die Sammlung offener Mengen ein klassisches Beispiel für ein vollständiges Gitter, genauer gesagt eine vollständige Heyting-Algebra (oder „ Rahmen “ oder „ Gebietsschema “). Filter und Netze sind Begriffe, die eng mit der Ordnungstheorie verbunden sind, und der Abschlussoperator von Mengen kann verwendet werden, um eine Topologie zu definieren. Über diese Beziehungen hinaus kann die Topologie ausschließlich im Hinblick auf die Gitter der offenen Menge betrachtet werden, was zum Studium der sinnlosen Topologie führt . Darüber hinaus ist eine natürliche Vorordnung von Elementen der zugrunde liegenden Menge einer Topologie durch die sogenannte Spezialisierungsordnung gegeben , dh tatsächlich eine Teilordnung, wenn die Topologie T 0 ist .

Umgekehrt verwendet man in der Ordnungstheorie oft topologische Ergebnisse. Es gibt verschiedene Möglichkeiten, Teilmengen einer Ordnung zu definieren, die als offene Mengen einer Topologie angesehen werden können. Betrachtet man Topologien auf einem Poset ( X , ≤), die wiederum ≤ als ihre Spezialisierungsordnung induzieren, ist die feinste derartige Topologie die Alexandrov-Topologie , die gegeben ist, indem alle oberen Mengen als offen genommen werden. Umgekehrt ist die gröbste ist Topologie , die induziert die Spezialisierung um die obere Topologie , die Komplemente der mit Haupt Ideale (dh Mengen der Form { y in X | y ≤ x } für einige x ) als eine Sauberkeitsschicht . Zusätzlich kann eine Topologie mit Spezialisierung Ordnung ≤ sein , um konsistente , was bedeutet , dass ihre offenen Mengen „unzugänglich durch gezielte suprema“ sind (in Bezug auf ≤). Die konsistente Topologie feinster Ordnung ist die Scott-Topologie , die gröber als die Alexandrov-Topologie ist. Eine dritte wichtige Topologie in diesem Sinne ist die Lawson-Topologie . Zwischen diesen Topologien und den Konzepten der Ordnungstheorie bestehen enge Verbindungen. Zum Beispiel behält eine Funktion gerichtete Suprema genau dann bei, wenn sie bezüglich der Scott-Topologie stetig ist (aus diesem Grund wird diese ordnungstheoretische Eigenschaft auch Scott-Stetigkeit genannt ).

Kategorientheorie

Die Visualisierung von Ordnungen mit Hasse-Diagrammen hat eine einfache Verallgemeinerung: Anstatt kleinere Elemente unter größeren anzuzeigen , kann die Richtung der Ordnung auch durch Richtungsangaben zu den Kanten eines Graphen dargestellt werden. Auf diese Weise wird jede Ordnung als äquivalent zu einem gerichteten azyklischen Graphen angesehen , in dem die Knoten die Elemente des Poset sind und es einen gerichteten Weg von a nach b genau dann gibt, wenn a ≤ b . Wenn man die Anforderung, azyklisch zu sein, fallen lässt, kann man auch alle Vorbestellungen erhalten.

Ausgestattet mit allen transitiven Kanten sind diese Graphen wiederum nur spezielle Kategorien , in denen Elemente Objekte sind und jede Menge von Morphismen zwischen zwei Elementen höchstens Singleton ist. Funktionen zwischen Aufträgen werden zu Funktoren zwischen Kategorien. Viele Ideen der Ordnungstheorie sind nur Konzepte der Kategorientheorie im Kleinen. Ein Infimum ist beispielsweise nur ein kategoriales Produkt . Allgemeiner kann man Infima und Suprema unter dem abstrakten Begriff einer kategorialen Grenze (bzw. colimit ) erfassen . Ein anderer Ort, an dem kategoriale Ideen vorkommen, ist das Konzept einer (monotonen) Galois-Verbindung , die genau das gleiche wie ein Paar adjungierter Funktoren ist .

Aber auch die Kategorientheorie hat ihren Einfluss auf die Ordnungstheorie in größerem Maßstab. Klassen von Posets mit entsprechenden Funktionen, wie oben diskutiert, bilden interessante Kategorien. Oftmals kann man auch Auftragskonstruktionen, wie die Produktbestellung , in Kategorien angeben. Weitere Einsichten ergeben sich, wenn Kategorien von Ordnungen kategorisch äquivalent zu anderen Kategorien, beispielsweise von topologischen Räumen, gefunden werden. Diese Forschungsrichtung führt zu verschiedenen Darstellungssätzen , die oft unter dem Label der Steindualität zusammengefasst werden .

Geschichte

Wie bereits erwähnt, sind Ordnungen in der Mathematik allgegenwärtig. Früheste explizite Erwähnungen von Teilordnungen dürften jedoch erst im 19. Jahrhundert zu finden sein. In diesem Zusammenhang sind die Arbeiten von George Boole von großer Bedeutung. Auch Arbeiten von Charles Sanders Peirce , Richard Dedekind und Ernst Schröder berücksichtigen ordnungstheoretische Konzepte.

Beiträge zur geordneten Geometrie wurden in einem Lehrbuch von 1961 aufgeführt :

Es war Pasch , der 1882 als erster darauf hinwies, dass eine Ordnungsgeometrie ohne Bezug auf das Messen entwickelt werden kann. Sein Axiomensystem wurde nach und nach von Peano (1889), Hilbert (1899) und Veblen (1904) verbessert .

—  HSM Coxeter , Einführung in die Geometrie

Im Jahr 1901 schrieb Bertrand Russell "Über den Begriff der Ordnung" und untersuchte die Grundlagen der Idee durch die Generierung von Serien . Er kehrte in Teil IV von The Principles of Mathematics (1903) auf das Thema zurück . Russell bemerkte, dass die binäre Beziehung aRb einen Sinn hat, der von a nach b geht, wobei die umgekehrte Beziehung einen entgegengesetzten Sinn hat, und der Sinn "die Quelle von Ordnung und Reihe ist". (S. 95) Er erkennt an, dass Immanuel Kant "sich des Unterschieds zwischen dem logischen Gegensatz und dem Gegensatz von Positiv und Negativ bewusst war". Er schrieb, dass Kant Anerkennung gebührt, da er "zum ersten Mal auf die logische Bedeutung asymmetrischer Beziehungen aufmerksam gemacht hat".

Der Begriff Poset als Abkürzung für teilweise geordnete Menge wurde von Garrett Birkhoff in der zweiten Auflage seines einflussreichen Buches Lattice Theory geprägt .

Siehe auch

Anmerkungen

Verweise

Externe Links