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

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

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

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 , содержащего ровно один элемент из каждой части разбиения. Это означает, что для данного отношения эквивалентности на множестве можно выбрать канонический репрезентативный элемент из каждого класса эквивалентности.

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

Разделы четырехэлементного набора, упорядоченные по уточнению

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

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

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

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

Примечания

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

Рекомендации

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