For a poset (=partially ordered set) $(X,\preceq)$, call a real-valued function $\phi : X \to \mathbf{R}$ strictly increasing iff $x \prec x'$ implies $\phi(x) < \phi(x')$.
(Q) what posets admit a strictly increasing real-valued function?
I'm also interested in variants, e.g. the same question restricted to some nice class of posets (product posets, say), or illuminating sufficient conditions.
Motivation 1: if a poset admits a strictly increasing real-valued function, then every chain is order-isomorphic to a subset of $\mathbf{R}$ (ordered by the usual $\leq$). (In particular, the strictly increasing function, restricted to a chain, is an order-embedding of that chain into $(\mathbf{R},\leq)$.)
Motivation 2: Interpret $\preceq$ preference: $x \prec x'$ means that $x$ is strictly worse than $x'$. Then in the language of economic theory, (Q) asks whether there exists a utility representation of $\preceq$.
For chains, I have an answer
(a chain is a poset $(X,\preceq)$ in which $x \preceq y$ or $y \preceq x$ for any $x,y \in X$):
(Q$'$) what chains admit a strictly increasing real-valued function?
An answer: those that are order-separable, meaning that they contain a countable order-dense subset. (A subset $Y \subseteq X$ is order-dense iff for any $x \prec x'$ in $X$, there is a $y \in Y$ such that $x \preceq y \preceq x'$.) This is because a strictly increasing map from a chain to $\mathbf{R}$ is precisely an order-embedding, and all and only order-separable chains embed into $\mathbf{R}$. (The latter is a standard result; e.g. Theorem 24 on p. 200 in Birkhoff's book (3rd ed., 1967).
(In light of this, it could be that a valid answer to (Q) is 'those posets whose every chain is order-separable'. If it's true, I don't know how to prove it.)
Observations:
- $\mathbf{R}^n$ with the usual (product) order admits the strictly increasing real-valued function $(x_n)_{n=1}^N \mapsto \sum_{n=1}^N x_n$. The sequence space $\ell^1$ with the product order similarly admits the strictly increasing real-valued function $(x_n)_{n \in \mathbf{N}} \mapsto \sum_{n \in \mathbf{N}} x_n$.
- $\mathbf{R}^2$ with the lexicographic (=dictionary) order does not admit a strictly increasing real-valued function, as is well-known.
- I conjecture that the $\mathcal{L}^1$ space over $[0,1]$ with Lebesgue measure, equipped with the product order, does not admit a strictly increasing real-valued function. (Certaintly $x \mapsto \int_{[0,1]} x$ is not strictly increasing.) Am I right?
I think I've done my homework, but didn't find much either on this site or elsewhere.
Best Answer
A counterexample.
It is not true that a poset, in which every chain in order-separable, necessarily admits a strictly increasing real-valued function. In fact, here is an example of a poset $(X,\preceq)$ of cardinality $\aleph_1$ which does not admit a strictly increasing real-valued function, even though every chain in $(X,\preceq)$ is finite.
Let $X=\omega_1\times\omega_1$. For $(\alpha,\beta),(\alpha',\beta')\in X$, define $$(\alpha,\beta)\prec(\alpha',\beta')\iff\alpha\lt\alpha'\text{ and }\beta\gt\beta'$$ and $$(\alpha,\beta)\preceq(\alpha',\beta')\iff(\alpha,\beta)\prec(\alpha',\beta')\text{ or }(\alpha,\beta)=(\alpha',\beta').$$ Since $(\omega_1,\lt)$ is well-ordered, it's clear that $(X,\preceq)$ contains no infinite chain. Assume for a contradiction that there is strictly increasing function $f:X\to\mathbb R$.
For each $\alpha\in\omega_1$ there exists $\beta_\alpha\in\omega_1$ such that $\{\xi\in\omega_1:f(\alpha,\xi)\ge f(\alpha,\beta_\alpha)\}$ is uncountable. Let $t_\alpha=f(\alpha,\beta_\alpha)$. Choose $\alpha,\alpha'\in\omega_1$ so that $\alpha\lt\alpha'$ and $t_\alpha\ge t_{\alpha'}$. Let $\beta'=\beta_{\alpha'}$, so that $f(\alpha',\beta')=t_{\alpha'}$. Choose $\beta\in\omega_1$ so that $\beta\gt\beta'$ and $f(\alpha,\beta)\ge f(\alpha,\beta_\alpha)=t_\alpha$. Then $(\alpha,\beta)\prec(\alpha',\beta')$ and $f(\alpha,\beta)\ge t_\alpha\ge t_{\alpha'}=f(\alpha',\beta')$, contradicting our assumption that $f$ is strictly increasing.
Remark. More generally, for any chain $Y$, a strictly increasing function $f:X\to Y$ exists if and only if $Y$ contains a subset of order type $\omega_1$ or $\omega_1^*$.
A characterization.
An order-ideal in a poset $(X,\preceq)$ is a set $A\subseteq X$ which is closed downward, i.e., if $x\in X$ and $x\preceq a\in A$, then $x\in A$.
A poset $(X,\preceq)$ admits a strictly increasing real-valued function if and only if there is a countable family $(A_n:n\in\mathbb N)$ of order-ideals such that, whenever $x_1,x_2\in X$ and $x_1\prec x_2$, there is some $n\in\mathbb N$ such that $x_1\in A_n$ and $x_2\notin A_n$.
Given such order-ideals, we can define a strictly increasing real-valued function by setting $$f(x)=\sum_{x\notin A_n}2^{-n}.$$ Conversely, given a strictly increasing function $g:X\to\mathbb R$, we can take the order-ideals $A_n=\{x\in X:g(x)\lt r_n\}$ where $\mathbb Q=\{r_n:n\in\mathbb N\}$ is some enumeration of the rational numbers.