order preserving function over Poset

401 Views Asked by At

I have a DAG (Directed Acyclic Graph) $G$ represents the dominance relation between solutions. A path from $x$ to $y$ means $y\succ x$ ($y$ dominates or better than $x$) where the absence of such a path means they are incomparable. The graph induces a Poset over the set of nodes (i.e. solutions). From my understanding this is called Hasse Diagrams (forgive my ignorance here).

I am trying to find a preserve ordering function over $G$ where if $x\succ y$ then $f(x)<f(y)$ and $f(x)=f(y)$ iff they are incomparable. Is such a function exists? One solution I am thinking about is to extract the set of chains for the Poset and then look for preserve ordering functions for total orders.

1

There are 1 best solutions below

7
On

In general this can not be accomplished. Consider the following poset: $\{a,b,c\}$, where $a<b$ but $a$ and $b$ are incomparable with $c$.

Suppose a function $f$ satisfies your requirements, then: $$f(a) = f(c) = f(b),$$ which is a contradiction