Disjunkte Sätze - Disjoint sets

Zwei unzusammenhängende Sätze.

In der Mathematik nennt man zwei Mengen disjunkte Mengen, wenn sie kein gemeinsames Element haben . Äquivalent sind zwei disjunkte Mengen Mengen, deren Schnittmenge die leere Menge ist . {1, 2, 3} und {4, 5, 6} sind beispielsweise disjunkte Mengen, während {1, 2, 3} und {3, 4, 5} nicht disjunkt sind. Eine Sammlung von mehr als zwei Mengen wird als disjunkt bezeichnet, wenn zwei verschiedene Mengen der Sammlung disjunkt sind.

Verallgemeinerungen

Eine unzusammenhängende Sammlung von Sets

Diese Definition von disjunkten Mengen kann auf eine Familie von Mengen erweitert werden : Die Familie ist paarweise disjunkt oder gegenseitig disjunkt, wenn immer . Alternativ verwenden einige Autoren auch den Begriff disjunkt, um auf diesen Begriff zu verweisen. ${\displaystyle (A_{i})_{i\in I}}$${\displaystyle A_{i}\cap A_{j}=\varnothing}$${\displaystyle i\neq j}$

Für Familien wird der Begriff paarweise disjunkt oder wechselseitig disjunkt manchmal auf subtile Weise anders definiert, indem wiederholte identische Mitglieder erlaubt sind: Die Familie ist paarweise disjunkt, wenn wann immer (jede zwei verschiedene Mengen in der Familie sind disjunkt). Zum Beispiel ist die Menge der Mengen { {0,1,2}, {3,4,5}, {6,7,8}, ... } disjunkt, ebenso wie die Menge { {...−2 ,0,2,4,...}, {...−3,−1,1,3,5 }} der beiden Paritätsklassen von ganzen Zahlen; die Familie mit 10 Gliedern ist nicht disjunkt (weil die Klassen der geraden und ungeraden Zahlen jeweils fünfmal vorhanden sind), aber sie ist nach dieser Definition paarweise disjunkt (da man nur dann eine nichtleere Schnittmenge zweier Glieder erhält, wenn die beiden die selbe Klasse). ${\displaystyle A_{i}\cap A_{j}=\varnothing}$${\displaystyle A_{i}\neq A_{j}}$${\displaystyle (\{n+2k\mid k\in\mathbb{Z}\})_{n\in\{0,1,\ldots,9\}}}$

Zwei Mengen werden als fast disjunkte Mengen bezeichnet, wenn ihre Schnittmenge in gewisser Weise klein ist. Zum Beispiel können zwei unendliche Mengen, deren Durchschnitt eine endliche Menge ist, als fast disjunkt bezeichnet werden.

In der Topologie gibt es verschiedene Begriffe von getrennten Mengen mit strengeren Bedingungen als Disjunktheit. Zum Beispiel können zwei Mengen als getrennt betrachtet werden, wenn sie disjunkte Abschlüsse oder disjunkte Nachbarschaften haben . In ähnlicher Weise in einem metrischen Raum , positiv getrennte Sätze sind Sätze von einem Nicht - Null getrennt Abstand .

Kreuzungen

Die Disjunktheit zweier Mengen oder einer Familie von Mengen kann durch Schnitte von Paaren derselben ausgedrückt werden.

Zwei Mengen A und B sind genau dann disjunkt, wenn ihr Durchschnitt die leere Menge ist . Aus dieser Definition folgt, dass jede Menge von der leeren Menge disjunkt ist und dass die leere Menge die einzige Menge ist, die von sich selbst disjunkt ist. ${\displaystyle A\cap B}$

Wenn eine Sammlung mindestens zwei Mengen enthält, bedeutet die Bedingung, dass die Sammlung disjunkt ist, dass die Schnittmenge der gesamten Sammlung leer ist. Eine Sammlung von Mengen kann jedoch eine leere Schnittmenge haben, ohne disjunkt zu sein. Während eine Sammlung von weniger als zwei Mengen trivialerweise disjunkt ist, da es keine zu vergleichenden Paare gibt, ist die Schnittmenge einer Sammlung von einer Menge gleich der Menge, die nicht leer sein kann. Zum Beispiel haben die drei Mengen { {1, 2}, {2, 3}, {1, 3} } einen leeren Schnittpunkt, sind aber nicht disjunkt. Tatsächlich gibt es in dieser Sammlung keine zwei getrennten Sets. Auch die leere Mengenfamilie ist paarweise disjunkt.

Eine Helly-Familie ist ein System von Mengen, in dem die einzigen Unterfamilien mit leeren Schnittpunkten diejenigen sind, die paarweise disjunkt sind. Zum Beispiel bilden die abgeschlossenen Intervalle der reellen Zahlen eine Helly-Familie: Wenn eine Familie abgeschlossener Intervalle einen leeren Durchschnitt hat und minimal ist (dh keine Unterfamilie der Familie hat einen leeren Durchschnitt), muss sie paarweise disjunkt sein.

Disjunkte Verbindungen und Partitionen

Eine Partition eines Satzes X ist eine beliebige Sammlung von untereinander disjunkten nicht leere Sätze , deren Vereinigung ist X . Jede Partition kann äquivalent durch eine Äquivalenzrelation beschrieben werden , eine binäre Relation , die beschreibt, ob zwei Elemente zu derselben Menge in der Partition gehören. Disjunkte-Mengen-Datenstrukturen und Partitionsverfeinerung sind zwei Techniken in der Informatik zum effizienten Verwalten von Partitionen einer Menge, die Vereinigungsoperationen unterliegen, die zwei Mengen zusammenführen, oder Verfeinerungsoperationen, die eine Menge in zwei aufteilen.

Eine disjunkte Vereinigung kann eines von zwei Dingen bedeuten. Am einfachsten kann es die Vereinigung von Mengen bedeuten, die disjunkt sind. Aber wenn zwei oder mehr Mengen nicht bereits disjunkt sind, kann ihre disjunkte Vereinigung gebildet werden, indem die Mengen modifiziert werden, um sie disjunkt zu machen, bevor die Vereinigung der modifizierten Mengen gebildet wird. Zum Beispiel können zwei Sätze disjunkt gemacht werden, indem jedes Element durch ein geordnetes Paar des Elements und einen Binärwert ersetzt wird, der anzeigt, ob es zum ersten oder zweiten Satz gehört. Bei Familien mit mehr als zwei Mengen kann man auf ähnliche Weise jedes Element durch ein geordnetes Paar des Elements und des Index der Menge, die es enthält, ersetzen.

Siehe auch

• Hyperebenen-Trennsatz für disjunkte konvexe Mengen
• Gegenseitig exklusive Veranstaltungen
• Relativ prim , Zahlen mit disjunkten Mengen von Primteilern
• Separoid
• Mengenpackung , das Problem, die größte disjunkte Unterfamilie einer Mengenfamilie zu finden

Verweise

Externe Links

• Weisstein, Eric W. "Disjoint Sets" . MathWorld .