1

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 countably infinite, the answer is yes. I'm wondering what about if $A$ is uncountably infinite? I'm almost sure there must be a counterexample, but I don't know how to find one. (For example, if $A=\mathbb{R}$, then the trivial map $f(x)=x$ works.)

Community
  • 1
boaten
  • 1,735

1 Answers1

1

The answer is no.

What you asking is basically, whether $A/{\sim}$ can be embedded into $\langle\mathbb{R},\leq\rangle$, where

$$x \sim y \quad\text{ if and only if }\quad x\ r\ y \land y\ r\ x.$$

A counterexample might be $\langle\mathbb{R}^2,\leq_\text{lex}\rangle$, that is,

$$(x_1,y_1) \leq_\text{lex} (x_2,y_2) \quad\text{ if and only if }\quad x_1 < x_2 \lor (x_1 = x_2 \land y_1 \leq y_2).$$

Here $\sim$ would be just identity, so we are trying to map lexicographical order on $\mathbb{R}^2$ into standard order of $\mathbb{R}$. Why these two are different? Suppose there exists an order-preserving mapping $f : \mathbb{R}^2 \to \mathbb{R}$ and define

\begin{align} a_x &= f(x,0) \\ b_x &= f(x,1) \end{align}

and observe that $a_x \lneq_\text{lex} b_x$ and for $x < y$ also $b_x \lneq_\text{lex} a_y$. In other words $\{(a_x,b_x) \mid x \in \mathbb{R}\}$ would constitute an uncountable set of disjoint open intervals, which is impossible (e.g. because rational numbers are countable).

I hope this helps $\ddot\smile$

dtldarek
  • 37,381