Poset: Exercises

https://arbital.com/p/poset_exercises

by Kevin Clancy Jun 18 2016 updated Aug 22 2016


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?

%%%hidden(Show solution): 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\}$~$.

%%hidden(Show solution): 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.

%%hidden(Show solution): A Hasse diagram of the power set of X, ordered by inclusion

%%%comment:
dot source:

digraph G {
  node [width = 0.1, height = 0.1]
  edge [arrowhead = "none"]
  e [label = "{}"]
  x [label = "{x}"]
  y [label = "{y}"]
  z [label = "{z}"]
  xy [label = "{x,y}"]
  xz [label = "{x,z}"]
  yz [label = "{y,z}"]
  xyz [label = "{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
}
%%%

%%

Hasse diagrams (encore)

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

%%hidden(Show solution): 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. %%


Comments

Mark Chimes

Does the first question seem a bit much of a 'gotcha'? I was slightly annoyed I got it wrong despite being quite capable of working with posets. XD

I suppose the way it is asked is completely valid, and will drive home the fact that relations have to be reflexive and illustrates very well what would be necessary to get a valid order.

What are other people's thoughts?

(Maybe it will be better once it isn't the only question, nor the first?).

Chris Pasek

I proposed an edit to fix these 2 issues (in the 1st example):

1) The answer claims there is no anti-symmetry, which is mistaken. In particular, if something breaks anti-symmetry, it cannot be a valid strict ordering (which is another claim from the answer).

2) This is less serious, but saying "everyone must follow orders that come from the CEO" in natural language is unclear on whether the CEO follows orders from himself.

Kevin Clancy

Thanks Chris. Edit accepted.

Eric Bruylant

Show solution Note that our description of Hasse diagrams made use of the covers relation $~$\\prec$~$\. The covers relation, however, is not a helpful in 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\.

Not clear what this means?