Seturi disjuncte - Disjoint sets

Două seturi disjuncte.

În matematică , se spune că două seturi sunt seturi disjuncte dacă nu au niciun element în comun. În mod echivalent, două mulțimi disjuncte sunt mulțimi a căror intersecție este mulțimea goală . De exemplu, {1, 2, 3} și {4, 5, 6} sunt seturi disjuncte, în timp ce {1, 2, 3} și {3, 4, 5} nu sunt disjuncte. O colecție de mai mult de două seturi se numește disjunctă dacă oricare două seturi distincte ale colecției sunt disjuncte.

Generalizări

O colecție disjunctă de seturi

Această definiție a seturilor disjuncte poate fi extinsă la o familie de seturi : familia este disjunsă în perechi sau disjunsă reciproc dacă este oricând . Alternativ, unii autori folosesc termenul disjunct pentru a se referi și la această noțiune. ${\ displaystyle (A_ {i}) _ {i \ în I}}$${\ displaystyle A_ {i} \ cap A_ {j} = \ varnothing}$${\ displaystyle i \ neq j}$

Pentru familii, noțiunea de disjuncție pereche sau disjuncție reciprocă este uneori definită într-o manieră subtil diferită, prin aceea că sunt permise membri identici repetați: familia este disjunsă în perechi dacă ori de câte ori (fiecare două seturi distincte din familie sunt disjuncte). De exemplu, colecția de seturi {{0,1,2}, {3,4,5}, {6,7,8}, ...} este disjunctă, la fel ca și setul {{...− 2 , 0,2,4, ...}, {...− 3, −1,1,3,5 }} din cele două clase de paritate ale numerelor întregi; familia cu 10 membri nu este disjunctă (deoarece clasele numerelor pare și impare sunt prezente fiecare de cinci ori), dar este disjunsă în perechi în conformitate cu această definiție (din moment ce unul primește o intersecție ne-goală a doi membri când cei doi sunt aceeași clasă). ${\ 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 \}}}$

Se spune că două seturi sunt seturi aproape disjuncte dacă intersecția lor este mică într-un anumit sens. De exemplu, două mulțimi infinite a căror intersecție este o mulțime finită se poate spune că sunt aproape disjuncte.

În topologie , există diverse noțiuni de seturi separate cu condiții mai stricte decât disjuncția. De exemplu, două seturi pot fi considerate a fi separate atunci când au închideri disjuncte sau cartiere disjuncte . În mod similar, într-un spațiu metric , seturile separate pozitiv sunt seturi separate de o distanță diferită de zero .

Intersecții

Separarea a două mulțimi sau a unei familii de mulțimi poate fi exprimată în termeni de intersecții de perechi de ele.

Două mulțimi A și B sunt disjuncte dacă și numai dacă intersecția lor este mulțimea goală . Din această definiție rezultă că fiecare set este disjunct de setul gol și că setul gol este singurul set care este disjunct de la sine. ${\ displaystyle A \ cap B}$

Dacă o colecție conține cel puțin două seturi, condiția ca colecția să fie disjunctă implică faptul că intersecția întregii colecții este goală. Cu toate acestea, o colecție de seturi poate avea o intersecție goală fără a fi disjunctă. În plus, în timp ce o colecție de mai puțin de două seturi este disjunctă în mod trivial, întrucât nu există perechi de comparat, intersecția unei colecții dintr-un set este egală cu acel set, care poate fi ne-gol. De exemplu, cele trei seturi {{1, 2}, {2, 3}, {1, 3}} au o intersecție goală, dar nu sunt disjuncte. De fapt, nu există două seturi disjuncte în această colecție. De asemenea, familia de seturi goale este separată în perechi.

O familie Helly este un sistem de seturi în cadrul cărora singurele subfamilii cu intersecții goale sunt cele care sunt despărțite în perechi. De exemplu, intervalele închise ale numerelor reale formează o familie Helly: dacă o familie de intervale închise are o intersecție goală și este minimă (adică nici o subfamilie a familiei nu are o intersecție goală), aceasta trebuie să fie pereche disjunctă.

Uniuni și partiții disjuncte

O partiție a unui set X este orice colecție de seturi de non-gol disjuncte a căror uniune este X . Fiecare partiție poate fi descrisă în mod echivalent printr-o relație de echivalență , o relație binară care descrie dacă două elemente aparțin aceluiași set din partiție. Structurile de date set-disjunct și rafinarea partiției sunt două tehnici în informatică pentru menținerea eficientă a partițiilor unui set supuse, respectiv, operațiilor de unire care fuzionează două seturi sau operațiuni de rafinare care împart un set în două.

O unire disjunctă poate însemna unul dintre cele două lucruri. Cel mai simplu, poate însemna unirea seturilor care sunt disjuncte. Dar dacă două sau mai multe seturi nu sunt deja disjuncte, unirea lor disjunctă se poate forma modificând seturile pentru a le face disjuncte înainte de a forma uniunea seturilor modificate. De exemplu, două seturi pot fi disjuncte prin înlocuirea fiecărui element cu o pereche ordonată a elementului și o valoare binară care indică dacă aparține primului sau celui de-al doilea set. Pentru familiile de mai mult de două seturi, unul poate înlocui în mod similar fiecare element cu o pereche ordonată a elementului și indexul setului care îl conține.

Vezi si

• Teorema de separare a hiperplanului pentru seturi convexe disjuncte
• Evenimente care se exclud reciproc
• Relativ prime , numere cu seturi disjuncte de divizori primi
• Separoid
• Ambalarea seturilor, problema găsirii celei mai mari subfamilii disjointe dintr-o familie de seturi

Referințe

linkuri externe

• Weisstein, Eric W. „Seturi disjuncte” . MathWorld .