nested set
   HOME

TheInfoList



OR:

In a
naive set theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike Set theory#Axiomatic set theory, axiomatic set theories, which are defined using Mathematical_logic#Formal_logical_systems, forma ...
, a nested set is a set containing a chain of
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s, forming a hierarchical structure, like Russian dolls. It is used as reference-concept in all scientific hierarchy definitions, and many technical approaches, like the
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
in computational data structures or
nested set model The nested set model is a technique for representing nested sets (also known as trees or hierarchies) in relational databases. Motivation The standard relational algebra and relational calculus, and the SQL operations based on them, are unable to ...
of
relational database A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...
s. Sometimes the concept is confused with a "set of sets" with a
hereditary property In mathematics, a hereditary property is a property of an object that is inherited by all of its subobjects, where the meaning of ''subobject'' depends on the context. These properties are particularly considered in topology and graph theory, but al ...
(like the finiteness in a
hereditarily finite set In mathematics and set theory, hereditarily finite sets are defined as finite sets whose elements are all hereditarily finite sets. In other words, the set itself is finite, and all of its elements are finite sets, recursively all the way down to t ...
).


Formal definition

Some authors prefer to use the term nested set collection, because it is a formal definition of a collective property of many sets. Others prefer to classify this relation as an
inclusion order In the mathematical field of order theory, an inclusion order is the partial order that arises as the subset-inclusion relation on some collection of objects. In a simple way, every poset ''P'' = (''X'',≤) is ( isomorphic to) an inclusion order ...
. A collection is a "set of sets". Let ''B'' be a
non-empty In mathematics, the empty set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exists by inclu ...
set and ''C'' be a collection of subsets of ''B''. Then ''C'' is a nested set collection if: * B \in C (and \empty \notin C) * \forall H,K \in C ~:~ H \cap K \neq \empty \implies H \subset K ~\lor~ K \subset H The first condition states that set ''B'', which contains all the elements of any subset, must belong to the Nested Set Collection. Some authors also state that ''B'' is not empty or the empty is not a subset of ''C''. The second condition states 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. In particular, when scanning all pairs of subsets at the second condition, it is true for any combination with ''B''.


Example

Using a set of atomic elements, as the set of the
playing card suit In playing cards, a suit is one of the categories into which the cards of a deck are divided. Most often, each card bears one of several pips (symbols) showing to which suit it belongs; the suit may alternatively or additionally be indicated by ...
s: : ''B'' = ;     ''B''1 = ;   ''B''2 = ;   ''B''3 = ;
''C'' = . The second condition (of the formal definition) can be checked by combining all pairs: : ''B''1 ∩ ''B''2 = ∅;  ''B''1 ∩ ''B''3 = ∅;  ''B''3 ⊂ ''B''2. There is a hierarchy that can be expressed by two branches and its nested order: ''B''3 ⊂ ''B''2 ⊂ ''B'';  ''B''1 ⊂ ''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. The concept of nesting is exemplified in Russian
matryoshka doll Matryoshka dolls ( ; rus, матрёшка, p=mɐˈtrʲɵʂkə, a=Ru-матрёшка.ogg), also known as stacking dolls, nesting dolls, Russian tea dolls, or Russian dolls, are a set of wooden dolls of decreasing size placed one inside ano ...
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: : \text \subset \text \subset \text \subset \text \, 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 A triangle is a polygon with three Edge (geometry), edges and three Vertex (geometry), vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC. In Euclidean geometry, an ...
,
hexagon In geometry, a hexagon (from Ancient Greek, Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple polygon, simple (non-self-intersecting) hexagon is 720°. Regular hexa ...
, etc. Nested hierarchies are the organizational schemes behind taxonomies and systematic classifications. For example, using the original
Linnaean taxonomy Linnaean taxonomy can mean either of two related concepts: # The particular form of biological classification (taxonomy) set up by Carl Linnaeus, as set forth in his ''Systema Naturae'' (1735) and subsequent works. In the taxonomy of Linnaeus t ...
(the version he laid out in the 10th edition of ''
Systema Naturae ' (originally in Latin written ' with the ligature æ) is one of the major works of the Swedish botanist, zoologist and physician Carl Linnaeus (1707–1778) and introduced the Linnaean taxonomy. Although the system, now known as binomial nomen ...
''), a human can be formulated as: : \text \subset \text \subset \text \subset \text \subset \text Taxonomies may change frequently (as seen in
biological taxonomy In biology, taxonomy () is the scientific study of naming, defining ( circumscribing) and classifying groups of biological organisms based on shared characteristics. Organisms are grouped into taxa (singular: taxon) and these groups are given ...
), but the underlying concept of nested hierarchies is always the same.


Containment hierarchy

A containment hierarchy is a direct extrapolation of the
nested hierarchy A hierarchy (from Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) that are represented as being "above", "below", or "at the same level as" one another. Hierarchy is an important ...
concept. All of the ordered sets are still nested, but every set must be "
strict In mathematical writing, the term strict refers to the property of excluding equality and equivalence and often occurs in the context of inequality and monotonic functions. It is often attached to a technical term to indicate that the exclusive ...
" — no two sets can be identical. The shapes example above can be modified to demonstrate this: : \text \subsetneq \text \subsetneq \text \subsetneq \text \, The notation x \subsetneq y \, means ''x'' is a subset of ''y'' but is not equal to ''y''. Containment hierarchy is used in
class inheritance In object-oriented programming, inheritance is the mechanism of basing an Object (computer science), object or Class (computer programming), class upon another object (Prototype-based programming, prototype-based inheritance) or class (Class-based ...
of
object-oriented programming Object-oriented programming (OOP) is a programming paradigm based on the concept of "objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of pr ...
.


See also

*
Hereditarily countable set In set theory, a set is called hereditarily countable if it is a countable set of hereditarily countable sets. This inductive definition is well-founded and can be expressed in the language of first-order set theory. A set is hereditarily count ...
*
Hereditary property In mathematics, a hereditary property is a property of an object that is inherited by all of its subobjects, where the meaning of ''subobject'' depends on the context. These properties are particularly considered in topology and graph theory, but al ...
*
Hierarchy (mathematics) In mathematics, a hierarchy is a set-theoretical object, consisting of a preorder defined on a set. This is often referred to as an ordered set, though that is an ambiguous term that many authors reserve for partially ordered sets or totally o ...
*
Nested set model The nested set model is a technique for representing nested sets (also known as trees or hierarchies) in relational databases. Motivation The standard relational algebra and relational calculus, and the SQL operations based on them, are unable to ...
for storing hierarchical information in relational databases


References

{{Set theory Set theory