# Poset: Exercises

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

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

• Does the first ques­tion seem a bit much of a ‘gotcha’? I was slightly an­noyed I got it wrong de­spite be­ing quite ca­pa­ble of work­ing with posets. XD

I sup­pose the way it is asked is com­pletely valid, and will drive home the fact that re­la­tions have to be re­flex­ive and illus­trates very well what would be nec­es­sary to get a valid or­der.

What are other peo­ple’s thoughts?

(Maybe it will be bet­ter once it isn’t the only ques­tion, nor the first?).

• I pro­posed an edit to fix these 2 is­sues (in the 1st ex­am­ple):

1) The an­swer claims there is no anti-sym­me­try, which is mis­taken. In par­tic­u­lar, if some­thing breaks anti-sym­me­try, it can­not be a valid strict or­der­ing (which is an­other claim from the an­swer).

2) This is less se­ri­ous, but say­ing “ev­ery­one must fol­low or­ders that come from the CEO” in nat­u­ral lan­guage is un­clear on whether the CEO fol­lows or­ders from him­self.

• Thanks Chris. Edit ac­cepted.

• Not clear what this means?