Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Hi Andreas. Thanks! Nice observation. I would still hope to see whether we can have an "absolute" example. –  Andres Caicedo Aug 1 '12 at 17:51
    
Oh, I like your $\omega_1$-sized example. Thanks! (You think it is hopeless to expect a choiceless variant?) –  Andres Caicedo Aug 2 '12 at 5:57
    
@Andres: Thanks. I won't say it's hopeless to expect a choiceless variant, but I have no idea where to look for one. –  Andreas Blass Aug 2 '12 at 14:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.