# Order-preserving embeddings

(Follow-up to Existence of a utility function on the reals.)

Say we have a totally ordered set $X$ which has a countable, dense subset $C$. I believe we can find an $f:C\to\mathbb R$ which is continuous and order-preserving. (For example, I think my previous question had this.)

Now, I wish to show that there is in fact a continuous order-preserving $g$ extending $f$ which maps $X\to\mathbb R$. I've been thinking of this proof:

Since $C$ is dense, we can write any $x\in X$ as the limit of a Cauchy sequence $x=lim_{i\to\infty}c_i$ for some $c_i\in C$. Then we can define $g(x)=\lim_{i\to\infty}f(c_i)$. Since $f$ is continuous, this is well defined and since it's order-preserving, so is $g$.

Is this legitimate? I think I'm implicitly assuming $X$ is a metric space but I don't know enough about topology to write it another way.

• I'm no topologist but your concern is valid. In general topological spaces sequences 'aren't good enough' - they cannot encode all the topological information contained in the space. For instance, in a general topological space you can't characterize open sets using sequences alone. You need to use 'nets' which generalize sequences. In any case, someone showed in your previous post that your first conjectured result isn't true. – Frank Mar 24 '14 at 1:33
• @Frank: it might not be true, but if so it's for a different reason (pedro's example didn't have a countable dense subset). – Xodarap Mar 24 '14 at 1:34
• Unless you assume that $X$ is densely ordered, you need to be careful about what you mean by "dense subset". It certainly is not enough that $C$ is dense in the order topology on $X$. – Niels J. Diepeveen Mar 24 '14 at 13:52

The idea that you sketched in your previous question gives you an order-preserving map of $C$ into $\Bbb R$, but the map may not be continuous: for instance, the map

$$f:[0,2]\cap\Bbb Q\to\Bbb R:x\mapsto\begin{cases} x,&\text{if }x\le 1\\ x+1,&\text{if }x> 1 \end{cases}$$

is order-preserving but not continuous at $1$, and it could in fact be produced by your construction. What you want is possible, but one has to work a bit harder.

Let $\langle X,\preceq\rangle$ be a linear order with a countable dense subset $C$, and let $f:C\to\Bbb Q$ be an order-preserving injection. Let

$$L=\left\{x\in C:x=\sup\big(C\cap(\leftarrow,x)\big)\right\}$$

and

$$R=\left\{x\in C:x=\inf\big(C\cap(x,\to)\big)\right\}\;,$$

where the suprema and infima are taken in $X$, not $C$. Let

$$L'=\big\{x\in C:f(x)=\sup\{f(y):y\in C\cap(\leftarrow,x)\big\}$$

and

$$R'=\big\{x\in C:f(x)=\inf\{f(y):y\in C\cap(x,\to)\big\}\;.$$

Then $f$ is continuous iff $L\subseteq L'$ and $R\subseteq R'$. If $f$ is not continuous, let $B_L=L\setminus L'$ and $B_R=R\setminus R'$. If $x\in B_L$, let

$$h_L(x)=\sup\{f(y):y\in C\cap(\leftarrow,x)\}\;,$$

and if $x\in B_R$, let

$$h_R(x)=\inf\{f(y):y\in C\cap(x,\to)\}\;.$$

Define a relation $\sim$ on $\Bbb Q$ by setting $p\sim q$ iff either $p=q$, or there is an $x\in B_L$ such that $p,q\in[h_L(x),f(x)]$, or there is an $x\in B_R$ such that $p,q\in[f(x),h_R(x)]$; $\sim$ is an equivalence relation on $\Bbb Q$ with order-convex equivalence classes. Thus, $\Bbb Q/\!\!\sim$ inherits a natural linear order from $\Bbb Q$, and it’s not hard to see that it’s a dense order and hence that there is an order-isomorphism $\psi:\Bbb Q/\!\!\sim\;\to\Bbb Q$; $\psi\circ f$ is then a continuous order-isomorphism of $C$ into $\Bbb Q$. Thus, we might as well assume that the original $f$ was continuous.

You now want to extend $f$ to $X$. Unfortunately, continuity of $f$ still isn’t enough. Suppose that $X=[0,2]$, $C=\Bbb Q\cap X$, and

$$f:C\to\Bbb R:x\mapsto\begin{cases} x,&\text{if }x<\sqrt2\\ x+1,&\text{if }x>\sqrt2\;; \end{cases}$$

then $f$ is a continuous order-isomorphism, but because of the gap between $\sup f[C\cap(\leftarrow\sqrt2)]$ and $\inf f[C\cap(\sqrt2,\to)]$ there is no way to extend $f$ continuously to $\sqrt2$. We have to work harder yet.

Let $x\in X\setminus C$; then $x$ is not an isolated point of $X$, so either $x=\sup\big(C\cap(\leftarrow,x)\big)$ and $x$ has an immediate successor $x^+\in X$ such that $x^+\in C$, or $x=\inf\big(C\cap(x,\to)\big)$ and $x$ has an immediate predecessor $x^-\in X$ such that $x^-\in C$, or $x=\sup\big(C\cap(\leftarrow,x)\big)=\inf\big(C\cap(x,\to)\big)$.

In the first case let

$$f(x)=\sup\{f(y):y\in C\cap(\leftarrow,x)\}\;,$$

and in the second case let

$$f(x)=\inf\{f(y):y\in C\cap(x,\to)\}\;;$$

it’s not hard to check that these cases are unproblematic. In the third case let

$$\ell(x)=\sup\{f(y):y\in C\cap(\leftarrow,x)\}\quad\text{and}\quad r(x)=f(x)=\inf\{f(y):y\in C\cap(x,\to)\}\;.$$

If $\ell(x)=r(x)$ we can define $f(x)=\ell(x)=r(x)$ with no problem. The problem arises precisely when $\ell(x)<r(x)$; call such a point $x\in X\setminus C$ a bad point, and let $B=\{x\in X\setminus C:x\text{ is bad}\}$. Observe that

$$\left\{\big(\ell(x),r(x)\big):x\in B\right\}$$

is a family of pairwise disjoint non-empty open intervals in $\Bbb R$, so $B$ must be countable.

Define a relation $\approx$ on $\Bbb R$ by $s\approx t$ iff either $s=t$, or there is an $x\in B$ such that $s,t\in[\ell(x),r(x)]$; $\approx$ is an equivalence relation on $\Bbb R$ with order-convex equivalence classes, so $\Bbb R/\!\!\approx$ inherits a natural linear order from $\Bbb R$. Let $q:\Bbb R\to\Bbb R/\!\!\approx$ be the quotient map, and let $\sqsubseteq$ be the induced order on $\Bbb R/\!\!\approx$.

It’s quite straightforward to verify that $\langle\Bbb R/\!\!\approx,\sqsubseteq\rangle$ is dense, Dedekind complete, and separable and has no endpoints, so it’s order-isomorphic to $\langle\Bbb R,\le\rangle$; let $\varphi:\Bbb R/\!\!\approx\;\to\Bbb R$ be an order-isomorphism. Then $\varphi\circ f:X\to\Bbb R$ is a continuous order-embedding of $\langle X,\preceq\rangle$ into $\langle\Bbb R,\le\rangle$.

• Sorry, what does the notation $(\leftarrow,x)$ mean? – Xodarap Oct 14 '14 at 13:30
• @Xodarap: $\{y:y<x\}$; you may be more familiar with the equivalent notation $(-\infty,x)$. – Brian M. Scott Oct 14 '14 at 19:00