Editing Partially ordered set (section)

== Examples ==

[[File:Division relation 4.svg|thumb|alt=Division Relationship Up to 4|'''Fig. 3''' Graph of the divisibility of numbers from 1 to 4. This set is partially, but not totally, ordered because there is a relationship from 1 to every other number, but there is no relationship from 2 to 3 or 3 to 4]]

Standard examples of posets arising in mathematics include:
* The [[real number]]s, or in general any totally ordered set, ordered by the standard ''less-than-or-equal'' relation ≤, is a partial order.
* On the real numbers <math>\mathbb{R}</math>, the usual [[less than]] relation < is a strict partial order. The same is also true of the usual [[greater than]] relation > on <math>\R</math>.
* By definition, every [[strict weak order]] is a strict partial order.
* The set of [[subset]]s of a given set (its [[power set]]) ordered by [[subset|inclusion]] (see Fig.&nbsp;1). Similarly, the set of [[sequence]]s ordered by [[subsequence]], and the set of [[string (computer science)|string]]s ordered by [[substring]].
* The set of [[natural number]]s equipped with the relation of [[divisor|divisibility]]. (see Fig.&nbsp;3 and Fig.&nbsp;6)
* The vertex set of a [[directed acyclic graph]] ordered by [[reachability]].
* The set of [[Linear subspace|subspaces]] of a [[vector space]] ordered by inclusion.
* For a partially ordered set ''P'', the [[sequence space]] containing all [[sequence]]s of elements from ''P'', where sequence ''a'' precedes sequence ''b'' if every item in ''a'' precedes the corresponding item in ''b''. Formally, <math>\left(a_n\right)_{n \in \N} \leq \left(b_n\right)_{n \in \N}</math> if and only if <math>a_n \leq b_n</math> for all <math>n \in \N</math>; that is, a [[componentwise order]].
* For a set ''X'' and a partially ordered set ''P'', the [[function space]] containing all functions from ''X'' to ''P'', where {{nowrap|''f'' ≤ ''g''}} if and only if {{nowrap|''f''(''x'') ≤ ''g''(''x'')}} for all <math>x \in X.</math>
* A [[Fence (mathematics)|fence]], a partially ordered set defined by an alternating sequence of order relations {{nowrap|''a'' < ''b'' > ''c'' < ''d'' ...}}
* The set of events in [[special relativity]] and, in most cases,{{efn|See ''{{slink|General relativity#Time travel}}''.}} [[general relativity]], where for two events ''X'' and ''Y'', {{nowrap|''X'' ≤ ''Y''}} if and only if ''Y'' is in the future [[light cone]] of ''X''. An event ''Y'' can be causally affected by ''X'' only if {{nowrap|''X'' ≤ ''Y''}}.

One familiar example of a partially ordered set is a collection of people ordered by [[genealogy|genealogical]] descendancy. Some pairs of people bear the descendant-ancestor relationship, but other pairs of people are incomparable, with neither being a descendant of the other.

=== Orders on the Cartesian product of partially ordered sets ===
{{multiple image
| align = right
| dirction = horizontal
| total_width = 550
| image1 = Lexicographic order on pairs of natural numbers.svg
| caption1 = '''Fig. 4a''' Lexicographic order on <math>\N \times \N</math>
| image2 = N-Quadrat, gedreht.svg|
| caption2 = '''Fig. 4b''' Product order on <math>\N \times \N</math>
| image3 = Strict product order on pairs of natural numbers.svg|
| caption3 = '''Fig. 4c''' Reflexive closure of strict direct product order on <math>\N \times \N.</math> Elements [[#Formal definition|covered]] by {{nowrap|(3, 3)}} and covering {{nowrap|(3, 3)}} are highlighted in green and red, respectively.
}}
In order of increasing strength, i.e., decreasing sets of pairs, three of the possible partial orders on the [[Cartesian product]] of two partially ordered sets are (see Fig.&nbsp;4):
* the [[lexicographical order]]: &nbsp; {{nowrap|(''a'', ''b'') ≤ (''c'', ''d'')}} if {{nowrap|''a'' < ''c''}} or ({{nowrap|1=''a'' = ''c''}} and {{nowrap|''b'' ≤ ''d''}});
* the [[product order]]:  &nbsp; (''a'', ''b'') ≤ (''c'', ''d'') if ''a'' ≤ ''c'' and ''b'' ≤ ''d'';
* the [[reflexive closure]] of the [[Direct product#Direct product of binary relations|direct product]] of the corresponding strict orders:  &nbsp; {{nowrap|(''a'', ''b'') ≤ (''c'', ''d'')}} if ({{nowrap|''a'' < ''c''}} and {{nowrap|''b'' < ''d''}}) or ({{nowrap|1=''a'' = ''c''}} and {{nowrap|1=''b'' = ''d''}}).

All three can similarly be defined for the Cartesian product of more than two sets.

Applied to [[ordered vector space]]s over the same [[Field (mathematics)|field]], the result is in each case also an ordered vector space.

See also [[Total order#Orders on the Cartesian product of totally ordered sets|orders on the Cartesian product of totally ordered sets]].

=== Sums of partially ordered sets ===
{{anchor|sum}}
Another way to combine two (disjoint) posets is the '''ordinal sum'''<ref>
{{citation
 | last1 = Neggers | first1 = J.
 | last2 = Kim | first2 = Hee Sik
 | contribution = 4.2 Product Order and Lexicographic Order
 | isbn = 9789810235895
 | pages = 62–63
 | publisher = World Scientific
 | title = Basic Posets
 | year = 1998
}}</ref> (or '''linear sum'''),{{sfnp|Davey|Priestley|2002|pp=[https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA17 17–18]}} {{nowrap|1=''Z'' = ''X'' ⊕ ''Y''}}, defined on the union of the underlying sets ''X'' and ''Y'' by the order {{nowrap|''a'' ≤<sub>''Z''</sub> ''b''}} if and only if:
* ''a'', ''b'' ∈ ''X'' with ''a'' ≤<sub>''X''</sub> ''b'', or
* ''a'', ''b'' ∈ ''Y'' with ''a'' ≤<sub>''Y''</sub> ''b'', or
* ''a'' ∈ ''X'' and ''b'' ∈ ''Y''.

If two posets are [[well-ordered]], then so is their ordinal sum.<ref>{{cite book|author=P. R. Halmos|title=Naive Set Theory|url=https://archive.org/details/naivesettheory0000halm_r4g0|url-access=registration|year=1974|publisher=Springer |isbn=978-1-4757-1645-0|page=[https://archive.org/details/naivesettheory0000halm_r4g0/page/82 82]}}</ref>

[[Series-parallel partial order]]s are formed from the ordinal sum operation (in this context called series composition) and another operation called parallel composition. Parallel composition is the [[disjoint union]] of two partially ordered sets, with no order relation between elements of one set and elements of the other set.