Value assignment for complete, transitive relation

Question

Consider a finite set $A$ and a relation $r$.

The relation $r$ is complete, i.e., for any $a,b\in A$, we have $arb$ or $bra$ or both.

The relation $r$ is transitive, i.e., for any $a,b,c\in A$, if $arb$ and $brc$, then $arc$.

Show that there exists a function $f:A\rightarrow\mathbb{R}$ such that for any $a,b\in A$, we have $arb$ if and only if $f(a)\geq f(b)$.

I have the intuition that for any $a,b\in A$, if $arb$ but not $bra$, then assign $f(a)>f(b)$. If $arb$ and $bra$, assign $f(a)=f(b)$.

But how to prove that we can assign values for all $a\in A$ without getting a contradiction?

Answer 1

Correct Proof

Define a relation s in A based on the relation r by asb if arb and bra. Then s is an equivalence relation (reflexive, transitive, symmetric) and the set A can be partitioned into equivalence classes $\mathscr A = ${$ A_1, A_2, ... $}. Now define the relation R on these equivalence classes by $A_i R A_j$ if $(a_i \in A_i) r (a_j \in A_j)$. This relation is well defined: if $A_i R A_j$ and $b \in A_i$ then $b r a_i$ and $a_i r a_j$ so $b r a_j$ by the transitivity of r. R is also a total order on the equivalence classes: complete, transitive, antisymmetric (and reflexive). The first two are inherited from r, and antisymmetric by the definition of the equivalence classes.

Now, with a finite A, $\mathscr A $ is also finite and can be sequenced (uniquely) as {$A_1, A_2, ...A_m$} where $A_{i+1} R A_i$. Now define the function f by the mapping $f: (a \in A_i) \rightarrow i$

$(a \in A_i) r (b \in A_j) \Leftrightarrow A_j R A_i \Leftrightarrow (j = i) $ by the reflexive property of R, or $(i > j)$ by the ordering of $\mathscr A$, i.e. $arb \Leftrightarrow f(a) \ge f(b)$.

Apologies: this proof I originally gave is not complete.

You can order the set A by the relation r, but not necessarily uniquely and this doesn't matter.

With A being finite with n elements, choose a sequence $(a_1, a_2, ....a_n)$ where $a_{i+1}ra_i$. You know that you can do this because of completeness and transitivity.

Then let f be the mapping $a_i \rightarrow i$

This original proof shows that if $i > j $ then $a_i r a_j$, but the definition of r allows $a_i r a_j$ and $a_j r a_i$ and in this case $a_j r a_i$ does not give $j \ge i$. The proof fails to consider "equivalent" elements in A, i.e. $a_i r a_j$ and $a_j r a_i$, hence the use of equivalence classes in the correct proof.

Answer 2

We can use induction on the size of $A$.

For $|A|=1$, the claim is trivial.

Suppose that any complete transitive relation on $n$ elements can be mapped to $(\Bbb R,\le)$, and let $(A,r)$ have $n+1$ elements.

Now you can proceed in many ways, perhaps the easiest is if we choose a smallest element $a_0$ of $A$, with respect to $r\ $ (such must exist, as $A$ is finite), and then use the induction hypothesis on the $n$ element set $A\setminus\{a_0\}\,$...

Note that we could equally well used $\Bbb Z$ or $\Bbb N$ in this construction instead of $\Bbb R$ as the codomain of $f$.