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

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

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

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

Приведённое определение непересекающихся множеств может быть расширено на любое семейство множеств. Семейство множеств попарно дизъюнктно (элементы попарно не пересекаются), если любые два множества в семействе не имеют общих элементов[1]. Например, набор множеств { {1}, {2}, {3}, ... } попарно дизъюнктен.

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

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

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

Пересечения

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

Два множества A и B дизъюнктны тогда и только тогда, когда их пересечение является пустым множеством[1]. Из этого определения следует, что любое множество дизъюнктно с пустым множеством и пустое множество является единственным множеством, дизъюнктным самому себе[4].

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

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

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

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

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

См. также

Примечания
  1. Halmos, 1960, с. 15.
  2. Halbeisen, 2011, с. 184.
  3. Copson, 1988, с. 62.
  4. Oberste-Vorth, Mouzakitis, Lawrence, 2012, с. 59.
  5. Smith, Eggen, St. Andre, 2010, с. 95.
  6. См. ответы на вопрос ″Является ли пустое семейство множеств попарно дизъюнктным?″ Архивная копия от 20 октября 2020 на Wayback Machine
  7. Bollobás, 1986, с. 82.
  8. Halmos, 1960, с. 28.
  9. Cormen, Leiserson, Rivest, Stein, 2001, с. 498–524.
  10. Paige, Tarjan, 1987, с. 973–989.
  11. Ferland, 2008, с. 45.
  12. Arbib, Kfoury, Moll, 1981, с. 9.
  13. В книге Вавилова дизъюнктное объединение понимается только в первом смысле. Для объединения во втором смысле используется термин свободное объединение, свободная сумма или копроизведение множеств.
  14. Monin, Hinchey, 2003, с. 21.
  15. Lee, 2010, с. 64.

Литература
  • Ralph W. Oberste-Vorth, Aristides Mouzakitis, Bonita A. Lawrence. Bridge to Abstract Mathematics. — Mathematical Association of America, 2012. — С. 59. — (MAA textbooks). — ISBN 9780883857793.
  • P. R. Halmos. Naive Set Theory. — Springer, 1960. — С. 15. — (Undergraduate Texts in Mathematics). — ISBN 9780387900926.
  • Douglas Smith, Maurice Eggen, Richard St. Andre. A Transition to Advanced Mathematics. — 7. — Cengage Learning, 2010. — С. 95. — ISBN 978-0-495-56202-3.
  • Béla Bollobás. Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability. — Cambridge University Press, 1986. — С. 82. — ISBN 978-0-521-33703-8.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Chapter 21: Data structures for Disjoint Sets // Introduction to Algorithms. — 2nd. — MIT Press, 2001. — С. 498–524. — ISBN 0-262-03293-7.
  • Robert Paige, Robert E. Tarjan. Three partition refinement algorithms // SIAM Journal on Computing. — 1987. — Т. 16, вып. 6. — С. 973–989. — doi:10.1137/0216062.
  • Kevin Ferland. Discrete Mathematics: An Introduction to Proofs and Combinatorics. — Cengage Learning, 2008. — С. 45. — ISBN 9780618415380.
  • Michael A. Arbib, A. J. Kfoury, Robert N. Moll. A Basis for Theoretical Computer Science. — Springer-Verlag, 1981. — С. 9. — (The AKM series in Theoretical Computer Science: Texts and monographs in computer science). — ISBN 9783540905738.
  • Jean François Monin, Michael Gerard Hinchey. Understanding Formal Methods. — Springer, 2003. — С. 21. — ISBN 9781852332471.
  • John M. Lee. Introduction to Topological Manifolds. — 2nd. — Springer, 2010. — Т. 202. — С. 64. — (Graduate Texts in Mathematics). — ISBN 9781441979407.
  • Lorenz J. Halbeisen. Combinatorial Set Theory: With a Gentle Introduction to Forcing. — Springer, 2011. — С. 184. — (Springer monographs in mathematics). — ISBN 9781447121732.
  • Edward Thomas Copson. Metric Spaces. — Cambridge University Press, 1988. — Т. 57. — С. 62. — (Cambridge Tracts in Mathematics). — ISBN 9780521357326.
  • Н.А. Вавилов. Не совсем наивная теория множеств. — Санкт-Петербург: СПбГУ, 2008.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.