The following is taken from chapter one of Efe Ok's book on Order Theory: Let R an acyclic binary relation on a nonempty countable set X. Prove or disprove: there is a map $f:X->\mathbb{R}$ with $f(x)>f(y)$ for each $x,y$ such that $xPy$ (i.e. $xRy$ and $yRx$ is false.)

My proof:Define $x\geq y$ iff $x=y$ or $(x,y)\in P^k$ for some $k$. Then we have $x \geq x$ and $z\geq y\geq x$ implies $z\geq x$. Asymmetry follows from the fact that $(x,y)\in P^k, (y,x)\in P^l$ implies $(x,x)\in P^{k+l}$, which violates acyclicity. So indeed, $\geq$ reflexive, transitive, asymmetric.

Let $X$ a countable set, $(c_n)_{n\in \mathbb{N}}$ the Cantor diagonalization of $\mathbb Q$. By countability $X=${$x_1,x_2,...$} for some sequence $(x_n)_{n\in \mathbb{N}}$. Let $X_n:=${$x_1,...x_n$}. We proceed by induction, covering the base case of $X_2$. Let $f(x_1):=0.$ If $x_2\geq x_1$ we let$f(x_2)$ the first $c_n$ greater than $0$ and if $x_1\geq x_2$ or $x_1,x_2$ not $\geq$ - comparable we let $f(x_2)$ the first $c_n$ less than zero. This is well defined due to asymmetry, transitivity of $\geq$. So then we have a map $f$ on $X_2$ (and trivially on $X_1$) such that for $(x_i,x_j)\in P$ we have that $f(x_i)>f(x_j)$, as desired.

Suppose then that such a map $f$ exists on $X_k$. Consider then $X_{k+1}=X_k \cup$ {$x_{k+1}$}. We need only find a desirable value for $x_{k+1}$. Let

$L_{-}:=max${$f(x_j)|x_{k+1}\geq x_j$} and $L_{+}:=min${$f(x_j)|x_j\geq x_{k+1} $}.

Suppose, for contradiction, that $L_{-}\geq L_{+}$. Then there exists $x^{+}, x^{-}$ with $f(x^{-})>f(x^{+})$ and $x^{+}\geq x \geq x^{-}$ Then by transitivity $x^{+}\geq x^{-}$. But then $f(x^{+})>f(x^{-})$. So indeed $L_{-}<L_{+}$. Then we let $f(x_{k+1})$ the first $c_n$ in $(L_{-},L_{+})$, the existence of which is guaranteed by density of $\mathbb Q$ in $\mathbb R$. Then for $x_i\neq x_j$ with $x_i P x_j$ we have that $x_i\geq x_j$ and so $f(x_i)\geq f(x_j)$. So indeed for any $n\in \mathbb{N}$ there is a map $f$ from $X_n$ into $\mathbb R$ with $f(x_i)>f(x_j)$ if $x_iPx_j.$

We use this construction then for $X$. Suppose, for contradiction, that this construction fails for $X$. Then there are $x_i, x_j$ with $x_iPx_j$ but $f(x_j)\geq f(x_i).$ Yet we know that the construction cannot fail on $X_{max(i,j)},$ a contradiction. So this construction works on the countable set.

So for $R$ an acyclic binary relation on a nonempty countable set $X$ there is a map $f:X\rightarrow \mathbb R$ with $f(x)>f(y)$ if $xPy$.

Questions: Does this proof work? It seems too long, complicated for what seems like a straightforward construction and problem. Am I overlooking something here? Thanks much.

  • 1
    $\begingroup$ I don't understand what's the difference between $xPy$ and $xRy$. If $xRy$ holds, then $yRx$ must be false, because $xRy$ and $yRx$ would mean $R$ is not acyclic. What am I missing? Do you have some weird definition of acyclicity? $\endgroup$ – bof Nov 11 '18 at 7:40
  • 1
    $\begingroup$ Why can't you just define $$f(x)=\sum_{x_n\le x}2^{-n}$$? $\endgroup$ – bof Nov 11 '18 at 7:45
  • $\begingroup$ @bof What Ok gives as definition for acyclicity is that $\Delta X \cap P^k=\emptyset$ for any $k$ a natural number. What you are referring to seems to me to be irreflexivity, which follows from acyclicity (under this definition), but which need only be equivalent if $P$ were transitive (I believe.) $\endgroup$ – mnewman Nov 11 '18 at 8:15
  • $\begingroup$ @bof And with respect to that function, I don't see how this function satisfies the demands of the problem. If, for example, we have $X_3$ we may have $x_3Px_1Px_2.$ So we need $f(x_3)>f(x_1)>f(x_2)$, but this cannot happen unless we know that there is an ordering of $X$ in this way. I believe such an ordering exists. Indeed, it can be seen as a corollary of my proof I believe, but I did not think I could state such a claim without proof as I am a novice, and this is simply the first section to Professor Ok's book. No such theorem has yet been given to me. $\endgroup$ – mnewman Nov 11 '18 at 8:20
  • $\begingroup$ @bof By "in this way" I mean that there is not $x_j$, $x_i$ with $i\geq j$ such that $x_iPx_j.$ $\endgroup$ – mnewman Nov 11 '18 at 8:37

Your Answer

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

Browse other questions tagged or ask your own question.