2
$\begingroup$

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}}$$

$\endgroup$
1
  • $\begingroup$As an aside, this is possible for any proper extension $F$ of $\mathbb{R}$. Indeed such extension cannot be archimedean, so there is $\omega \in F$ with $\mathbb{N}<\omega$, and then setting $g(x_1,...,x_n)=\sum \limits_{i=1}^n x_i \omega^{n-i}$ works.$\endgroup$
    – nombre
    CommentedOct 13, 2020 at 7:34

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

    You must log in to answer this question.

    Start asking to get answers

    Find the answer to your question by asking.

    Ask question

    Explore related questions

    See similar questions with these tags.