В наивной теории множеств , вложенное множество [ сомнительное ] представляет собой набор , содержащий цепочку подмножеств, образующий иерархическую структуру, как русские кукол .
Он используется в качестве референса-концепции во всех научных иерархии определений, и многие технических подходов, как дерево в вычислительных структурах данных или вложенные множества модели из реляционных баз данных .
Иногда это понятие путают с «множеством множеств» с наследственным свойством (например, с конечностью в наследственно конечном множестве ).
Формальное определение [ править ]
Некоторые авторы предпочитают использовать термин « коллекция вложенных наборов», поскольку это формальное определение коллективного свойства многих наборов. Другие [1] предпочитают классифицировать это отношение как порядок включения . Коллекция - это «набор наборов».
Пусть B будет непустое множество и C является семейство подмножеств B . Тогда C является вложенной коллекцией множеств, если:
- (и )
Первое условие гласит, что набор B , содержащий все элементы любого подмножества, должен принадлежать к коллекции вложенных наборов. Некоторые авторы [1] также утверждает , что Б не пустой или пустой не является подмножество C .
Второе условие гласит, что пересечение каждой пары наборов в коллекции вложенных наборов не является пустым набором только в том случае, если один набор является подмножеством другого. [2]
В частности, при сканировании всех пар подмножеств во втором состоянии, это верно для любой комбинации с B .
Пример [ править ]
Используя набор атомарных элементов , как подходит набор игральных карт :
- B = {♠, ♥, ♦, ♣}; B 1 = {♠, ♥}; B 2 = {♦, ♣}; B 3 = {♣};
C = { B , B 1 , B 2 , B 3 }.
Второе условие (формального определения) можно проверить, объединив все пары:
- B 1 ∩ B 2 = ∅; B 1 ∩ B 3 = ∅; B 3 ⊂ B 2 .
Существует иерархия, которая может быть выражена двумя ветвями и ее порядком вложенности: B 3 ⊂ B 2 ⊂ B ; В 1 ⊂ B .
Производные концепции [ править ]
Как наборы, которые являются общей абстракцией и основой для многих концепций, вложенный набор является основой для «вложенной иерархии», «иерархии включения» и других.
Вложенная иерархия [ править ]
Вложенная иерархия или иерархия включения - это иерархическое упорядочение вложенных наборов . [3] Концепция гнездования представлена на примере русских матрешек . Каждая кукла окружена другой куклой, вплоть до внешней куклы. Внешняя кукла содержит все внутренние куклы, следующая внешняя кукла содержит все оставшиеся внутренние куклы и так далее. Матрешки представляют собой вложенную иерархию, где каждый уровень содержит только один объект, т. Е. Есть только одна кукла каждого размера; Обобщенная вложенная иерархия допускает наличие нескольких объектов внутри уровней, но каждый объект имеет только одного родителя на каждом уровне. Иллюстрируя общую концепцию:
Квадрат всегда можно назвать четырехугольником, многоугольником или формой. Таким образом, это иерархия. Однако рассмотрите набор полигонов, использующих эту классификацию. Квадрат может быть только четырехугольником; он никогда не может быть треугольником , шестиугольником и т. д.
Вложенные иерархии - это организационные схемы, лежащие в основе таксономий и систематических классификаций. Например, используя исходную таксономию Линнея (версию, которую он изложил в 10-м издании Systema Naturae ), человека можно сформулировать как: [4]
Таксономии могут часто меняться (как видно из биологической таксономии ), но основная концепция вложенных иерархий всегда одна и та же.
Иерархия содержания [ править ]
Иерархия включения - это прямая экстраполяция концепции вложенной иерархии . Все упорядоченные наборы по-прежнему являются вложенными, но каждый набор должен быть « строгим » - никакие два набора не могут быть идентичными. Приведенный выше пример фигур можно изменить, чтобы продемонстрировать это:
Обозначение означает, что x является подмножеством y, но не равно y .
Сдерживание иерархия используется в наследовании классов в объектно-ориентированном программировании .
См. Также [ править ]
- Наследственно счетное множество
- Наследственная собственность
- Иерархия (математика)
- Модель вложенных множеств для хранения иерархической информации в реляционных базах данных
Ссылки [ править ]
- ^ а б Б. Корте и Дж. Выген (2012). Комбинаторная оптимизация . Спрингер, Гейдельберг.
- ^ (определение на стр. 221) «Электронные библиотеки и архивы: 8-я Итальянская исследовательская конференция, IRCDL 2012 - Бари, Италия, 9–10 февраля 2012 г., пересмотренные избранные статьи» , под редакцией Маристелла Агости, Флориана Эспозито, Стефано Ферилли, Никола Ферро . Опубликовано в 2013 году. ISBN 9783642358340 .
- ^ Лейн, Дэвид (2006). «Иерархия, сложность, общество». В Pumain, Дениз (ред.). Иерархия в естественных и социальных науках . Нью-Йорк, Нью-Йорк: Springer-Verlag . С. 81–120. ISBN 978-1-4020-4126-6.
- ^ Linnaei, Карл фон (1959). Systema naturae per regna tria naturae: классы secundum, ordines, роды, виды, cum characteribus, дифференциалы, синонимы, locis (на латыни) (10-е изд.) Стокгольм : Impensis Direct. ISBN 0-665-53008-0. Проверено 24 сентября 2011 .
