Diszjunkt halmazok

A matematikában két halmazt diszjunktnak vagy diszjunktnak mondunk , ha nincs közös elemük. Ezzel egyenértékűen a diszjunkt halmazok olyan halmazok, amelyek metszéspontja az üres halmaz [1] . Például az {1, 2, 3} és a {4, 5, 6} diszjunkt halmazok, míg az {1, 2, 3} és a {3, 4, 5} nem.

Általánosítások

A diszjunkt halmazok fenti definíciója kiterjeszthető bármely halmazcsaládra . Egy halmazcsalád páronként diszjunktív (az elemek páronként diszjunkt ), ha a család bármely két halmazának nincs közös eleme [1] . Például a { {1}, {2}, {3}, ... } halmazok páronként diszjunkt.

Két halmazt majdnem diszjunktnak mondunk , ha a metszéspontjuk bizonyos értelemben kicsi. Például két végtelen halmaz , amelyek metszéspontja véges halmaz , szinte diszjunktnak tekinthető [2] .

A topológiában különféle jelölések léteznek az elválasztott halmazokra , amelyek szigorúbb feltételekkel rendelkeznek, mint metszéspont nélkül. Például két halmazról akkor beszélünk, ha szétválasztható, ha nem összefüggő lezárásaik vagy szomszédságaik vannak . Hasonlóképpen a metrikus térben a pozitívan elválasztott halmazok olyan halmazok, amelyeket nem nulla távolság választ el [3] .

Példák

Crossings

A halmazok vagy halmazcsaládok diszjunktsága metszéspontokkal fejezhető ki .

Két A és B halmaz akkor és csak akkor diszjunkt, ha metszéspontja üres halmaz [1] . Ebből a definícióból következik, hogy bármely halmaz diszjunktív az üres halmazzal, és az üres halmaz az egyetlen halmaz, amely diszjunktív önmagával szemben [4] .

Egy F halmazcsalád páronként diszjunktív, ha a család bármely két halmazának metszéspontja üres [1] . Ha egy család egynél több halmazt tartalmaz, ebből az következik, hogy a család összes halmazának metszéspontja üres. Az egyhalmazú család azonban definíció szerint "páronként diszjunkt", és nyilvánvalóan lehet egy nem üres metszéspontja. Ezenkívül egy halmazcsaládnak lehet üres metszéspontja, de nem lehet páronként diszjunkt [5] . Például három { {1, 2}, {2, 3}, {1, 3} } halmaznak van üres metszéspontja, de nincsenek páronként diszjunktak. Valójában nincs két diszjunkt halmaz ebben a halmazban. Ezenkívül az üres halmazcsalád páronként diszjunkt [6] .

A Helly család  egy halmazrendszer, amelyben csak az üres metszésponttal rendelkező alcsaládok vannak páronként diszjunktak. Például a valós tengelyen lévő zárt intervallumok Helly családot alkotnak - ha egy zárt intervallumcsaládnak van üres metszéspontja és minimális (vagyis egyetlen alcsaládnak sincs üres metszéspontja), akkor páronként diszjunktnak kell lennie [7] .

Diszjunkt uniók és partíciók

Az X halmaz partíciója olyan kölcsönösen diszjunkt halmazok halmaza, amelyek uniója egyenlő X [8] . Bármely partíció ekvivalens módon leírható egy ekvivalenciarelációval , egy bináris relációval , amely meghatározza, hogy két elem ugyanahhoz a halmazhoz tartozik-e a dekompozícióban vagy sem [8] . A diszjunkt halmazrendszerek [9] és a partíciófinomítás [10] két technika a számítástechnikában egy objektumhalmaz partícióinak hatékony kezelésére, illetve a két halmazt összevonó egyesítő művelethez, illetve a finomítási művelethez, ami az egyik készletet kettéosztja..

A széthúzott unió két dolgot jelenthet. Ez a legegyszerűbb esetben diszjunktív halmazok unióját jelentheti [11] . De ha két vagy több halmaz nem diszjunkt, akkor diszjunkt uniójuk a halmazok módosításával alakítható ki [12] [13] . Például két halmaz szétválasztható úgy, hogy az elemeket rendezett elempárokra és egy indexre cseréljük, amely meghatározza, hogy az elem az első vagy a második halmazba tartozik-e [14] . Ugyanez a technika alkalmazható kettőnél több halmazt tartalmazó családoknál [15] .

Lásd még

Jegyzetek

  1. ↑ 1 2 3 4 Halmos, 1960 , p. tizenöt.
  2. ↑ Halbeisen, 2011 , p. 184.
  3. ↑ Copson, 1988 , p. 62.
  4. ↑ Oberste-Vorth, Mouzakitis, Lawrence, 2012 , p. 59.
  5. ↑ Smith, Eggen, St. Andrew, 2010 , p. 95.
  6. ↑ Tekintse meg a ″Disjunktív páronként az üres halmazcsalád?″ kérdésre adott válaszokat. Archiválva : 2020. október 20. a Wayback Machine -nél
  7. ↑ Bollobás, 1986 , p. 82.
  8. ↑ 1 2 Halmos, 1960 , p. 28.
  9. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , p. 498–524.
  10. ↑ Paige, Tarjan, 1987 , p. 973–989.
  11. ↑ Ferland, 2008 , p. 45.
  12. ↑ Arbib, Kfoury, Moll, 1981 , p. 9.
  13. ↑ Vavilov könyvében a diszjunktív unió csak az első értelemben értendő. A második értelemben vett egyesülésre a szabad unió , a szabad összeg vagy a halmazok együttterméke kifejezést használjuk .
  14. ↑ Monin és Hinchey, 2003 , p. 21.
  15. ↑ Lee, 2010 , p. 64.

Irodalom

Linkek