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

Line 4 of the procedure is indicating that a candidate better than the best we’ve seen so far is also better than every other candidate we’ve seen up until now. This indicates that we perceive the relation to be transitive.

Next, consider the simplicty of our procedure and how there are no edge cases or conditions. We expect to be able to perform this comparison on all candidates, and therefore our relation must be a total relation.

The procedure itself uses a strict \(>\) relation, but at this point we will suppose the existence of a separate \(\geq\) relation to show that the procedure implies a total order. In the context of the hiring problem we would likely seek to avoid incurring an additional hire cost when interviewing a candidate that is indistinguishible from our current employee. Thus it stands to reason that with this new underlying relation our definition of “better” would derive the relation \(>\) from \(\geq\) by seeking a candidate that is \(\geq\) best, but not \(=\) best. This does not invalidate previously determine propeties, but will simplify determining the remaining two properties necessary for a total order.

Trivially any candidate is identical to themself, and so our relation is reflexive.

If candidate two candidates \(x\) and \(y\) satisfy both \(x \geq y\) and \(y \geq x\) then \(x = y\). As in, candidate \(x\) and candidate \(y\) must be employees of identical caliber, not necessarily that they are the same person. Our relation is therefore antisymmetric.

Our relation is reflexive, antisymmetric, transitive and a total relation. Therefore it is a total order.