Beziehungen. Teil II

Die formale Modellierungstheorie verwendet algebraische Beziehungen, einschließlich dieser in den Signaturen von Modellen algebraischer Strukturen, die reale physikalische, technische Objekte und die Prozesse ihrer Funktionsweise beschreiben. Diese Veröffentlichung ist eine Fortsetzung der vorherigen , deren Lektüre wünschenswert ist, da dort viele hier verwendete Konzepte und Begriffe beschrieben werden.



Die Präsentation wird nicht im traditionellen (Pfeil-) Stil angeboten, sondern so, wie ich selbst diese ganze Küche sowohl aus Lehrbüchern / Handbüchern als auch aus Zeitschriftenartikeln darstellen und beherrschen musste. Ich halte den von mir erstellten Katalog für besonders nützlich. Er ermöglicht es Ihnen, fast jeden Raum auszuwählen und seine Elemente in einer praktischen Form darzustellen: eine Matrix, ein Diagramm usw. Sie können sofort sehen, womit Sie es zu tun haben, und Eigenschaften (die bereits ausgeschrieben wurden) müssen häufig nicht überprüft werden.

Beziehungskonzept

Ich denke, dass der Begriff Haltung jedem Leser vertraut ist, aber nach einer Definition zu fragen, wird die meisten verwirren. Dafür gibt es viele Gründe. Sie sind meistens bei Lehrern anzutreffen, die, wenn sie im Unterricht Beziehungen verwendeten, sich nicht auf diesen Begriff konzentrierten und keine denkwürdigen Beispiele gaben. Einige Kommentatoren des Artikels haben die Kommentare ihrem eigenen Konto zugeordnet und Minuspunkte hinzugefügt. Aber man kann ein Nähen nicht in einem Sack verstecken. Es gab keine ernsthaften Veröffentlichungen und nein. Fragen Sie sich, haben Sie mit einem Beziehungsraum gearbeitet? Und antworte dir ehrlich. Was können Sie der Welt über diesen Raum erzählen? Führen Sie zunächst zumindest seine Elemente auf und geben Sie Eigenschaften an. Sie betrachten das DBMS sogar mit den Augen ihrer Schöpfer, aber sie sehen auch nicht alles oder sie zeigen nicht alles, wie zum Beispiel in Mikroschaltungen.



Hier werde ich eine kleine Wiederholung machen. Man sollte mit der abstrakten Menge A = {a1, a2, a3, ..., an} beginnen. Sie können darüber lesen Sie hier . Zum besseren Verständnis werden wir die Menge auf 3 Elemente reduzieren, d.h. A = {a1, a2, a3}. Nun führen wir die kartesische Multiplikation × = ^{2 durch} und zählen explizit alle Elemente des kartesischen Quadrats

× = {(a1, a1), (a1, a2), (a1, a3), (a2, a1), (a2, a2) auf ), (a2, a3), (a3, a1), (a3, a2), (a3, a3)}.

Wir haben 9 geordnete Elementpaare von A × A erhalten, in einem Paar ist das erste Element vom ersten Faktor, das zweite vom zweiten. Versuchen wir nun, alle Teilmengen aus dem kartesischen A × A-Quadrat zu erhalten. Die Teilmengen enthalten eine unterschiedliche Anzahl von Paaren: eins, zwei, drei usw. Bis zu allen 9 Paaren nehmen wir auch die leere Menge ∅ in diese Liste auf. Wie viele Untergruppen gibt es? Viele, nämlich 2 ⁹= 512 Elemente.



Definition . Eine Teilmenge einer kartesischen Quadratmenge wird als binäre Beziehung bezeichnet. Wenn das kartesische Quadrat zweier Faktoren ein binäres Verhältnis ist, wenn es 3 ist, ist es intern, von 4 ist es tetrar und von n ist es n-ary. Arity ist die Anzahl der Stellen in einem Beziehungselement.

Definition . Die Menge aller Teilmengen der Menge A wird als Boolescher Wert bezeichnet. Boolean besteht aus 2 ^{| A |} Elemente, hier | A | Ist die Kardinalität der Menge.



Beziehungen können auf verschiedene Arten definiert werden:

• Aufzählung von Elementen; R1 = {(a2, a2), (a2, a3), (a3, a1)}; R2 = {(a3, a3)}
• binärer Vektor; <000011100>; <000000001>
• Matrix;
• Grafik und andere Möglichkeiten.

Als nächstes wenden wir uns der Betrachtung von Beziehungsräumen zu, unter der Annahme, dass das Konzept, die Eigenschaften von Beziehungen und die Operationen mit ihnen dem Leser zumindest im Umfang unserer Veröffentlichung im Link vertraut sind.

Binäre Beziehungsräume

Lassen Sie uns vorab klarstellen, dass Beziehungen streng (dies sind alles antireflexive Beziehungen) oder nicht streng (alle anderen) sein können. Wir werden uns auf das Verhältnis von Gleichgültigkeit und Präferenz konzentrieren, wobei letztere in schwache Präferenzen und strenge Präferenzen (aus irgendeinem Grund nicht stark) unterteilt sind. Im Allgemeinen gibt es in der Wissenschaft keine Ordnung mit Terminologie, und höchstwahrscheinlich wird es keine geben. In der Kryptographie ist beispielsweise das Entfernen einer Verschlüsselung aus einem Kryptogramm bei Vorhandensein eines Schlüssels eine Entschlüsselung und ohne Schlüssel eine Entschlüsselung. Es scheint, dass ein Decoder decodiert, aber nein.



Der Raum der binären Beziehungen mit einer Trägermenge ist eine beliebige Teilmenge der Menge der binären Beziehungen, die auf angegeben sind. Betrachten Sie die Haupträume für Präferenzbeziehungen (Abbildung 2.15).



R.- Der Raum aller Beziehungen mit schwacher Präferenz erfüllt die Bedingung der Reflexivität und Vollständigkeit.

QT - schwache Präferenzen, die die Quasi-Transitivitätsbedingung erfüllen.

QO ist der Raum linearer Quasi- Ordnungen , dh Beziehungen von QT, die transitiv sind.

TO ist der Raum aller perfekten Ordnungen, dh Beziehungen aus der QO, die antisymmetrisch sind.

SP - der Raum aller Beziehungen von strenger Präferenz, erfüllt die Eigenschaften von Antireflexivität und Antisymmetrie.

RO- Beziehungen strenger Teilordnung oder transitiver strenger Präferenzen. Da Relationen strikter Teilordnung transitiv sind, ist es natürlich, sie zu verwenden, um sie durch reduzierte Graphen darzustellen, dh solche, in denen die Transitivitätsbögen weggelassen werden. Solche abgekürzten Graphen werden Hasse-Diagramme genannt.

QS ist der Raum von Quasiserien, dh strengen Teilordnungen, für die die Beziehung I = ¬ (PUP ^-1 ) eine Äquivalenz ist.

TSO ist der Raum strenger linearer Ordnungen, dh jener Teilordnungen, für die die Vollständigkeitseigenschaft erfüllt ist.

Es sollte beachtet werden, dass es insgesamt n solcher Beziehungen gibt! .. Zum Beispiel beträgt für n = 3 die Anzahl der perfekten Beziehungen 6, und sie sind alle in Fig. 4 gezeigt. 2.13.

T.- der Raum aller Toleranzverhältnisse (Gleichgültigkeit), sie haben die Eigenschaften von Symmetrie und Reflexivität.

TOT ist der Raum transitiv orientierter Toleranzbeziehungen, d.

H. Beziehungen, so dass das Komplement zu I als eine Vereinigung von gegenseitig inversen transitiven Beziehungen dargestellt wird, d. H. ¬I = R∩R ^-1 .

Ich bin der Raum aller Äquivalenzbeziehungen, dh symmetrischer, reflexiver und transitiver Beziehungen.

Der E- Raum der Gleichheitsrelationen besteht aus einer Relation, die durch eine Diagonalmatrix dargestellt wird. Es gibt eine Eins-zu-Eins-Beziehung zwischen den Räumen R, P und I, die durch die Abbildung von Präferenzbeziehungen bestimmt wird.









Abbildung 2.15 Schema von Räumen binärer Beziehungen



Die aufgedeckten Verbindungen zwischen den Räumen werden verwendet, um Entscheidungsprobleme (DM) von einem Raum in einen anderen zu übertragen, wo sie auf einfachere Weise gelöst werden können. Anschließend wird die resultierende Lösung in den ursprünglichen Raum zurückgeführt, in dem der DP formuliert wurde.

Diese Beziehungen sind in Abb. 1 schematisch dargestellt. 2.14. Räume binärer Beziehungen (Arten von Beziehungen) sind in Abb. 1 dargestellt. 2.15.

Äquivalenzbeziehungen

Definition . Eine binäre Beziehung σ ⊆ A × A, die drei Eigenschaften von Reflexivität, Symmetrie und Transitivität aufweist, wird als binäre Äquivalenzbeziehung (BOE) bezeichnet. Die Äquivalenzbeziehung σ (x, y), (x, y) ∊σ, xσy, x≈y wird bezeichnet. Es ist zweckmäßig, eine Matrixdarstellung (tabellarisch) der Beziehung zu verwenden. Unten in Abbildung 2.24 ist nur eine Matrixdarstellung dargestellt. Über dem Satz von 4 Elementen befinden sich 15 BOEs, die alle abgebildet sind.



Darstellung und Analyse der Struktur von Äquivalenzbeziehungen (n = 4)

Die Äquivalenz aus binären Beziehungen ist vielleicht die häufigste BO. Selten kommt die Wissenschaft ohne dieses Konzept aus, aber selbst wenn Äquivalenzen verwendet werden, um Fragen zu stellen, kann es schwierig sein zu verstehen, was der Autor meinte. Selbst bei korrekter Definition und Aufzählung der dieser binären Beziehung innewohnenden Eigenschaften bleiben die Wahrnehmungsschwierigkeiten bestehen.



Beginnen wir mit einem Beispiel zu Äquivalenzen, das die Einschränkungen ihrer Anzahl veranschaulicht.



Beispiel 1 . Es sollen drei Würfel sein. Lassen Sie uns eine Liste der Eigenschaften erstellen, mit denen die Würfel ausgestattet sind, und deren praktische Verwendung (die Eigenschaften der Würfel) sie sozusagen austauschbar macht. Weisen wir den Würfeln Zahlen zu und stellen ihre Eigenschaften in Tabelle 1 dar.





Für jede der Eigenschaften entstehen BOE- und Äquivalenzklassen. Wenn wir die Liste der Eigenschaften fortsetzen, erhalten wir keine neuen Äquivalenzbeziehungen. Es wird nur Wiederholungen von bereits gebauten geben, aber für andere Zeichen. Lassen Sie uns den Zusammenhang zwischen BOE und Sets zeigen.



Betrachten Sie eine Menge von drei Elementen A = {1,2,3} und erhalten Sie dafür alle möglichen Partitionen in alle Teile. ①1 | 2 | 3; ~ 12 | 3; ~ 13 | 2; | 1 | 23; ⑤123. Die letzte Aufteilung in einen Teil. Partitionsnummern und BOs in Kreisen.



Definition . Eine Partition einer Menge A ist eine Familie i, i = 1 (1) I, von nicht leeren paarweise disjunkten Teilmengen von , deren Vereinigung die gesamte ursprüngliche Menge = Ui, i∩j = ∅, ∀ i ≠ j bildet. Die Teilmengen i werden Äquivalenzklassen der Partition der ursprünglichen Menge genannt.



Dies sind alles Partitionen des Sets (5 Stück). Die BO-Analyse zeigt, dass es auch nur 5 verschiedene Äquivalenzrelationen gibt. Ist dieser Zufall ein Zufall? Wir können jede Partition einer Matrix aus neun Zellen (3 × 3 = 9) zuordnen, von denen jede entweder ein geordnetes Elementpaar aus Satz A enthält oder die Zelle leer bleibt, wenn für das entsprechende Paar kein Objekt vorhanden ist. Die Zeilen und Spalten der Matrix sind mit Elementen der Menge A markiert, und der Zeilen-Spalten-Schnittpunkt entspricht einem geordneten Paar (i, j). Es ist kein Paar, das in eine Matrixzelle passt, sondern nur eins oder null, jedoch wird null oft überhaupt nicht geschrieben.



Nein, der Zufall ist kein Zufall. Es stellt sich heraus, dass jede Partition der Menge in Eins-zu-Eins-Entsprechung mit der BOE steht und die Kardinalität der Menge eine beliebige | A | sein kann = n.



Diese Beziehung ist vielleicht die häufigste in Bezug auf die Verwendung im wissenschaftlichen Verkehr, aber die Menge der in dieser Hinsicht realisierten Eigenschaften schränkt ihre Verbreitung stark ein.

Von allen abstrakten binären Beziehungen über eine Menge von drei Elementen (es gibt insgesamt 2 ⁹ = 512 Beziehungen) sind also nur fünf Äquivalenzen - Träger der erforderlichen Eigenschaften, weniger als ein Prozent.



Für | A | = 4 Beziehungen existieren 2 ¹⁶= 65536, aber es gibt nur 15 Äquivalenzen. Dies ist eine sehr seltene Art von Beziehung. Andererseits sind Äquivalenzbeziehungen bei angewandten Problemen weit verbreitet. Überall dort, wo es Mengen sehr unterschiedlicher Objekte und unterschiedliche Aufteilungen solcher Mengen (nicht Zahlen) in Teile gibt und gibt, entstehen Äquivalenzbeziehungen. Sie können als mathematische (algebraische) Modelle solcher Partitionen bezeichnet werden, die Objektgruppen nach verschiedenen Kriterien klassifizieren.



Die minimale Partition der Menge A, die aus Teilmengen A = U {a} mit einem Element gebildet wird, und die Partition A, die aus der Menge {A} selbst besteht, werden als triviale (unpassende) Partitionen bezeichnet.



Gitter (4): Alle Partitionen der Menge = {a1, a2, a3, a4} = {1,2,3,4}





Die minimale Partitionierung entspricht der Äquivalenzrelation P15, die als Gleichheit oder Einheitsrelation bezeichnet wird. Jede Äquivalenzklasse enthält ein einzelnes Element. Einer Partition der Menge A, die nur die Menge A selbst enthält, entspricht eine Äquivalenzbeziehung, die alle Elemente des kartesischen Quadrats A × A enthält.





Der Typ, der den Äquivalenzbeziehungen am nächsten kommt, sind Toleranzbeziehungen . Die Menge der Toleranzbeziehungen enthält alle Äquivalenzbeziehungen. Für Träger A gibt es drei Toleranzelemente 8. Alle haben die Eigenschaften Reflexivität und Symmetrie.



Wenn die Transitivitätseigenschaft erfüllt ist, wandeln sich fünf der acht Toleranzen in Äquivalenzen um (Abbildungen 2.24 und 2.25).



Definition . Die Menge der Äquivalenzklassen [a] σ der Elemente der Menge A wird als Quotientensatz (bezeichnet mit A / σ) der Menge A durch die Äquivalenz σ bezeichnet.



Definition . Eine natürliche (kanonische) Abbildung f: A → A / σ ist eine Abbildung f, so dass f (a) = [a] σ.

Toleranzverhältnisse und ihre Analyse

Diese BOs wurden bereits früher erwähnt, aber hier werden wir sie genauer betrachten. Jeder kennt die Konzepte von Ähnlichkeit, Ähnlichkeit, Ähnlichkeit, Ununterscheidbarkeit, Austauschbarkeit von Objekten. Sie scheinen inhaltlich ähnlich zu sein, aber nicht dasselbe. Wenn nur Ähnlichkeit für Objekte angezeigt wird, ist es unmöglich, sie in klare Klassen zu unterteilen, sodass die Objekte innerhalb einer Klasse ähnlich sind und es keine Ähnlichkeit zwischen Objekten verschiedener Klassen gibt. Bei Ähnlichkeit entsteht eine vage Situation ohne klare Grenzen. Andererseits kann die Anhäufung unbedeutender Unterschiede in ähnlichen Objekten zu völlig unterschiedlichen Objekten führen.



Im vorherigen Teil haben wir die sinnvolle Bedeutung des Ähnlichkeitsverhältnisses (Äquivalenz) von Objekten diskutiert. Ebenso wichtig ist die Situation, in der die Ähnlichkeit von Objekten festgestellt werden muss.



Lassen Sie die Form geometrischer Körper untersuchen. Wenn die Ähnlichkeit der Form von Objekten, beispielsweise Würfeln, ihre vollständige Austauschbarkeit in einer bestimmten Lernsituation bedeutet, dann ist die Ähnlichkeit eine teilweise Austauschbarkeit (wenn es unter den Würfeln Parallelepipeds gibt, die ihnen sehr ähnlich sind), dh die Möglichkeit der Austauschbarkeit mit einigen (in dieser Situation zulässig) ) Verluste.



Das größte Maß für Ähnlichkeit ist die Ununterscheidbarkeit, überhaupt nicht die Gleichheit, wie es auf den ersten Blick scheinen mag. Identität ist eine qualitativ andere Eigenschaft. Identität kann nur als Sonderfall von Ununterscheidbarkeit und Ähnlichkeit angesehen werden.



Der Punkt ist, dass nicht unterscheidbare Objekte (sowie ähnliche, ähnliche) nicht in Klassen unterteilt werden können, so dass die Elemente in jeder Klasse nicht unterschiedlich sind und die Elemente verschiedener Klassen offensichtlich unterschiedlich sind.



In der Tat werden wir die Menge der Punkte (x, y) in der Ebene betrachten. Der Wert d habe einen Wert, der kleiner als die Auflösbarkeitsschwelle des Auges ist, dh d ist eine solche Entfernung, bei der zwei Punkte, die sich in dieser Entfernung befinden, zu einem verschmelzen, d. visuell nicht unterscheidbar (im gewählten Abstand der Ebene vom Betrachter). Betrachten Sie nun n Punkte, die auf einer geraden Linie liegen und in einem Abstand d voneinander beabstandet sind. Jedes Paar

benachbarter Punkte ist nicht zu unterscheiden, aber wenn n groß genug ist, sind der erste und der letzte Punkt weit voneinander entfernt und sicherlich unterscheidbar.



Der traditionelle Ansatz zur Untersuchung der Ähnlichkeit oder Ununterscheidbarkeit besteht darin, zuerst das Ähnlichkeitsmaß zu bestimmen und dann die relative Position ähnlicher Objekte zu untersuchen. Der englische Mathematiker Zieman, der Modelle des visuellen Apparats studierte, schlug eine axiomatische Definition der Ähnlichkeit vor. So wurde es möglich, die Eigenschaften der Ähnlichkeit zu untersuchen, unabhängig davon, wie genau sie in einer bestimmten Situation spezifiziert ist: der Abstand zwischen Objekten, das Zusammentreffen einiger Merkmale oder die subjektive Meinung des Betrachters.

Lassen Sie uns eine Erläuterung des Konzepts der Ähnlichkeit oder Ununterscheidbarkeit einführen.



Definition . Die Beziehung T auf der Menge M wird als Toleranzverhältnis oder Toleranz bezeichnet, wenn sie reflexiv und symmetrisch ist.



Die Richtigkeit dieser Definition ergibt sich aus der Tatsache, dass das Objekt offensichtlich nicht von sich selbst zu unterscheiden ist und natürlich wie sich selbst aussieht (dies gibt die Reflexivität der Beziehung). Die Reihenfolge, in der zwei Objekte betrachtet werden, hat keinen Einfluss auf die endgültige Schlussfolgerung über ihre Ähnlichkeit oder Unähnlichkeit (Symmetrie).

Aus dem Beispiel mit visueller Ununterscheidbarkeit von Punkten in der Ebene geht hervor, dass die Transitivität der Toleranz nicht für alle Objektpaare erfüllt ist.



Es ist auch klar, dass, da Ähnlichkeit ein Sonderfall der Ähnlichkeit ist, Äquivalenz ein Sonderfall der Toleranz sein muss. Wenn wir die Definitionen von Äquivalenz und Toleranz vergleichen, sind wir davon überzeugt, dass dies der Fall ist. Das philosophische Prinzip: "Das Besondere ist reicher als das Allgemeine" wird klar bestätigt. Eine zusätzliche Eigenschaft - Transitivität - macht einige der Toleranzbeziehungen gleichwertig. Zwei Zwillinge sind sich so ähnlich, dass sie ohne Risiko Prüfungen für einander ablegen können. Wenn jedoch zwei Schüler nur gleich sind, ist ein solcher Trick zwar machbar, aber riskant.



Jedes Element der Menge enthält bestimmte Informationen zu ähnlichen Elementen. Aber nicht alle Informationen, wie bei identischen Elementen. Hier sind unterschiedliche Informationsgrade möglich, die ein Element in Bezug auf ein anderes enthält.



Betrachten wir Beispiele, bei denen Toleranz auf unterschiedliche Weise festgelegt wird.



Beispiel 2 . Die Menge M besteht aus russischen Wörtern mit vier Buchstaben - im Nominativ gebräuchliche Substantive. Wir werden solche Wörter ähnlich nennen, wenn sie sich um nicht mehr als einen Buchstaben unterscheiden. Das bekannte Problem "Aus einer Fliege einen Elefanten machen" wird wie folgt formuliert. Suchen Sie eine Folge von Wörtern, die mit dem Wort "Fliege" beginnen und mit dem Wort "Elefant" enden. Dabei handelt es sich um zwei benachbarte Wörter, die im Sinne der gerade gegebenen Definition ähnlich sind. Die Lösung für dieses Problem:



fly - mura - tura - tara - kara - kare - cafe - kaffr - musher - skiff - hook - croc - time - stock - stöhnen - elefant.



Beispiel 3... Sei p eine natürliche Zahl. Wir bezeichnen mit Sp die Sammlung aller nicht leeren Teilmengen der Menge M = {1, 2, ..., p}. Die Beziehung "mindestens ein gemeinsames Element haben" auf der Menge Sp ist eine Toleranzbeziehung. Dann werden zwei solche Teilmengen als tolerant bezeichnet, wenn sie mindestens ein gemeinsames Element haben. Es ist leicht zu erkennen, dass die Reflexivität und Symmetrie der Beziehung erfüllt ist.



Die Menge Sp heißt (p –1) -dimensionaler Simplex. Dieses Konzept verallgemeinert das Konzept eines Segments, Dreiecks und Tetraeders auf den mehrdimensionalen Fall. Die Zahlen 1, 2, 3, ..., p werden als Eckpunkte eines Simplex interpretiert. Zwei-Element-Teilmengen - als Kanten, Drei-Elemente-Teilmengen - als flache (zweidimensionale) Flächen, andere k-Element-Teilmengen - als (k –1) -dimensionale Flächen. Die Anzahl aller Elemente (Teilmengen) von Sp beträgt 2 ^p - 1.



Toleranz von Teilmengen (Flächen) bedeutet, dass sie gemeinsame Eckpunkte haben.



Definition . Die Menge M mit der darauf angegebenen Toleranzrelation τ wird als Toleranzraum bezeichnet. Somit ist der Toleranzraum ein Paar (M, τ).



Beispiel 4 . Der Toleranzraum Sp kann auf den unendlichen Fall verallgemeinert werden. Sei H eine beliebige Menge. Wenn SH die Sammlung aller nicht leeren Teilmengen der Menge H ist, dann ist die Toleranzbeziehung T auf SH durch die Bedingung gegeben: X T Y wenn X∩Y ≠ ≠. Die Symmetrie und Reflexivität dieser Beziehung ist offensichtlich. Der SH-Raum wird als <H, T> bezeichnet und als "universeller" Toleranzraum bezeichnet.



Beispiel 5... Sei p eine natürliche Zahl. Wir bezeichnen mit Bp die Menge aller Punkte des p-dimensionalen Raums, deren Koordinaten gleich 0 oder 1 sind. Die Toleranz in Bp wird durch die Regel angegeben: xτy, wenn x und y mindestens eine zusammenfallende Komponente (Koordinate) enthalten. Die Gesamtzahl der Elemente in Bp beträgt 2 ^r . Für jedes Element x = (a1, a2, ..., ap) aus der Menge Bp gibt es nur ein Element y = (1 - a1, 1 - a2, ..., 1 - ap), das dafür nicht tolerant ist.

Offensichtlich besteht Bp aus allen Eckpunkten des p-dimensionalen Würfels.



Beispiel 6 . Betrachten Sie den Toleranzraum, dessen Komponenten reale Werte annehmen.



Dies ist insbesondere die Menge aller Punkte x = (a1, a2) in der kartesischen Ebene. Die Toleranz von zwei Punkten bedeutet, dass sie mindestens eine Koordinate haben. Dies bedeutet, dass zwei tolerante Punkte entweder auf einer gemeinsamen Vertikalen oder auf einer gemeinsamen Horizontalen liegen.



Für andere Werte von p kann der Raum als eine Menge von Punkten im p-dimensionalen Raum interpretiert werden. Insbesondere kann jedes Element x als eine numerische Funktion betrachtet werden, die auf der Menge der natürlichen Zahlen {1, 2, 3, ...} definiert ist und jeder natürlichen Zahl i: 1 ≤ i ≤ p eine reelle Zahl ai (eine endliche Zahlenfolge) zuweist. Dann bedeutet die Toleranz zweier Funktionen x und y, dass sie mindestens an einem Punkt gleich sind.

Teilordnungsbeziehungen und ihre Analyse

Geordnete Mengen sind Mengen mit einer darauf eingeführten Ordnungsbeziehung. Definition . Eine Menge A und eine binäre Ordnungsrelation R darauf (≤) werden als teilweise geordnet bezeichnet, wenn die Relation (wie in BOE) drei Bedingungen enthält (eine Bedingung ist unterschiedlich):

• Reflexivität ≤ x ≤ A (xRx); (Antireflexivität ∀ x A ¬ (xRx));
• Antisymmetrie ∀ , y ∊ (Ry yRx → x = y);
• Transitivität ∀ x, y, z ∊ A (xRy & yRz → xRz).

Mit einer Antireflexionshaltung entsteht eine strikte Teilordnung . Die Menge B (A) aller Teilmengen der Menge A, geordnet nach Einbeziehung von Elementen, ist eine teilweise geordnete Menge (PN). Die teilweise geordnete Menge (B (A), ⊆) wird oft als Boolescher Wert bezeichnet.



Ein Element x∊A POZA A deckt ein Element y∊A ab, wenn x> y und es kein z∊A gibt, so dass x> z> y. Ein Elementpaar x, y∊A heißt vergleichbar, wenn x ≥ y oder x ≤ y ist.



Wenn in PLA A jedes Paar seiner Elemente vergleichbar ist, wird A als linear geordnete Menge oder Kette bezeichnet .



Wenn eine Pest B nur aus miteinander unvergleichbaren Elementen besteht, wird die Menge B als Antichain bezeichnet... Eine Kette in PLAG A wird als gesättigt bezeichnet, wenn sie nicht in einer anderen Kette als sich selbst verschachtelt werden kann.



Die gesättigte Antichain ist ähnlich definiert. Eine maximale Kette (Antichain) ist eine Kette (Antichain), die die maximale Anzahl von Elementen enthält.



Ein Element m eines PLM A wird als minimal bezeichnet, wenn es kein anderes Element ∊ in als m gibt und so, dass ≤ m ist. Ein Element M einer Pest A heißt maximal, wenn es kein Element x "größer" als M gibt, außer M und so, dass x ≥ M.



Ein Element y∊A einer Pest A heißt maximal, wenn ∀ x∊ A x ≤ y ist. Das Element y∊ A PLAG A heißt das kleinstewenn ∀ x∊A x ≥ y. Für die größten und kleinsten Elemente ist es üblich, die Bezeichnungen 1 bzw. 0 zu verwenden. Sie werden universelle Grenzen genannt. Jede Pest A hat höchstens ein kleinstes und höchstens ein größtes Element. In PLA A sind mehrere minimale und mehrere maximale Elemente zulässig. Es ist

zweckmäßig, ein endliches PLA A mit einem Hasse-Diagramm darzustellen , bei dem es sich um einen gerichteten Graphen handelt. Seine Scheitelpunkte sind über die Ebenen des Diagramms verteilt und entsprechen Elementen von A, und jeder Bogen geht nach unten und wird genau dann gezeichnet, wenn das Element vorhanden ist x∊A deckt das Element y∊A ab.



Transitive Bögen werden nicht gezeichnet. Hasse-Diagrammebenen enthalten Elemente des gleichen Ranges, d.h. verbunden mit den minimalen Elementen des PCM durch Pfade gleicher Länge (entsprechend der Anzahl der Bögen).

Sei B eine nicht leere Teilmenge von PLA A, dann heißt ein Element x∊A die exakte Obergrenze (bezeichnet mit sup _A B) der Menge B, wenn x ≥ y für alle y∊B ist und wenn es sich aus der Wahrheit der Beziehung z ≥ y für alle y∊B ergibt, dass z ≥ x.



Die genaue Untergrenze (bezeichnet mit inf _A B) einer Menge B ist ein Element x∊A, wenn x ≤ y für alle y∊B ist und wenn die Bedingung z ≤ y für alle y∊B impliziert, dass z ≤ x ist.



Beispiel 7 . Es werden zwei endliche numerische Mengen

A = {0,1,2, ..., 21} und B = {6,7,10,11} angegeben.



CHUM (A, ≤) ist in Abb. 1 dargestellt. 2.26.



Die Sammlung B ^Δ aller Obergrenzen für wird als oberer Kegel für die Menge B bezeichnet. Die Sammlung ^∇von allen unteren Flächen für B wird der untere Kegel für B genannt.







Jede Teilmenge von PLA ist auch PLP in Bezug auf die geerbte Reihenfolge. Wenn die Menge die größten und / oder kleinsten Elemente enthält, sind sie maximal (minimal). Das Gegenteil ist nicht wahr. Boolean hat ein einzelnes kleinstes (Ø) und ein einzelnes größtes Element.



In der gegebenen Menge ist das kleinste Element Null (0) und stimmt mit dem einzigen minimalen Element überein, und das größte Element existiert nicht. Die maximalen Elemente sind {19, 20, 21}. Die genaue Obergrenze für B = {6,7,10,11} ist Element 21 (dies ist das kleinste Element im oberen Kegel).



Allgemeine Situation. Es sei eine Menge gegeben, deren Kardinalität ******* ist. Lassen Sie uns von allen binären Beziehungen, die auf dieser Menge möglich sind, die binären Präferenzrelationen und die damit verbundenen strengen partiellen Ordnungsrelationen herausgreifen.



Teilordnungen unterscheiden sich von strengen Teilordnungen nur dadurch, dass sie zusätzliche Elemente (in der Matrixdarstellung - Diagonale) (ai, ai) = 1, i = 1 (1) n und die Anzahl dieser und anderer Ordnungen im vollständigen Satz von Beziehungen enthalten das Gleiche. Bisher wurden keine Abhängigkeiten (Formel, Algorithmus) gefunden, die es ermöglichen würden, die Anzahl der Teilaufträge für n zu berechnen und aufzulisten.



Verschiedene Autoren haben die folgenden Ergebnisse durch direkte Berechnung ermittelt und veröffentlicht (Tabelle 2.12).



Die Computerexperimente des Autors ermöglichten es, nicht nur die Anzahl, sondern auch die Form (Darstellung) von Teilordnungen bei unterschiedlichen Potenzen des Multiplikator-Trägers von Beziehungen zu erhalten. Der Drucker verschluckte sich daran, so große Listen zu drucken, aber nicht nur Schönheit erfordert Opfer, die Wissenschaft lehnt sie auch nicht ab.





Tabelle 2.12 zeigt: n = | A | - die Kardinalität des Set-Carriers; die zweite Zeile ist die Anzahl aller binären Beziehungen auf der Menge A; und weiter



| In (n) | - die Anzahl der Klassen nichtisomorpher Beziehungen;

| (n) | - die Anzahl der Beziehungen teilweiser Ordnung;

| Gn (n) | - die Anzahl der Klassen nicht isomorpher Teilordnungsbeziehungen;

| Gl (n) | = n! - die Anzahl der linearen Ordnungsrelationen.



Wie Sie sehen können, gibt es in der Tabelle für kleines n, zum Beispiel G (n = 4), nur 219 Daten, deren Werte mit zunehmendem n sehr schnell wachsen, was ihre quantitative (und qualitative) direkte Analyse selbst mit einem Computer erheblich erschwert.



Die folgende Tabelle zeigt die Möglichkeit, Γ (n = 4) aller Teilordnungen aus dem Schnittpunkt jeder mit jeder linearen Teilordnung zu erzeugen. In dieser Situation entstehen jedoch redundante (sich wiederholende), die für kleine n manuell abgeschnitten (neu berechnet) werden können. Es stellt sich heraus, 300 Matrizen, aber es gibt nur 219 PLs unter ihnen. Allgemeine Formeln wurden nicht erhalten. Auf globaler Ebene ist die Situation ähnlich, obwohl ich keine Veröffentlichungen über PLM-Transfers westlicher Autoren gesehen habe. Unsere Algorithmen sind völlig originell und wegweisend.



Ich werde ein mögliches Schema zur Lösung des Problems der Aufzählung der Elemente des Raums von Teilordnungen (n = 4) geben.





Die Menge der strengen Teilordnungen in der lexikografischen Reihenfolge der linearen Ordnungen (n = 4) wird durch ihre gegenseitige Überschneidung erzeugt.







Mehrere wichtige Definitionen der Mathematik für Konzepte, die häufig in Texten enthalten sind.



Definition . Ein geschlossenes Intervall ist eine Menge der Form {x: a ≤ x ≤ b}; Ein offenes Intervall ist nicht geschlossen, und ein halboffenes Intervall, dh eine Menge der Form {x: a <x ≤ b}, wobei a <b, oder der Form {x: a ≤ x <b} ist weder offen noch geschlossen.



Definition . Die Grenze eines beliebigen Intervalls einer reellen Linie in der üblichen Topologie reeller Zahlen besteht nur aus den Enden dieses Intervalls, unabhängig davon, ob dieses Intervall offen, geschlossen oder halb offen ist. Die Grenze der Menge rationaler Zahlen sowie die Grenze der Menge aller irrationalen Zahlen ist die gesamte Menge reeller Zahlen.



Definition... Jede linear geordnete Menge, in der jede nicht leere Teilmenge das kleinste Element enthält, wird als gut geordnet bezeichnet.



Definition . Eine Familie R wird genau dann als Kette (manchmal Turm, Nest) bezeichnet, wenn für eines ihrer Elemente A und B entweder A ⊂ B oder B ⊂ A gilt. Diese Bedingung entspricht der Behauptung, dass die Familie R durch Aufnahme oder in der akzeptierten Terminologie linear geordnet ist - dass die Familie R zusammen mit der Inklusionsbeziehung eine Kette ist.



P r und n c und p m a bis s und m al n über s t und H a ​​u s d o r f a. Für jede Familie von Mengen A und jedes Nest R, das durch Elemente der Familie A gebildet wird, gibt es ein maximales Nest M in A, das R enthält.



Ein wichtiger Satz über Mengen und ihre Familien (J. L. Kelly "Allgemeine Topologie", S. 55).

Satz. (a) PRINTSIpMACKSIMALN über ELEMENT. Ein maximales Element in der Familie A einer Menge liegt vor, wenn für jedes Nest in A ein Element in A vorhanden ist, das ein beliebiges Element dieses Nestes enthält.



(b) PRINTSIpMINIMALNO ELEMENT. Das kleinste Element in einer Familie A existiert, wenn für jedes Nest in A ein Element in A vorhanden ist, das in jedem Element dieses Nestes enthalten ist.



(c) Lemma T yuk und. Jede Familie von Sätzen endlichen Charakters hat ein maximales Element.



(d) LEMMA KURATOVSKOGO. Jede Kette in einem (teilweise) geordneten Satz ist in einer maximalen Kette enthalten.



(e) Tsons Lemma. Wenn jede Kette einer teilweise geordneten Menge oben begrenzt ist, hat diese Menge ein maximales Element.



(f) A bis s und o m und eine Wahl. Sei Xα eine nicht leere Menge für jedes Element a aus der Menge der Indizes A. Dann existiert eine Funktion c auf A, so dass c (a) ∊ Xα für jedes a aus A ist.



(G) Postulat Tserm elo. Für jede Familie A disjunkter nicht leerer Mengen gibt es eine Menge C, so dass die AUC für jedes A von A aus genau einem Punkt besteht.



(h) DRUCKE und P in voller Reihenfolge der Lieferung. Jedes Set kann komplett bestellt werden.