Misplaced Pages

This is an old revision of this page, as edited by Hooman Mallahzadeh (talk | contribs) at 12:24, 8 July 2020. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In mathematics, especially order theory, a (non-strict) partial order is a binary relation ≤ over a set P satisfying particular axioms which are discussed below. When a ≤ b, we say that a is related to b. (This does not imply that b is also related to a, because the relation need not be symmetric.)

The axioms for a non-strict partial order state that the relation ≤ is reflexive, antisymmetric, and transitive. That is, for all a, b, and c in P, it must satisfy:

1. a ≤ a (reflexivity: every element is related to itself).
2. if a ≤ b and b ≤ a, then a = b (antisymmetry: two distinct elements cannot be related in both directions).
3. if a ≤ b and b ≤ c, then a ≤ c (transitivity: if a first element is related to a second element, and, in turn, that element is related to a third element, then the first element is related to the third element).

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, as long as it is clear from the context that no other kind of order is 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. In the figure on top-right, e.g. {x} and {x,y,z} are comparable, while {x} and {y} are not. 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 subset of a poset in which no two distinct elements are comparable is called an antichain (e.g. the set of singletons {{x}, {y}, {z}} in the top-right figure). An element a is said to be strictly less than an element b, if a ≤ b and a≠b. An element a is said to be covered by another element b, written a⋖b (or a<:b), if a is strictly less than b and no third element c fits between them; formally: if both a≤b and a≠b are true, and a≤c≤b is false for each c with a≠c≠b. A more concise definition will be given below using the strict order corresponding to "≤". For example, {x} is covered by {x,z} in the top-right figure, but not by {x,y,z}.

Notes

1. Simovici, Dan A.; Djeraba, Chabane (2008). "Partially Ordered Sets". Mathematical Tools for Data Mining: Set Theory, Partial Orders, Combinatorics. Springer. ISBN 9781848002012. {{cite book}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (help)