Take the 2-minute tour ×

Let $f:X \to Y$ be a function.

Suppose first that $\leq_X$ is a partial order on $X$.

Is it possible to define a partial order $\leq_Y$ on $Y$, induced by $\leq_X$ (and optimal in some way), so that $f:(X, \leq_X) \to (Y, \leq_Y)$ becomes order-prerserving (and thus can be viewed as a morphism of posets)?

Now suppose that $\leq_Y$ is a partial order on $Y$, and consider the converse problem:

Find a partial order for $X$, optimal in some sense, so that $f$ is order-preserving.

Are there standard names for these "induced" partial orders?

(I'm thinking of something in the spirit of weak/strong topologies.)

More generally, if $R$ is an arbitrary asymmetric binary relation, and $\bar{R}$ its transitive closure, then $I\cup \bar{R}$ is a partial order.

Is there a name for such order (vis-à-vis $R$)?

I've searched for likely candidates such as "the partial order generated by", etc., without much success?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Without extra assumptions on $f$, you can't always do it.

For the first situation, say that $f$ is not injective, and there exists $x_1\lt x_2\lt x_3$ such that $f(x_1)=f(x_3)$ but $f(x_2)\neq f(x_1)$. For $f$ to be order preserving, we would need $f(x_1)\lt_Y f(x_2)$, and we would also need $f(x_2)\lt_Y f(x_3)=f(x_1)$, which means that $\leq_Y$ is not antisymmetric.

If $f$ is injective, you can always use transport of structure to define a partial order on $f(X)$, and then extend to a partial order on all of $Y$ by adding $y\leq_Y y$ for every $y\in Y$ and nothing else. More generally, using transport of structure for any $f$ and adding the diagonal will give you a pre-order on $Y$ (a relation that is reflexive and transitive, but not necessarily antisymmetric), and then you can take the appropriate quotient to get an order on $Y/\sim$ so that $f$ is order preserving.

The second situation is a bit better: there is always at least one possibility. Take the trivial partial order on $X$ ($x_1\leq_X x_2$ if and only if $x_1=x_2$). Then $f$ is certainly order-preserving. Thus, the collection of all partial orders on $X$ such that $f$ is order preserving is non-empty. Moreover, if you have a chain of partial orders on $X$ such that $f$ is order-preserving, then their union is a partial order on $X$ (verify!), and $f$ is order-preserving relative to the union. So by Zorn's Lemma, the collection of partial orders on $X$ for which $f$ is order preserving has maximal elements.

(Note that $f$ is order-preserving if $x_1\leq x_2$ implies $f(x_1)\leq f(x_2)$, but we do not require the implication in the other direction).

share|improve this answer
Thanks! Clarification: by "chain of partial orders" do you mean an inclusion chain, like $\leq_0 \;\subseteq\; \leq_1 \;\subseteq\; \leq_2 \cdots$? –  kjo Feb 21 '12 at 0:44
@kjo: Yes; partial orders on $X$ are subsets of $X\times X$, and they are naturally partially ordered by inclusion (as subsets of $X\times X$). –  Arturo Magidin Feb 21 '12 at 2:02

Your Answer


