Вложенный набор

редактировать

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

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

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

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

Иногда это понятие путают с «набором множеств» с a (как конечность в a).

Содержание

1 Формальное определение
- 1.1 Пример
2 Производные концепции
- 2.1 Вложенная иерархия
- 2.2 Иерархия сдерживания
3 См. Также
4 Ссылки

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

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

Пусть B - непустое множество, а C - набор подмножеств B. Тогда C является набором вложенных множеств, если:

$B ∈ C {\ displaystyle B \ in C}$ ${\ displaystyle B \ в C}$ (и $∅ ∉ C {\ displaystyle \ emptyset \ notin C}$ ${\ displaystyle \ emptyset \ notin C}$ )
$∀ H, K ∈ C: H ∩ K ≠ ∅ ⇒ H ⊂ K ∨ K ⊂ H {\ displaystyle \ forall H, K \ in C ~: ~ H \ cap K \ neq \ emptyset ~ \ Rightarrow ~ H \ subset K ~ \ lor ~ K \ subset H}$ ${\ displaystyle \ forall H, K \ in C ~: ~ H \ cap K \ neq \ emptyset ~ \ Rightarrow ~ H \ подмножество K ~ \ lor ~ K \ subset H}$

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

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

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

Пример

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

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

B = {♠, ♥, ♦, ♣}; B 1 = {♠, ♥}; B 2 = {♦, ♣}; B 3 = {♣};. C = {B, B 1, B 2, B 3}.

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

B1∩ B 2 = ∅; B 1 ∩ B 3 = ∅; B 3 ⊂ B 2.

Существует иерархия, которая может быть выражена двумя ветвями и ее вложенным порядком: B 3 ⊂ B 2 ⊂ B; B 1 ⊂ B.

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

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

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

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

квадрат ⊂ четырехугольник ⊂ многоугольник ⊂ shape {\ displaystyle {\ text {square}} \ subset {\ text {quadrangular}} \ subset {\ text {polygon}} \ subset {\ text {shape }} \,}

{\ text {квадрат}} \ subset {\ text {четырехугольник}} \ subset {\ text {polygon}} \ subset {\ text {shape}} \,

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

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

H. sapiens ⊂ Homo ⊂ приматы ⊂ Mammalia ⊂ Animalia {\ displaystyle {\ text {H. sapiens}} \ subset {\ text {Homo}} \ subset {\ text {Primates}} \ subset {\ text {Mammalia}} \ subset {\ text {Animalia}}}

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

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

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

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

квадрат ⊊ четырехугольник ⊊ многоугольник ⊊ форма {\ displaystyle {\ text {square}} \ subsetneq {\ text {четырехугольник}} \ subsetneq {\ text {polygon}} \ subsetneq {\ text {shape}} \,}

{\ text {квадрат}} \ subsetneq {\ text {четырехугольник}} \ subsetneq {\ text {polygon}} \ subsetneq {\ text {shape}} \,

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

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

См. Также

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