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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

Производные понятия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Б. Корте и Дж. Виген (2012). Комбинаторная оптимизация . Спрингер, Гейдельберг.
2. «Цифровые библиотеки и архивы: 8-я итальянская исследовательская конференция, IRCDL 2012 - Бари, Италия, 9–10 февраля 2012 г., переработанные избранные статьи» под редакцией Маристеллы Агости, Флорианы Эспозито , Стефано Ферилли, Никола Ферро. Опубликовано в 2013 году. ISBN 9783642358340 . Определение на странице 221. 
3. Лейн, Дэвид (2006). «Иерархия, сложность, общество». В Пумэне, Дениз (ред.). Иерархия в естественных и социальных науках . Нью-Йорк, Нью-Йорк: Springer-Verlag . стр. 81–120. ISBN 978-1-4020-4126-6.
4. Линнаи, Карл фон (1959). Systema naturae per regna tria naturae: secundum classs, ordines, роды, виды, cumcharacteribus, Differentiis, синонимы, locis (на латыни) (10-е изд.). Стокгольм : Impensis Direct. ISBN 0-665-53008-0. Проверено 24 сентября 2011 г.