# Existence of a map f from countable set X to reals loyal to antisymmetric part of acyclic binary relation R

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_{-}. 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.

• 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? – bof Nov 11 '18 at 7:40
• Why can't you just define $$f(x)=\sum_{x_n\le x}2^{-n}$$? – bof Nov 11 '18 at 7:45
• @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.) – mnewman Nov 11 '18 at 8:15
• @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. – mnewman Nov 11 '18 at 8:20
• @bof By "in this way" I mean that there is not $x_j$, $x_i$ with $i\geq j$ such that $x_iPx_j.$ – mnewman Nov 11 '18 at 8:37