Непересекающиеся множества

Два непересекающихся множества.

В математике говорят, что два множества не пересекаются или дизъюнктны, если у них нет общих элементов. Эквивалентно, непересекающиеся множества — это множества, пересечение которых является пустым множествомШаблон:Sfn. Например, {1, 2, 3} и {4, 5, 6} непересекающиеся множества, в то время как {1, 2, 3} и {3, 4, 5} таковыми не являются.

Обобщения

Попарно независимые семейства множеств

Приведённое определение непересекающихся множеств может быть расширено на любое Шаблон:Не переведено 5. Семейство множеств попарно дизъюнктно (элементы попарно не пересекаются), если любые два множества в семействе не имеют общих элементовШаблон:Sfn. Например, набор множеств Шаблон:Nowrap попарно дизъюнктен.

Говорят, что два множества Шаблон:Не переведено 5, если их пересечение в некотором смысле мало. Например, два бесконечных множества, пересечение которых является конечным множеством, можно считать почти не пересекающимисяШаблон:Sfn.

В топологии существуют различные обозначения разделённых множеств с более строгими условиями, чем отсутствие пересечения. Например, два множества считаются разделимыми, когда они имеют непересекающиеся замыкания или непересекающиеся окрестности. Подобно этому, в метрическом пространстве Шаблон:Не переведено 5 — это множества, разделённые ненулевым расстояниемШаблон:Sfn.

Примеры

• 
  Множество, состоящее из барабана и гитары, не пересекается с множеством, состоящим из карты и книги
• 
  Семейство попарно непересекающиеся множеств
• 
  Семейство множеств, не являющихся попарно непересекающимися

Пересечения

Дизъюнктность множеств или семейств множеств можно выразить в терминах пересечений.

Два множества A и B дизъюнктны тогда и только тогда, когда их пересечение $A\cap B$ является пустым множествомШаблон:Sfn. Из этого определения следует, что любое множество дизъюнктно с пустым множеством и пустое множество является единственным множеством, дизъюнктным самому себеШаблон:Sfn.

Семейство F множеств попарно дизъюнктно, если для любых двух множеств в семействе их пересечение пустоШаблон:Sfn. Если семейство содержит более одного множества, отсюда следует, что пересечение всех множеств семейства пусто. Однако семейство, состоящее из одного множества, по определению является «попарно дизъюнктным» и очевидно может иметь непустое пересечение. Кроме того, семейство множеств может иметь пустое пересечение, но не быть попарно дизъюнктноШаблон:Sfn. Например, три множества Шаблон:Nowrap имеют пустое пересечение, но они не попарно дизъюнктны. Фактически нет двух дизъюнктных множеств в этом наборе. Также пустое семейство множеств является попарно дизъюнктным.

Семейство Хелли — это система множеств, в которой только подсемейства с пустым пересечением попарно дизъюнктны. Например, замкнутые интервалы на вещественной оси образуют семейство Хелли — если семейство замкнутых интервалов имеет пустое пересечение и минимально (то есть никакое подсемейство не имеет пустое пересечение), оно должно быть попарно дизъюнктноШаблон:Sfn.

Дизъюнктные объединения и разбиения

Разбиение множества X — это любой набор взаимно дизъюнктных множеств, объединение которых равно XШаблон:Sfn. Любое разбиение можно эквивалентно описать отношением эквивалентности, бинарным отношением, определяющим, принадлежат два элемента одному и тому же множеству в разложении или нетШаблон:Sfn. Системы непересекающихся множествШаблон:Sfn и Шаблон:Не переведено 5Шаблон:Sfn — две техники в информатике для эффективной работы с разбиениями набора объектов, соответственно, для операции объединения, которая сливает вместе два множества, и операции измельчения, которая разбивает одно множество на два.

Дизъюнктное объединение может означать две вещи. В наиболее простом случае это может означать объединение дизъюнктных множествШаблон:Sfn. Но если два или более множеств не дизъюнктны, их дизъюнктное объединение может быть образовано путём модификации множествШаблон:Sfn. Например, два множества могут быть сделаны дизъюнктыми путём замены элементов упорядоченными парами элемента и индекса, определяющего, какому множеству принадлежит элемент – первому или второмуШаблон:Sfn. Та же техника может быть применена для семейств из более чем двух множествШаблон:Sfn.

См. также

• Теорема о разделяющей гиперплоскости для непересекающихся выпуклых множеств
• Несовместимые события
• Взаимно простые числа, числа с непересекающимися множествами простых делителей
• Упаковка множеств, задача нахождения наибольшего дизъюнктного подсемейства семейства множеств

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:MathWorld