TAOCP 2.2.3 Exercise 9

Section 2.2.3: Linked Allocation

Exercise 9. [20] Which of the following relations is a partial ordering on the specified set $S$? [Note: If the relation "$x \prec y$" is defined below, the intent is to define the relation "$x \preceq y \equiv (x \prec y \text{ or } x = y)$," and then to determine whether $\preceq$ is a partial ordering.]

(a) $S =$ all rational numbers, $x \prec y$ means $x > y$.

(b) $S =$ all people, $x \prec y$ means $x$ is an ancestor of $y$.

(d) $S =$ all the mathematical results proved in this book, $x \prec y$ means the proof of $y$ depends upon the truth of $x$.

(e) $S =$ all positive integers, $x \preceq y$ means $x + y$ is even.

(f) $S =$ a set of subroutines, $x \prec y$ means "$x$ calls $y$," that is, $y$ may be in operation while $x$ is in operation, with recursion not allowed.

Verified: yes
Solve time: 47s

Solution

A relation $\preceq$ is a partial ordering if and only if it is reflexive, antisymmetric, and transitive.

(a)

Here $S$ is the set of all rational numbers, and $x \prec y$ means $x>y$. Therefore

$$ x\preceq y \iff (x>y \text{ or } x=y), $$

which is equivalent to

$$ x\ge y. $$

Reflexivity holds since $x=x$.

If $x\preceq y$ and $y\preceq x$, then $x\ge y$ and $y\ge x$, hence $x=y$. Thus antisymmetry holds.

If $x\preceq y$ and $y\preceq z$, then $x\ge y$ and $y\ge z$, hence $x\ge z$, so $x\preceq z$. Thus transitivity holds.

Therefore $\preceq$ is a partial ordering.

$$ \boxed{\text{Yes}} $$

(b)

Here $S$ is the set of all people, and $x \prec y$ means that $x$ is an ancestor of $y$.

By definition,

$$ x\preceq y \iff (x \text{ is an ancestor of } y \text{ or } x=y). $$

Reflexivity holds because $x=x$.

Suppose $x\preceq y$ and $y\preceq x$. If $x\ne y$, then $x$ is an ancestor of $y$ and $y$ is an ancestor of $x$, which is impossible. Hence $x=y$. Antisymmetry holds.

If $x\preceq y$ and $y\preceq z$, then each relation is either equality or ancestry. In every case, $x$ is either equal to or an ancestor of $z$. Thus $x\preceq z$. Transitivity holds.

Therefore $\preceq$ is a partial ordering.

$$ \boxed{\text{Yes}} $$

(c)

Here $S$ is the set of all integers, and

$$ x\preceq y $$

means that $x$ is a multiple of $y$.

Reflexivity holds since

$$ x=1\cdot x. $$

Antisymmetry fails. For example,

$$ 2\preceq (-2) $$

because $2=(-1)(-2)$, and

$$ (-2)\preceq 2 $$

because $-2=(-1)2$; yet

$$ 2\ne -2. $$

Since antisymmetry fails, $\preceq$ is not a partial ordering.

$$ \boxed{\text{No}} $$

(d)

Here $S$ is the set of all mathematical results proved in this book, and $x\prec y$ means that the proof of $y$ depends upon the truth of $x$.

Then

$$ x\preceq y $$

means that either $x=y$ or the proof of $y$ depends on $x$.

Reflexivity holds because of the equality clause.

If $x\preceq y$ and $y\preceq x$ with $x\ne y$, then the proof of $y$ depends on $x$ and the proof of $x$ depends on $y$. Such circular dependence cannot occur among valid proofs. Hence $x=y$, so antisymmetry holds.

If $x\preceq y$ and $y\preceq z$, then either equalities occur or the proof of $z$ depends on a result whose proof depends on $x$. Therefore the proof of $z$ depends on $x$, and $x\preceq z$. Thus transitivity holds.

Therefore $\preceq$ is a partial ordering.

$$ \boxed{\text{Yes}} $$

(e)

Here $S$ is the set of all positive integers, and

$$ x\preceq y $$

means that $x+y$ is even.

Reflexivity holds because

$$ x+x=2x $$

is even.

Antisymmetry fails. For example,

$$ 1\preceq 3 $$

and

$$ 3\preceq 1 $$

since both sums equal $4$, yet

$$ 1\ne 3. $$

Therefore $\preceq$ is not a partial ordering.

$$ \boxed{\text{No}} $$

(f)

Here $S$ is a set of subroutines, and $x\prec y$ means that $x$ calls $y$. Recursion is not allowed.

Then

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

Reflexivity holds because of equality.

Transitivity fails. Let $x$ call $y$ and let $y$ call $z$. Then

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

But $x$ need not call $z$ directly, so $x\preceq z$ need not hold. Hence transitivity fails.

Since a partial ordering must be transitive, $\preceq$ is not a partial ordering.

$$ \boxed{\text{No}} $$

Therefore the relations that define partial orderings are

$$ \boxed{(a),\ (b),\ (d)}. $$

The relations in

$$ \boxed{(c),\ (e),\ (f)} $$

do not define partial orderings.