Disjunktní množiny

V matematice se o dvou množinách říká, že jsou disjunktní nebo disjunktní , pokud nemají společné prvky. Ekvivalentně jsou disjunktní množiny množiny, jejichž průnikem je prázdná množina [1] . Například {1, 2, 3} a {4, 5, 6} jsou disjunktní množiny, zatímco {1, 2, 3} a {3, 4, 5} nikoli.

Zobecnění

Výše uvedená definice disjunktních množin může být rozšířena na jakoukoli rodinu množin . Rodina množin je párově disjunktní (prvky jsou párově disjunktní ), pokud jakékoli dvě množiny v rodině nemají žádné společné prvky [1] . Například množina množin { {1}, {2}, {3}, ... } je párově disjunktní.

O dvou množinách se říká, že jsou téměř disjunktní , pokud je jejich průsečík v určitém smyslu malý. Například dvě nekonečné množiny , jejichž průnikem je konečná množina , lze považovat za téměř disjunktní [2] .

V topologii existují různé zápisy pro oddělené množiny s přísnějšími podmínkami než bez průniku. Například se říká, že dvě sady jsou oddělitelné, když mají nesouvislé uzávěry nebo nesouvislé sousedství . Podobně v metrickém prostoru jsou kladně oddělené množiny množiny oddělené nenulovou vzdáleností [3] .

Příklady

Přejezdy

Nesouvislost množin nebo rodin množin lze vyjádřit pomocí průniků .

Dvě množiny A a B jsou disjunktní právě tehdy, když je jejich průsečík prázdná množina [1] . Z této definice vyplývá, že jakákoli množina je disjunktivní s prázdnou množinou a prázdná množina je jedinou množinou, která je sama se sebou disjunktivní [4] .

Rodina F množin je párově disjunktivní, jestliže pro libovolné dvě množiny v rodině je jejich průsečík prázdný [1] . Pokud rodina obsahuje více než jednu množinu, znamená to, že průsečík všech množin v rodině je prázdný. Rodina s jednou množinou je však podle definice „párově disjunktní“ a zjevně může mít neprázdný průsečík. Kromě toho může mít rodina množin prázdný průsečík, ale nesmí být párově disjunktní [5] . Například tři množiny { {1, 2}, {2, 3}, {1, 3} } mají prázdný průsečík, ale nejsou párově disjunktní. Ve skutečnosti v této množině nejsou žádné dvě disjunktní množiny. Také prázdná rodina množin je párově disjunktní [6] .

Rodina Helly  je souborový systém, ve kterém jsou pouze podrodiny s prázdným průnikem párově disjunktní. Například uzavřené intervaly na reálné ose tvoří rodinu Helly – pokud má rodina uzavřených intervalů prázdný průsečík a je minimální (to znamená, že žádná podrodina nemá prázdný průsečík), musí být párově disjunktní [7] .

Disjunktní spojení a oddíly

Rozdělení množiny X je jakákoliv množina vzájemně disjunktních množin, jejichž sjednocení je rovno X [8] . Jakýkoli oddíl lze ekvivalentně popsat relací ekvivalence , binární relací , která určuje, zda dva prvky patří do stejné množiny v rozkladu nebo ne [8] . Systémy disjunktních množin [9] a zpřesnění rozdělení [10] jsou dvě techniky v informatice pro efektivní řešení rozdělení množiny objektů, respektive pro operaci sjednocení, která spojuje dvě množiny dohromady, a operaci zpřesnění, který rozděluje jednu sadu na dvě. .

Disjunktní spojení může znamenat dvě věci. V nejjednodušším případě to může znamenat sjednocení disjunktivních množin [11] . Pokud však dvě nebo více množin není disjunktních, lze jejich disjunktní sjednocení vytvořit úpravou množin [12] [13] . Například dvě množiny mohou být disjunktní nahrazením prvků uspořádanými dvojicemi prvků a indexem, který určuje, zda prvek patří do první nebo druhé množiny [14] . Stejnou techniku ​​lze aplikovat na rodiny s více než dvěma sadami [15] .

Viz také

Poznámky

  1. ↑ 1 2 3 4 Halmos, 1960 , str. patnáct.
  2. ↑ Halbeisen, 2011 , s. 184.
  3. ↑ Copson, 1988 , str. 62.
  4. ↑ Oberste-Vorth, Mouzakitis, Lawrence, 2012 , str. 59.
  5. ↑ Smith, Eggen, St. Andrew, 2010 , str. 95.
  6. ↑ Podívejte se na odpovědi na otázku ″Je prázdná rodina množin párově disjunktivní?″ Archivováno 20. října 2020 na Wayback Machine
  7. ↑ Bollobás, 1986 , s. 82.
  8. ↑ 1 2 Halmos, 1960 , str. 28.
  9. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , str. 498–524.
  10. ↑ Paige, Tarjan, 1987 , str. 973–989.
  11. ↑ Ferland, 2008 , s. 45.
  12. ↑ Arbib, Kfoury, Moll, 1981 , str. 9.
  13. ↑ Ve Vavilovově knize je disjunktivní spojení chápáno pouze v prvním smyslu. Pro sjednocení ve druhém smyslu se používá termín free union , free sum , nebo coproduct of sets .
  14. ↑ Monin a Hinchey, 2003 , str. 21.
  15. ↑ Lee, 2010 , str. 64.

Literatura

Odkazy