Embedding $^\omega\omega$ and $S_\omega$ with lexicographic order into $\mathbb{R}$

Question

Let $^\omega\omega$ be the collection of all functions $f:\omega\to\omega$. We order $^\omega\omega$ lexicographically, that is: For $f\neq g \in \,^\omega\omega$ let $m(f,g):= \min\{n\in\omega:f(n)\neq g(n)\}$, and then we say $f < g$ if and only if $f(m(f,g))<g(m(f,g))$.

This establishes a linear order $\leq_{\text{lex}}$ on $^\omega\omega$ which can be "inherited" to $S_\omega$, the collection of all bijections $\varphi:\omega\to\omega$.

Question. Is one of $(^\omega\omega, \leq_{\text{lex}})$ and/or $(S_\omega, (\leq_{\text{lex}} \cap \; (S_\omega \times S_\omega)))$ order-isomorphic to a subset of $\mathbb{R}$?

Side note. I suspect that there is a simple argument establishing that $(^\omega\omega, \leq_{\text{lex}}) \not \cong (S_\omega, (\leq_{\text{lex}} \cap \; (S_\omega \times S_\omega)))$, but I couldn't do it right now. I suppose that the "unit vectors" $\{(1, 0, 0,\ldots), (0,1,0,0,\ldots), (0,0,1,0,0,\ldots),\ldots\} \subseteq \, ^\omega\omega$ pose problems when mapped to $S_\omega$, but I am unable to complete this line of argument.

Answer 1

There's a general argument we can use for any question of this form.

Cantor's theorem shows that every countable linear order embeds into $\mathbb{Q}$. Consequently, every separable linear order (= has a countable dense suborder) embeds into $\mathbb{R}$. This gives a positive answer to both your questions; for example, the eventually-zero sequences form a countable dense suborder of $({}^\omega\omega,\le_\mathsf{lex})$, while the eventually-identity permutations form a countable dense suborder of $S_\omega$ (although strictly speaking we don't need to think about this separately).

In general, "small" dense suborders are useful for proving embeddability facts; meanwhile, "long" well-ordered suborders are useful for proving non-embeddability facts (e.g. that there is no order-preserving map from $({}^\omega\omega, \le_{\mathsf{dom}})$ to $\mathbb{R}$, where $\le_\mathsf{dom}$ is the partial order of eventual domination).

Answer 2

Let $0\leq a_0 < b_0 < a_1 < b_1 < a_2 < b_2 < \ldots \leq 1$, and let $\varphi_k \colon [0,1] \to [a_k,b_k]$ be the unique increasing linear bijection taking $0$ to $a_k$ and $1$ to $b_k$. Given $f\colon \mathbb{N}\to\mathbb{N}$, let $\varphi(f)$ be the limit of $\varphi_{f(0)}(\varphi_{f(1)}(\cdots(\varphi_{f(k)}(0))\cdots))$ as $k\to+\infty$, which exists as this sequence is nondecreasing and bounded between $0$ and $1$. If $f(0) < g(0)$ then $\varphi(f)\leq b_{f(0)} < a_{g(0)} \leq \varphi(g)$; and shows more generally (by applying the increasing function $\varphi_{f(0)}\circ\cdots\circ\varphi_{f(m-1)})$) that $\varphi(f) < \varphi(g)$ whenever $f(m) < g(m)$ for the first $m$ such that $f(n)\neq g(n)$. So $\varphi \colon \mathbb{N}^{\mathbb{N}} \to [0,1]$ is increasing for the lexicographic order on $\mathbb{N}^{\mathbb{N}}$. The image of $\varphi$ answers your question.