Мәндік жиын және реттелу принципі

Mathematical set with an ordering

In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable. Formally, a partial order is a homogeneous binary relation that is reflexive, antisymmetric, and transitive. A partially ordered set (poset for short) is an ordered pair of a set (called the ground set of ) and a partial order on When the meaning is clear from context and there is no ambiguity about the partial order, the set itself is sometimes called a poset.

The term partial order usually refers to the reflexive partial order relations, referred to in this article as non strict partial orders. However some authors use the term for the other common type of partial order relations, the irreflexive partial order relations, also called strict partial orders. Strict and non strict partial orders can be put into a one to one correspondence, so for every strict partial order there is a unique corresponding non strict partial order, and vice versa.

A reflexive, weak, commonly referred to simply as a partial order, is a homogeneous relation ≤ on a set that is reflexive, antisymmetric, and transitive. That is, for all it must satisfy:
Reflexivity: , i. e. every element is related to itself. Antisymmetry: if and then , i. e. no two distinct elements precede each other. Transitivity: if and then
A non strict partial order is also known as an antisymmetric preorder.

An irreflexive, strong, So the definition is the same if it omits either irreflexivity or asymmetry (but not both). A strict partial order is also known as an asymmetric strict preorder.

The dual (or opposite) of a partial order relation is defined by letting be the converse relation of , i. e. if and only if The dual of a non strict partial order is a non strict partial order, and the dual of a strict partial order is a strict partial order. The dual of a dual of a relation is the original relation.

Given a set and a partial order relation, typically the non strict partial order , we may uniquely extend our notation to define four partial order relations and , where is a non strict partial order relation on , is the associated strict partial order relation on (the irreflexive kernel of ), is the dual of , and is the dual of Strictly speaking, the term partially ordered set refers to a set with all of these relations defined appropriately. But practically, one need only consider a single relation, or , or, in rare instances, the strict and non strict relations together,

The term ordered set is sometimes used as a shorthand for partially ordered set, 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. Some authors use different symbols than such as or to distinguish partial orders from total orders. When referring to partial orders, should not be taken as the complement of The relation is the converse of the irreflexive kernel of , which is always a subset of the complement of , but is equal to the complement of if, and only if, is a total order.

Another way of defining a partial order, found in computer science, is via a notion of comparison. Specifically, given as defined previously, it can be observed that two elements x and y may stand in any of four mutually exclusive relationships to each other: either x < y, or 1=x = y, or x > y, or x and y are incomparable. This can be represented by a function that returns one of four codes when given two elements. This definition is equivalent to a partial order on a setoid, where equality is taken to be a defined equivalence relation rather than the primitive notion of set equality. Wallis defines a more general notion of a partial order relation as any homogeneous relation that is transitive and antisymmetric. This includes both reflexive and irreflexive partial orders as subtypes. A finite poset can be visualized through its Hasse diagram. Specifically, taking a strict partial order relation , a directed acyclic graph (DAG) may be constructed by taking each element of to be a node and each element of to be an edge. The transitive reduction of this DAG is then the Hasse diagram. Similarly this process can be reversed to construct strict partial orders from certain DAGs. In contrast, the graph associated to a non strict partial order has self loops at every node and therefore is not a DAG; when a non strict order is said to be depicted by a Hasse diagram, actually the corresponding strict order is shown.

A poset is called a subposet of another poset provided that is a subset of and is a subset of The latter condition is equivalent to the requirement that for any and in (and thus also in ), if then
If is a subposet of and furthermore, for all and in , whenever we also have , then we call the subposet of induced by , and write .

A partial order on a set is called an extension of another partial order on provided that for all elements whenever it is also the case that A linear extension is an extension that is also a linear (that is, total) order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. Every partial order can be extended to a total order (order extension principle). In computer science, algorithms for finding linear extensions of partial orders (represented as the reachability orders of directed acyclic graphs) are called topological sorting.

Every poset (and every preordered set) may be considered as a category where, for objects and there is at most one morphism from to More explicitly, let if x ≤ y (and otherwise the empty set) and Such categories are sometimes called posetal. Posets are equivalent to one another if and only if they are isomorphic. In a poset, the smallest element, if it exists, is an initial object, and the largest element, if it exists, is a terminal object. Also, every preordered set is equivalent to a poset. Finally, every subcategory of a poset is isomorphism closed.