Hierarchy (mathematics)

For other uses, see hierarchy (disambiguation).

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 ordered sets. The term pre-ordered set is unambiguous, and is always synonymous with a mathematical hierarchy. The term hierarchy is used to stress a hierarchical relation among the elements.

Sometimes, a set comes equipped with a natural hierarchical structure. For example, the set of natural numbers N is equipped with a natural pre-order structure, where $n\leq n'$ whenever we can find some other number $m$ so that $n+m=n'$. That is, $n'$ is bigger than $n$ only because we can get to $n'$ from $n$ using $m$. This idea can be applied to any commutative monoid. On the other hand, the set of integers Z requires a more sophisticated argument for its hierarchical structure, since we can always solve the equation $n+m=n'$ by writing $m=(n'-n)$.

Other natural hierarchies arise in computer science, where the word refers to partially ordered sets whose elements are classes of objects of increasing complexity. In that case, the preorder defining the hierarchy is the class-containment relation. Containment hierarchies are thus special cases of hierarchies.

Related terminology

Individual elements of a hierarchy are often called levels and a hierarchy is said to be infinite if it has infinitely many distinct levels but said to collapse if it has only finitely many distinct levels.

Example

In theoretical computer science, the time hierarchy is a classification of decision problems according to the amount of time required to solve them.

See also

• Order theory
• Nested set collection
• Lattice

Tree related topics:

• Tree structure
• Tree (data structure)
• Tree (graph theory)
• Tree network
• Tree (descriptive set theory)
• Tree (set theory)

Effective complexity hierarchies:

• Polynomial hierarchy
• Exponential hierarchy
• Chomsky hierarchy

Ineffective complexity hierarchies:

• Arithmetical hierarchy
• Hyperarithmetical hierarchy
• Analytical hierarchy

In set theory or logic:

• Borel hierarchy
• Difference hierarchy
• Wadge hierarchy
• Abstract algebraic hierarchy