TAOCP 2.2.3 Exercise 15

Let $(S,\preceq)$ be a partially ordered set.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.2.3: Linked Allocation

Exercise 15. [M25] Show that for any partial ordering on a finite set $S$ there is a unique set of irredundant relations that characterizes this ordering, as in (18) and Fig. 6. Is the same fact true also when $S$ is an infinite set?

Verified: yes
Solve time: 1m49s

Solution

Let $(S,\preceq)$ be a partially ordered set. Following the terminology of (18) and Fig. 6, call a relation $x\prec y$ irredundant if it is not implied by transitivity from other relations. Equivalently, $(x,y)$ is irredundant if

$$ x\prec y $$

and there is no $z\in S$ such that

$$ x\prec z\prec y. $$

These are exactly the covering relations of the poset. Define

$$ R={(x,y)\in S\times S:\ x\prec y \text{ and there is no } z \text{ with } x\prec z\prec y}. $$

We shall show that when $S$ is finite, $R$ is the unique irredundant set of relations that determines the order.

Existence

Let $x,y\in S$ with $x\prec y$.

Since $S$ is finite, among all chains from $x$ to $y$,

$$ x=x_0\prec x_1\prec\cdots\prec x_k=y, $$

choose one having maximal length.

We claim that each adjacent pair $x_{i-1}\prec x_i$ is irredundant. Suppose instead that for some $i$ there exists $z$ with

$$ x_{i-1}\prec z\prec x_i. $$

Then inserting $z$ into the chain gives

$$ x=x_0\prec\cdots\prec x_{i-1}\prec z\prec x_i\prec\cdots\prec x_k=y, $$

a longer chain from $x$ to $y$, contradicting maximality. Hence every adjacent pair belongs to $R$.

Therefore

$$ x=x_0\preceq x_1\preceq\cdots\preceq x_k=y $$

is a chain whose successive relations lie in $R$. By transitivity, every relation $x\preceq y$ of the original order follows from $R$.

Conversely, every relation in $R$ already belongs to $\preceq$, and every relation obtained from $R$ by repeated applications of transitivity also belongs to $\preceq$, since $\preceq$ is transitive. Thus $R$ generates exactly the given partial order.

Hence an irredundant characterization exists.

Uniqueness

Suppose $R'$ is another irredundant set of relations that generates the same partial order.

Take any $(x,y)\in R$. Since $R'$ generates the order and $x\prec y$, there is a chain

$$ x=x_0\prec x_1\prec\cdots\prec x_k=y $$

whose successive pairs belong to $R'$.

If $k>1$, then $x_1$ satisfies

$$ x\prec x_1\prec y, $$

contradicting the fact that $(x,y)$ is irredundant. Therefore $k=1$, so $(x,y)\in R'$.

Hence $R\subseteq R'$.

Interchanging the roles of $R$ and $R'$ gives $R'\subseteq R$. Therefore

$$ R=R'. $$

Thus every partial ordering on a finite set has a unique irredundant set of relations. Equivalently, the Hasse diagram of a finite poset is uniquely determined.

Infinite sets

The statement is false for infinite sets.

Consider the set

$$ S=\mathbb{Q} $$

with the usual order $\le$.

For any $a<b$ in $\mathbb{Q}$, there exists a rational number $c$ such that

$$ a<c<b. $$

Therefore no pair $a<b$ is irredundant. The set of irredundant relations is empty.

But the empty set of relations generates only the identity relation (after adding reflexivity), not the usual order on $\mathbb{Q}$. Hence the order on $\mathbb{Q}$ cannot be characterized by its irredundant relations.

So the finite theorem fails for infinite sets: an infinite poset need not even possess an irredundant characterization, let alone a unique one.

Therefore:

  • For every finite partially ordered set, there is a unique irredundant set of relations characterizing the order.
  • For infinite partially ordered sets, the statement is false. For example, $(\mathbb{Q},\le)$ has no irredundant relations at all, so the order cannot be recovered from irredundant relations. ∎