FACTOID # 17: Though Rhode Island is the smallest state in total area, it has the longest official name: The State of Rhode Island and Providence Plantations.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Partially ordered set

In mathematics, especially order theory, a partially ordered set (or poset) is a set equipped with a partial order relation. This relation formalizes the intuitive concept of an ordering, sequencing, or arrangement of the set's elements. Such an ordering does not necessarily need to be total, that is, it need not guarantee the mutual comparability of all objects in the set, but it can be. (In mathematical usage, a total order is a kind of partial order.) A poset defines a poset topology. Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, a finitary relation is defined by one of the formal definitions given below. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, the poset topology associated with a partially ordered set S (or poset for short) is the Alexandrov topology (open sets are up-sets) on the poset of finite chains of S, ordered by inclusion. ...

Contents

Formal definition

A partial order is a binary relation R over a set P which is reflexive, antisymmetric, and transitive, i.e., for all a, b, and c in P, we have that: In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ...

  • aRa (reflexivity);
  • if aRb and bRa then a = b (antisymmetry); and
  • if aRb and bRc then aRc (transitivity).

A set with a partial order is called a partially ordered set. 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. In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ...


Examples

The set of subsets of {x,y,z}, ordered by inclusion
The set of subsets of {x,y,z}, ordered by inclusion
  • The set of natural numbers equipped with the divisibility relation.

Image File history File links Download high resolution version (1050x799, 67 KB) Summary PNG file created as SVG, rendered by Batik, and uploaded by author. ... Image File history File links Download high resolution version (1050x799, 67 KB) Summary PNG file created as SVG, rendered by Batik, and uploaded by author. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... The feasible regions of linear programming are defined by a set of inequalities. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ...

Strict and weak partial orders

In some contexts, the partial order defined above is called a weak (or reflexive) partial order. In these contexts a strict (or irreflexive) partial order is a binary relation that is irreflexive and transitive, and therefore antisymmetric. In other words, for all a, b, and c in P, we have that: In mathematics, the concept of binary relation is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ...

  • ¬(aRa) (irreflexivity);
  • if ab and aRb then ¬(bRa) (antisymmetry); and
  • if aRb and bRc then aRc (transitivity).

If R is a weak partial order, then R − {(a, a) | a in P} is the corresponding strict partial order. Similarly, every strict partial order has a corresponding weak partial order, and so the definition of each is readily expressed in terms of the other.


Strict partial orders are also useful because they correspond more directly to directed acyclic graphs (dags): every strict partial order is a dag, and the transitive closure of a dag is both a strict partial order and also a dag itself. A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ... In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ...


See also: strict weak ordering A strict weak ordering is a binary relation that defines an equivalence relation and has the properties stated below. ...


Linear extension

A total order T is a linear extension of a partial order P if, whenever xy in P it also holds that xy in T. In computer science, algorithms for finding linear extensions of partial orders are called topological sorting. In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In graph theory, a topological sort of a directed acyclic graph (DAG) is a linear ordering of its nodes which is compatible with the partial order R induced on the nodes where x comes before y (xRy) if theres a directed path from x to y in the DAG...


Category theory

When considered as a category where hom(x, y) = {(x, y) | xy} and (y, z)o(x, y) = (x, z), posets are equivalent to one another if and only if they are isomorphic. In a poset, the smallest element, if any, is an initial object, and the largest element, if any, a terminal object. Also, every pre-ordered set is equivalent to a poset. Finally, every subcategory of a poset is isomorphism-closed. In mathematics, categories allow one to formalize notions involving abstract structure and processes which preserve structure. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ... In mathematics, an initial object of a category C is an object I in C such that to every object X in C, there exists precisely one morphism I → X. The dual notion is that of a terminal object: T is terminal, if to every object X in C... In mathematics, an initial object of a category C is an object I in C such that to every object X in C, there exists precisely one morphism I → X. The dual notion is that of a terminal object: T is terminal, if to every object X in C...


See also


  Results from FactBites:
 
Partially ordered set - definition of Partially ordered set in Encyclopedia (322 words)
In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering.
Partially ordered sets are studied in order theory.
Strict partial orders are also useful because they correspond more directly to directed acyclic graphs (dags): every strict partial order is a dag, and the transitive closure of a dag is both a strict partial order and also a dag itself.
Partially ordered set - Wikipedia, the free encyclopedia (535 words)
In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation.
A partial order is a binary relation R over a set P which is reflexive, antisymmetric and transitive.
The set of subsets of {x,y,z}, ordered by inclusion
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m