Partially ordered set

related topics
{math, number, function}
{son, year, death}

In mathematics, especially order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other. These relations are called partial orders to reflect the fact that not every pair of elements of a poset need be related: for some pairs, it may be that neither element precedes the other in the poset. Thus, partial orders generalize the more familiar total orders, in which every pair is related. A finite poset can be visualized through its Hasse diagram, which depicts the ordering relation between certain pairs of elements and allows one to reconstruct the whole partial order structure.

A familiar real-life example of a partially ordered set is a collection of people ordered by genealogical descendancy. Some pairs of people bear the ancestor-descendant relationship, but other pairs bear no such relationship.

Contents

Formal definition

A partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., for all a, b, and c in P, we have that:

  • a ≤ a (reflexivity);
  • if a ≤ b and b ≤ a then a = b (antisymmetry);
  • if a ≤ b and b ≤ c then a ≤ c (transitivity).

In other words, a partial order is an antisymmetric preorder.

A set with a partial order is called a partially ordered set (also called a poset). The term ordered set is sometimes also used for posets, as long as it is clear from the context that no other kinds of orders are meant. In particular, totally ordered sets can also be referred to as "ordered sets", especially in areas where these structures are more common than posets.

Full article ▸

related documents
Ordered pair
Normal space
Topological vector space
Direct product
B-spline
NP (complexity)
A* search algorithm
Graph theory
Empty set
Greatest common divisor
Net (mathematics)
Banach space
Polish notation
Universal quantification
Binomial theorem
Affine transformation
Free group
Tensor
Grover's algorithm
Optimization (mathematics)
Sheffer stroke
Knapsack problem
Cyclic group
Document Type Definition
Associative array
Henri Lebesgue
Stokes' theorem
Algebraically closed field
Minimum spanning tree
LL parser