Beziehung (Mathematik) - Relation (mathematics)
Transitive binäre Beziehungen | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
homogene Beziehung sein transitiv : für alle , wenn und dann , und es gibt zusätzliche Eigenschaften , dass eine homogene Beziehung erfüllen kann. | gibt an, dass die Eigenschaft der Spalte von der Definition des Zeilenbegriffs (ganz links) erforderlich ist. Zum Beispiel erfordert die Definition einer Äquivalenzrelation, dass diese symmetrisch ist. Alle Definitionen erfordern stillschweigend die
In der Mathematik ist eine binäre Beziehung über die Mengen X und Y eine Teilmenge des kartesischen Produkts X × Y ; das heißt, es ist eine Menge geordneter Paare ( x , y ) bestehend aus Elementen x in X und y in Y . Es kodiert das allgemeine Konzept der Relation: Ein Element x ist mit einem Element y verbunden , und zwar genau dann, wenn das Paar ( x , y ) zu der Menge geordneter Paare gehört, die die binäre Relation definiert . Eine binäre Relation ist der am besten untersuchte Spezialfall n = 2 einer n- ären Relation über Mengen X 1 , ..., X n , die eine Teilmenge des kartesischen Produkts X 1 × ... × X n ist .
Ein Beispiel für eine binäre Relation ist die " Divisions " - Relation über die Menge der Primzahlen und die Menge der ganzen Zahlen , bei der jede Primzahl p auf jede ganze Zahl z bezogen ist , die ein Vielfaches von p ist , aber nicht auf eine ganze Zahl , die nicht ist ein Vielfaches von p . In dieser Beziehung zum Beispiel bezieht sich die Primzahl 2 auf Zahlen wie -4, 0, 6, 10, aber nicht auf 1 oder 9, ebenso wie die Primzahl 3 auf 0, 6 und 9, aber nicht zu 4 oder 13.
Binäre Beziehungen werden in vielen Zweigen der Mathematik verwendet, um eine Vielzahl von Konzepten zu modellieren. Dazu zählen unter anderem:
- das " ist größer als ", " ist gleich " und "teilt" Relationen in der Arithmetik ;
- das " ist deckungsgleich mit " der Beziehung in der Geometrie ;
- die Beziehung "ist benachbart zu" in der Graphentheorie ;
- die "ist orthogonal zu"-Beziehung in der linearen Algebra .
Eine Funktion kann als eine spezielle Art von binärer Relation definiert werden. Binäre Relationen werden auch in der Informatik stark verwendet , beispielsweise in einem relationalen Datenbankmanagementsystem (RDBMS).
Eine binäre Relation über die Mengen X und Y ist ein Element der Potenzmenge von X × Y . Da die letztere Menge nach Inklusion (⊆) geordnet ist , hat jede Relation einen Platz im Gitter der Teilmengen von X × Y . Eine binäre Relation ist entweder eine homogene Relation oder eine heterogene Relation, je nachdem ob X = Y ist oder nicht.
Da Relationen Mengen sind, können sie mit Mengenoperationen manipuliert werden, einschließlich Vereinigung , Schnitt und Komplementation , und erfüllen die Gesetze einer Algebra von Mengen . Darüber hinaus stehen Operationen wie die Umkehrung einer Relation und die Komposition von Relationen zur Verfügung, die den Gesetzen einer Relationsrechnung genügen , für die es Lehrbücher von Ernst Schröder , Clarence Lewis und Gunther Schmidt gibt . Eine tiefere Analyse von Beziehungen beinhaltet die Zerlegung in Teilmengen, die Konzepte genannt werden , und deren Einordnung in ein vollständiges Gitter .
In einigen Systemen der axiomatischen Mengenlehre werden Relationen auf Klassen erweitert , die Verallgemeinerungen von Mengen sind. Diese Erweiterung wird unter anderem benötigt, um die Konzepte von "ist ein Element von" oder "ist eine Teilmenge von" in der Mengenlehre zu modellieren, ohne auf logische Inkonsistenzen wie Russells Paradox zu stoßen .
Die Begriffe Korrespondenz , dyadische Beziehung und zweistellige Relation sind Synonyme für binäre Beziehung, obwohl einige Autoren die Bezeichnung „binary relation“ für jede Teilmenge eines karthesischen Produkts verwenden X × Y ohne Bezug auf X und Y , und behält den Begriff „Korrespondenz " für eine binäre Relation bezüglich X und Y .
Definition
Gegebenen Mengen X und Y ist das kartesische Produkt X × Y definiert als {( x , y ) | x ∈ X und y ∈ Y } , und seine Elemente werden geordnete Paare genannt.
Eine binäre Relation R über den Mengen X und Y ist eine Teilmenge von X × Y . Der Satz X wird , um die genannte Domäne oder Gruppe von Weggang von R und die Gruppe Y die codomain oder Gruppe von Ziel von R . Um die Auswahlmöglichkeiten der Mengen X und Y zu spezifizieren , definieren einige Autoren eine binäre Relation oder Korrespondenz als ein geordnetes Tripel ( X , Y , G ) , wobei G eine Teilmenge von X × Y ist , die als Graph der binären Relation bezeichnet wird. Die Aussage ( x , y ) R lautet „ x ist R-bezogen auf y “ und wird in Infixnotation als xRy geschrieben . Der Definitionsbereich oder aktiven Domäne von R ist die Menge aller x , so dass xRy für mindestens eine y . Die codomain der Definition , aktiven codomain , Bild oder Bereich von R ist die Menge aller y , so dass xRy für mindestens ein x . Der Körper von R ist die Vereinigung seines Definitionsbereichs und seines Definitionsbereichs.
Wenn X = Y ist , wird eine binäre Beziehung als homogene Beziehung (oder Endoration ) bezeichnet. Ansonsten handelt es sich um ein heterogenes Verhältnis .
Bei einer binären Beziehung ist die Reihenfolge der Elemente wichtig; wenn x ≠ y dann kann yRx unabhängig von xRy wahr oder falsch sein . Beispiel: 3 teilt 9, aber 9 teilt nicht 3.
Beispiel
EIN
B ′
|
Ball | Wagen | Puppe | Tasse |
---|---|---|---|---|
John | + | − | − | − |
Maria | − | − | + | − |
Venus | − | + | − | − |
EIN
B
|
Ball | Wagen | Puppe | Tasse |
---|---|---|---|---|
John | + | − | − | − |
Maria | − | − | + | − |
Ian | − | − | − | − |
Venus | − | + | − | − |
Das folgende Beispiel zeigt, dass die Wahl der Codomäne wichtig ist. Angenommen, es gibt vier Objekte A = {ball, car, doll, cup} und vier Personen B = {John, Mary, Ian, Venus} . Eine mögliche Relation auf A und B ist die Relation "im Besitz von", gegeben durch R = {(ball, John), (doll, Mary), (car, Venus)} . Das heißt, John besitzt den Ball, Mary besitzt die Puppe und Venus besitzt das Auto. Niemand besitzt den Pokal und Ian besitzt nichts, siehe 1. Beispiel. Als Menge beinhaltet R Ian nicht, und daher hätte R als Teilmenge von A × {John, Mary, Venus} angesehen werden können , dh als Relation über A und {John, Mary, Venus}, siehe 2. Beispiel. Während die zweite Beispielrelation surjektiv ist (siehe unten ), ist dies bei der ersten nicht der Fall.
Spezielle Arten von binären Beziehungen
Einige wichtige Typen von binären Beziehungen R über die Mengen X und Y sind unten aufgeführt.
Einzigartigkeitseigenschaften:
- Injektiv (auch links-eindeutig genannt )
- Für alle x , z ∈ X und alle y ∈ Y , wenn xRy und zRy dann x = z . Für solche Beziehung, { Y } wird als einen Primärschlüssel von R . Zum Beispiel sind die grünen und blauen binären Relationen im Diagramm injektiv, aber die rote nicht (da sie sowohl -1 als auch 1 zu 1 bezieht), noch die schwarze (da sie sowohl -1 als auch 1 zu 0) bezieht .
- Funktional (auch rechts-eindeutig , rechts-definit oder univalent genannt )
- Für alle x ∈ X und alle y , z ∈ Y , wenn xRy und xRz dann y = z . Eine solche binäre Beziehung wird als Partialfunktion bezeichnet . Für eine solche Relation wird { X } Primärschlüssel von R genannt . Zum Beispiel sind die roten und grünen binären Beziehungen im Diagramm funktional, aber die blaue nicht (da sie 1 mit -1 und 1 in Beziehung setzt) und die schwarze (da sie 0 mit -1 und 1 in Beziehung setzt). .
- Eins zu eins
- Injektiv und funktional. Zum Beispiel ist die grüne Binärrelation im Diagramm eins zu eins, die roten, blauen und schwarzen jedoch nicht.
- Eins-zu-viele
- Injektiv und nicht funktionsfähig. Zum Beispiel ist die blaue Binärrelation im Diagramm eins-zu-viele, die roten, grünen und schwarzen jedoch nicht.
- Viele-zu-eins
- Funktionell und nicht injektiv. Zum Beispiel ist die rote Binärrelation im Diagramm viele-zu-eins, die grünen, blauen und schwarzen jedoch nicht.
- Viel zu viel
- Weder injektiv noch funktionell. Zum Beispiel ist die schwarze Binärrelation im Diagramm viele zu viele, die roten, grünen und blauen jedoch nicht.
Totalitätseigenschaften (nur definierbar, wenn Domäne X und Codomäne Y angegeben sind):
- Seriell (auch Links-Total genannt )
- Für alle x in X existiert ein y in Y , so dass xRy . Mit anderen Worten, der Bereich der Definition von R gleich X . Diese Eigenschaft, obwohl von einigen Autoren auch als total bezeichnet , unterscheidet sich von der Definition von verbunden ( von einigen Autoren auch als total bezeichnet ) im Abschnitt Eigenschaften . Eine solche binäre Beziehung wird als mehrwertige Funktion bezeichnet . Zum Beispiel sind die roten und grünen Binärbeziehungen im Diagramm seriell, aber die blaue nicht (da sie sich nicht auf eine reelle Zahl bezieht), noch die schwarze (da sie sich nicht auf eine reelle Zahl bezieht) ).
- Surjektiv (auch richtig-total oder auf genannt )
- Für alle y in Y existiert ein x in X , so dass xRy . In anderen Worten, die codomain der Definition von R gleich Y . Zum Beispiel sind die grünen und blauen Binärbeziehungen im Diagramm surjektiv, aber die rote nicht (da sie keine reelle Zahl auf −1 bezieht) und die schwarze (da sie keine reelle Zahl auf 2 . bezieht) ).
Eindeutigkeits- und Gesamtheitseigenschaften (nur definierbar, wenn Domain X und Codomain Y angegeben sind):
- Eine Funktion
- Eine binäre Beziehung, die funktional und seriell ist. Beispielsweise sind die roten und grünen Binärbeziehungen im Diagramm Funktionen, die blauen und schwarzen jedoch nicht.
- Eine Injektion
- Eine injektive Funktion. Zum Beispiel ist die grüne Binärrelation im Diagramm eine Injektion, die roten, blauen und schwarzen jedoch nicht.
- Eine Surjektion
- Eine surjektive Funktion. Zum Beispiel ist die grüne Binärrelation im Diagramm eine Surjektion, die roten, blauen und schwarzen jedoch nicht.
- Eine Bijektion
- Eine Funktion, die injektiv und surjektiv ist. Zum Beispiel ist die grüne Binärrelation im Diagramm eine Bijektion, die roten, blauen und schwarzen jedoch nicht.
Operationen auf binären Beziehungen
Union
Wenn R und S binäre Relationen über Mengen X und Y sind, dann ist R ∪ S = {( x , y ) | xRy oder xSy } ist die Vereinigungsrelation von R und S über X und Y .
Das Identitätselement ist die leere Relation. Zum Beispiel ist ≤ die Vereinigung von < und =, und ≥ ist die Vereinigung von > und =.
Überschneidung
Wenn R und S binäre Relationen über Mengen X und Y sind, dann ist R ∩ S = {( x , y ) | xRy und xSy } ist die Schnittrelation von R und S über X und Y .
Das Identitätselement ist die universelle Relation. Zum Beispiel ist die Relation "ist durch 6 teilbar" der Schnittpunkt der Relationen "ist durch 3 teilbar" und "ist durch 2 teilbar".
Komposition
Wenn R eine binäre Beziehung über die Mengen X und Y ist und S eine binäre Beziehung über die Mengen Y und Z ist, dann ist S ∘ R = {( x , z ) | es existiert y ∈ Y , so dass xRy und YSZ } (auch bezeichnet durch R ; S ) ist die Zusammensetzung Beziehung von R und S in X und Z .
Das Identitätselement ist die Identitätsrelation. Die Reihenfolge der R und S in der Bezeichnung S ∘ R , verwendet hier stimmt der Standardnotations um Zusammensetzung von Funktionen . Zum Beispiel ergibt die Komposition "ist Mutter von" ∘ "ist Eltern von" "ist Großeltern mütterlicherseits von", während die Komposition "ist Eltern von" ∘ "ist Mutter von" ergibt "ist Großmutter von". Für den ersteren Fall, wenn x der Elternteil von y und y die Mutter von z ist , dann ist x der mütterliche Großelternteil von z .
Umgekehrt
Wenn R eine binäre Relation über den Mengen X und Y ist, dann ist R T = {( y , x ) | xRy } ist die umgekehrte Relation von R über Y und X .
Zum Beispiel ist = die Umkehrung von sich selbst, ebenso wie ≠, und < und > sind die Umkehrung des jeweils anderen, ebenso wie ≤ und ≥. Eine binäre Relation ist genau dann gleich ihrer Umkehrung, wenn sie symmetrisch ist .
Ergänzen
Wenn R eine binäre Beziehung über die Mengen X und Y ist, dann ist R = {( x , y ) | nicht xRy } (auch bezeichnet durch R oder ¬ R das ist) komplementäre Beziehung von R über X und Y .
Beispiel : = und ≠ sind jeweils Komplement des anderen, wie sind ⊆ und ⊈, ⊇ und ⊉ und ∈ und ∉ und für insgesamt Aufträge , auch <und ≥, und> und ≤.
Das Komplement der umgekehrten Relation R T ist die Umkehrung des Komplements:
Wenn X = Y , hat das Komplement folgende Eigenschaften:
- Ist eine Relation symmetrisch, so ist es auch das Komplement.
- Das Komplement einer reflexiven Relation ist irreflexiv – und umgekehrt.
- Das Komplement einer strengen schwachen Ordnung ist eine totale Vorbestellung – und umgekehrt.
Beschränkung
Wenn R eine binäre homogene Relation über einer Menge X ist und S eine Teilmenge von X ist, dann ist R | S = {( x , y ) | xRy und x ∈ S und y ∈ S } ist der Restriktionsbeziehung vonRzuSüberX.
Wenn R eine binäre Relation über den Mengen X und Y ist und wenn S eine Teilmenge von X ist, dann ist R | S = {( x , y ) | xRy und x ∈ S } ist derLinksrestriktionsbeziehung vonRzuSüberXundY.
Wenn R eine binäre Relation über den Mengen X und Y ist und wenn S eine Teilmenge von Y ist, dann ist R | S = {( x , y ) | xRy und y ∈ S } ist derrechtsbeschränkende Beziehung vonRzuSüberXundY.
Wenn eine Relation reflexiv , irreflexiv, symmetrisch , antisymmetrisch , asymmetrisch , transitiv , total , trichotom , eine partielle Ordnung , totale Ordnung , strenge schwache Ordnung , totale Vorordnung (schwache Ordnung) oder eine Äquivalenzrelation ist , dann sind es auch ihre Restriktionen.
Die transitive Schließung einer Restriktion ist jedoch eine Teilmenge der Restriktion der transitiven Schließung, dh im Allgemeinen ungleich. Beschränkt man beispielsweise die Beziehung " x ist Eltern von y " auf Frauen, so ergibt sich die Beziehung " x ist Mutter von Frau y "; seine transitive Schließung verbindet eine Frau nicht mit ihrer Großmutter väterlicherseits. Auf der anderen Seite ist die transitive Schließung von "ist Eltern von" "ist Vorfahre von"; seine Beschränkung auf Frauen bezieht eine Frau mit ihrer Großmutter väterlicherseits.
Auch die verschiedenen Konzepte der Vollständigkeit (nicht zu verwechseln mit "Gesamtheit") übertragen sich nicht auf Einschränkungen. Über den reellen Zahlen ist beispielsweise eine Eigenschaft der Relation ≤, dass jede nichtleere Teilmenge S von R mit einer oberen Schranke in R eine kleinste obere Schranke (auch Supremum genannt) in R hat . Für die rationalen Zahlen ist dieses Supremum jedoch nicht notwendigerweise rational, so dass dieselbe Eigenschaft nicht für die Beschränkung der Beziehung ≤ auf die rationalen Zahlen gilt.
Eine binäre Relation R über den Mengen X und Y heißt {{em|enthalten in einer Relation S über X und Y , geschriebenwenn R eine Teilmenge von S ist , das heißt für alleundwenn xRy , dann xSy . Wenn R in S enthalten ist und S in R enthalten ist , dannheißen R und S gleich geschrieben R = S . Wenn R in enthalten ist S aber S nicht in enthaltenen R , dann R wird gesagt, dasskleiner alsS, geschrieben R ⊊ S . Bei denrationalen Zahlenist beispielsweise die Beziehung > kleiner als ≥ und gleich der Zusammensetzung> ∘ >.
Homogenes Verhältnis
Eine homogene Relation (auch Endoration genannt ) über eine Menge X ist eine binäre Relation über X und sich selbst, dh sie ist eine Teilmenge des kartesischen Produkts X × X . Sie wird auch einfach eine (binäre) Relation über X genannt . Ein Beispiel für eine homogene Beziehung ist die Verwandtschaftsbeziehung , bei der die Beziehung über Menschen besteht.
Eine homogene Relation R über einer Menge X kann mit einem gerichteten einfachen Graphen identifiziert werden , der Schleifen zulässt , oder, wenn er symmetrisch ist , mit einem ungerichteten einfachen Graphen, der Schleifen zulässt , wobei X die Eckenmenge und R die Kantenmenge ist (es gibt eine Kante von einer Ecke x zu einer Ecke y genau dann, wenn xRy ). Sie wird als Adjazenzrelation des Graphen bezeichnet.
Die Menge aller homogenen Relationen über einer Menge X ist die Menge 2 X × X, die eine Boolesche Algebra ist, die durch die Involution der Abbildung einer Relation auf ihre umgekehrte Relation erweitert wurde . Betrachtet man die Zusammensetzung von Relationen als binäre Operation auf , bildet sie eine Halbgruppe mit Involution .
Besondere homogene Beziehungen
Einige wichtige besondere homogene Beziehungen über einer Menge X sind:
- Die leere Beziehung
- E = ∅ ⊆ X × X ;
- Die universelle Beziehung
- U = X × X ;
- Die Identitätsbeziehung
- Ich = {( x , x ) | x ∈ X } .
Für beliebige Elemente x und y von X :
- xEy gilt nie;
- xUy gilt immer;
- xIy gilt genau dann, wenn x = y ist .
Eigenschaften
Einige wichtige Eigenschaften, die eine homogene Relation R über einer Menge X haben kann, sind:
- Reflexiv
- für alle x ∈ X , xRx . Zum Beispiel ist ≥ eine reflexive Beziehung, aber > nicht.
- Irreflexiv (oder streng )
- für alle x ∈ X , nicht xRx . Zum Beispiel ist > eine irreflexive Relation, ≥ jedoch nicht.
Die vorherigen 2 Alternativen sind nicht erschöpfend; zB ist die rote Binärrelation y = x 2 aus dem Abschnitt § Spezielle Arten von Binärrelationen weder irreflexiv noch reflexiv, da sie das Paar (0, 0) bzw. nicht (2, 2) enthält .
- Symmetrisch
- für alle x , y ∈ X , wenn xRy dann yRx . Zum Beispiel, „ist ein Blut Verwandter“ ist eine symmetrische Beziehung, da x eine Blut Verwandter ist y , wenn und nur wenn y ein Blut Verwandter ist x .
- Antisymmetrisch
- für alle x , y ∈ X , wenn xRy und yRx dann x = y . ist beispielsweise eine antisymmetrische Beziehung; so ist >, aber leer (die Bedingung in der Definition ist immer falsch).
- Asymmetrisch
- für alle x , y ∈ X , wenn xRy dann nicht yRx . Eine Relation ist genau dann asymmetrisch, wenn sie sowohl antisymmetrisch als auch irreflexiv ist. Zum Beispiel ist > eine asymmetrische Beziehung, ≥ jedoch nicht.
Auch hier sind die vorherigen 3 Alternativen bei weitem nicht erschöpfend; als Beispiel über den natürlichen Zahlen ist die durch x > 2 definierte Relation xRy weder symmetrisch noch antisymmetrisch, geschweige denn asymmetrisch.
- Transitiv
- für alle x , y , z ∈ X , wenn xRy und yRz dann xRz . Eine transitive Relation ist genau dann irreflexiv, wenn sie asymmetrisch ist. Zum Beispiel ist "ist Vorfahre von" eine transitive Beziehung, während "ist Eltern von" dies nicht ist.
- Dicht
- für alle x , y ∈ X , so dass xRy , existiert ein z ∈ X , so dass xRz und zRy . Dies wird in dichten Ordnungen verwendet .
- In Verbindung gebracht
- für alle x , y ∈ X , wenn x ≠ y dann xRy oder yRx . Diese Eigenschaft wird manchmal "total" genannt, was sich von den Definitionen von "total" unterscheidet, die im Abschnitt Spezielle Typen von binären Beziehungen angegeben sind .
- Stark verbunden
- für alle x , y ∈ X , xRy oder yRx . Diese Eigenschaft wird manchmal "total" genannt, was sich von den Definitionen von "total" unterscheidet, die im Abschnitt Spezielle Typen von binären Beziehungen angegeben sind .
- Trichotom
- für alle x , y ∈ X gilt genau eines von xRy , yRx oder x = y . Zum Beispiel ist > eine trichotome Relation, während die Relation "dividiert" über die natürlichen Zahlen dies nicht ist.
- Seriell (oder links insgesamt )
- für alle x ∈ X gibt es einige y ∈ X , so dass xRy . Zum Beispiel ist > eine serielle Beziehung über die ganzen Zahlen. Aber es ist keine serielle Beziehung über die positiven ganzen Zahlen, denn es gibt kein y in den positiven ganzen Zahlen mit 1 > y . < ist jedoch eine serielle Beziehung über die positiven ganzen Zahlen, die rationalen Zahlen und die reellen Zahlen. Jede reflexive Relation ist seriell: Wählen Sie für ein gegebenes x y = x .
- Fundiert
- jede nichtleere Teilmenge S von X enthält ein minimales Element bezüglich R . Begründetheit impliziert die absteigende Kettenbedingung ( dh es kann keine unendliche Kette ... x n R ... Rx 3 Rx 2 Rx 1 existieren). Wird das Axiom der abhängigen Wahl angenommen, sind beide Bedingungen äquivalent.
- Vorbestellen
- Eine Relation, die reflexiv und transitiv ist.
- Gesamtvorbestellung (auch lineare Vorbestellung oder schwache Bestellung )
- Eine Relation, die reflexiv, transitiv und verbunden ist.
- Teilbestellung (auch Bestellung )
- Eine Relation, die reflexiv, antisymmetrisch und transitiv ist.
- Strenge Teilordnung (auch strenge Ordnung )
- Eine Relation, die irreflexiv, antisymmetrisch und transitiv ist.
- Gesamtordnung (auch lineare Ordnung , einfache Ordnung oder Kette )
- Eine Relation, die reflexiv, antisymmetrisch, transitiv und verbunden ist.
- Strenge Gesamtordnung (auch strenge lineare Ordnung , strenge einfache Ordnung oder strenge Kette )
- Eine Beziehung, die irreflexiv, antisymmetrisch, transitiv und verbunden ist.
- Partielle Äquivalenzrelation
- Eine symmetrische und transitive Relation.
- Äquivalenzrelation
- Eine Relation, die reflexiv, symmetrisch und transitiv ist. Es ist auch eine symmetrische, transitive und serielle Relation, da diese Eigenschaften Reflexivität implizieren.
Betrieb
Wenn R eine homogene Beziehung über eine Menge X ist, dann ist jede der folgenden eine homogene Beziehung über X :
- Reflexverschluss
- R = , definiert als R = = {( x , x ) | x ∈ X } ∪ R oder die kleinste reflexive Beziehung über X, die R enthält . Dies kann als gleich dem Schnitt aller reflexiven Relationen, die R enthalten, nachgewiesen werden .
- Reflexive Reduktion
- R ≠ , definiert als R ≠ = R \ {( x , x ) | x ∈ X } oder die größte irreflexive Relation über X in enthaltenen R .
- Transitive Schließung
- R + , definiert als die kleinste transitive Beziehung über X, die R enthält . Dies ist gleich dem Schnittpunkt aller transitiven Beziehungen, die R enthalten .
- Reflexive transitive Schließung
- R *, definiert als R * = ( R + ) = , die kleinste Vorbestellung, die R enthält .
- Reflexiver transitiver symmetrischer Verschluss
- R ≡ , definiert als die kleinste Äquivalenzrelation über X mit R .
Alle im Abschnitt § Operationen auf binäre Relationen definierten Operationen gelten auch für homogene Relationen.
Homogene Beziehungen nach Eigentum Reflexivität Symmetrie Transitivität Verbundenheit Symbol Beispiel Gerichteter Graph → Ungerichteter Graph Symmetrisch Abhängigkeit Reflexiv Symmetrisch Turnier Irreflexiv Antisymmetrisch Hackordnung Vorbestellen Reflexiv Jawohl ≤ Präferenz Gesamtvorbestellung Reflexiv Jawohl Jawohl ≤ Teilbestellung Reflexiv Antisymmetrisch Jawohl ≤ Teilmenge Strenge Teilordnung Irreflexiv Antisymmetrisch Jawohl < Strenge Teilmenge Gesamtbestellung Reflexiv Antisymmetrisch Jawohl Jawohl ≤ Alphabetischer Reihenfolge Strenge Gesamtbestellung Irreflexiv Antisymmetrisch Jawohl Jawohl < Strenge alphabetische Reihenfolge Partielle Äquivalenzrelation Symmetrisch Jawohl Äquivalenzrelation Reflexiv Symmetrisch Jawohl , ≡ Gleichberechtigung
Beispiele
-
Auftragsbeziehungen , einschließlich strenger Aufträge :
- Größer als
- Größer als oder gleich wie
- Weniger als
- Weniger als oder gleich
- Teilt (gleichmäßig)
- Teilmenge von
-
Äquivalenzbeziehungen :
- Gleichberechtigung
- Parallel zu (für affine Räume )
- Ist in Bijektion mit
- Isomorph
-
Toleranzbeziehung , eine reflexive und symmetrische Beziehung:
- Abhängigkeitsbeziehung , eine endliche Toleranzbeziehung
- Unabhängigkeitsbeziehung , das Komplement einer Abhängigkeitsbeziehung
- Verwandtschaftsbeziehungen
Siehe auch
- Abstraktes Umschreibsystem
- Additive Relation , ein mehrwertiger Homomorphismus zwischen Modulen
- Kategorie von Relationen , eine Kategorie mit Mengen als Objekten und heterogenen binären Relationen als Morphismen
- Confluence (Begriffsumschreibung) diskutiert einige ungewöhnliche, aber grundlegende Eigenschaften binärer Beziehungen
- Korrespondenz (algebraische Geometrie) , eine binäre Beziehung, die durch algebraische Gleichungen definiert wird
- Hasse-Diagramm , ein grafisches Mittel zur Darstellung einer Ordnungsbeziehung
- Inzidenzstruktur , eine heterogene Beziehung zwischen Punktmenge und Linien
- Logik der Verwandten , eine Theorie der Beziehungen von Charles Sanders Peirce
- Ordnungstheorie , untersucht Eigenschaften von Ordnungsbeziehungen
Anmerkungen
Verweise
Literaturverzeichnis
- Codd, Edgar Frank (1990). Das relationale Modell für das Datenbankmanagement: Version 2 (PDF) . Boston: Addison-Wesley . ISBN 978-0201141924.
- Enderton, Herbert (1977). Elemente der Mengenlehre . Boston: Akademische Presse . ISBN 978-0-12-238440-0.
- Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander (2000). Monoide, Acts und Kategorien: mit Anwendungen für Kranzprodukte und Grafiken . Berlin: De Gruyter . ISBN 978-3-11-015248-7.
- Peirce, Charles Sanders (1873). "Beschreibung einer Notation für die Logik der Relativen, resultierend aus einer Erweiterung der Konzepte der Booleschen Logik der Logik" . Memoiren der American Academy of Arts and Sciences . 9 (2): 317–178. doi : 10.2307/25058006 . hdl : 2027/hvd.32044019561034 . JSTOR 25058006 . Abgerufen 2020-05-05 .
- Schmidt, Günther (2010). Relationale Mathematik . Cambridge: Cambridge University Press . ISBN 978-0-521-76268-7.