# Value assignment for complete, transitive relation on countably infinite set

Consider a 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$.

Must there exist 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)$?

If $A$ is finite, the answer is yes. I'm wondering what about if $A$ is countably infinite? Is there a counterexample?

## 1 Answer

Call $a,a' \in A$ equivalent provided both $ara'$ and $a'ra$, and note the conditions imply $f(a)=f(a')$ for equivalent $a,a'$. Let $T$ be a set of representatives for the equivalence classes, and enumerate $T$ as $t_0,t_1,t_2,...$. None of these $t$ are equivalent, so in all cases either $t<t'$ [meaning $trt']$ or $t'<t$ [meaning $t'rt$], but never both.

Based on this we may map $T$ (and so also $A$) into the set of dyadic rationals by an inductive process. First put $f(t_0)=0.$ Next if $t_1>t_0$ put $f(t_1)=1,$ and in the opposite case if $t_1<t_0$ put $f(t_1)=-1.$

Now assume that $f(t_i)$ has been defined for each $i \le m$, and that the values so far comprise a collection of dyadic rationals whose least element is an integer $a$ and greatest element another integer $b$. That is, the dyadics so far assigned to lie in the closed interval $[a,b]$, and each of $a,b$ have been assigned to. Now we consider the next $t$ namely $t_{m+1}.$ It either is > than each of $t_0...t_m$, in which case we put $f(t_{m+1})=b+1$, or it may be < than each of $t_0,...,t_m$ and we put $f(t_{m+1})=a-1,$ or finally there may be indices $i,j$ for which $t_i<t_{m+1}<t_j,$ in which case we put $f(t_{m+1})=(f(t_i)+f(t_j))/2.$

Since the terms in $T$ have all been assigned, and equivalent $a$'s have to go to the same $f$ value, this is a map from $A$ into the dyadic rationals and has the order preserving property required.

• I think I reversed $\le$ with $\ge$ above, but the fix is obvious, namely define $t>t'$ to mean $trt'$ and also $t<t'$ to mean $t'rt.$ – coffeemath May 26 '14 at 5:06