# 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.

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.

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$$.

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>

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.

• @1 I was go­ing to add an ex­am­ples lens to this page, but I seem to have lost the abil­ity to cre­ate lenses. I re­mem­ber be­ing able to cre­ate lenses by plac­ing an or­ange but­ton in the bot­tom right cor­ner. That does not cur­rently work, how­ever: the “cre­ate lens” icon doesn’t show up.

• We re­moved that but­ton from the quick menu be­cause it had too many but­tons. Now you have to cre­ate a page, then add this page as a par­ent, and then change the page’s type to “Lens” in set­tings. As I typed this, I re­al­ized how many steps that is. We’ll make this sim­pler.

• Should the p’s and q’s in one of these be switched?

• Would it be ap­pro­pri­ate to link to the Un­der­ly­ing set page here?

• Maybe. I haven’t done so be­cause the un­der­ly­ing set page de­scribes un­der­ly­ing sets speci­fi­cally in terms of alge­braic struc­tures. I think that a link to that page would there­fore just cause con­fu­sion.

• de­scribes un­der­ly­ing sets speci­fi­cally in terms of alge­braic structures

Yeah, I was won­der­ing about that. Does it make sense to have an “un­der­ly­ing set” page that works for both cases?

Ac­tu­ally, I’m go­ing to ask this in the slack, as oth­ers may have opinions…

• I’m think­ing the full name of the ar­ti­cle should be “Par­tially or­dered set”, with “poset” as an alias and al­ter­nate form in the ar­ti­cle.