TAOCP 2.2.3 Exercise 10

Section 2.2.3: Linked Allocation

Exercise 10. [M21] Given that "$\subset$" is a relation that satisfies properties (i) and (ii) of a partial ordering, prove that the relation "$\preceq$", defined by the rule "$x \preceq y$ if and only if $x = y$ or $x \subset y$," satisfies all three properties of a partial ordering.

Verified: yes
Solve time: 35s

---

Solution

Assume that the relation "$\subset$" satisfies properties (i) and (ii) of a partial ordering, namely:

(i) Transitivity:

$$ x \subset y,\ y \subset z \implies x \subset z. $$

(ii) Irreflexivity:

$$ x \not\subset x. $$

Define a new relation "$\preceq$" by

$$ x \preceq y \iff (x=y)\ \text{or}\ (x\subset y). $$

We must prove that $\preceq$ satisfies the three properties of a partial ordering.

First, $\preceq$ is reflexive. For every element $x$,

$$ x=x, $$

hence, by the definition of $\preceq$,

$$ x\preceq x. $$

Next, $\preceq$ is antisymmetric. Assume that

$$ x\preceq y,\qquad y\preceq x. $$

We must show that $x=y$.

Suppose, on the contrary, that $x\ne y$. Since $x\preceq y$ and $x\ne y$, the definition of $\preceq$ implies

$$ x\subset y. $$

Similarly, from $y\preceq x$ and $y\ne x$,

$$ y\subset x. $$

Property (i) then gives

$$ x\subset x. $$

This contradicts property (ii). Therefore the assumption $x\ne y$ is impossible, and we conclude that

$$ x=y. $$

Hence $\preceq$ is antisymmetric.

Finally, $\preceq$ is transitive. Assume that

$$ x\preceq y,\qquad y\preceq z. $$

There are four cases.

If $x=y$ and $y=z$, then $x=z$, so $x\preceq z$.

If $x=y$ and $y\subset z$, then

$$ x\subset z, $$

hence $x\preceq z$.

If $x\subset y$ and $y=z$, then

$$ x\subset z, $$

hence $x\preceq z$.

If $x\subset y$ and $y\subset z$, property (i) yields

$$ x\subset z, $$

hence $x\preceq z$.

In every case,

$$ x\preceq z. $$

Therefore $\preceq$ is transitive.

Since $\preceq$ is reflexive, antisymmetric, and transitive, it satisfies all three properties of a partial ordering.

This completes the proof.

∎