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

Множества, не имеющие общих элементов

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

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

Обобщения

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

Это определение непересекающихся множеств может быть распространено на семейства множеств и индексированные семейства множеств. По определению, коллекция множеств называется семейством множеств (например , множеством мощности ). В некоторых источниках это множество множеств, в то время как другие источники допускают, что это будет мультимножество множеств, в котором некоторые множества повторяются. Индексированное семейство множеств по определению является функцией со значениями множества (то есть это функция, которая назначает множество каждому элементу в своей области), область определения которой называется ее индексным множеством (а элементы ее области называются индексами ). ${\displaystyle \left(A_{i}\right)_{i\in I},}$ ${\displaystyle A_{i}}$ ${\displaystyle i\in I}$ ${\displaystyle I}$

Существует два слегка отличающихся определения того, когда семейство множеств называется попарно непересекающимся . Согласно одному такому определению, семейство является непересекающимся, если каждые два множества в семействе либо идентичны, либо непересекающиеся. Это определение позволило бы попарно непересекающимся семействам множеств иметь повторяющиеся копии одного и того же множества. Согласно альтернативному определению, каждые два множества в семействе должны быть непересекающимися; повторяющиеся копии не допускаются. Те же два определения можно применить к индексированному семейству множеств: согласно первому определению, каждые два различных индекса в семействе должны называть множества, которые являются непересекающимися или идентичными, в то время как согласно второму определению каждые два различных индекса должны называть непересекающиеся множества. ^[2] Например, семейство множеств { {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, ... } является непересекающимся согласно обоим определениям, как и семейство { {..., −2, 0, 2, 4, ...}, {..., −3, −1, 1, 3, 5} } двух классов четности целых чисел. Однако семейство с 10 членами имеет пять повторений каждого из двух непересекающихся множеств, поэтому оно попарно непересекающееся согласно первому определению, но не согласно второму. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle (\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}}$

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

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

Пересечения

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

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

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

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

Несвязные объединения и разбиения

Разделом множества X называется любая совокупность взаимно непересекающихся непустых множеств, объединение которых равно X. ^[8] Каждое разделение может быть эквивалентно описано отношением эквивалентности — бинарным отношением , которое описывает, принадлежат ли два элемента одному и тому же множеству в разделе. [ ^8] Структуры данных непересекающихся множеств ^[9] и уточнение раздела ^[10] — это два метода в информатике для эффективного поддержания разделов множества, подвергаемых соответственно операциям объединения, которые объединяют два множества, или операциям уточнения, которые разбивают одно множество на два.

Непересекающееся объединение может означать одно из двух. Проще говоря, это может означать объединение множеств, которые не пересекаются. ^[11] Но если два или более множеств уже не являются непересекающимися, их непересекающееся объединение может быть сформировано путем изменения множеств так, чтобы они стали непересекающимися перед формированием объединения измененных множеств. ^[12] Например, два множества могут быть сделаны непересекающимися, заменив каждый элемент упорядоченной парой элемента и двоичным значением, указывающим, принадлежит ли он первому или второму множеству. ^[13] Для семейств из более чем двух множеств можно аналогичным образом заменить каждый элемент упорядоченной парой элемента и индексом множества, которое его содержит. ^[14]

Смотрите также

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

Ссылки

1. Halmos, PR (1960), Наивная теория множеств, Учебники по математике для студентов , Springer, стр. 15, ISBN 9780387900926.
2. Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2010), Переход к высшей математике, Cengage Learning, стр. 95, ISBN 978-0-495-56202-3.
3. Хальбейзен, Лоренц Дж. (2011), Комбинаторная теория множеств: с мягким введением в принуждение, монографии Springer по математике, Springer, стр. 184, ISBN 9781447121732.
4. Копсон, Эдвард Томас (1988), Метрические пространства, Cambridge Tracts in Mathematics, т. 57, Cambridge University Press, стр. 62, ISBN 9780521357326.
5. Оберсте-Форт, Ральф В.; Музакитис, Аристидес; Лоуренс, Бонита А. (2012), Мост к абстрактной математике, учебники MAA, Математическая ассоциация Америки, стр. 59, ISBN 9780883857793.
6. "Является ли пустое семейство множеств попарно непересекающимся?". Mathematics Stack Exchange . Получено 2024-10-10 .
7. Боллобаш, Бела (1986), Комбинаторика: системы множеств, гиперграфы, семейства векторов и комбинаторная вероятность, Cambridge University Press, стр. 82, ISBN 9780521337038.
8. Halmos (1960), стр. 28.
9. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2001), «Глава 21: Структуры данных для непересекающихся множеств», Введение в алгоритмы (второе издание), MIT Press, стр. 498–524, ISBN 0-262-03293-7.
10. Пейдж, Роберт; Тарьян, Роберт Э. (1987), «Три алгоритма уточнения разделов», SIAM Journal on Computing , 16 (6): 973–989, doi :10.1137/0216062, MR  0917035, S2CID  33265037.
11. Ферланд, Кевин (2008), Дискретная математика: Введение в доказательства и комбинаторику, Cengage Learning, стр. 45, ISBN 9780618415380.
12. Арбиб, Майкл А.; Кфури, А. Дж.; Молл, Роберт Н. (1981), Основы теоретической информатики , Серия AKM в Теоретической информатике: Тексты и монографии по информатике, Springer-Verlag, стр. 9, ISBN 9783540905738.
13. Монен, Жан Франсуа; Хинчи, Майкл Джерард (2003), Понимание формальных методов, Springer, стр. 21, ISBN 9781852332471.
14. Ли, Джон М. (2010), Введение в топологические многообразия , Graduate Texts in Mathematics, т. 202 (2-е изд.), Springer, стр. 64, ISBN 9781441979407.

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

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