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

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

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

В теории множеств в математике и формальной логике два множества называются непересекающимися, если у них нет общего элемента . Эквивалентно, два непересекающихся множества — это множества, пересечение которых является пустым множеством . ^[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, p. 15, ISBN 9780387900926.
2. Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2010), Переход к высшей математике, Cengage Learning, стр. 95, ISBN 978-0-495-56202-3.
3. Хальбайзен, Лоренц Дж. (2011), Комбинаторная теория множеств: с мягким введением в принуждение, монографии Спрингера по математике, Springer, стр. 184, ISBN 9781447121732.
4. Копсон, Эдвард Томас (1988), Метрические пространства, Кембриджские трактаты по математике, том. 57, Издательство Кембриджского университета, стр. 57. 62, ISBN 9780521357326.
5. Оберсте-Ворт, Ральф В.; Музакитис, Аристид; Лоуренс, Бонита А. (2012), Мост к абстрактной математике, учебники MAA, Математическая ассоциация Америки, стр. 59, ISBN 9780883857793.
6. См. ответы на вопрос «Является ли пустое семейство множеств попарно непересекающимся?»
7. Боллобас, Бела (1986), Комбинаторика: системы множеств, гиперграфы, семейства векторов и комбинаторная вероятность, Cambridge University Press, стр. 82, ISBN 9780521337038.
8. Халмош (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, p. 45, ISBN 9780618415380.
12. Арбиб, Майкл А.; Кфури, Эй Джей; Молл, Роберт Н. (1981), Основа теоретической информатики , Серия AKM по теоретической информатике: тексты и монографии по информатике, Springer-Verlag, стр. 9, ISBN 9783540905738.
13. Монен, Жан Франсуа; Хинчи, Майкл Джерард (2003), Понимание формальных методов, Springer, стр. 21, ISBN 9781852332471.
14. Ли, Джон М. (2010), Введение в топологические многообразия , Тексты для аспирантов по математике, том. 202 (2-е изд.), Спрингер, с. 64, ISBN 9781441979407.

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

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