Mapping real coordinate space to hyperreal numbers while preserving "lexicographic order"

Question

Coming up with a function $f:X^n \rightarrow \mathbb{R}$ where $X$ is a finite set of whole numbers such that lexicographic order is preserved is straightforward:

$$f(x_1, x_2, \ldots ,x_{n-1}, x_n)=\sum_{i=1}^{n}{x_i (\max(X))^{n-i}}$$

Is it possible to come up with an similar function, but one that maps real coordinate space to hyperreal numbers while preserving "lexicographic order" ($g:\mathbb{R}^n \rightarrow {}^*\mathbb{R}$)? I ask about hyperreal numbers because it is not possible in the case of real numbers (Debreu, G. (1954). Representation of a preference ordering by a numerical function. Decision processes, 3, 159-165.) Also, I say "lexicographic order" with quotes because lexicographic order (based on my understanding) technically is an ordering of sequences of elements of a finite set, but it doesn't seem unreasonable to extend the concept to include sequences of elements of an infinite set, i.e. $$(x_1, x_2, \dots ,x_{n-1}, x_n) \leq(y_1, y_2, \ldots ,y_{n-1}, y_n) \iff (x_1<y_1) \lor ((x_1=y_1) \land ((x_2<y_2) \lor \ldots ))$$

Would something like the following work?

$$g(x_1, x_2, \ldots ,x_{n-1}, x_n)=\sum_{i=1}^{n}{x_i \omega^{n-i}}$$

Answer 1

Your understanding is correct; given any two partially ordered sets $(A, <_A)$ and $(B, <_B)$ we can always define the lexicographic ordering on the cartesian product $A \times B$ by $$(a_1, b_1) \leq_{\text{lex}} (a_2, b_2) \iff a_1 <_A a_2 \text{ or } (a_1 = a_2 \text{ and } b_1 <_B b_2);$$ this extends naturally to finite and infinite products of partially ordered sets, although in the case of infinite products $\leq_{\text{lex}}$ behaves slightly differently (namely, it is not a well-order).

---

The function $g: \mathbb R^n \to {}^*\mathbb R$ that you define indeed does the job; here are the details.

Let $\mathcal U$ be a non-principal ultrafilter on $\mathbb N$, so that ${}^* \mathbb R = \mathbb R^{\mathbb N} / \mathcal U$; note also that since $\mathcal U$ is non-principal, it contains the Fréchet filter, so all cofinite sets of $\mathbb N$ are in $\mathcal U$. Throughout, if $(a_n) \in \mathbb R^{\mathbb N}$ we denote its equivalence class in ${}^* \mathbb R$ by $[(a_n)]$. Moreover, recall that a standard number $r$ in ${}^*\mathbb R$ is given by the equivalence class of the constant sequence $(r, r, r, \dots)$, and that if $[(a_n)], [(b_n)] \in {}^*\mathbb R$, then $$[(a_n)] < [(b_n)] \iff \{n \in \mathbb N: a_n < b_n \} \in \mathcal U. \tag {$\dagger$}$$

We prove now that for all $n \in \mathbb N$ if $(x_1,x_2, \dots, x_n) \leq_{\text{lex}} (y_1, y_2, \dots, y_n)$ in $\mathbb R^n$, then $g(x_1, x_2, \dots, x_n) \leq g(y_1, y_2, \dots, y_n)$ in ${}^*\mathbb R$. We do this by strong induction on $n$; the case $n=1$ is trivial, so assume that there is $ k \in \mathbb N^{>1}$ such that the result holds for all $n \leq k$ and suppose that $(x_1, x_2 \dots, x_{k}, x_{k+1}) \leq_{\text{lex}} (y_1, y_2, \dots, y_k, y_{k+1})$. We have two main cases:

• $\underline{x_1 < y_1}$. We will show that for all $x_2, x_3, \dots, x_k, x_{k+1}, y_2, y_3, \dots, y_k, y_{k+1} \in \mathbb R$, we have that $$x_1\omega^k + \sum_{i=2}^{k+1}x_i\omega^{k+1-i} \leq y_1\omega^k + \sum_{i=2}^{k+1}y_i\omega^{k+1-i}. \tag{$\star$}$$ Assume not for contradiction, so that there exist $x_2, x_3, \dots, x_k, x_{k+1}, y_2, y_3, \dots, y_k, y_{k+1} \in \mathbb R$ such that $$y_1\omega^k + \sum_{i=2}^{k+1}y_i\omega^{k+1-i} < x_1\omega^k + \sum_{i=2}^{k+1}x_i\omega^{k+1-i}.\tag{$\ast$}$$ Since $\omega = [(1,2,3, \dots)] = [(n)]$, by $(\dagger)$ we have that $(\ast)$ is equivalent to the statement that the set \begin{align} S &= \Bigg\{ n \in \mathbb N : y_1n^k + y_2n^{k-1} + \dots + y_{k+1}n^0 < x_1n^k + x_2n^{k-1} + \dots + x_{k+1}n^0 \Bigg\} \\ &= \Bigg\{ n \in \mathbb N: (y_1-x_1)n^k < (x_2-y_2)n^{k-1} + \dots + (x_{k+1} -y_{k+1} )n^0 \Bigg\} \\ &= \Bigg\{ n \in \mathbb N: (y_1 -x_1)n^k < \sum_{i=2}^{k+1}(x_i-y_i)n^{k+1-i}\Bigg\}\end{align} is in our ultrafilter $\mathcal U$. On the other hand, note that since $x_1 < y_1$, we have that $0 < (y_1 -x_1) n^k$ for all $n \in \mathbb N$, so that $(y_1 -x_1)n^k$ in a strictly increasing function in $n$. In particular, there exists $N \in \mathbb N$ such that for all $n \geq N$ we have $(y_1-x_1)n^k \geq \sum_{i=2}^{k+1}(x_i-y_i)n^{k+1-i}$; therefore, the set $$S' = \Bigg\{n\in \mathbb N : (y_1-x_1)n^k \geq \sum_{i=1}^{k+1}(x_i-y_1)n^{k+1-i}\Bigg\} $$ is cofinite, so $S' \in \mathcal U$. However, note that $S' = S \backslash \mathbb N$, so we have that $S \in \mathcal U$ and $S \backslash \mathbb N \in \mathcal U$, contradicting the fact that $\mathcal U$ is an ultrafilter; therefore our assumtion is false and $(\star)$ follows, as required.
• $\underline{x_1 = y_1 \text{ and } x_2 < y_2}$. Since $x_1 = y_1$, showing that $$x_1\omega^k +\sum_{i=2}^{k+1}x_i\omega^{k+1-i} \leq y_1\omega^k +\sum_{i=2}^{k+1}y_i\omega^{k+1-i} $$ simplifies to showing that $$\sum_{i=2}^{k+1}x_i\omega^{k+1-i} \leq \sum_{i=2}^{k+1}y_i\omega^{k+1-i}.\tag{$\ddagger$}$$ Define now $(x'_1, x'_2, \dots, x'_k) = (x_2, x_3, \dots, x_{k+1})$ and $(y'_1, y'_2, \dots, y'_{k}) = (y_2, y_3, \dots, y_{k+1})$. Since $x_2 < y_2$, we have that $x'_1 <y'_1$, so $(x'_1, x'_2, \dots, x'_k) \leq_{\text{lex}} (y'_1, y'_2, \dots, y'_{k})$ by definition of $\leq_{\text{lex}}$, and moreover $(\ddagger)$ becomes $$\sum_{i=1}^{k}x'_i\omega^{k-i} \leq \sum_{i=1}^{k}y'_i\omega^{k-i};\tag{$\star\star$}$$ by our inductive hypothesis, $(\star\star)$ holds, therefore so does $(\ddagger)$ and we're done.

The other cases (say $x_1 = y_1$, $x_2= y_2$ and $x_3 < y_3$) follow the same argument as in the point above using the strong induction assumption.