Editing Partially ordered set (section)

== Derived notions ==

The examples use the poset <math>(\mathcal{P}(\{x, y, z\}),\subseteq)</math> consisting of the [[Power set|set of all subsets]] of a three-element set <math>\{x, y, z\},</math> ordered by set inclusion (see Fig.&nbsp;1).
* ''a'' is ''related to'' ''b'' when ''a'' ≤ ''b''. This does not imply that ''b'' is also related to ''a'', because the relation need not be [[Symmetric relation|symmetric]]. For example, <math>\{x\}</math> is related to <math>\{x, y\},</math> but not the reverse.
* ''a'' and ''b'' are ''[[Comparability|comparable]]'' if {{nowrap|''a'' ≤ ''b''}} or {{nowrap|''b'' ≤ ''a''}}. Otherwise they are ''incomparable''. For example, <math>\{x\}</math> and <math>\{x, y, z\}</math> are comparable, while <math>\{x\}</math> and <math>\{y\}</math> are not.
* A ''[[Totally ordered set|total order]]'' or ''linear order'' is a partial order under which every pair of elements is comparable, i.e. [[Trichotomy (mathematics)|trichotomy]] holds. For example, the natural numbers with their standard order.
* A ''[[Chain (order theory)|chain]]'' is a subset of a poset that is a totally ordered set. For example, <math>\{ \{\,\}, \{x\}, \{x, y, z\} \}</math> is a chain.
* An ''[[antichain]]'' is a subset of a poset in which no two distinct elements are comparable. For example, the set of [[Singleton (mathematics)|singleton]]s <math>\{\{x\}, \{y\}, \{z\}\}.</math>
* An element ''a'' is said to be ''strictly less than'' an element ''b'', if ''a'' ≤ ''b'' and <math>a \neq b.</math> For example, <math>\{x\}</math> is strictly less than <math>\{x, y\}.</math>
* An element ''a'' is said to be ''[[Covering relation|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 <math>a \neq b</math> are true, and ''a'' ≤ ''c'' ≤ ''b'' is false for each ''c'' with <math>a \neq c \neq b.</math> Using the strict order <, the relation ''a'' ⋖ ''b'' can be equivalently rephrased as "{{nowrap|''a'' < ''b''}} but not {{nowrap|''a'' < ''c'' < ''b''}} for any ''c''". For example, <math>\{x\}</math> is covered by <math>\{x, z\},</math> but is not covered by <math>\{x, y, z\}.</math>

=== Extrema ===
[[File:Hasse diagram of powerset of 3 no greatest or least.svg|thumb|upright=1.5|'''Fig. 5''' The figure above with the greatest and least elements removed. In this reduced poset, the top row of elements are all {{em|maximal}} elements, and the bottom row are all {{em|minimal}} elements, but there is no {{em|greatest}} and no {{em|least}} element.]]

There are several notions of "greatest" and "least" element in a poset <math>P,</math> notably:
* [[Greatest element]] and least element: An element <math>g \in P</math> is a {{em|greatest element}} if <math>a \leq g</math> for every element <math>a \in P.</math> An element <math>m \in P</math> is a {{em|least element}} if <math>m \leq a</math> for every element <math>a \in P.</math> A poset can only have one greatest or least element. In our running example, the set <math>\{x, y, z\}</math> is the greatest element, and <math>\{\,\}</math> is the least.
* [[Maximal element]]s and minimal elements: An element <math>g \in P</math> is a maximal element if there is no element <math>a \in P</math> such that <math>a > g.</math> Similarly, an element <math>m \in P</math> is a minimal element if there is no element <math>a \in P</math> such that <math>a < m.</math> If a poset has a greatest element, it must be the unique maximal element, but otherwise there can be more than one maximal element, and similarly for least elements and minimal elements. In our running example, <math>\{x, y, z\}</math> and <math>\{\,\}</math> are the maximal and minimal elements. Removing these, there are 3 maximal elements and 3 minimal elements (see Fig.&nbsp;5).
* [[Upper and lower bounds]]: For a subset ''A'' of ''P'', an element ''x'' in ''P'' is an upper bound of ''A'' if ''a''&nbsp;≤&nbsp;''x'', for each element ''a'' in ''A''. In particular, ''x'' need not be in ''A'' to be an upper bound of ''A''. Similarly, an element ''x'' in ''P'' is a lower bound of ''A'' if ''a''&nbsp;≥&nbsp;''x'', for each element ''a'' in ''A''. A greatest element of ''P'' is an upper bound of ''P'' itself, and a least element is a lower bound of ''P''. In our example, the set <math>\{x, y\}</math> is an {{em|upper bound}} for the collection of elements <math>\{\{x\}, \{y\}\}.</math>

[[File:Infinite lattice of divisors.svg|thumb|upright|'''Fig. 6''' [[Nonnegative integer]]s, ordered by divisibility]]
As another example, consider the positive [[integer]]s, ordered by divisibility: 1 is a least element, as it [[divisor|divides]] all other elements; on the other hand this poset does not have a greatest element.  This partially ordered set does not even have any maximal elements, since any ''g'' divides for instance 2''g'', which is distinct from it, so ''g'' is not maximal. If the number 1 is excluded, while keeping divisibility as ordering on the elements greater than 1, then the resulting poset does not have a least element, but any [[prime number]] is a minimal element for it. In this poset, 60 is an upper bound (though not a least upper bound) of the subset <math>\{2, 3, 5, 10\},</math> which does not have any lower bound (since 1 is not in the poset); on the other hand 2 is a lower bound of the subset of powers of 2, which does not have any upper bound.  If the number 0 is included, this will be the greatest element, since this is a multiple of every integer (see Fig.&nbsp;6).