Lineare Ordnungsbeziehung auf einer Menge. Auftragsbeziehung. Bestellte Sets. Strenge Beziehungen

Das letzte Beispiel führt das Konzept der alphabetischen Reihenfolge ein.

Alphabet ist ein Tupel paarweise unterschiedlicher Zeichen, die als Buchstaben des Alphabets bezeichnet werden. Ein Beispiel ist das Alphabet einer beliebigen europäischen Sprache sowie das Alphabet mit 10 arabischen Ziffern. Auf einem Computer bestimmen die Tastatur und einige unterstützende Tools das Alphabet gültiger Zeichen.

Wort im AlphabetA - Tupel von Buchstaben des Alphabets A. Das Wort wird in alphabetischer Reihenfolge von links nach rechts ohne Leerzeichen geschrieben. Eine natürliche Zahl ist aufgrund der nichtlinearen Anordnung von Symbolen nicht immer ein Wort hochgestellte (Exponenten) und tiefgestellte (Variablenindizes, Logarithmenbasen) Symbole, Bruchstriche, Zeichenradikale usw.; Aufgrund einiger Konventionen kann es jedoch in eine Zeichenfolge geschrieben werden, die beispielsweise in der Computerprogrammierung verwendet wird (z. B. wird das Potenzierungszeichen als zwei Multiplikationszeichen hintereinander geschrieben: 5**3 bedeutet die dritte Potenz von Nummer 5.

Lexikographische (alphabetische) Ordnung - für verschiedene Wörter im Alphabet mit geordnet

Symbole legen die Reihenfolge fest: , wenn

mögliche Einführung , bei dem entweder

(Unterwort kann leer sein) oder - leeres Unterwort

In dieser Definition - ein Präfix (anfängliches Unterwort), das für beide Wörter gleich ist - oder die ersten auf der linken Seite sind unterschiedlich

Zeichen, entweder - das letzte Zeichen im Wort - Schwanz

Unterwörter.

Somit wird die alphabetische Reihenfolge von Wörtern durch das erste Symbol auf der linken Seite bestimmt, das sie unterscheidet (z. B. steht das Wort KONUS vor dem Wort COSINE, weil sie sich zuerst im dritten Buchstaben unterscheiden, und im russischen Alphabet steht N vor S). Das Leerzeichen gilt auch als Vorzeichen vor jedem Zeichen des Alphabets – für den Fall, dass eines der Wörter ein Präfix eines anderen ist (z. B. CON und CONE).

Übung.Überprüfen Sie, ob die alphabetische Reihenfolge der natürlichen Zahlen mit der gleichen Anzahl an Dezimalstellen mit ihrer Reihenfolge nach der Größe übereinstimmt.

Lassen A - Teilweise bestelltes Set. Das Element heißt maximal V A, wenn es kein Element für welches gibt A< b. Element A angerufen das größte V A, wenn für jeden anders als A Element abgeschlossen B<а-

Symmetrisch bestimmt minimal und am kleinsten Elemente. Die Konzepte der größten und maximalen (bzw. kleinsten und minimalen) Elemente sind unterschiedlich – siehe. Beispiel in Abb. 14. Die Menge in Abb. 14,a hat das größte Element R, es ist auch das Maximum, es gibt zwei Minimumelemente: s und t, es gibt kein Kleinstes. In Abb. 14b hingegen gibt es eine Menge mit zwei maximalen Elementen / und J, Es gibt kein Größtes, Minimales, also Kleinstes – eines: T.

Wenn eine Menge das größte (bzw. kleinste) Element hat, dann gibt es im Allgemeinen nur eines (es kann sein, dass es keines gibt).

Es kann mehrere maximale und minimale Elemente geben (in einer unendlichen Menge darf es überhaupt keine geben; im letzten Fall muss es welche geben).

Schauen wir uns zwei weitere Beispiele an. - Relation auf einer Menge N:

„J teilt X", oder "X ist ein Teiler einer Zahl Y"(Zum Beispiel,

) ist reflexiv und transitiv. Betrachten wir es auf einer endlichen Menge von Teilern der Zahl 30.

Die Relation ist eine partielle Ordnungsrelation (nicht streng)

und wird durch die folgende Matrix der Ordnung 8 dargestellt, die 31 Zeichen enthält

Der entsprechende Kreis mit 8 Eckpunkten muss 31 Links enthalten. . Allerdings ist es für die Anzeige bequemer, wenn wir 8 ausschließen

Konnektive-Schleifen, die die Reflexivität der Beziehung darstellen (diagonale Elemente der Matrix) und transitive Konnektive, d.h. Bänder

Wenn es eine Zwischenzahl Z gibt, so dass

(zum Beispiel das Konnektiv weil). Dann im Schema

Es bleiben 12 Bänder übrig (Abb. 15); fehlende Links werden „durch Transitivität“ impliziert. Die Zahl 1 ist die kleinste und die Zahl 30

größte Elemente in . Wenn wir von der Zahl 30 ausschließen und

Betrachten Sie dann die gleiche Teilordnung auf der Menge

Es gibt kein maximales Element, aber es gibt 3 maximale Elemente: 6, 10, 15

Jetzt bauen wir die gleiche Schaltung für eine Beziehung auf einem Booleschen Wert auf

(die Menge aller Teilmengen) einer Drei-Elemente-Menge

Enthält 8 Elemente:

Überprüfen Sie, ob die Elemente übereinstimmen a, b, c, jeweils die Zahlen 2, 3, 5 und die Operationen zum Kombinieren von Mengen sind Multiplikationen der entsprechenden Zahlen (d. h. zum Beispiel die entsprechende Teilmenge).

Produkt 2 5 = 10), dann sieht die Beziehungsmatrix genau so aus

dasselbe wie für Relation; Diagramme dieser beiden Beziehungen mit den beschriebenen

Abkürzungen von Schleifen und transitiven Konnektiven stimmen bis zur Notation überein (siehe Abb. 16). Das kleinste Element ist

Und das Größte -

Binäre Beziehungen R auf einem Set A Und S auf einem Set IN werden genannt isomorph, wenn dazwischen A und B Es ist möglich, eine Eins-zu-eins-Korrespondenz Г herzustellen, in der, wenn (d. h.

Elemente stehen in Beziehung R), dann (Bilder

Diese Elemente stehen in Beziehung S).

Somit sind teilweise geordnete Mengen isomorph.

Das betrachtete Beispiel lässt eine Verallgemeinerung zu.

Eine boolesche Beziehung ist eine Teilordnung. Wenn

Diese. ein Haufen E enthält P Elemente, dann jedes

entspricht der Teilmenge P-dimensionaler Vektor mit

Komponenten, wobei die charakteristische Funktion ist

setze A/ . Die Menge aller dieser Vektoren kann als Menge von Punkten betrachtet werden P-dimensionaler Rechenraum mit den Koordinaten 0 oder 1, also als Eckpunkte P-dimensional

Einheitswürfel, bezeichnet mit , d.h. Würfel mit Kanten der Einheitslänge. Für n = 1, 2, 3 angegebene Punkte repräsentieren jeweils die Enden eines Segments, die Eckpunkte eines Quadrats und eines Würfels – daher der gebräuchliche Name. Für /7=4 ist eine grafische Darstellung dieser Beziehung in Abb. 17 dargestellt. In der Nähe jedes Scheitelpunkts eines 4-dimensionalen Würfels befindet sich das entsprechende

Teilmenge der 4-Elemente-Menge und vierdimensional

ein Vektor, der die charakteristische Funktion dieser Teilmenge darstellt. Eckpunkte, die Teilmengen entsprechen, die sich durch das Vorhandensein genau eines Elements unterscheiden, werden miteinander verbunden.

In Abb. 17 ist ein vierdimensionaler Würfel so dargestellt, dass auf einer

Auf dieser Ebene liegen unvergleichbare Elemente paarweise vor und enthalten die gleiche Anzahl an Einheiten im Datensatz (von 0 bis 4), oder mit anderen Worten, die gleiche Anzahl an Elementen in den dargestellten Teilmengen.

In Abb. 18a, b - andere visuelle Darstellungen eines 4-dimensionalen Würfels;

in Abb. 18a die Achse der ersten Variablen OH nach oben gerichtet (gewollte Abweichung von der Vertikalen, damit verschiedene Kanten des Würfels nicht ineinander übergehen):

in diesem Fall entspricht der dreidimensionale Unterwürfel X= 0 liegt unten und für X= 1 - höher. In Abb. 186 gleiche Achse OH vom Inneren des Würfels nach außen gerichtet; der innere Teilwürfel entspricht X= Oh, und das Äußere ist es X = 1.

IN
Die Materialdatei zeigt ein Bild eines 5-dimensionalen Einheitswürfels (S. 134).

Eigenschaften von Beziehungen:

1) Reflexivität;

2) Symmetrie;

3)Transitivität.

4) Verbundenheit.

Attitüde R auf einem Set X angerufen reflektierend, wenn es um jedes Element der Menge geht X Wir können sagen, dass er in einer Beziehung ist R Mit mir: XRx. Wenn die Beziehung reflexiv ist, gibt es an jedem Scheitelpunkt des Graphen eine Schleife. Umgekehrt ist ein Graph, dessen jeder Scheitelpunkt eine Schleife enthält, ein reflexiver Beziehungsgraph.

Beispiele für reflexive Beziehungen sind die Beziehung „Vielfaches“ auf der Menge der natürlichen Zahlen (jede Zahl ist ein Vielfaches ihrer selbst), die Ähnlichkeitsbeziehung von Dreiecken (jedes Dreieck ist sich selbst ähnlich) und die Beziehung „Gleichheit“ ( jede Zahl ist sich selbst gleich) usw.

Es gibt Beziehungen, die nicht die Eigenschaft der Reflexivität haben, zum Beispiel die Beziehung der Rechtwinkligkeit von Segmenten: ab, ba(Es gibt kein einziges Segment, von dem man sagen kann, dass es senkrecht zu sich selbst steht) . Daher gibt es im Diagramm dieser Beziehung keine einzige Schleife.

Die Relation „länger“ für Segmente, „mehr um 2“ für natürliche Zahlen usw. hat nicht die Eigenschaft der Reflexivität.

Attitüde R auf einem Set X angerufen entspiegelt, wenn für irgendein Element aus der Menge X immer falsch XRx: .

Es gibt Beziehungen, die weder reflexiv noch antireflexiv sind. Ein Beispiel für eine solche Beziehung ist die Beziehung „Punkt“. X symmetrisch zum Punkt bei relativ gerade l", definiert auf einer Menge von Punkten der Ebene. Tatsächlich alle Punkte einer Geraden l zu sich selbst symmetrisch sind, und Punkte, die nicht auf einer Geraden liegen lch, selbst sind nicht symmetrisch.

Attitüde R auf einem Set X angerufen symmetrisch, wenn die Bedingung erfüllt ist: aus der Tatsache, dass das Element X steht im Zusammenhang mit dem Element j Daraus folgt, dass das Element j steht im Zusammenhang R mit Element X:xRyyRx.

Der symmetrische Beziehungsgraph hat die folgende Funktion: zusammen mit jedem Pfeil, der von kommt X Zu j, das Diagramm enthält einen Pfeil, der von ausgeht j Zu X(Abb. 35).

Beispiele für symmetrische Beziehungen können die folgenden sein: die Beziehung der „Parallelität“ von Segmenten, die Beziehung der „Rechtwinkligkeit“ von Segmenten, die Beziehung der „Gleichheit“ von Segmenten, die Beziehung der Ähnlichkeit von Dreiecken, die Beziehung der „Gleichheit“ von Brüche usw.

Es gibt Beziehungen, die nicht die Eigenschaft der Symmetrie haben.

In der Tat, wenn das Segment X länger als das Segment bei, dann das Segment bei darf nicht länger als das Segment sein X. Der Graph dieser Beziehung weist eine Besonderheit auf: Der die Eckpunkte verbindende Pfeil ist nur in eine Richtung gerichtet.

Attitüde R angerufen antisymmetrisch, wenn für irgendwelche Elemente X Und j von der Wahrheit xRy sollte falsch sein yRx: : xRyyRx.

Neben der „längeren“ Relation gibt es auf vielen Segmenten weitere antisymmetrische Relationen. Beispielsweise ist die „Größer als“-Relation für Zahlen (if X mehr bei, Das bei mehr kann es nicht geben X), die „mehr über“-Einstellung usw.

Es gibt Beziehungen, die weder die Eigenschaft der Symmetrie noch die Eigenschaft der Antisymmetrie haben.

Beziehung R auf einer Menge X angerufen transitiv, wenn aus diesem Element X steht im Zusammenhang R mit Element ja, und Element j steht im Zusammenhang R mit Element z Daraus folgt, dass das Element X steht im Zusammenhang R mit Element z: xRy Und yRzxRz.

Transitiver Beziehungsgraph, bei dem jedes Pfeilpaar von kommt X Zu j und von j Zu z, enthält einen Pfeil, der von ausgeht X Zu z.

Die Relation „länger“ auf einer Menge von Segmenten hat auch die Transitivitätseigenschaft: wenn das Segment A länger als das Segment B, Liniensegment B länger als das Segment Mit, dann das Segment A länger als das Segment Mit. Die Beziehung „Gleichheit“ auf einer Menge von Segmenten hat auch die Eigenschaft der Transitivität: (a=b, b=c)(a=c).

Es gibt Beziehungen, die nicht die Eigenschaft der Transitivität haben. Eine solche Beziehung ist beispielsweise die Rechtwinkligkeitsbeziehung: wenn ein Segment A senkrecht zum Segment B, und das Segment B senkrecht zum Segment Mit, dann die Segmente A Und Mit nicht senkrecht!

Es gibt eine weitere Eigenschaft von Beziehungen, die Eigenschaft der Verbundenheit genannt wird, und eine Beziehung, die diese Eigenschaft aufweist, wird Verbundenheit genannt.

Attitüde R auf einem Set X angerufen in Verbindung gebracht, wenn für irgendwelche Elemente X Und j Aus dieser Menge ist die Bedingung erfüllt: if X Und j sind dann auch unterschiedlich X steht im Zusammenhang R mit Element j, oder Element j steht im Zusammenhang R mit Element X. Mit Symbolen lässt sich das so schreiben: xyxRy oder yRx.

Beispielsweise hat die Relation „größer als“ für natürliche Zahlen die Eigenschaft des Zusammenhangs: Für beliebige verschiedene Zahlen x und y kann man entweder angeben x>y, oder y>x.

In einem verbundenen Beziehungsgraphen sind zwei beliebige Eckpunkte durch einen Pfeil verbunden. Auch die gegenteilige Aussage trifft zu.

Es gibt Beziehungen, die nicht über die Eigenschaft der Verbundenheit verfügen. Eine solche Beziehung ist beispielsweise die Beziehung der Teilbarkeit auf der Menge der natürlichen Zahlen: Wir können solche Zahlen x und nennen j egal wie hoch die Zahl ist X ist kein Teiler einer Zahl j, noch Zahl j ist kein Teiler einer Zahl X(Zahlen 17 Und 11 , 3 Und 10 usw.) .

Schauen wir uns ein paar Beispiele an. Am Set X=(1, 2, 4, 8, 12) die Relation „Anzahl“ ist gegeben X Vielfaches der Zahl j" Lassen Sie uns einen Graphen dieser Beziehung erstellen und seine Eigenschaften formulieren.

Das Gleichheitsverhältnis von Brüchen wird als Äquivalenzrelation bezeichnet.

Attitüde R auf einem Set X angerufen Äquivalenzrelation, wenn es gleichzeitig die Eigenschaften Reflexivität, Symmetrie und Transitivität besitzt.

Beispiele für Äquivalenzbeziehungen sind: Gleichheitsbeziehungen geometrischer Figuren, Parallelitätsbeziehungen von Linien (vorausgesetzt, dass zusammenfallende Linien als parallel betrachtet werden).

In der oben diskutierten Beziehung „Gleichheit der Brüche“ ist die Menge X in drei Teilmengen aufgeteilt: ( ; ; }, {; } , (). Diese Teilmengen schneiden sich nicht und ihre Vereinigung fällt mit der Menge zusammen X, d.h. wir haben eine Aufteilung der Menge in Klassen.

Also, Wenn eine Äquivalenzrelation für eine Menge X gegeben ist, dann erzeugt sie eine Partition dieser Menge in paarweise disjunkte Teilmengen – Äquivalenzklassen.

Somit haben wir die Gleichheitsbeziehung auf der Menge festgestellt
X=( ;; ; ; ; ) entspricht der Aufteilung dieser Menge in Äquivalenzklassen, die jeweils aus einander gleichen Brüchen bestehen.

Das Prinzip der Aufteilung einer Menge in Klassen mithilfe einer Äquivalenzrelation ist ein wichtiges Prinzip der Mathematik. Warum?

Erstens bedeutet „äquivalent“ gleichwertig, austauschbar. Daher sind Elemente derselben Äquivalenzklasse austauschbar. Somit sind Brüche, die in derselben Äquivalenzklasse (; ; ) liegen, sind vom Gesichtspunkt des Verhältnisses von Gleichheit und Bruch nicht zu unterscheiden kann beispielsweise durch ein anderes ersetzt werden . Und dieser Ersatz wird das Ergebnis der Berechnungen nicht ändern.

Zweitens wird angenommen, dass die Äquivalenzklasse durch jeden ihrer Vertreter bestimmt wird, da die Äquivalenzklasse Elemente enthält, die aus der Sicht einer Beziehung nicht unterscheidbar sind, d.h. ein beliebiges Element der Klasse. Somit kann jede Klasse gleicher Brüche angegeben werden, indem jeder Bruch angegeben wird, der zu dieser Klasse gehört. Die Äquivalenzklasse nach einem Vertreter ermöglicht es Ihnen, eine Menge von Vertretern aus Äquivalenzklassen anstelle aller Elemente der Menge zu untersuchen. Beispielsweise erzeugt die Äquivalenzrelation „die gleiche Anzahl von Eckpunkten haben“, die für eine Menge von Polygonen definiert ist, eine Aufteilung dieser Menge in Klassen von Dreiecken, Vierecken, Fünfecken usw. Eigenschaften, die einer bestimmten Klasse innewohnen, werden bei einem ihrer Vertreter berücksichtigt.

Drittens wird die Partitionierung einer Menge in Klassen mithilfe einer Äquivalenzrelation verwendet, um neue Konzepte einzuführen. Beispielsweise kann das Konzept eines „Linienbündels“ als das definiert werden, was parallele Linien miteinander gemeinsam haben.

Eine weitere wichtige Beziehungsart ist die Auftragsbeziehung. Betrachten wir das Problem am Set X={3, 4, 5, 6, 7, 8, 9, 10 ) die Beziehung „haben den gleichen Rest, wenn sie durch geteilt werden 3 " Diese Beziehung erzeugt eine Partition der Menge X in Klassen: Alle Zahlen fallen in eins, wenn sie durch geteilt werden 3 es stellt sich heraus, dass es der Rest ist 0 (Das sind Zahlen 3, 6, 9 ). Im zweiten - Zahlen, wenn sie durch geteilt werden 3 der Rest ist 1 (Das sind Zahlen 4, 7, 10 ). Die dritte enthält alle Zahlen, die geteilt durch werden 3 der Rest ist 2 (Das sind Zahlen 5, 8 ). Tatsächlich schneiden sich die resultierenden Mengen nicht und ihre Vereinigung fällt mit der Menge zusammen X. Daher ist die Beziehung „den gleichen Rest haben, wenn geteilt durch 3 ", am Set definiert X ist eine Äquivalenzrelation.

Um ein anderes Beispiel zu nennen: Die vielen Schüler einer Klasse können nach Größe oder Alter sortiert werden. Beachten Sie, dass diese Beziehung die Eigenschaften Antisymmetrie und Transitivität hat. Oder jeder kennt die Reihenfolge der Buchstaben im Alphabet. Dies wird durch die „Sollte“-Haltung gewährleistet.

Attitüde R auf einem Set X angerufen Beziehung einer strengen Ordnung, wenn es gleichzeitig die Eigenschaften Antisymmetrie und Transitivität besitzt. Beispielsweise ist die Relation „ X< j».

Wenn die Beziehung die Eigenschaften Reflexivität, Antisymmetrie und Transitivität hat, dann ist sie eine solche nicht strikte Beziehung. Beispielsweise ist die Relation „ Xj».

Beispiele für Ordnungsrelationen sind: die „Kleiner-als“-Relation auf einer Menge natürlicher Zahlen, die „Kürzer“-Relation auf einer Menge von Segmenten. Wenn eine Ordnungsrelation auch die Eigenschaft der Verbundenheit hat, dann spricht man von einer solchen lineare Ordnungsrelation. Zum Beispiel die Beziehung „kleiner als“ auf der Menge der natürlichen Zahlen.

Ein Haufen X angerufen ordentlich, wenn darauf eine Bestellrelation angegeben ist.

Zum Beispiel viele X={2, 8, 12, 32 ) kann mit der „Kleiner als“-Relation (Abb. 41) bestellt werden, oder dies kann mit der „Mehrfach“-Relation (Abb. 42) erfolgen. Da es sich jedoch um Ordnungsbeziehungen handelt, ordnen die Beziehungen „kleiner als“ und „mehrfach“ die Menge der natürlichen Zahlen auf unterschiedliche Weise. Mit der „Kleiner-als“-Relation können Sie zwei beliebige Zahlen aus einer Menge vergleichen X, aber die Relation „multiple“ hat diese Eigenschaft nicht. Okay, ein paar Zahlen. 8 Und 12 hat nichts mit der Relation „vielfach“ zu tun: Das kann man nicht sagen 8 mehrere 12 oder 12 mehrere 8.

Man sollte nicht denken, dass alle Beziehungen in Äquivalenzbeziehungen und Ordnungsbeziehungen unterteilt sind. Es gibt eine Vielzahl von Beziehungen, die weder Äquivalenzbeziehungen noch Ordnungsbeziehungen sind.

Ein Haufen X (\displaystyle X), auf dem die partielle Ordnungsrelation eingeführt wird, heißt teilweise bestellt. Eine nicht strikte Teilordnungsrelation wird oft mit bezeichnet ≼ (\displaystyle \preccurlyeq ).

Optionen

Teilordnungsbeziehung R (\displaystyle R) angerufen lineare Ordnung, wenn die Bedingung erfüllt ist

Ein Haufen X (\displaystyle X), auf dem eine lineare Ordnungsrelation eingeführt wird, heißt linear geordnet, oder Kette.

Attitüde R (\displaystyle R), das nur die Bedingungen der Reflexivität und Transitivität erfüllt, heißt Vorbestellung oder Quasi-Bestellung.

Strenge Ordnung

Wenn die Bedingung der Reflexivität durch die Bedingung der Antireflexivität ersetzt wird:

dann erhalten wir die Definition strikt, oder antireflexive Teilordnung(normalerweise durch das Symbol gekennzeichnet ≺ (\displaystyle \prec )).

Kommentar. Die gleichzeitige Antireflexivität und Transitivität einer Beziehung bringt Antisymmetrie mit sich. Daher ist die Beziehung Beziehung einer strengen Ordnung genau dann, wenn es antireflexiv und transitiv ist.

Im Allgemeinen, wenn R (\displaystyle R) ist also eine transitive, antisymmetrische Relation

Beispiele

• Auf der Menge der reellen Zahlen sind die Beziehungen „mehr als“ und „kleiner als“ Beziehungen strenger Ordnung, und „mehr als oder gleich“ und „kleiner als oder gleich“ sind nicht strenge Beziehungen.
• Die Teilbarkeitsrelation auf einer Menge von ganzen Zahlen ist eine Relation nicht strenger Ordnung.

Dushnik-Miller-Dimension

Geschichte

Zeichen < {\displaystyle <} Und > (\displaystyle >) erfunden

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 Hauptmerkmal 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 strenge (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 wird auch Teilordnung genannt nicht streng in Ordnung. Oftmals wird eine partielle (nicht strenge) Ordnungsrelation 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 sogenanntes 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.