Разделение множества

Математические способы группировки элементов множества

Набор марок, разделенных на пачки: ни одна марка не находится в двух пачках, ни одна пачка не пуста, и каждая марка находится в пачке.

52 раздела множества с 5 элементами. Цветная область обозначает подмножество X, которое образует элемент охватывающего раздела. Неокрашенные точки обозначают одноэлементные подмножества. Первое показанное разделение содержит пять одноэлементных подмножеств; последнее разделение содержит одно подмножество с пятью элементами.

Традиционные японские символы для 54 глав «Повести о Гэндзи» основаны на 52 способах разделения пяти элементов (два красных символа представляют одно и то же разделение, а зеленый символ добавляется для достижения 54). ^[1]

В математике разбиение множества — это группировка его элементов в непустые подмножества таким образом, что каждый элемент входит ровно в одно подмножество.

Каждое отношение эквивалентности на множестве определяет разбиение этого множества, а каждое разбиение определяет отношение эквивалентности. Множество, снабженное отношением эквивалентности или разбиением, иногда называется сетоидом , как правило, в теории типов и теории доказательств .

Определение и обозначения

Разбиение множества X — это множество непустых подмножеств X, такое, что каждый элемент x из X принадлежит ровно одному из этих подмножеств ^[2] (т. е. подмножества являются непустыми взаимно непересекающимися множествами ).

Эквивалентно, семейство множеств P является разбиением X тогда и только тогда, когда выполняются все следующие условия: ^[3]

• Семейство P не содержит пустого множества (то есть ). ${\displaystyle \emptyset \notin P}$
• Объединение множеств в P равно X (то есть ). Говорят, что множества в P исчерпывают или покрывают X . См. также коллективно исчерпывающие события и покрытие (топология) . ${\displaystyle \textstyle \bigcup _{A\in P}A=X}$
• Пересечение любых двух различных множеств в P пусто (то есть ). Элементы P называются попарно непересекающимися или взаимоисключающими. См. также взаимоисключаемость . ${\displaystyle (\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset }$

Наборы в называются блоками , частями или ячейками , разбиения. ^[4] Если тогда мы представим ячейку , содержащую , как . То есть, это обозначение для ячейки , в которой содержится . ${\displaystyle P}$ ${\displaystyle a\in X}$ ${\displaystyle a}$ ${\displaystyle [a]}$ ${\displaystyle [a]}$ ${\displaystyle P}$ ${\displaystyle a}$

Каждое разделение может быть идентифицировано с отношением эквивалентности на , а именно отношением таким, что для любого мы имеем тогда и только тогда, когда (эквивалентно, тогда и только тогда, когда ). Обозначение вызывает идею о том, что отношение эквивалентности может быть построено из раздела. Наоборот, каждое отношение эквивалентности может быть идентифицировано с разделом. Вот почему иногда неформально говорят, что «отношение эквивалентности то же самое, что и раздел». Если P — раздел, идентифицированный с данным отношением эквивалентности , то некоторые авторы пишут . Это обозначение наводит на мысль о том, что раздел — это множество X, разделенное на ячейки. Обозначение также вызывает идею о том, что из отношения эквивалентности можно построить раздел. ${\displaystyle P}$ ${\displaystyle X}$ ${\displaystyle \sim _{\!P}}$ ${\displaystyle a,b\in X}$ ${\displaystyle a\sim _{\!P}b}$ ${\displaystyle a\in [b]}$ ${\displaystyle b\in [a]}$ ${\displaystyle \sim _{\!P}}$ ${\displaystyle \sim }$ ${\displaystyle P=X/{\sim }}$

Ранг равен , если конечен .​​ ${\displaystyle P}$ ${\displaystyle |X|-|P|}$ ${\displaystyle X}$

Примеры

• Пустой набор имеет ровно один раздел, а именно . (Примечание: это раздел, а не элемент раздела.) ${\displaystyle \emptyset }$ ${\displaystyle \emptyset }$
• Для любого непустого множества X , P = { X } является разбиением X , называемым тривиальным разбиением .
  • В частности, каждый синглтон-набор { x } имеет ровно один раздел, а именно { { x } }.
• Для любого непустого собственного подмножества A множества U множество A вместе со своим дополнением образуют разбиение U , а именно, { A , U ∖ A }.
• Набор {1, 2, 3} имеет следующие пять разделов (по одному разделу на элемент):
  • { {1}, {2}, {3} }, иногда пишется 1 | 2 | 3.
  • { {1, 2}, {3} } или 1 2 | 3.
  • { {1, 3}, {2} } или 1 3 | 2.
  • { {1}, {2, 3} } или 1 | 2 3.
  • { {1, 2, 3} } или 123 (в контекстах, где не возникнет путаницы с числом).
• Следующие не являются разделами {1, 2, 3}:
  • { {}, {1, 3}, {2} } не является разделом (какого-либо множества), поскольку одним из его элементов является пустое множество .
  • { {1, 2}, {2, 3} } не является разделом (какого-либо множества), поскольку элемент 2 содержится более чем в одном блоке.
  • { {1}, {2} } не является разделом {1, 2, 3}, поскольку ни один из его блоков не содержит 3; однако он является разделом {1, 2}.

Разбиения и отношения эквивалентности

Для любого отношения эквивалентности на множестве X множество его классов эквивалентности является разбиением X. Наоборот, из любого разбиения P множества X мы можем определить отношение эквивалентности на X , установив x ~ y точно тогда, когда x и y находятся в одной и той же части в P. Таким образом, понятия отношения эквивалентности и разбиения по сути эквивалентны. ^[5]

Аксиома выбора гарантирует для любого разбиения множества X существование подмножества X, содержащего ровно один элемент из каждой части разбиения. Это подразумевает, что при заданном отношении эквивалентности на множестве можно выбрать канонический представительный элемент из каждого класса эквивалентности.

Уточнение разделов

Разбиения 4-элементного множества, упорядоченные по уточнению

Разбиение α множества X является уточнением разбиения ρ множества X — и мы говорим, что α тоньше , чем ρ , и что ρ грубее , чем α — если каждый элемент α является подмножеством некоторого элемента ρ . Неформально это означает, что α является дальнейшей фрагментацией ρ . В этом случае записывается, что α ≤ ρ .

Это отношение «тоньше, чем» на множестве разбиений X является частичным порядком (поэтому обозначение «≤» уместно). Каждое множество элементов имеет наименьшую верхнюю границу (их «соединение») и наибольшую нижнюю границу (их «встречу»), так что оно образует решетку , и, более конкретно (для разбиений конечного множества), это геометрическая и сверхразрешимая решетка. ^{[6] [7]} Решетка разбиений множества из 4 элементов имеет 15 элементов и изображена на диаграмме Хассе слева.

Соединения и стыки разделов α и ρ определяются следующим образом. Соединения — это разделы, блоки которых являются пересечениями блока α и блока ρ , за исключением пустого множества. Другими словами, блок — это пересечение блока α и блока ρ , которые не являются непересекающимися друг с другом. Чтобы определить соединение , сформируйте отношение между блоками A из α и блоками B из ρ с помощью A ~ B, если A и B не являются непересекающимися. Тогда — это разделы, в которых каждый блок C является объединением семейства блоков, связанных этим отношением. ${\displaystyle \alpha \wedge \rho }$ ${\displaystyle \alpha \wedge \rho }$ ${\displaystyle \alpha \vee \rho }$ ${\displaystyle \alpha \vee \rho }$

На основе эквивалентности геометрических решеток и матроидов эта решетка разбиений конечного множества соответствует матроиду, в котором базовый набор матроида состоит из атомов решетки, а именно, разбиений с синглетными множествами и одного двухэлементного множества. Эти атомарные разбиения соответствуют один к одному ребрам полного графа . Замыкание матроида множества атомарных разбиений является самым тонким общим огрублением из всех; в терминах теории графов это разбиение вершин полного графа на связные компоненты подграфа, образованного данным набором ребер. Таким образом, решетка разбиений соответствует решетке плоскостей графического матроида полного графа. ${\displaystyle n-2}$

Другой пример иллюстрирует уточнение разбиений с точки зрения отношений эквивалентности. Если D — это набор карт в стандартной колоде из 52 карт, отношение «того же цвета» на D , которое можно обозначить как ~ _C , имеет два класса эквивалентности: наборы {красные карты} и {черные карты}. Двухчастное разбиение, соответствующее ~ _C, имеет уточнение, которое дает отношение «той же масти» ~ _S , которое имеет четыре класса эквивалентности {пики}, {бубны}, {червы} и {трефы}.

Непересекающиеся перегородки

Разбиение множества N = {1, 2, ..., n } с соответствующим отношением эквивалентности ~ является непересекающимся, если оно обладает следующим свойством: Если четыре элемента a , b , c и d из N, имеющие a < b < c < d, удовлетворяют a ~ c и b ~ d , то a ~ b ~ c ~ d . Название происходит от следующего эквивалентного определения: Представьте себе элементы 1, 2, ..., n из N, нарисованные как n вершин правильного n -угольника (в порядке против часовой стрелки). Затем разбиение можно визуализировать, нарисовав каждый блок в виде многоугольника (вершины которого являются элементами блока). Тогда разбиение является непересекающимся тогда и только тогда, когда эти многоугольники не пересекаются.

Решетка непересекающихся разбиений конечного множества образует подмножество решетки всех разбиений, но не подрешетку, поскольку операции соединения двух решеток не согласованы.

Решетка непересекающихся разбиений приобрела важность из-за ее роли в теории свободных вероятностей .

Подсчет разделов

Общее число разделов n- элементного набора — это число Белла B _n . Первые несколько чисел Белла — это B ₀ = 1, B ₁ = 1, B ₂ = 2, B ₃ = 5, B ₄ = 15, B ₅ = 52 и B ₆ = 203 (последовательность A000110 в OEIS ). Числа Белла удовлетворяют рекурсии

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}}$

и имеют экспоненциальную производящую функцию

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}.}$

Построение треугольника Белла

Числа Белла также могут быть вычислены с помощью треугольника Белла , в котором первое значение в каждой строке копируется из конца предыдущей строки, а последующие значения вычисляются путем сложения двух чисел, числа слева и числа сверху слева от позиции. Числа Белла повторяются вдоль обеих сторон этого треугольника. Числа внутри треугольника подсчитывают разделы, в которых заданный элемент является наибольшим синглтоном .

Число разбиений n -элементного множества ровно на k (непустых) частей называется числом Стирлинга второго рода S ( n , k ).

Число непересекающихся разбиений n -элементного множества называется числом Каталана.

${\displaystyle C_{n}={1 \over n+1}{2n \choose n}.}$

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

• Точное покрытие
• Блочная конструкция
• Кластерный анализ
• Список тем раздела
• Ламинирование (топология)
• принцип МЕСЕ
• Отношение частичной эквивалентности
• Алгебра разбиения
• Уточнение раздела
• Точечно-конечная коллекция
• Схемы рифмовки по разделам набора
• Слабое упорядочение (упорядоченное разбиение множества)

Примечания

1. Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики», в Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: древняя и современная , Oxford University Press, стр. 7–37
2. Халмос, Пол (1960). Наивная теория множеств Р. Спрингер. п. 28. ISBN 9780387900926.
3. Лукас, Джон Ф. (1990). Введение в абстрактную математику. Rowman & Littlefield. стр. 187. ISBN 9780912675732.
4. Бруальди 2004, стр. 44–45.
5. Шехтер 1997, стр. 54.
6. Биркгофф, Гарретт (1995), Теория решеток, Colloquium Publications, т. 25 (3-е изд.), Американское математическое общество, стр. 95, ISBN 9780821810255.
7. * Stern, Manfred (1999), Полумодулярные решетки. Теория и приложения , Энциклопедия математики и ее приложений, т. 73, Cambridge University Press, doi :10.1017/CBO9780511665578, ISBN 0-521-46105-7

Ссылки

• Бруальди, Ричард А. (2004). Введение в комбинаторику (4-е изд.). Pearson Prentice Hall. ISBN 0-13-100119-1.
• Шехтер, Эрик (1997). Справочник по анализу и его основам . Academic Press. ISBN 0-12-622760-8.