| Revision as of 12:24, 8 July 2020 editHooman Mallahzadeh (talk | contribs)Extended confirmed users3,908 edits ←Removed redirect to Partially ordered set#Formal definitionTags: Removed redirect Visual edit: Switched← Previous edit | Revision as of 12:24, 8 July 2020 edit undoHooman Mallahzadeh (talk | contribs)Extended confirmed users3,908 editsNo edit summaryNext edit → | ||
| Line 12: | Line 12: | ||
| For ''a, b'', elements of a partially ordered set ''P'', if ''a'' ≤ ''b'' or ''b'' ≤ ''a'', then ''a'' and ''b'' are ''']'''. 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 ''']''' 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 ''']''' (e.g. the set of ]s {{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 ''']''' 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 ] 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}. | For ''a, b'', elements of a partially ordered set ''P'', if ''a'' ≤ ''b'' or ''b'' ≤ ''a'', then ''a'' and ''b'' are ''']'''. 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 ''']''' 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 ''']''' (e.g. the set of ]s {{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 ''']''' 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 ] 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== | |||
| {{reflist}} | |||
Revision as of 12:24, 8 July 2020
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:
- a ≤ a (reflexivity: every element is related to itself).
- if a ≤ b and b ≤ a, then a = b (antisymmetry: two distinct elements cannot be related in both directions).
- 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
- 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)