| Revision as of 12:24, 8 July 2020 editHooman Mallahzadeh (talk | contribs)Extended confirmed users3,908 editsNo edit summary← Previous edit |
Latest revision as of 18:59, 2 September 2024 edit undoTule-hog (talk | contribs)Extended confirmed users4,451 edits add rcat |
| (4 intermediate revisions by 4 users not shown) |
| Line 1: |
Line 1: |
|
|
#REDIRECT ] |
|
In ], especially ], a (non-strict) '''partial order'''<ref>{{cite book|chapter=Partially Ordered Sets|title=Mathematical Tools for Data Mining: Set Theory, Partial Orders, Combinatorics|publisher=Springer|year=2008|isbn=9781848002012|chapter-url=https://books.google.com/books?id=6i-F3ZNcub4C&pg=PA127|author1=Simovici, Dan A. |author2=Djeraba, Chabane |lastauthoramp=yes }}</ref> is a ] ≤ over a ] ''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 ].) |
|
|
|
|
|
|
|
{{Rcatsh| |
|
The axioms for a non-strict partial order state that the relation ≤ is ], ], and ]. That is, for all ''a'', ''b'', and ''c'' in ''P'', it must satisfy: |
|
|
|
{{R to section}} |
|
|
{{R with Wikidata item}} |
|
|
{{R with history}} |
|
|
}} |
|
|
|
|
|
|
{{Authority control}} |
|
# ''a'' ≤ ''a'' (]: every element is related to itself). |
|
|
# if ''a'' ≤ ''b'' and ''b'' ≤ ''a'', then ''a'' = ''b'' (]: two distinct elements cannot be related in both directions). |
|
|
# if ''a'' ≤ ''b'' and ''b'' ≤ ''c'', then ''a'' ≤ ''c'' (]: 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 ]. |
|
|
|
|
|
A set with a partial order is called a ''']''' (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, ] 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 ''']'''. 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}} |
|