Poset: Exercises

Try these ex­er­cises to test your poset knowl­edge.

Cor­po­rate Ladder

Imag­ine a com­pany with five dis­tinct roles: CEO, mar­ket­ing man­ager, mar­keter, IT man­ager, and IT worker. At this com­pany, if the CEO gives an or­der, ev­ery­one else must fol­low it. If an or­der comes from an IT man­ager, only IT work­ers are obli­gated to fol­low it. Similarly, if an or­der comes from a mar­ket­ing man­ager, only mar­keters are obli­gated to fol­low it. No­body is obli­gated to fol­low or­ders from mar­keters or IT work­ers.

Do the work­ers at this com­pany form a poset un­der the “obli­gated to fol­low or­ders from” re­la­tion?

While not tech­ni­cally a poset due to its lack of re­flex­ivity, it is pretty close. It is ac­tu­ally a strict or­der­ing, whose un­der­ly­ing par­tial or­der could be ob­tained by mak­ing the rea­son­able as­sump­tion that each worker will fol­low her own or­ders.

Bag Inclusion

We can define a no­tion of power sets for bags as fol­lows. Let \(X\) be a set, then we use \(\mathcal{M}(X)\) to de­note the set of all bags con­tain­ing el­e­ments of \(X\). Let \(A \in \mathcal{M}(X)\). The mul­ti­plic­ity func­tion of \(A\), \(1_A : X \rightarrow \mathbb N\) maps each el­e­ment of \(X\) to the num­ber of times that el­e­ment oc­curs in \(A\). We can use mul­ti­plic­ity func­tions to define a in­clu­sion re­la­tion \(\subseteq\) for bags. For \(A, B \in \mathcal M(X)\), we write \(A \subseteq B\) when­ever for all \(x \in X\), \(1_A(x) \leq 1_B(x)\).

Does \(\mathcal{M}(X)\) form a poset un­der the bag in­clu­sion re­la­tion \(\subseteq\)? If so, prove it. Other­wise, show that it does not satisfy one of the three poset prop­er­ties.

Duality

Give the dual of the fol­low­ing propo­si­tion.

For all posets \(P\) and all \(p, q \in P\), \(q \prec p\) im­plies that \(\{ r \in P~|~r \leq p \}\) is a su­per­set of \(\{ r \in P~|~r \leq q\}\).

For all posets \(P\) and all \(p, q \in P\), \(q \succ p\) im­plies that \(\{ r \in P~|~r \geq p \}\) is a su­per­set of \(\{ r \in P~|~r \geq q\}\) (where \(q \succ p\) means \(p \prec q\)).

Hasse diagrams

Let \(X = \{ x, y, z \}\). Draw a Hasse di­a­gram for the poset \(\langle \mathcal P(X), \subseteq \rangle\) of the power set of \(X\) or­dered by in­clu­sion.

A Hasse diagram of the power set of X, ordered by inclusion

<div><div>

com­ment: dot source:

di­graph G { node = 0.1, height = 0.1 edge = “none” e = “{}” x = “{x}” y = “{y}” z = “{z}” xy = “{x,y}” xz = “{x,z}” yz = “{y,z}” xyz = “{x,y,z}”

rankdir = BT; e → x e → y e → z x → xy x → xz y → xy y → yz z → xz z → yz xy → xyz xz → xyz yz → xyz } <div>%%

%%

Hasse di­a­grams (en­core)

Is it pos­si­ble to draw a Hasse di­a­gram for any poset?

Note that our de­scrip­tion of Hasse di­a­grams made use of the cov­ers re­la­tion \(\prec\). The cov­ers re­la­tion, how­ever, is not ad­e­quate to de­scribe the struc­ture of many posets. Con­sider the poset \(\langle \mathbb R, \leq \rangle\) of the real num­bers or­dered by the stan­dard com­par­i­son \(\leq\). We have \(0 < 1\), but how would we con­vey that with a Hasse di­a­gram? The prob­lem is that \(0\) has no cov­ers, even though it is not a max­i­mal el­e­ment in \(\mathbb R\). In fact, for any \(x \in \mathbb R\) such that \(x > 0\), we can find a \(y \in \mathbb R\) such that \(0 < y < x\). This “in­finite den­sity” of \(\mathbb R\) makes it im­pos­si­ble to de­pict us­ing a Hasse di­a­gram.

Parents:

  • Partially ordered set

    A set en­dowed with a re­la­tion that is re­flex­ive, tran­si­tive, and an­ti­sym­met­ric.

    • Order theory

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