Auftragsbeziehung. Bestellte Sets

Das Wort „Ordnung“ wird häufig in den unterschiedlichsten Sachverhalten verwendet. Der Offizier gibt den Befehl: „Rechne in numerischer Reihenfolge“, Rechenoperationen werden in einer bestimmten Reihenfolge ausgeführt, Sportler werden nach ihrer Größe eingestuft, alle führenden Schachspieler werden in einer bestimmten Reihenfolge nach den sogenannten Elo-Koeffizienten (amerikanischer Professor) geordnet Wer hat das Koeffizientensystem entwickelt, das es ermöglicht, alle Erfolge und Misserfolge der Spieler zu berücksichtigen), nach der Meisterschaft sind alle Fußballmannschaften in einer bestimmten Reihenfolge angeordnet usw. Bei der Herstellung eines Teils gibt es eine Reihenfolge der Vorgänge, die Reihenfolge der Wörter in einem Satz (versuchen Sie zu verstehen, was der Satz „Auf dem alten Mann“ bedeutet, dass ich den Esel nicht gepflanzt habe!“

Indem wir die Elemente einer bestimmten Menge nacheinander anordnen, ordnen wir sie oder stellen eine Beziehung zwischen ihnen her in Ordnung. Das einfachste Beispiel ist die natürliche Ordnung der natürlichen Zahlen. Ihre Natürlichkeit liegt darin, dass wir für zwei beliebige natürliche Zahlen wissen, welche auf die andere folgt oder welche größer als die andere ist, sodass wir die natürlichen Zahlen in einer Reihenfolge anordnen können, in der sich die größere Zahl beispielsweise in befindet rechts vom kleineren: 1, 2, 3, ... . Natürlich kann die Reihenfolge der Elemente in jede Richtung geschrieben werden, nicht nur von links nach rechts. Der Begriff der natürlichen Zahlen enthält bereits die Idee der Ordnung. Indem wir eine relative Anordnung der Elemente einer beliebigen Menge festlegen, definieren wir darauf eine binäre Ordnungsbeziehung, die in jedem konkreten Fall einen eigenen Namen haben kann, zum Beispiel „weniger sein“, „älter sein“, „bis“. in „, „folgen“ usw. enthalten sein. Auch symbolische Ordnungsbezeichnungen können variiert werden, zum Beispiel Í usw.

Das Hauptunterscheidungsmerkmal einer Ordnungsrelation besteht darin, dass sie die Eigenschaft der Transitivität besitzt. Wenn wir es also mit einer Folge einiger Objekte zu tun haben x 1, x 2, ..., x n,..., geordnet zum Beispiel nach Relation, dann nach dem, was ausgeführt wird x 1x 2... x n..., das sollte für jedes Paar gelten x i, x j Elemente dieser Sequenz sind ebenfalls erfüllt x ix j:

Für ein Elementpaar x iJ Im Beziehungsgraphen zeichnen wir einen Pfeil vom Scheitelpunkt x i Zum Seitenanfang x j, also vom kleineren zum größeren Element.

Der Ordnungsbeziehungsgraph kann durch die Verwendung der sogenannten Methode vereinfacht werden Hasse-Diagramme. Das Hasse-Diagramm ist wie folgt aufgebaut. Kleinere Elemente werden tiefer platziert, größere höher. Da eine solche Regel allein zur Darstellung nicht ausreicht, werden Linien gezeichnet, die zeigen, welches der beiden Elemente größer und welches kleiner als das andere ist. In diesem Fall reicht es aus, nur Linien für die unmittelbar aufeinander folgenden Elemente zu zeichnen. Beispiele für Hasse-Diagramme sind in der Abbildung dargestellt:

Sie müssen keine Pfeile in ein Hasse-Diagramm einfügen. Das Hasse-Diagramm kann in einer Ebene gedreht werden, jedoch nicht beliebig. Beim Drehen ist es notwendig, die relative Position (oben - unten) der Eckpunkte des Diagramms beizubehalten:

Attitüde R in Hülle und Fülle X angerufen Haltung strenger Ordnung, wenn es transitiv und asymmetrisch ist.

Eine Menge, in der eine strenge Ordnungsrelation definiert ist, heißt bestellt. Beispielsweise wird die Menge der natürlichen Zahlen nach der Relation „kleiner als“ geordnet. Aber diese gleiche Menge wird auch durch eine andere Beziehung geordnet – „unterteilt in“ und „mehr“.

Der Graph der „Kleiner-als“-Beziehung in der Menge der natürlichen Zahlen kann als Strahl dargestellt werden:

Attitüde R V X sogenannte Relation nicht strikte (teilweise) Ordnung, wenn es transitiv und antisymmetrisch ist. Jede Beziehung nicht strenger Ordnung ist reflexiv.

Das Epitheton „partiell“ drückt die Tatsache aus, dass möglicherweise nicht alle Elemente einer Menge in einer bestimmten Hinsicht vergleichbar sind.

Typische Beispiele für partielle Ordnungsbeziehungen sind die Beziehungen „nicht größer als“, „nicht kleiner als“ und „nicht größer als“. Der Partikel „nicht“ in den Namen von Beziehungen dient dazu, deren Reflexivität auszudrücken. Die Relation „nicht mehr als“ fällt mit der Relation „kleiner als oder gleich“ zusammen, und die Relation „nicht weniger“ ist dasselbe wie „größer als oder gleich“. In diesem Zusammenhang spricht man auch von Teilordnung nicht streng in Ordnung. Oftmals wird eine partielle (nicht strenge) Ordnungsbeziehung mit dem Symbol „“ gekennzeichnet.

Die Inklusionsrelation Í zwischen Teilmengen einer bestimmten Menge ist ebenfalls eine Teilordnung. Offensichtlich sind in dieser Hinsicht nicht alle zwei Teilmengen vergleichbar. Die folgende Abbildung zeigt die Reihenfolge der teilweisen Einbeziehung aller Teilmengen der Menge (1,2,3) in die Menge. Die Pfeile im Diagramm, die nach oben zeigen sollten, werden nicht angezeigt.

Mengen, für die eine Teilordnung gegeben ist, werden aufgerufen teilweise geordnet, oder einfach bestellt Sätze.

Elemente X Und bei Die teilweise geordnete Menge wird aufgerufen Vergleichen Sie mit uns Wenn Xbei oder beiX. Ansonsten sind sie nicht vergleichbar.

Eine geordnete Menge, in der zwei beliebige Elemente vergleichbar sind, heißt linear geordnet, und die Ordnung ist lineare Ordnung. Die lineare Ordnung wird auch perfekte Ordnung genannt.

Beispielsweise sind die Menge aller reellen Zahlen mit natürlicher Ordnung sowie alle ihre Teilmengen linear geordnet.

Es können Objekte unterschiedlichster Art bestellt werden hierarchisch. Hier sind einige Beispiele.

Beispiel 1: Die Teile eines Buches sind so angeordnet, dass ein Buch Kapitel enthält, Kapitel Abschnitte enthalten und Abschnitte Unterabschnitte enthalten.

Beispiel 2. Ordner im Dateisystem des Computers sind ineinander verschachtelt und bilden eine verzweigte Struktur.

Beispiel 3. Die Beziehung zwischen Eltern und Kindern kann als sogenannte dargestellt werden Familienstammbaum, was zeigt, wer wessen Vorfahr (oder Nachkomme) ist.

Lass das Set an A Teilauftrag ist gegeben. Element X angerufen Maximum Minimum) Element der Menge A, wenn aus der Tatsache, dass Xbei(beiX), Gleichheit folgt X= u. Mit anderen Worten, das Element X ist für jedes Element das Maximum (Minimum). bei oder stimmt das nicht? Xbei(beiX) oder ausgeführt wird X=u. Somit ist das maximale (minimale) Element größer (kleiner) als alle von ihm verschiedenen Elemente, mit denen es in Beziehung steht.

Element X angerufen größte (kleinste), wenn für irgendjemanden beiÎ A durchgeführt bei< х (х< у).

Eine teilweise geordnete Menge kann mehrere minimale und/oder maximale Elemente haben, es kann jedoch nicht mehr als ein minimales und maximales Element geben. Das kleinste (größte) Element ist auch das Minimum (Maximum), aber das Gegenteil ist nicht der Fall. Die Abbildung links zeigt eine Teilordnung mit zwei minimalen und zwei maximalen Elementen, rechts eine Teilordnung mit den kleinsten und größten Elementen:

In einer endlichen teilweise geordneten Menge gibt es immer minimale und maximale Elemente.

Eine geordnete Menge mit den größten und kleinsten Elementen heißt begrenzt. Die Abbildung zeigt ein Beispiel für eine unendlich beschränkte Menge. Natürlich ist es unmöglich, eine unendliche Menge auf einer endlichen Seite darzustellen, aber Sie können das Prinzip ihrer Konstruktion zeigen. Zur Vereinfachung der Zeichnung sind hier die Schleifen in der Nähe der Scheitelpunkte nicht dargestellt. Aus dem gleichen Grund werden die Bögen, die die Transitivitätseigenschaft anzeigen, nicht angezeigt. Mit anderen Worten: Die Abbildung zeigt das Hasse-Diagramm der Ordnungsrelation.

Unendliche Mengen dürfen keine maximalen oder minimalen Elemente oder beides haben. Beispielsweise hat die Menge der natürlichen Zahlen (1,2, 3, ...) ein kleinstes Element von 1, aber kein Maximum. Die Menge aller reellen Zahlen natürlicher Ordnung hat weder ein kleinstes noch ein größtes Element. Allerdings besteht seine Teilmenge aus allen Zahlen X< 5 hat das größte Element (die Zahl 5), aber nicht das kleinste.

Vorlesungsplan Nr. 14 Klassifikation binärer Beziehungen

1. Klassifikation antisymmetrischer Beziehungen
2. Klassifikation reflexiver Beziehungen
2.1. Quasi-Ordnungsbeziehungen
2.2. Nicht strikte Teilordnungsbeziehungen
2.3. Nicht streng geordnete Beziehungen
2.4. Laxe Qualitätsbestellung
2.5. Laxe schwache Ordnung
2.6. Lose Reihenfolge
3. Dualität der Beziehungen strenger und nicht strenger Ordnung
4. Überprüfung der Eigenschaften verschiedener Arten von Beziehungen

Klassifikation antisymmetrischer Beziehungen

Struktur azyklischer Beziehungsgraphen

Struktur qualitativer Ordnungsbeziehungsgraphen

Struktur von Beziehungsgraphen schwacher Ordnung

Strenge Beziehungen

Eine strenge Ordnung (strenge Präferenz, starke Ordnung, strikte lineare Ordnung) ist eine antireflexive, transitive, schwach verbundene binäre Beziehung (12).

Die strikte Ordnung ist ein Sonderfall der schwachen Ordnung (strenge Teilpräferenz) mit der zusätzlichen Bedingung der schwachen Kopplung.

Beispiel: Die „streng kleiner als“-Relation für eine Menge von ganzen Zahlen.

Klassifikation reflexiver Beziehungen

Quasi-Ordnungsbeziehungen

Diese binären Beziehungen ermöglichen den Vergleich von Elementen einer bestimmten Menge, jedoch nicht durch Ähnlichkeit, sondern durch die Anordnung der Elemente von Gruppen in einer bestimmten Reihenfolge, d.h. durch Teilbestellung.

Eine Quasi-Ordnung (laxe Teilpräferenz) ist eine reflexive und transitive binäre Beziehung (3).

Beispiel: „ein Bruder sein“ (Ivan-Peter, Andrey-Anna)

Eigenschaften von Quasi-Ordnungen

1. Der Schnittpunkt von Quasi-Ordnungen bleibt eine Quasi-Ordnung.
2. Der symmetrische Teil der Quasi-Ordnung hat die Eigenschaften Reflexivität, Symmetrie und Transitivität und ist daher eine Äquivalenzrelation. R c = R / R inv
3. Mithilfe dieser Schnittmenge ist es möglich, Gruppen von Optionen zu identifizieren, die einander äquivalent sind. Anschließend kann eine nicht strenge Teilordnungsbeziehung, die durch die ursprüngliche Beziehung erzeugt wird, zwischen den ausgewählten Gruppen hergestellt werden.
4. Der asymmetrische Teil der Quasi-Ordnung ist eine transitive und antireflexive Relation = qualitative Ordnung.

Nicht strikte Teilordnungsbeziehungen

Eine nichtstrikte partielle Ordnungsrelation (4) ist eine Relation, die die Eigenschaften Reflexivität, Antisymmetrie und Transitivität aufweist.

Eine schwache Teilordnung ist eine antisymmetrische Quasiordnung

Beispiel: Die für Mengen (und ihre Teilmengen) definierte „Teil sein“-Relation

Eigenschaften nichtstrikter Teilordnungen

1. Der Schnittpunkt nicht strenger Teilordnungen bleibt eine nicht strenge Teilordnung.
2. Der symmetrische Teil einer nicht strengen Teilordnung ist eine Diagonale.
3. Der asymmetrische Teil einer nichtstrikten Teilordnung ist eine (strikte) qualitative Ordnung.
4. In der Theorie intelligenter Systeme spielen teilweise geordnete Mengen – Domänen – zusammen mit den auf ihnen definierten Beziehungen nicht strenger Teilordnung eine wichtige Rolle.
5. Teilweise geordnete Mengen mit der zusätzlichen Eigenschaft, dass für jedes Elementpaar Ober- und Untergrenzen existieren, werden Gitter genannt. Ein Sonderfall von Verbänden sind Boolesche Algebren.

Lose Ordnungsbeziehungen

Eine lose Ordnung ist eine reflexive Relation mit der schwach verbundenen Eigenschaft (5).

Eine lose Reihenfolge kann auch als vollständig zusammenhängende Beziehung definiert werden.

Ein lockeres Ordnungsverhältnis kann als Ergebnis der Kombination bestimmter Toleranz- und Dominanzverhältnisse dargestellt werden.

Eigenschaften von Beziehungen nichtstrikter Teilordnung

1. Der Schnittpunkt und die Vereinigung vollständig zusammenhängender Beziehungen bleibt eine vollständig zusammenhängende Beziehung.
2. Der symmetrische Teil der nicht strengen Teilordnung ist die Toleranz.
3. Der asymmetrische Teil der nicht strengen Teilordnung ist Dominanz.
4. Für vollständig zusammenhängende Beziehungen ist die Negativität der Beziehung eine notwendige Bedingung für Transitivität.
5. Für vollständig zusammenhängende Beziehungen ist die Eigenschaft der Transitivität eine hinreichende Bedingung für die Negativität der Beziehung.

Beziehungen nicht strenger qualitativer Ordnung

Eine binäre Relation R heißt nichtstrikte qualitative Ordnung, wenn sie negativ-transitiv und vollständig zusammenhängend ist (6).

Eine nicht strikte qualitative Ordnung ist eine negative, nicht strikte Ordnung.

Das Verhältnis einer nicht strengen qualitativen Ordnung kann als Ergebnis der Kombination einiger Beziehungen von Toleranz und qualitativer Ordnung dargestellt werden.

Eigenschaften von Beziehungen nicht strenger qualitativer Ordnung

1. Der symmetrische Teil der nicht strengen qualitativen Ordnung ist die Toleranz. NT?
2. Der asymmetrische Teil einer nicht strengen qualitativen Ordnung ist transitiv, also eine Relation einer qualitativen Ordnung.
3. Somit kann eine Relation einer nicht strengen qualitativen Ordnung als Ergebnis der Kombination der durch die ursprüngliche Relation erzeugten Toleranz- und qualitativen Ordnungsbeziehungen dargestellt werden.
4. Die duale Relation hat die Eigenschaften der Asymmetrie und Transitivität und ist daher eine Relation qualitativer Ordnung.

Nicht strikte Beziehungen schwacher Ordnung

Eine nichtstrikte schwache Ordnung ist eine vollständig zusammenhängende transitive und negative transitive Beziehung (7).

Eine vollständig zusammenhängende transitive Beziehung wird als nichtstrikte schwache Ordnung bezeichnet.

Eine nicht strikte schwache Ordnung ist eine transitive nicht strikte Ordnung.

Eigenschaften von Beziehungen nicht strenger schwacher Ordnung

1. Der symmetrische Teil einer nicht strengen schwachen Ordnung ist eine Äquivalenz.
2. Der asymmetrische Teil R ac einer nicht strengen schwachen Ordnung ist transitiv, also eine Relation qualitativer Ordnung.
3. Somit kann eine nicht strenge Relation schwacher Ordnung als Ergebnis der Kombination der Äquivalenz- und schwachen Relationen dargestellt werden, die durch die ursprüngliche Relation erzeugt wurden.
4. Eine nicht strikte schwache Ordnung kann als eine Menge teilweise geordneter Schichten dargestellt werden, von denen jede eine Äquivalenzklasse ist.

Beziehungen nichtstrikter (linearer) Ordnung

Eine nichtstrikte Ordnung (eine nichtstrikte lineare Ordnung) ist eine antisymmetrische, transitive, vollständig zusammenhängende binäre Beziehung (8).

Eine nichtstrikte Ordnung ist eine antisymmetrische, nichtstrikte schwache Ordnung.

Eine nicht strikte Ordnung ist eine antisymmetrische nicht strikte Ordnung.

Eigenschaften von Beziehungen nicht strenger linearer Ordnung

1. Der symmetrische Teil einer nicht strengen Ordnung ist eine Diagonale.
2. Der asymmetrische Teil R ac nicht strenger Ordnung ist transitiv und schwach zusammenhängend, daher handelt es sich um eine Relation strenger Ordnung.
3. Die duale Beziehung hat die Eigenschaften der Asymmetrie, der Negatransitivität und der schwachen Verbindung und ist daher eine Beziehung strenger Ordnung. Außerdem stimmt es mit R ac überein.
4. Somit kann eine nicht-strikte Ordnungsbeziehung als Ergebnis der Kombination der durch die ursprüngliche Beziehung erzeugten diagonalen und strengen Ordnung dargestellt werden.

Dualität der Beziehungen strenger und nicht strenger Ordnung

Übersicht über die Eigenschaften verschiedener Arten von Beziehungen

Das Wort „Ordnung“ wird häufig in verschiedenen Sachverhalten verwendet. Der Offizier gibt den Befehl: „Berechnen Sie nach der Reihenfolge der Zahlen“, arithmetische Operationen werden in einer bestimmten Reihenfolge ausgeführt, Athleten werden nach ihrer Größe eingestuft, es gibt eine Reihenfolge für die Durchführung von Operationen bei der Herstellung eines Teils und die Reihenfolge der Wörter in einem Satz.

Was ist in allen Fällen gemeinsam, wenn es um Ordnung geht? Tatsache ist, dass das Wort „Reihenfolge“ die folgende Bedeutung hat: Es bedeutet, welches Element einer gegebenen Menge welchem ​​folgt (oder welches Element welchem ​​vorausgeht).

Attitüde " X folgt bei„transitiv: wenn“ X folgt bei" Und " bei folgt z", Das " X folgt z" Außerdem muss diese Beziehung antisymmetrisch sein: für zwei verschiedene X Und bei, Wenn X folgt bei, Das bei folgt nicht X.

Definition. Attitüde R auf einem Set X angerufen Beziehung einer strengen Ordnung, wenn es transitiv und antisymmetrisch ist.

Lassen Sie uns die Merkmale des Graphen und des Graphen der Beziehungen strenger Ordnung herausfinden.

Schauen wir uns ein Beispiel an. Am Set X= (5, 7, 10, 15, 12) gegebenes Verhältnis R: « X < bei" Definieren wir diese Beziehung, indem wir die Paare auflisten
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Lassen Sie uns sein Diagramm erstellen. Wir sehen, dass der Graph dieser Beziehung keine Schleifen hat. In der Grafik sind keine Doppelpfeile zu sehen. Wenn von X Der Pfeil geht zu bei, und von bei- V z, dann von X Der Pfeil geht zu z(Abb. 8).

Mit dem konstruierten Diagramm können Sie die Elemente der Menge anordnen X in dieser Reihenfolge:

{5, 7, 10, 12, 15}.

In Abb. 6 (§ 6 dieses Kapitels) sind die Spalten VII, VIII Diagramme von Beziehungen strenger Ordnung.

Nicht strikte Beziehung

Das Gegenteil der Relation „kleiner als“ in der Menge der reellen Zahlen ist die Relation „nicht weniger“. Es handelt sich nicht mehr um ein streng geordnetes Verhältnis. Der Punkt ist, wann X = bei, Beziehungen sind erfüllt X ³ bei Und bei ³ X, d.h. Die „nicht weniger“-Haltung ist reflexiv.

Definition. Attitüde R auf einem Set X angerufen nicht strikte Beziehung, wenn es reflexiv, antisymmetrisch und transitiv ist.

Solche Relationen sind Vereinigungen einer strengen Ordnungsrelation mit einer Identitätsrelation.

Betrachten Sie die Relation „nicht mehr“ (£) für die Menge

X= (5, 7, 10, 15, 12). Lassen Sie uns sein Diagramm erstellen (Abb. 9).

Ein Beziehungsgraph nicht strikter Ordnung hat im Gegensatz zu einem Beziehungsgraphen strikter Ordnung Schleifen an jedem Scheitelpunkt.

In Abb. 6 (§ 6 dieses Kapitels) Spalten V, VI sind Diagramme von Beziehungen nicht strenger Ordnung.

Bestellte Sets

Eine Menge kann aufgrund einer Ordnungsrelation geordnet (man sagt auch vollständig geordnet) sein, während eine andere Menge aufgrund einer solchen Beziehung ungeordnet oder teilweise geordnet sein kann.

Definition. Ein Haufen X angerufen bestellt eine Ordnungsbeziehung R, wenn für zwei beliebige Elemente x, y aus X:

(X, bei) Î R oder ( y, x) Î R.

Wenn R eine Relation strenger Ordnung ist, dann die Menge X geordnet nach dieser Beziehung vorausgesetzt: if X, bei zwei beliebige ungleiche Elemente der Menge X, Das ( X, bei) Î R oder ( y, x) Î R oder zwei beliebige Elemente x, y Sätze X sind gleich.

Aus dem Schulmathematikunterricht ist bekannt, dass Zahlenmengen vorliegen N , Z , Q , R geordnet nach der Relation „kleiner als“ (<).

Die Menge der Teilmengen einer bestimmten Menge wird nicht durch Einführung der Inklusionsrelation (I) oder der strikten Inklusion (S) im obigen Sinne geordnet, weil Es gibt Teilmengen, von denen keine in der anderen enthalten ist. In diesem Fall sagen wir, dass die gegebene Menge teilweise durch die Relation Í (oder Ì) geordnet ist.

Betrachten Sie das Set X= (1, 2, 3, 4, 5, 6) und es enthält zwei Beziehungen „kleiner als“ und „geteilt durch“. Es ist leicht zu überprüfen, dass es sich bei beiden Beziehungen um Ordnungsbeziehungen handelt. Der Beziehungsgraph „Kleiner als“ kann als Strahl dargestellt werden.

Der Graph der Relation „dividiert durch“ kann nur auf einer Ebene dargestellt werden.

Darüber hinaus weist der Graph der zweiten Relation Eckpunkte auf, die nicht durch einen Pfeil verbunden sind. Beispielsweise gibt es keinen Pfeil, der die Zahlen 4 und 5 verbindet (Abb. 10).

Die erste Beziehung „ X < bei„heißt linear. Im Allgemeinen, wenn die Beziehung geordnet ist R(streng und nicht streng) am Set X hat die Eigenschaft: für jeden X, beiÎ X oder xRy, oder yRx, dann nennt man es eine lineare Ordnungsrelation und die Menge X– eine linear geordnete Menge.

Wenn das Set X natürlich, und besteht aus N Elemente, dann lineare Reihenfolge X kommt es darauf an, seine Elemente mit den Nummern 1,2,3, ... zu nummerieren, N.

Linear geordnete Mengen haben eine Reihe von Eigenschaften:

1°. Lassen a, b, c– Elemente des Sets X, geordnet nach der Relation R. Wenn das bekannt ist aRв Und in Rс, dann sagen sie, dass das Element V liegt zwischen den Elementen A Und Mit.

2°. Ein Haufen X, linear geordnet nach der Beziehung R heißt diskret, wenn zwischen zwei seiner Elemente nur eine endliche Menge von Elementen dieser Menge liegt.

3°. Eine linear geordnete Menge heißt dicht, wenn zwischen zwei verschiedenen Elementen dieser Menge ein Element der Menge liegt.

Sei R eine binäre Relation auf der Menge A.

DEFINITION. Eine binäre Relation R auf einer Menge A heißt Ordnungsrelation auf A oder Ordnung auf A, wenn sie transitiv und antisymmetrisch ist.

DEFINITION. Eine Relation der Ordnung R auf einer Menge A heißt nicht streng, wenn sie auf A, also für jedes von A, reflexiv ist.

Eine Ordnungsrelation R heißt streng (auf A), wenn sie auf A, also für jedes von A, antireflexiv ist. Aus der Antireflexivität der transitiven Relation R folgt jedoch, dass sie antisymmetrisch ist. Daher kann die folgende äquivalente Definition angegeben werden.

DEFINITION. Eine binäre Relation R auf einer Menge A heißt strikte Ordnung auf A, wenn sie transitiv und antireflexiv auf A ist.

Beispiele. 1. Sei die Menge aller Teilmengen der Menge M. Die Inklusionsrelation auf einer Menge ist eine Relation nichtstrikter Ordnung.

2. Beziehungen auf der Menge der reellen Zahlen sind Beziehungen strenger bzw. nicht strenger Ordnung.

3. Die Teilbarkeitsrelation in der Menge der natürlichen Zahlen ist eine Relation nichtstrikter Ordnung.

DEFINITION. Eine binäre Relation R auf einer Menge A heißt Vorordnungsrelation oder Vorordnung auf A, wenn sie reflexiv und transitiv ist.

Beispiele. 1. Die Teilbarkeitsrelation in der Menge der ganzen Zahlen ist keine Ordnung. Es ist jedoch reflexiv und transitiv, also eine Vorordnung.

2. Die Relation der logischen Implikation ist eine Vorordnung auf der Menge der Aussagenlogikformeln.

Lineare Ordnung. Ein wichtiger Sonderfall der Ordnung ist die lineare Ordnung.

DEFINITION. Eine Ordnungsrelation auf einer Menge heißt lineare Ordnungsrelation oder lineare Ordnungsrelation, wenn sie auf zusammenhängend ist, d. h. für jedes x, y aus A

Eine Ordnungsrelation, die nicht linear ist, wird üblicherweise als Teilordnungsrelation oder Teilordnung bezeichnet.

Beispiele. 1. Die Relation „kleiner als“ auf der Menge der reellen Zahlen ist eine Relation linearer Ordnung.

2. Die in Wörterbüchern der russischen Sprache verwendete Ordnungsbeziehung wird als lexikographisch bezeichnet. Die lexikografische Reihenfolge der Wortmenge in der russischen Sprache ist eine lineare Reihenfolge.