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?


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.

  • $\begingroup$ 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.$ $\endgroup$ – coffeemath May 26 '14 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.