Seturi disjuncte

În matematică , se spune că două mulțimi sunt disjunse sau disjunse , dacă nu au elemente în comun. În mod echivalent, mulțimile disjunse sunt mulțimi a căror intersecție este mulțimea goală [1] . De exemplu, {1, 2, 3} și {4, 5, 6} sunt mulțimi disjunse, în timp ce {1, 2, 3} și {3, 4, 5} nu sunt.

Generalizări

Definiția de mai sus a mulțimilor disjunctive poate fi extinsă la orice familie de mulțimi . O familie de mulțimi este disjunctivă în perechi (elementele sunt disjunctive în perechi ) dacă oricare două mulțimi din familie nu au elemente în comun [1] . De exemplu, setul de mulțimi {{1}, {2}, {3}, ... } este disjuns pe perechi.

Se spune că două mulțimi sunt aproape disjunse dacă intersecția lor este într-un fel mică. De exemplu, două mulțimi infinite a căror intersecție este o mulțime finită pot fi considerate aproape disjunctive [2] .

În topologie , există diferite notații pentru mulțimi separate cu condiții mai stricte decât fără intersecție. De exemplu, se spune că două seturi sunt separabile atunci când au închideri disjunse sau vecinătăți disjunse . În mod similar, într-un spațiu metric, mulțimile separate pozitiv sunt mulțimi separate printr-o distanță diferită de zero [3] .

Exemple

Încrucișări

Disjunctura de multimi sau familii de multimi poate fi exprimata in termeni de intersectii .

Două mulțimi A și B sunt disjunse dacă și numai dacă intersecția lor este o mulțime goală [1] . Din această definiție rezultă că orice mulțime este disjunctivă cu mulțimea goală, iar mulțimea goală este singura mulțime care este disjunctivă la sine [4] .

O familie F de mulțimi este disjunctivă perechi dacă pentru oricare două mulțimi din familie intersecția lor este goală [1] . Dacă o familie conține mai multe mulțimi, rezultă că intersecția tuturor mulțimilor din familie este goală. Cu toate acestea, o familie cu un singur set este, prin definiție, „disjunc în perechi” și, evident, poate avea o intersecție nevidă. În plus, o familie de mulțimi poate avea o intersecție goală, dar nu poate fi disjuns pe perechi [5] . De exemplu, trei mulțimi {{1, 2}, {2, 3}, {1, 3} } au o intersecție goală, dar nu sunt disjunse în perechi. De fapt, nu există două seturi disjunse în acest set. De asemenea, familia goală de mulțimi este disjunsă în perechi [6] .

O familie Helly  este un sistem de set în care numai subfamiliile cu intersecția goală sunt disjunse pe perechi. De exemplu, intervalele închise pe axa reală formează o familie Helly - dacă o familie de intervale închise are o intersecție goală și este minimă (adică nicio subfamilie nu are o intersecție goală), aceasta trebuie să fie disjunsă pe perechi [7] .

Uniri și partiții disjuncte

O partiție a unei mulțimi X este orice mulțime de mulțimi disjunse reciproc a căror unire este egală cu X [8] . Orice partiție poate fi descrisă în mod echivalent printr-o relație de echivalență , o relație binară care determină dacă două elemente aparțin aceleiași mulțimi în descompunere sau nu [8] . Sistemele de mulțimi disjuncte [9] și rafinarea partițiilor [10] sunt două tehnici în informatică pentru a trata eficient partițiile unui set de obiecte, respectiv, pentru operația de unire, care îmbină două mulțimi împreună, și operația de rafinare, care împarte un set în două...

O uniune disjunctă poate însemna două lucruri. În cel mai simplu caz, aceasta poate însemna unirea mulțimilor disjunctive [11] . Dar dacă două sau mai multe mulțimi nu sunt disjunse, uniunea lor disjunctă se poate forma prin modificarea mulțimilor [12] [13] . De exemplu, două mulțimi pot fi făcute disjunctive prin înlocuirea elementelor cu perechi ordonate de elemente și un index care determină dacă elementul aparține primului sau celui de-al doilea set [14] . Aceeași tehnică poate fi aplicată familiilor cu mai mult de două seturi [15] .

Vezi și

Note

  1. ↑ 1 2 3 4 Halmos, 1960 , p. cincisprezece.
  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. ↑ Vezi răspunsurile la întrebarea ″Este familia goală de seturi disjunctive perechi?″ Arhivat 20 octombrie 2020 la Wayback Machine
  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. ↑ În cartea lui Vavilov, unirea disjunctivă este înțeleasă doar în primul sens. Pentru unire în al doilea sens, se folosește termenul unire liberă , sumă liberă sau coprodus al mulțimilor .
  14. ↑ Monin și Hinchey, 2003 , p. 21.
  15. ↑ Lee, 2010 , p. 64.

Literatură

Link -uri