Poset: Exercises

Kevin Clancy18 Jun 2016 15:12 UTC

Try these exercises to test your poset knowledge.

Corporate Ladder

Imagine a company with five distinct roles: CEO, marketing manager, marketer, IT manager, and IT worker. At this company, if the CEO gives an order, everyone else must follow it. If an order comes from an IT manager, only IT workers are obligated to follow it. Similarly, if an order comes from a marketing manager, only marketers are obligated to follow it. Nobody is obligated to follow orders from marketers or IT workers.

Do the workers at this company form a poset under the “obligated to follow orders from” relation?

While not technically a poset due to its lack of reflexivity, it is pretty close. It is actually a strict ordering, whose underlying partial order could be obtained by making the reasonable assumption that each worker will follow her own orders.

Bag Inclusion

We can define a notion of power sets for bags as follows. Let \(X\) be a set, then we use \(\mathcal{M}(X)\) to denote the set of all bags containing elements of \(X\). Let \(A \in \mathcal{M}(X)\). The multiplicity function of \(A\), \(1_A : X \rightarrow \mathbb N\) maps each element of \(X\) to the number of times that element occurs in \(A\). We can use multiplicity functions to define a inclusion relation \(\subseteq\) for bags. For \(A, B \in \mathcal M(X)\), we write \(A \subseteq B\) whenever for all \(x \in X\), \(1_A(x) \leq 1_B(x)\).

Does \(\mathcal{M}(X)\) form a poset under the bag inclusion relation \(\subseteq\)? If so, prove it. Otherwise, show that it does not satisfy one of the three poset properties.

Duality

Give the dual of the following proposition.

For all posets \(P\) and all \(p, q \in P\), \(q \prec p\) implies that \(\{ r \in P~|~r \leq p \}\) is a superset of \(\{ r \in P~|~r \leq q\}\).

For all posets \(P\) and all \(p, q \in P\), \(q \succ p\) implies that \(\{ r \in P~|~r \geq p \}\) is a superset 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 diagram for the poset \(\langle \mathcal P(X), \subseteq \rangle\) of the power set of \(X\) ordered by inclusion.

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

<div><div>

comment: dot source:

digraph 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 diagrams (encore)

Is it possible to draw a Hasse diagram for any poset?

Note that our description of Hasse diagrams made use of the covers relation \(\prec\). The covers relation, however, is not adequate to describe the structure of many posets. Consider the poset \(\langle \mathbb R, \leq \rangle\) of the real numbers ordered by the standard comparison \(\leq\). We have \(0 < 1\), but how would we convey that with a Hasse diagram? The problem is that \(0\) has no covers, even though it is not a maximal element 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 “infinite density” of \(\mathbb R\) makes it impossible to depict using a Hasse diagram.

Kevin Clancy18 Jun 2016 15:12 UTC

Parents: