Partially ordered set

A par­tially or­dered set (also called a poset) is a pair \(\langle P, \leq \rangle\) of a set \(P\) and a bi­nary re­la­tion \(\leq\) on \(P\) such that for all \(p,q,r \in P\), the fol­low­ing prop­er­ties are satis­fied:

\(P\) is referred to as the poset’s un­der­ly­ing set and \(\leq\) is referred to as its or­der re­la­tion. Posets are the cen­tral ob­ject of study in or­der the­ory.

No­ta­tions and fundamentals

Greater than

A greater than re­la­tion \(\geq\) can be de­rived as the trans­pose of a poset’s less than re­la­tion: \(a \geq b\) means that \(b \leq a\).

Incomparability

For poset el­e­ments \(p\) and \(q\), if nei­ther \(p \leq q\) nor \(q \leq p\) then we say that \(p\) and \(q\) are in­com­pa­rable, and write \(p \parallel q\).

Strict orders

From any poset \(\langle P, \leq \rangle\), we can de­rive an un­der­ly­ing strict or­der \(<). For \(p, q \in P\), \(p < q\) means that the fol­low­ing con­di­tions are satis­fied:

  • 1.) \(p \leq q\)

  • 2.) \(p \neq q\)

The cover relation

From any poset \(\langle P, \leq \rangle\), we can de­rive an un­der­ly­ing cover re­la­tion \(\prec\), defined such that for \(p,q \in P\), \(p \prec q\) when­ever the fol­low­ing two con­di­tions are satis­fied:

  • 1.) \(p < q\)

  • 2.) For all \(r \in P\), \(p \leq r < q\) im­plies \(p = r\)

Sim­ply put, \(p \prec q\) means that \(q\) is the small­est el­e­ment of \(P\) which is strictly greater than \(p\). \(p \prec q\) is pro­nounced ”\(p\) is cov­ered by \(q\)”, or ”\(q\) cov­ers \(p\)”, and \(q\) is said to be a cover of \(p\).

Hasse diagrams

Let \(\langle P, \leq \rangle\) be the poset such that \(P = \{ p, q, r \}\) and \(\leq = \{(p,p),(p,q)(p,r),(q,q),(q,r),(r,r) \}\). The or­der re­la­tion \(\leq\), be­ing bi­nary, can be de­picted as a di­rected graph, though the re­sult­ing image leaves some­thing to be de­sired.

Naive first attempt at representing P with a directed graph

com­ment: dot source:

di­graph G { node = 0.1, height = 0.1 rankdir = BT; p → q; q → r; p → p; r → r; q → q; p → r; } <div>

In­clud­ing an edge for ev­ery pair in \(\leq\) re­sults in a rather noisy look­ing graph. In par­tic­u­lar, as long as we are un­der as­sump­tion that the graph we are view­ing de­picts a poset, plac­ing a re­flex­ive edge on each node is te­dious and re­dun­dant. Our first step to­ward clean­ing up this graph is to re­move all re­flex­ive edges, in­stead leav­ing re­flex­ivity as an im­plicit as­sump­tion. Like­wise, we can leave those edges which are im­plied by tran­si­tivity — \((p,r)\) is the only such edge in this poset — im­plicit. As a fi­nal step, we re­move the ar­row heads from our edges, leav­ing their di­rec­tions im­plied by the y-co­or­di­nates of the nodes they con­nect: an edge be­tween two nodes means that the poset el­e­ment cor­re­spond­ing to the lower node is less than the poset el­e­ment cor­re­spond­ing to the higher node. The sim­plified de­pic­tion of \(\langle P, \leq \rangle\) then fol­lows.

Hasse diagram for P

com­ment: dot source:

di­graph G { node = 0.1, height = 0.1; edge = “none”; rankdir = BT; p → q; q → r; } <div>

Such a de­pic­tion is called a Hasse di­a­gram; draw­ing a Hasse di­a­gram is the stan­dard method for vi­su­ally de­pict­ing a poset. Now that we un­der­stand what Hasse di­a­grams are, we can provide a con­cise defi­ni­tion: a Hasse di­a­gram is a graph-based vi­sual de­pic­tion of a poset \(\langle P, \leq \rangle\), where el­e­ments of \(P\) are rep­re­sented as nodes, and for all \((p,q) \in P^2\) such that \(p \prec q\), an up­ward edge is drawn from \(p\) to \(q\).

\(p \leq q\) re­quires that \(p\) must ap­pear lower in a Hasse di­a­gram than \(q\). How­ever, the con­verse is not true. In the fol­low­ing Hasse di­a­gram, \(t \parallel r\) even though \(t\) is po­si­tioned lower than \(r\).

t is lower than r but incomparable to r

com­ment: dot source:

di­graph G { node = 0.1, height = 0.1; edge = “none”; rankdir = BT; p → t; p → r; t → q; q → s; r → s; } <div>

Duality

Every poset \(\langle P, \leq \rangle\) has a cor­re­spond­ing dual poset \(\langle P^{\partial}, \geq \rangle\), where \(P^{\partial}\) (pro­nounced “P op”) is a set whose el­e­ments are in cor­re­spon­dence with those of \(P\), and \(\geq\) is the trans­pose of \(\leq\) dis­cussed pre­vi­ously. The Hasse di­a­gram of \(P^{\partial}\) is ob­tained by flip­ping the Hasse di­a­gram of \(P\) up­side down. When­ever \(\phi\) is a prop­si­tion about posets, we ob­tain \(\phi\)’s dual propo­si­tion \(\phi^{\partial}\) by re­plac­ing all oc­curences of \(\leq\) with \(\geq\) and all oc­cur­rences of \(\geq\) with \(\leq\).

The ex­is­tence of dual posets and dual propo­si­tions gives rise to the du­al­ity prin­ci­ple: if a propo­si­tion \(\forall P. \phi\), quan­tified over all posets, is true then its dual \(\forall P. \phi^{\partial}\) is also true. The du­al­ity prin­ci­ple works be­cause in­stan­ti­at­ing \(\forall P. \phi\) with a poset \(P\) is equiv­a­lent to in­stan­ti­at­ing \(\forall P. \phi^{\partial}\) with \(P^{\partial}\). This is due to the fact that \(a \leq b\) in \(P\) iff \(a \geq b\) in \(P^{\partial}\). The­o­rems in­volv­ing posets of­ten come with a free dual the­o­rem thanks to the du­al­ity prin­ci­ple.

knows-req­ui­site(Cat­e­gory the­ory):

Poset as category

Any poset \(\langle P, \leq \rangle\) can be viewed as a cat­e­gory in which the ob­jects are the el­e­ments of \(P\), and for all \(p,q \in P\), there is a unique mor­phism from \(p\) to \(q\) iff \(p \leq q\). This cat­e­gory has clo­sure un­der mor­phism com­po­si­tion due to the tran­si­tivity of \(\leq\) and iden­tity mor­phisms due to the re­flex­ivity of \(\leq\). As­so­ci­a­tivity of mor­phism com­po­si­tion stems from the unique­ness of ar­rows be­tween any pair of ob­jects. The func­tors be­tween poset cat­e­gories are mono­tone maps. <div>

Ad­di­tional Material

For some ad­di­tional ex­am­ples of posets, see Poset: Ex­am­ples. To test your knowl­edge of posets, try these ex­er­cises. The most use­ful op­er­a­tors on el­e­ments of a poset are called the join and meet. We can re­late the el­e­ments of one poset to an­other through the use of mono­tone func­tions.

Children:

Parents:

  • Order theory

    The study of bi­nary re­la­tions that are re­flex­ive, tran­si­tive, and an­ti­sym­metic.