View source for Nested set collection

[[File:Russian-Matroshka no bg.jpg|260px|right|thumb|A nested set of [[Matryoshka doll|Russian dolls]].]]
[[File:OrdineCropped.jpg|260px|thumb|Nested set representing a biological taxonomy example. ''Outside-in:'' order, family, genus, species.]]
A '''nested set collection''' or '''nested set family''' is a collection of sets that consists of chains of [[Subset|subset]]s forming a hierarchical structure, like [[Matryoshka doll|Russian dolls]]. 

It is used as reference concept in [[Hierarchy|scientific hierarchy]] definitions, and many technical approaches, like the [[Tree (data structure)|tree]] in [[Data structure|computational data structures]] or [[Nested set model|nested set model]] of [[Relational database|relational database]]s.

Sometimes the concept is confused with a collection of sets with a [[Hereditary property|hereditary property]] (like finiteness in a [[Hereditarily finite set|hereditarily finite set]]).

==Formal definition==
Some authors regard a nested set collection as a family of sets. Others<ref name="Korte2012">{{cite book
| author=B. Korte and J. Vygen
| title=Combinatorial Optimization
| publisher=Springer, Heidelberg
| year=2012
}}</ref> prefer to classify it relation as an [[Inclusion order|inclusion order]].

Let ''B'' be a [[Empty set|non-empty]] set and '''C''' a collection of subsets of ''B''. Then '''C''' is a nested set collection if:
* <math>B \in \mathbf{C}</math> (and, for some authors, <math>\empty \notin \mathbf{C}</math>)
* <math>\forall H,K \in \mathbf{C} ~:~ H \cap K \neq \empty \implies H \subset K ~\lor~ K \subset H</math>

The first condition states that the whole set ''B'', which contains all the elements of every subset, must belong to the nested set collection. Some authors<ref name="Korte2012"/> do not assume that ''B'' is nonempty, or assume that the empty set is not a member of '''C'''.{{clarify|date=December 2021}}

The second condition states that the intersection of every couple of sets in the nested set collection is not the empty set only if one set is a subset of the other.<ref>''"Digital Libraries and Archives: 8th Italian Research Conference, IRCDL 2012 - Bari, Italy, February 9–10, 2012, Revised Selected Papers"'', edited by Maristella Agosti, Floriana Esposito, Stefano Ferilli, Nicola Ferro. Published in 2013. {{ISBN|9783642358340}}.  Definition at page 221.</ref>

In particular,  when scanning all pairs of subsets at the second condition, it is true for any combination  with ''B''.

===  Example ===
[[File:Hasse-diagram-ofNestedSetExample.png|260px|thumb|Expressing the example as a [[Partially ordered set|partially ordered set]] by its [[Hasse diagram|Hasse diagram]].]]
Using a set of atomic elements, as the set of the playing card suits:
: ''B'' = {♠, ♥, ♦, ♣};  &nbsp; &nbsp; ''B''<sub>1</sub> = {♠, ♥};  &nbsp; ''B''<sub>2</sub> = {♦, ♣};   &nbsp; ''B''<sub>3</sub> = {♣};<br/> '''C''' = {''B'',  ''B''<sub>1</sub>,  ''B''<sub>2</sub>, ''B''<sub>3</sub>}.

The second condition of the formal definition can be checked by combining all pairs:
: ''B''<sub>1</sub> ∩ ''B''<sub>2</sub> = ∅;&nbsp;    ''B''<sub>1</sub> ∩ ''B''<sub>3</sub> = ∅;&nbsp;  ''B''<sub>3</sub> ⊂ ''B''<sub>2</sub>.

There is a hierarchy that can be expressed by two branches and its nested order:  ''B''<sub>3</sub> ⊂  ''B''<sub>2</sub> ⊂ ''B'';&nbsp;  ''B''<sub>1</sub> ⊂ ''B''.

== Derived concepts ==
As sets, that are general abstraction and foundations for many concepts, the ''nested set'' is the foundation for "nested hierarchy", "containment hierarchy" and others.
 
===Nested hierarchy===
A nested hierarchy or ''inclusion hierarchy'' is a hierarchical ordering of ''nested set''s.<ref name="natsocsci-ch4">{{cite encyclopedia|title=Hierarchy, Complexity, Society|last=Lane|first=David|pages=81–120|encyclopedia=Hierarchy in Natural and Social Sciences|editor=Pumain, Denise|publisher=[[Physics:Springer-Verlag|Springer-Verlag]]|location=New York, New York|year=2006|isbn=978-1-4020-4126-6}}</ref> The concept of nesting is exemplified in Russian [[Matryoshka doll|matryoshka doll]]s. Each doll is encompassed by another doll, all the way to the outer doll. The outer doll holds all of the inner dolls, the next outer doll holds all the remaining inner dolls, and so on. Matryoshkas represent a nested hierarchy where each level contains only one object, i.e., there is only one of each size of doll; a generalized nested hierarchy allows for multiple objects within levels but with each object having only one parent at each level. Illustrating the general concept:

: <math> \text{square} \subset \text{quadrilateral} \subset \text{polygon} \subset \text{shape} \, </math>

A square can always also be referred to as a quadrilateral, polygon or shape. In this way, it is a hierarchy. However, consider the set of polygons using this classification. A square can ''only'' be a quadrilateral; it can never be a [[Triangle|triangle]], [[Hexagon|hexagon]], etc.

Nested hierarchies are the organizational schemes behind [[Taxonomy (general)|taxonomies]] and systematic classifications. For example, using the original [[Linnaean taxonomy]] (the version he laid out in the 10th edition of ''[[Biology:Systema Naturae|Systema Naturae]]''), a human can be formulated as:<ref>{{cite book|title=Systema naturae per regna tria naturae :secundum classes, ordines, genera, species, cum characteribus, differentiis, synonymis, locis|last=Linnaei|first=Carl von|year=1959|edition=10th|language=Latin|url=https://www.biodiversitylibrary.org/bibliography/542#|location=[[Place:Stockholm|Stockholm]]|publisher=Impensis Direct|isbn=0-665-53008-0|accessdate=2011-09-24}}</ref>

: <math>\text{H. sapiens} \subset \text{Homo} \subset \text{Primates} \subset \text{Mammalia} \subset \text{Animalia}</math>

Taxonomies may change frequently (as seen in biological taxonomy), but the underlying concept of nested hierarchies is always the same.

===Containment hierarchy===
A containment hierarchy is a direct extrapolation of the nested hierarchy concept. All of the ordered sets are still nested, but every set must be "strict" — no two sets can be identical. The shapes example above can be modified to demonstrate this:

: <math> \text{square} \subsetneq \text{quadrilateral} \subsetneq \text{polygon} \subsetneq \text{shape} \, </math>

The notation <math> x \subsetneq y \, </math> means ''x'' is a subset of ''y'' but is not equal to&nbsp;''y''.

Containment hierarchy is used in [[Inheritance (object-oriented programming)|class inheritance]] of [[Object-oriented programming|object-oriented programming]].

==See also==
* [[Hereditarily countable set]]
* [[Hereditary property]]
* [[Hierarchy (mathematics)]]
* [[Nested set model]] for storing hierarchical information in relational databases

==References==
{{Reflist}}


[[Category:Set theory]]

{{Sourceattribution|Nested set collection}}