# Recognizing linear orders embeddable in $\Bbb R^2$ ordered lexicographically

Let $(C, \leq_C)$ be any chain: binary relation $\leq_C$ on $C$ is reflexive, antisymmetric, transitive, and total.

Give $\mathbb{R}^2$ the lexicographic order: for all real numbers $a,b,c,d$, $(a,b) \leq_L (c,d)$ if and only if $a < c$ or ($a = c$ and $b \leq d$).

Question: what are necessary and sufficient conditions for there to be an order-isomorphism from $(C, \leq_C)$ to a subset of $(\mathbb{R}^2, \leq_L)$, i.e., a function $f: C \to \mathbb{R}^2$ with $x \leq_C y$ if and only if $f(x) \leq_L f(y)$?

Motivation: I know what characterizes order-isomorphisms to subsets of $\mathbb{R}$ with its usual order. Birkhoff's Lattice Theory (3rd ed, p. 200), for instance, shows that such an isomorphism exists if and only if $C$ has a countable "order-dense" subset $D$: a countable subset $D$ of $C$ such that for all $a, b \in C \setminus D$ with $a <_C b$ there is a $d \in D$ with $a <_C d <_C b$.

But I find lexicographic orders much more difficult to grasp. My initial guess was that there might be an appealing extension of the order-density-condition to answer my question (for $\mathbb{R}^2$ and perhaps with an inductive argument for $\mathbb{R}^n$), but I have not been able to find one.

• Your question and the title do not match. Apr 8, 2015 at 5:54
• @GregMartin No, that is not necessary. The lexicographic order on $\mathbb{R}^2$ has no order-dense subset. Apr 8, 2015 at 7:43
• @AsafKaragila I will be happy to edit. What about "Embedding a chain into $\mathbb{R}^2$ with lexicographic order"? Apr 8, 2015 at 7:46
• Yes, that would be better. Apr 8, 2015 at 10:45
• Sorry - for some reason I thought the OP wanted to embed $C^2$, not $C$ itself, into $\Bbb R^2$. Apr 8, 2015 at 17:42

Corrected version. Let $$\pi_1:\Bbb R_{\text{lex}}^2\to\Bbb R:\langle x,y\rangle\mapsto x$$ be the projection to the first coordinate. Let $$A\subseteq\Bbb R_{\text{lex}}^2$$ be well-ordered or inversely well-ordered. Clearly $$A\cap(\{x\}\times\Bbb R)$$ is countable for each $$x\in\Bbb R$$, and $$\pi_1[A]$$ is also countable, so $$A$$ is countable. Thus, the first requirement is that $$C$$ have no uncountable subset well-ordered or inversely well-ordered by $$\le_C$$, and I will henceforth assume that $$C$$ has satisfies this requirement.

Define an equivalence relation $$\sim$$ on $$C$$ as follows: for $$x,y\in C$$ with $$x\le_C y$$ let $$x\sim y$$ and $$y\sim x$$ iff the interval $$[x,y]$$ in $$C$$ has a countable order-dense subset. Let $$\mathscr{E}$$ be the set of $$\sim$$-equivalence classes; clearly each $$E\in\mathscr{E}$$ is order-convex. Let $$E\in\mathscr{E}$$. Then either $$E$$ has a $$\le_C$$-last element, or there is an ordinary sequence $$\langle y_n:n\in\Bbb N\rangle$$ cofinal in $$E$$: if not, $$E$$ would contain an uncountable well-ordered set. Similarly, either $$E$$ has a $$\le_C$$-first element, or it has an ordinary co-initial sequence $$\langle x_n:n\in\Bbb N\rangle$$. If $$E$$ has a last element $$y$$, let $$y_n=y$$ for all $$n\in\Bbb N$$, and if $$E$$ has a first element $$x$$, let $$x_n=x$$ for all $$n=\Bbb N$$. Without loss of generality $$x_0\le y_0$$. Then $$E=\bigcup_{n\in\Bbb N}[x_n,y_n]$$, so $$E$$ has a countable order-dense subset and is therefore order-isomorphic to a subset of $$\Bbb R$$. Moreover, since the $$\sim$$-classes are convex, the order $$\le_C$$ induces a natural linear order $$\preceq$$ on $$\mathscr{E}$$.

Theorem. $$\langle C,\le_C\rangle$$ order-embeds in the lexicographically ordered plane iff $$\langle\mathscr{E},\preceq\rangle$$ has a countable order-dense subset.

Proof. For $$x\in C$$ let $$E(x)$$ be the $$\sim$$-equivalence class of $$x$$. Suppose first that $$\langle\mathscr{E},\preceq\rangle$$ is separable. Then there is an order-embedding $$\varphi:\mathscr{E}\to\Bbb R$$, and for each $$E\in\mathscr{E}$$ there is an order-embedding $$\varphi_E:E\to\Bbb R$$; clearly the map $$\psi:C\to\Bbb R^2_{\text{lex}}:x\mapsto\left\langle\varphi\big(E(x)\big),\varphi_{E(x)}(x)\right\rangle$$ is an order-embedding of $$C$$ into the lexicographically ordered plane.

Conversely, suppose that there is an order-embedding $$\psi:C\to\Bbb R^2_{\text{lex}}$$. For $$\alpha\in\Bbb R$$ let $$C_\alpha=\big\{x\in C:\psi(x)\in\{\alpha\}\times\Bbb R\big\}\;;$$ and let $$A=\{\alpha\in\Bbb R:C_\alpha\ne\varnothing\}$$. Clearly $$x\sim y$$ whenever there is an $$\alpha\in A$$ such that $$x,y\in C_\alpha$$, so $$\mathscr{C}=\{C_\alpha:\alpha\in A\}$$ is a refinement of $$\mathscr{E}$$ by order-convex subsets of $$C$$. And $$\mathscr{C}$$ in the order induced by $$\le_C$$ clearly has a countable order-dense subset, so $$\mathscr{E}$$ has as well. $$\dashv$$

• I will have to go through all steps carefully, since I am rather new to this and want to make sure I understand every little step. But at first sight, I think I understand it. How this might extend to $\mathbb{R}^3$ and so on is still beyond my ken, but I will give that a try as soon as I worked out the details of your proof. Apr 9, 2015 at 9:53
• I think it works if $\sim$ is redefined to $[x,y]$ having a countable order-dense subset in Birkhoff's sense (see def in my original question). But if I understand it correctly, that is not the same as saying that $[x,y]$ is separable as a LOTS: $\mathbb{R} \times \{0,1\}$ ordered lexicographically has no countable order dense subset in Birkhoff's sense, but is separable as a LOTS via $\mathbb{Q} \times \{0,1\}$. Hence, "is separable as a LOTS" does not imply "can be order-embedded into $\mathbb{R}$", which you seem to use in, for instance, the first step of the proof. Am I missing something? Apr 16, 2015 at 8:41
• I don't see why an equivalence class $E$ order-embeds into the reals even if intervals between any two of its elements do. Isn't this a counterexample? Let $E = [0, \omega_1)$ be a set of ordinals, where $\omega_1$ is the first uncountable ordinal. The interval between any $x$ and $y$ in $E$ is countable, hence order-embeds in the reals: $x \sim y$. So $E$ is an equivalence class, but doesn't order-embed in the reals: it has uncountably many elements, so uncountably many successors. If there were an embedding, this gives uncountably many disjoint open intervals in the reals, an impossibility.
– Mark
May 8, 2015 at 10:38
• A bit more detail for the claim about the countable cofinal subset: each chain (here $E$) has a well-ordered cofinal subset. Why? Well, partially order the class of well-ordered subsets of $E$ by the relation “is an initial segment of”. Verify that Zorn’s lemma applies. Its maximal element is cofinal, otherwise it can be extended by one more larger element. Here (see beginning of the answer), well-ordered implies countable: the elements of this well-ordered cofinal set labeled in the obvious way (least element first, then inductively) generate a sequence $y_0 < y_1 < \cdots$.
– Mark
May 19, 2015 at 6:16
• Thank you both for taking the time to do this! I never would have figured this out myself. I am getting this way slower that you seem to do. @Mark explained a final step that I didn't quite understand in Brian M. Scott's revised answer. May 21, 2015 at 6:56