Question

If $P$ and $P'$ are partial orders, a strictly order preserving map from $P$ to $P'$ is an $f:P\to P'$ satisfying that $x\lt y$ implies $f(x)\lt f(y)$ for all $x,y\in P$.

An interval in $P$ is a set of the form ${}[x,y]=\{z\mid x\le z\le y\}$, where $x\le y$. Note that points in an interval need not be comparable with one another. The height of an interval is the supremum of the lengths of $< $-chains of elements in the interval.

Clearly, if there is a strictly order preserving map from $P$ to $\mathbb Z$, then all intervals in $P$ have finite height. If $P$ is countable, this condition also suffices for the existence of such a map. This dates back to Erné in 1979.

However, there are examples of uncountable $P$ with all intervals of finite height for which there is no strictly order preserving map into $\mathbb Z$. The examples I know have size continuum ($=|\mathbb R|$) or larger. A nice example due to Farley and Schröder can be found here.

Is there an example of size $\omega_1$, preferably one that does not require the axiom of choice?

Answer 1

The construction of Farley and Schroeder that you linked to essentially gives an example of size the bounding number $\mathfrak b$. So it's at least consistent with $\neg$CH to have an example of size $\aleph_1$. Details: Take an unbounded family $\mathcal B$ of functions $\omega\to\omega$, and form the analog of the Farley-Schroeder example with just the functions in $\mathcal B$ at the bottom level instead of all functions. If there were a strictly order-preserving map $f$ to $\mathbb Z$, then the paper shows how to obtain a $F$ that majorizes every $b\in\mathcal B$ up to an additive constant (namely $-f(b)$). Then any $G$ that eventually majorizes the countably many functions $F+$ constant would also eventually majorize all the functions in $\mathcal B$, which contradicts the choice of $\mathcal B$.

EDIT: Here's a variant of the same construction that gives an $\omega_1$-sized example. The poset will consist of a "low" copy of the set $\omega_1$ of countable ordinals, a "high" copy of the same set, and some finite chains joining elements in the low copy to elements in the high copy. I'll write $\alpha-$ for the low copy of an ordinal $\alpha<\omega_1$ and $\alpha+$ for the high copy. The main issue is how long to make the finite chains between low and high copies. For each countable ordinal $\beta$, fix a one-to-one function $f_\beta:\beta\to\omega$. Join $\alpha-$ to $\beta+$ by a chain of length $f_\beta(\alpha)$ if $\alpha<\beta$; don't join them by any chain if $\alpha\geq\beta$. Clearly each interval in this poset is either one of the finite chains or a subset of one. So I need only prove that there is no strictly order-preserving map $g$ from my poset to $\mathbb Z$.

Suppose, toward a contradiction, that $g$ were such a map. Since the low copy of $\omega_1$ is uncountable and the range of $g$ is countable, $g$ must be constant, say with value $a$, on an uncountable subset $\{\alpha-:\alpha\in X\}$ of the low copy. Similarly, it is constant, say with value $b$, on $\{\beta+:\beta\in Y\}$ for some uncountable $Y$. Fix some $\beta\in Y$ that is larger than the $\omega$-th element of $X$. So there are infinitely many ordinals $\alpha\in X$ with $\alpha<\beta$. These infinitely many $\alpha$'s are mapped by $f_\beta$ to infinitely many natural numbers, so we can find $\alpha\in X$ with $f_\beta(\alpha)>b-a$. But then the chain between $\alpha-$ and $\beta+$ is longer than the difference between $g(\beta+)=b$ and $g(\alpha-)=a$, so $g$ cannot be strictly order-preserving.