Коллекция вложенных наборов

Вложенный набор матрешек .

Вложенный набор, представляющий пример биологической таксономии . Внешнее внутри: порядок, семейство, род, вид.

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

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

Иногда это понятие путают с набором множеств с наследственным свойством (например, конечностью в наследственно конечном множестве ).

Формальное определение

Некоторые авторы рассматривают коллекцию вложенных множеств как семейство множеств. Другие предпочитаю классифицировать это отношение как порядок включения .

Пусть B — непустое множество, а C — подмножеств B. совокупность Тогда C является вложенной коллекцией множеств, если:

• $B\in \mathbf {C}$ (и, по мнению некоторых авторов, $\emptyset \notin \mathbf {C}$)
• $\forall H,K\in \mathbf {C} ~:~H\cap K\neq \emptyset \implies H\subset K~\lor ~K\subset H$

Первое условие гласит, что весь набор B , содержащий все элементы каждого подмножества, должен принадлежать коллекции вложенных множеств. Некоторые авторы не предполагайте, что B непусто.

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

В частности, при сканировании всех пар подмножеств при втором условии это справедливо для любой комбинации с B .

Пример

Выразив пример как частично упорядоченное множество с помощью его диаграммы Хассе .

Использование набора атомарных элементов в соответствии с набором игральных карт :

Б = {♠, ♥, ♦, ♣}; Б ₁ = {♠, ♥}; В ₂ = {♦, ♣}; В ₃ = {♣};
C знак равно { B , B ₁ , B ₂ , B ₃ }.

Второе условие формального определения можно проверить, объединив все пары:

В ₁ ∩ В ₂ = ∅; В ₁ ∩ В ₃ = ∅; Б ₃ ⊂ Б ₂ .

Существует иерархия, которую можно выразить двумя ветвями и ее вложенным порядком: B ₃ ⊂ B ₂ ⊂ B ; Б ₁ ⊂ Б .

Производные концепции

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

Вложенная иерархия

Вложенная иерархия или иерархия включения — это иерархическое упорядочение вложенных множеств . Идея гнездования иллюстрируется русскими матрешками . Каждая кукла окружена другой куклой, вплоть до внешней куклы. Внешняя кукла содержит все внутренние куклы, следующая внешняя кукла содержит все оставшиеся внутренние куклы и так далее. Матрешки представляют собой вложенную иерархию, где каждый уровень содержит только один объект, т. е. существует только одна кукла каждого размера; обобщенная вложенная иерархия позволяет использовать несколько объектов на уровнях, но каждый объект имеет только одного родителя на каждом уровне. Иллюстрируем общую концепцию:

${\text{square}}\subset {\text{quadrilateral}}\subset {\text{polygon}}\subset {\text{shape}}\,$

Квадрат всегда можно также назвать четырехугольником, многоугольником или фигурой. Таким образом, это иерархия. Однако рассмотрим набор полигонов, используя эту классификацию. Квадрат может быть только четырехугольником; это никогда не может быть треугольник , шестиугольник и т. д.

Вложенные иерархии — это организационные схемы, лежащие в основе таксономий и систематических классификаций. Например, используя оригинальную таксономию Линнея (версию, которую он изложил в 10-м издании Systema Naturae ), человека можно сформулировать как:

${\text{H. sapiens}}\subset {\text{Homo}}\subset {\text{Primates}}\subset {\text{Mammalia}}\subset {\text{Animalia}}$

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

Иерархия сдерживания

Иерархия включения — это прямая экстраполяция концепции вложенной иерархии . Все упорядоченные наборы по-прежнему являются вложенными, но каждый набор должен быть « строгим » — никакие два набора не могут быть идентичными. Пример фигур выше можно изменить, чтобы продемонстрировать это:

${\text{square}}\subsetneq {\text{quadrilateral}}\subsetneq {\text{polygon}}\subsetneq {\text{shape}}\,$

Обозначения $x\subsetneq y\,$ означает, что x является подмножеством y , но не равен y .

Иерархия включения используется при наследовании классов объектно -ориентированного программирования .

См. также

• Наследственно счетное множество
• Наследственная собственность
• Иерархия (математика)
• Модель вложенных множеств для хранения иерархической информации в реляционных базах данных.