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

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

Обобщения

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

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

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

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

Перекрестки

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

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

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

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

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

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

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

См. также

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

Ссылки

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

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

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

[halmos-1] Jump up to: ^а ^б Халмос, PR (1960), Наивная теория множеств , Тексты для студентов по математике , Springer, стр. 15, ISBN 9780387900926 .

[douglas-2] Jump up to: ^а ^б Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (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 .

[h60-28-8] Jump up to: ^а ^б Халмош (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), Введение в топологические многообразия , Тексты для аспирантов по математике, том. 202 (2-е изд.), Спрингер, с. 64, ISBN 9781441979407 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]