Partially ordered set - AbsoluteAstronomy.com

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, especially order theory

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

, a partially ordered set (or poset) formalizes and generalizes 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

Relation (mathematics)

In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...

that indicates that, for certain pairs of elements in the set, one of the elements precedes the other. Such a relation is called a partial order to reflect the fact that not every pair of elements 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 order

Total order

In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

s, in which every pair is related. A finite poset can be visualized through its Hasse diagram

Hasse diagram

In order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction...

, which depicts the ordering relation.

A familiar real-life example of a partially ordered set is a collection of people ordered by genealogical

Genealogy

Genealogy is the study of families and the tracing of their lineages and history. Genealogists use oral traditions, historical records, genetic analysis, and other records to obtain information about a family and to demonstrate kinship and pedigrees of its members...

descendancy. Some pairs of people bear the descendant-ancestor relationship, but other pairs bear no such relationship.

Formal definition

A partial order is a binary relation

Binary relation

In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

"≤" over a set P which is reflexive

Reflexive relation

In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...

, antisymmetric

Antisymmetric relation

In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,...

, and transitive

Transitive relation

In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

, 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

Preorder

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...

.

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.

For a, b, elements of a partially ordered set P, if a ≤ b or b ≤ a, then a and b are comparable. Otherwise they are incomparable. A partial order under which every pair of elements is comparable is called a total order or linear order; a totally ordered set is also called a chain (e.g., the natural numbers with their standard order). A poset in which no two distinct elements are comparable is called an antichain

Antichain

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...

Examples

Standard examples of posets arising in mathematics include:

The real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s ordered by the standard less-than-or-equal relation ≤ (a totally ordered set as well).

The set of natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s equipped with the relation of divisibility.

The vertex set of a directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

ordered by reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...

.

The set of subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of a given set (its power set) ordered by inclusion
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

(see the figure on top-right).

The set of subspaces of a vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

ordered by inclusion.

For a partially ordered set P, the sequence space
Sequence space
In functional analysis and related areas of mathematics, a sequence space is a vector space whose elements are infinite sequences of real or complex numbers. Equivalently, it is a function space whose elements are functions from the natural numbers to the field K of real or complex numbers...

containing all sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...

s of elements from P, where sequence a precedes sequence b if every item in a precedes the corresponding item in b. Formally, (a_n)_n∈ℕ ≤ (b_n)_n∈ℕ if and only if a_n ≤ b_n for all n in ℕ.

For a set X and a partially ordered set P, the function space
Function space
In mathematics, a function space is a set of functions of a given kind from a set X to a set Y. It is called a space because in many applications it is a topological space, a vector space, or both.-Examples:...

containing all functions from X to P, where f ≤ g if and only if f(x) ≤ g(x) for all x in X.

A fence
Fence (mathematics)
In mathematics, a fence, also called a zigzag poset, is a partially ordered set in which the order relations form a path with alternating orientations:orA fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions.A linear extension of a fence is...

, a partially ordered set defined by an alternating sequence of order relations a < b > c < d ...

Extrema

There are several notions of "greatest" and "least" element in a poset P, notably:

Greatest element
Greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...

and least element: An element g in P is a greatest element if for every element a in P, a ≤ g. An element m in P is a least element if for every element a in P, a ≥ m. A poset can only have one greatest or least element.
Maximal element
Maximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...

s and minimal elements: An element g in P is a maximal element if there is no element a in P such that a > g. Similarly, an element m in P is a minimal element if there is no element a in P such that a < m. If a poset has a greatest element, it must be the unique maximal element, but otherwise there can be more than one maximal element, and similarly for least elements and minimal elements.
Upper and lower bounds: For a subset A of P, an element x in P is an upper bound of A if a ≤ x, for each element a in A. In particular, x need not be in A to be an upper bound of A. Similarly, an element x in P is a lower bound of A if a ≥ x, for each element a in A. A greatest element of P is an upper bound of P itself, and a least element is a lower bound of P.

For example, consider the positive integers, ordered by divisibility: 1 is a least element, as it divides all other elements; on the other hand this poset does not have a greatest element (although if one would include 0 in the poset, which is a multiple of any integer, that would be a greatest element). This partially ordered set does not even have any maximal elements, since any g divides for instance 2g, which is distinct from it, so g is not be maximal. If we exclude the number 1, while keeping divisibility as ordering on the elements greater than 1, then the resulting poset does not have a least element, but any prime number

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

is a minimal element for it. In this poset, 60 is an upper bound (though not a least upper bound) of the subset {2,3,5,10}, which subset does not have any lower bound (since 1 is not in the poset); on the other hand 2 is a lower bound of the subset of powers of 2, which subset does not have any upper bound.

Orders on the Cartesian product of partially ordered sets

In order of increasing strength, i.e., decreasing sets of pairs, three of the possible partial orders on the Cartesian product

Cartesian product

In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...

of two partially ordered sets are:

Lexicographical order
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...

: (a,b) ≤ (c,d) if and only if a < c or (a = c and b ≤ d).
(a,b) ≤ (c,d) if and only if a ≤ c and b ≤ d (the product order
Product order
In mathematics, given two ordered sets A and B, one can induce a partial ordering on the Cartesian product A × B. Giventwo pairs and in A × B, one sets ≤...

).
(a,b) ≤ (c,d) if and only if (a < c and b < d) or (a = c and b = d) (the reflexive closure of the direct product of the corresponding strict orders).

All three can similarly be defined for the Cartesian product of more than two sets.

Applied to ordered vector space

Ordered vector space

In mathematics an ordered vector space or partially ordered vector space is a vector space equipped with a partial order which is compatible with the vector space operations.- Definition:...

s over the same field

Field (mathematics)

In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

, the result is in each case also an ordered vector space.

See also orders on the Cartesian product of totally ordered sets.

Strict and non-strict partial orders

In some contexts, the partial order defined above is called a non-strict (or reflexive, or weak) partial order. In these contexts a strict (or irreflexive) partial order "<" is a binary relation that is irreflexive and transitive

Transitive relation

In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

, and therefore asymmetric

Asymmetric relation

Asymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.That is,\lnot....

. In other words, asymmetric (hence irreflexive) and transitive.

Thus, for all a, b, and c in P, we have that:

¬(a < a) (irreflexivity);
if a < b then ¬(b < a) (asymmetry); and
if a < b and b < c then a < c (transitivity).

There is a 1-to-1 correspondence between all non-strict and strict partial orders.

If "≤" is a non-strict partial order, then the corresponding strict partial order "<" is the reflexive reduction given by:

a < b if and only if (a ≤ b and a ≠ b)

Conversely, if "<" is a strict partial order, then the corresponding non-strict partial order "≤" is the reflexive closure given by:

a ≤ b if and only if a < b or a = b.

This is the reason for using the notation "≤".

Strict partial orders are useful because they correspond more directly to directed acyclic graph

Directed acyclic graph

In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

s (dags): every strict partial order is a dag, and the transitive closure

Transitive closure

In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...

of a dag is both a strict partial order and also a dag itself.

Inverse and order dual

The inverse or converse ≥ of a partial order relation ≤ satisfies x≥y if and only if y≤x. The inverse of a partial order relation is reflexive, transitive, and antisymmetric, and hence itself a partial order relation. The order dual of a partially ordered set is the same set with the partial order relation replaced by its inverse. The irreflexive relation > is to ≥ as < is to ≤.

Any one of these four relations ≤, <, ≥, and > on a given set uniquely determine the other three.

In general two elements x and y of a partial order may stand in any of four mutually exclusive relationships to each other: either x < y, or x = y, or x > y, or x and y are incomparable (none of the other three). A totally ordered

Total order

In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

set is one that rules out this fourth possibility: all pairs of elements are comparable and we then say that trichotomy holds. The natural number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s, the integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s, the rationals

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

, and the real

Real number

In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s are all totally ordered by their algebraic (signed) magnitude whereas the complex number

Complex number

A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

s are not. This is not to say that the complex numbers cannot be totally ordered; we could for example order them lexicographically via x+iy < u+iv if and only if x < u or (x = u and y < v), but this is not ordering by magnitude in any reasonable sense as it makes 1 greater than 100i. Ordering them by absolute magnitude yields a preorder in which all pairs are comparable, but this is not a partial order since 1 and i have the same absolute magnitude but are not equal, violating antisymmetry.

Number of partial orders

Sequence [ A001035] in OEIS

On-Line Encyclopedia of Integer Sequences

The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...

gives the number of partial orders on a set of n labeled elements:
The number of strict partial orders is the same as that of partial orders.

If we count only up to

Up to

In mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...

isomorphism, we get 1, 1, 2, 5, 16, 63, 318, … .

Linear extension

A partial order ≤^* on a set X is an extension of another partial order ≤ on X provided that for all elements x and y of X, whenever x ≤y, it is also the case that x ≤^* y. A linear extension

Linear extension

In order theory, a branch of mathematics, a linear extension of a partial order is a linear order that is compatible with the partial order.-Definitions:...

is an extension that is also a linear (i.e., total) order. Every partial order can be extended to a total order (order-extension principle).

In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, algorithms for finding linear extensions of partial orders (represented as the reachability

Reachability

In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...

orders of directed acyclic graph

Directed acyclic graph

s) are called topological sorting

Topological sorting

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering...

In category theory

Every poset (and every preorder

Preorder

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...

) may be considered as a category

Category (mathematics)

In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...

in which every hom-set has at most one element. More explicitly, let hom(x, y) = {(x, y)} if x ≤ y (and otherwise the empty set) and (y, z)o(x, y) = (x, z). Posets are equivalent

Equivalence of categories

In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...

to one another if and only if they are isomorphic. In a poset, the smallest element, if any, is an initial object

Initial object

In category theory, an abstract branch of mathematics, an initial object of a category C is an object I in C such that for every object X in C, there exists precisely one morphism I → X...

, and the largest element, if any, a terminal object. Also, every preordered set is equivalent to a poset. Finally, every subcategory of a poset is isomorphism-closed.

A functor from a poset category (a diagram

Diagram (category theory)

In category theory, a branch of mathematics, a diagram is the categorical analogue of an indexed family in set theory. The primary difference is that in the categorical setting one has morphisms. An indexed family of sets is a collection of sets, indexed by a fixed set; equivalently, a function...

indexed by a poset category) is a commutative diagram

Commutative diagram

In mathematics, and especially in category theory, a commutative diagram is a diagram of objects and morphisms such that all directed paths in the diagram with the same start and endpoints lead to the same result by composition...

Partial orders in topological spaces

If P is a partially ordered set that has also been given the structure of a topological space

Topological space

Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

, then it is customary to assume that is a closed subset of the topological product space

. Under this assumption partial order relations are well behaved at limits

Limit of a sequence

The limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...

in the sense that if

and

a i \leq b i

for all i, then

a \leq b

Interval

For a ≤ b, the closed interval

Interval (mathematics)

In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

[a,b] is the set of elements x satisfying a ≤ x ≤ b (i.e. a ≤ x and x ≤ b). It contains at least the elements a and b.

Using the corresponding strict relation "<", the open interval (a,b) is the set of elements x satisfying a < x < b (i.e. a < x and x < b). An open interval may be empty even if a < b. For example, the open interval (1,2) on the integers is empty since there are no integers i such that 1 < i < 2.

Sometimes the definitions are extended to allow a > b, in which case the interval is empty.

The half-open intervals [a,b) and (a,b] are defined similarly.

A poset is locally finite

Locally finite poset

In mathematics, a locally finite poset is a partially ordered set P such that for all x, y ∈ P, the interval [x, y] consists of finitely many elements....

if every interval is finite. For example, the integers are locally finite under their natural ordering.

This concept of an interval in a partial order should not be confused with the particular class of partial orders known as the interval order

Interval order

In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.More formally, a...

External links

sequence [ A001035] in OEIS
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...

: number of partial orders on a set of n elements.

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.