Exercise 5.1.1

Show that the assumption that we are always able to determine which candidate is best, in line 4 of procedure HIRE-ASSISTANT, implies that we know a total order of the ranks of the candidates.

A total order is a partial order that is a total relation ($\forall a,b \in A: a R b \text{ or } b R a$). A relation is a partial order if it is reflexive, antisymmetric and transitive.

Let's assume that the relation is "is as good or better".

• Reflexive: This is a bit trivial, but everybody is as good or better as themselves.
• Transitive: If A is better than B and B is better than C, then A is better than C - that's also obvious.
• Antisymmetric: If A is better than B, then B is not better than A.

So far we have a partial order.

Since we assume we can compare any two candidates, then comparison must be a total relation and thus we have a total order.