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

редактировать

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

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

Содержание

1 Обобщения
2 Пересечения
3 Непересекающиеся объединения и разделы
4 См. Также
5 Ссылки
6 Внешние ссылки

Обобщения

Непересекающаяся коллекция наборы

Это определение непересекающихся множеств может быть расширено до семейства множеств $(A i) i ∈ I {\ displaystyle (A_ {i}) _ {i \ in I}}$ ${\ displaystyle (A_ {i}) _ {i \ in I}}$ : семейство попарно не пересекается или попарно не пересекается, если $A i ∩ A j = ∅ {\ displaystyle A_ {i} \ cap A_ { j} = \ varnothing}$ ${\ displaystyle A_ {i} \ cap A_ {j } = \ varnothing}$ всякий раз, когда $i ≠ j {\ displaystyle i \ neq j}$ $i \ neq j$ . В качестве альтернативы некоторые авторы используют термин дизъюнктный для обозначения этого понятия.

Для семейств понятие попарно непересекающихся или взаимно непересекающихся иногда определяется несколько иначе, в том смысле, что допускаются повторяющиеся идентичные члены: семейство попарно не пересекается, если $A i ∩ A j = ∅ { \ displaystyle A_ {i} \ cap A_ {j} = \ varnothing}$ ${\ displaystyle A_ {i} \ cap A_ {j } = \ varnothing}$ всякий раз, когда $A i ≠ A j {\ displaystyle A_ {i} \ neq A_ {j}}$ ${\ displaystyle A_ {i} \ neq A_ {j}}$ (любые два различных набора в семействе не пересекаются). Например, набор наборов {{0,1,2}, {3,4,5}, {6,7,8},...} не пересекается, как и набор {{..., - 2,0,2,4,...}, {..., - 3, -1,1,3,5}} двух классов четности целых чисел; семейство $({n + 2 k ∣ k ∈ Z}) n ∈ {0, 1,…, 9} {\ displaystyle (\ {\, n + 2k \ mid k \ in \ mathbb {Z} \, \}) _ {n \ in \ {0,1, \ ldots, 9 \}}}$ ${\ displaystyle (\ {\, n + 2k \ mid k \ in \ mathbb {Z} \, \}) _ {n \ in \ { 0,1, \ ldots, 9 \}}}$ с 10 членами не является непересекающимся (потому что классы четных и нечетных чисел представлены каждый пять раз), но в соответствии с этим определением он попарно не пересекается (поскольку получается непустое пересечение двух членов только в том случае, если они являются одним и тем же классом).

Два множества называются почти непересекающимися множествами, если их пересечение в некотором смысле мало. Например, два бесконечных множества, пересечение которых является конечным множеством, могут быть названы почти не пересекающимися.

В топологии существуют различные понятия разделенных множеств с более строгими условиями, чем дизъюнктность. Например, два набора могут считаться разделенными, если они имеют непересекающиеся замыкания или непересекающиеся окрестности. Аналогично, в метрическом пространстве , положительно разделенные множества - это множества, разделенные ненулевым расстоянием .

Пересечения

Непересекаемость двух множеств или семейство множеств, может быть выражено через пересечения их пар.

Два набора A и B не пересекаются тогда и только тогда, когда их пересечение $A ∩ B {\ displaystyle A \ cap B}$ $A \ cap B$ является пустым набором. Из этого определения следует, что каждый набор не пересекается с пустым набором, и что пустой набор является единственным набором, который не пересекается с самим собой.

Если набор содержит не менее двух наборов, условие, что набор дизъюнктно означает, что пересечение всего набора пусто. Однако набор множеств может иметь пустое пересечение, не будучи непересекающимся. Кроме того, хотя набор из менее чем двух наборов тривиально не пересекается, поскольку нет пар для сравнения, пересечение набора из одного набора равно этому набору, который может быть непустым. Например, три набора {{1, 2}, {2, 3}, {1, 3}} имеют пустое пересечение, но не пересекаются. На самом деле в этом наборе нет двух непересекающихся множеств. Также пустое семейство множеств попарно не пересекается.

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

Непересекающиеся объединения и разбиения

A разбиение множества X - это любой набор взаимно непересекающихся непустых множеств, объединение которых равно X.Каждый раздел может быть эквивалентно описан отношением эквивалентности, двоичным отношением, которое описывает, принадлежат ли два элемента одному и тому же набору в разделе. Структуры данных с непересекающимися наборами и уточнение разделов - это два метода в компьютерной науке для эффективного обслуживания разделов набора, подвергающегося, соответственно, операциям объединения, которые объединяют два набора, или операциям уточнения, которые разделяют один набор на два.

A непересекающееся объединение может означать одно из двух. Проще говоря, это может означать объединение не пересекающихся множеств. Но если два или более наборов еще не являются непересекающимися, их непересекающееся объединение может быть сформировано путем модификации наборов, чтобы сделать их не пересекающимися перед формированием объединения модифицированных наборов. Например, два набора могут быть разделены путем замены каждого элемента упорядоченной парой элемента и двоичного значения, указывающего, принадлежит ли он первому или второму набору. Для семейств, состоящих из более чем двух наборов, можно аналогичным образом заменить каждый элемент упорядоченной парой элемента и индекса набора, который его содержит.

См. Также

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

Ссылки

Внешние ссылки

Вайсштейн, Эрик У. «Непересекающиеся множества». MathWorld.