Show that the assumption that we are always able to determine which candidate is best, in line 4 of procedure \(\textsc{Hire-Assistant}\), implies that we know a total order on the ranks of the candidates.
To show this, we need to demonstrate that being able to compare any two candidates implies the three properties of a total order: comparability, transitivity, and antisymmetry.
What is a Total Order?
A total order on a set \(S\) is a binary relation \(\le\) that satisfies:
- Comparability: For all \(a, b \in S\), either \(a \le b\) or \(b \le a\)
- Transitivity: For all \(a, b, c \in S\), if \(a \le b\) and \(b \le c\), then \(a \le c\)
- Antisymmetry: For all \(a, b \in S\), if \(a \le b\) and \(b \le a\), then \(a = b\)
Applying to the Hiring Problem
In line 4 of \(\textsc{Hire-Assistant}\), we check “if candidate \(i\) is better than candidate \(best\)”. This assumption means:
Comparability: We can compare any two candidates \(i\) and \(j\) to determine which one is better. Either candidate \(i\) is better than candidate \(j\), or candidate \(j\) is better than candidate \(i\), or they are equally qualified.
Transitivity: If candidate \(i\) is better than candidate \(j\), and candidate \(j\) is better than candidate \(k\), then candidate \(i\) must be better than candidate \(k\). This is necessary for the algorithm to work correctly—otherwise, we might have circular comparisons where \(i > j\), \(j > k\), but \(k > i\), which would make it impossible to determine a “best” candidate.
Antisymmetry: If candidate \(i\) is at least as good as candidate \(j\), and candidate \(j\) is at least as good as candidate \(i\), then they must be equally qualified. The problem statement assumes no two candidates are equally qualified, so we have strict antisymmetry.
Since we can assign a unique rank to each candidate (with better candidates having higher ranks), and these ranks satisfy all three properties, we have a total order on the set of candidates.