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

[[Файл:Disjunkte Mengen.svg|thumb|Два непересекающихся множества.]]

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

==Обобщения==
[[Файл:Disjuct-sets.svg|thumb|Попарно независимые семейства множеств]]
Приведённое определение непересекающихся множеств может быть расширено на любое {{не переведено 5|семейство множеств|||family of sets}}. Семейство множеств '''попарно дизъюнктно'''  (элементы '''попарно не пересекаются'''), если любые два множества в семействе не имеют общих элементов{{sfn|Halmos|1960|с=15}}.
Например, набор множеств {{nowrap|1={ {1}, {2}, {3}, ... } }} попарно дизъюнктен.

Говорят, что два множества {{не переведено 5|Почти непересекающиеся множества|почти не пересекаются||almost disjoint sets}}, если их пересечение в некотором смысле мало. Например, два [[Бесконечное множество|бесконечных множества]], пересечение которых является [[Конечное множество|конечным множеством]], можно считать почти не пересекающимися{{sfn|Halbeisen|2011|с=184}}.

В [[Топология|топологии]] существуют различные обозначения [[Принцип разделимости|разделённых множеств]] с более строгими условиями, чем отсутствие пересечения. Например, два множества считаются разделимыми, когда они имеют непересекающиеся [[Замыкание (геометрия)|замыкания]] или непересекающиеся [[Окрестность|окрестности]]. Подобно этому, в [[Метрическое пространство|метрическом пространстве]] {{не переведено 5|положительно разделённые множества|||positively separated sets}} — это множества, разделённые ненулевым [[Метрическое пространство|расстоянием]]{{sfn|Copson|1988|с=62}}.

==Примеры==
<gallery widths="250">
File:Veranschaulichung von disjunkten Mengen.svg|Множество, состоящее из барабана и гитары, не пересекается с множеством, состоящим из карты и книги
File:Example of a pairwise disjoint family of sets.svg|Семейство попарно непересекающиеся множеств
File:Example of a non pairwise disjoint family of sets.svg|Семейство множеств, не являющихся попарно непересекающимися
</gallery>

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

Два множества ''A'' и ''B'' дизъюнктны тогда и только тогда, когда их пересечение <math>A\cap B</math> является [[Пустое множество|пустым множеством]]{{sfn|Halmos|1960|с=15}}.
Из этого определения следует, что любое множество дизъюнктно с пустым множеством и пустое множество является единственным множеством, дизъюнктным самому себе{{sfn|Oberste-Vorth, Mouzakitis, Lawrence|2012|с=59}}.

Семейство ''F'' множеств попарно дизъюнктно, если для любых двух множеств в семействе их пересечение пусто{{sfn|Halmos|1960|с=15}}.
Если семейство содержит более одного множества, отсюда следует, что пересечение всех множеств семейства пусто. Однако семейство, состоящее из одного множества, по определению является «попарно дизъюнктным» и очевидно может иметь непустое пересечение. Кроме того, семейство множеств может иметь пустое пересечение, но не быть попарно дизъюнктно{{sfn|Smith, Eggen, St. Andre|2010|с=95}}. Например, три множества {{nowrap|1={ {1, 2}, {2, 3}, {1, 3} } }} имеют пустое пересечение, но они не попарно дизъюнктны. Фактически нет двух дизъюнктных множеств в этом наборе. Также пустое семейство множеств является попарно дизъюнктным<ref>См. ответы на вопрос [http://math.stackexchange.com/q/1211584/32951 ″Является ли пустое семейство множеств попарно дизъюнктным?″]</ref>.

[[Семейство Хелли]] — это система множеств, в которой только подсемейства с пустым пересечением попарно дизъюнктны. Например, [[Промежуток (математика)|замкнутые интервалы]] на [[Вещественное число|вещественной оси]] образуют семейство Хелли — если семейство замкнутых интервалов имеет пустое пересечение и минимально (то есть никакое подсемейство не имеет пустое пересечение), оно должно быть попарно дизъюнктно{{sfn|Bollobás|1986|с=82}}.

==Дизъюнктные объединения и разбиения==
[[Разбиение множества]] ''X'' — это любой набор взаимно дизъюнктных множеств, [[Объединение множеств|объединение]] которых равно ''X''{{sfn|Halmos|1960|с=28}}. Любое разбиение можно эквивалентно описать [[Отношение эквивалентности|отношением эквивалентности]], [[Бинарное отношение|бинарным отношением]], определяющим, принадлежат два элемента одному и тому же множеству в разложении или нет{{sfn|Halmos|1960|с=28}}.
[[Система непересекающихся множеств|Системы непересекающихся множеств]]{{sfn|Cormen, Leiserson, Rivest, Stein|2001|с=498–524 }}  и {{не переведено 5|измельчение разбиения|||partition refinement}}{{sfn|Paige, Tarjan|1987|с= 973–989}} — две техники в информатике для эффективной работы с разбиениями набора объектов, соответственно, для операции объединения, которая сливает вместе два множества, и операции измельчения, которая разбивает одно множество на два.

[[Дизъюнктное объединение]] может означать две вещи. В наиболее простом случае это может означать объединение дизъюнктных множеств{{sfn|Ferland|2008|с=45}}. Но если два или более множеств не дизъюнктны, их дизъюнктное объединение может быть образовано путём модификации множеств{{sfn|Arbib, Kfoury, Moll|1981|с=9}}<ref>В книге Вавилова дизъюнктное объединение понимается только в первом смысле. Для объединения во втором смысле используется термин '''свободное объединение''', '''свободная сумма''' или '''копроизведение множеств'''.</ref>.  Например, два множества могут быть сделаны дизъюнктыми путём замены элементов упорядоченными парами элемента и индекса, определяющего, какому множеству принадлежит элемент – первому или второму{{sfn|Monin, Hinchey|2003|с=21}}.
Та же техника может быть применена для семейств из более чем двух множеств{{sfn|Lee|2010|с=64}}.

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

==Примечания==
{{примечания|2}}

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

[[Категория:Базовые концепции теории множеств]]
[[Категория:Семейства множеств]]

{{rq|checktranslate|style}}