Раздел набора

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

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

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

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

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

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

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

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

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

Ранг $P$ является $|X|-|P|$ , если $X$ является конечным .

Примеры

Пустой набор $\emptyset$ имеет ровно один раздел, а именно $\emptyset$ . (Примечание: это раздел, а не его член.)
Для любого непустого множества P X = { 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 точно тогда, когда и y находятся в одной и той же части P. x Таким образом, понятия отношения эквивалентности и разбиения по существу эквивалентны. ^[5]

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

Доработка перегородок

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

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

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

На основании эквивалентности геометрических решеток и матроидов эта решетка разбиений конечного множества соответствует матроиду, в котором базовый набор матроида состоит из атомов решетки, а именно разбиений с $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 ). Числа колокола удовлетворяют рекурсии

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

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

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

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

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

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

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

См. также

Примечания

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

Ссылки

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

[1] Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики», Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: древнее и современное , Oxford University Press, стр. 7–37.

[2] Халмос, Пол (1960). Наивная теория множеств Р. Спрингер. п. 28. ISBN 9780387900926 .

[3] Лукас, Джон Ф. (1990). Введение в абстрактную математику . Роуман и Литтлфилд. п. 187. ИСБН 9780912675732 .

[FOOTNOTEBrualdi200444–45-4] Бруальди 2004 , стр. 44–45.

[FOOTNOTESchechter199754-5] Шехтер 1997 , с. 54.

[6] Биркгоф, Гарретт (1995), Теория решетки , Публикации коллоквиума, том. 25 (3-е изд.), Американское математическое общество, с. 95, ISBN 9780821810255 .

[7] * Стерн, Манфред (1999), Полумодульные решетки. Теория и приложения , Энциклопедия математики и ее приложений, том. 73, Издательство Кембриджского университета, doi : 10.1017/CBO9780511665578 , ISBN 0-521-46105-7

[1]

[2]

[3]

[4]

[5]

[6]

[7]