Отображение реального координатного пространства в гиперреальные числа с сохранением «лексикографического порядка»
Придумываем функцию $f:X^n \rightarrow \mathbb{R}$ где $X$ является конечным набором целых чисел, таким, что сохраняется лексикографический порядок, просто:
$$f(x_1, x_2, \ldots ,x_{n-1}, x_n)=\sum_{i=1}^{n}{x_i (\max(X))^{n-i}}$$
Можно ли придумать аналогичную функцию, но такую, которая отображает реальное координатное пространство в гиперреальные числа, сохраняя «лексикографический порядок» ($g:\mathbb{R}^n \rightarrow {}^*\mathbb{R}$)? Я спрашиваю о гиперреальных числах, потому что это невозможно в случае действительных чисел (Debreu, G. (1954). Представление порядка предпочтений числовой функцией. Процессы принятия решений, 3 , 159–165.) Также я говорю: « лексикографический порядок »с кавычками, потому что лексикографический порядок (на основе моего понимания) технически представляет собой упорядочение последовательностей элементов конечного набора, но не кажется неразумным расширить эту концепцию, чтобы включить последовательности элементов бесконечного набора, т.$$(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 ))$$
Хотели бы что-нибудь сделать следующее?
$$g(x_1, x_2, \ldots ,x_{n-1}, x_n)=\sum_{i=1}^{n}{x_i \omega^{n-i}}$$
Ответы
Ваше понимание правильное; учитывая любые два частично упорядоченных набора$(A, <_A)$ и $(B, <_B)$ мы всегда можем определить лексикографический порядок в декартовом произведении $A \times B$ по $$(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);$$ это естественным образом распространяется на конечные и бесконечные произведения частично упорядоченных множеств, хотя в случае бесконечных произведений $\leq_{\text{lex}}$ ведет себя немного иначе (а именно, это нехороший порядок).
Функция $g: \mathbb R^n \to {}^*\mathbb R$то, что вы определяете, действительно работает; вот подробности.
Позволять $\mathcal U$ быть неглавным ультрафильтром на $\mathbb N$, так что ${}^* \mathbb R = \mathbb R^{\mathbb N} / \mathcal U$; также обратите внимание, что поскольку$\mathcal U$неглавная, она содержит фильтр Фреше , поэтому все конфинитные множества$\mathbb N$ находятся в $\mathcal U$. Всюду, если$(a_n) \in \mathbb R^{\mathbb N}$ обозначим его класс эквивалентности в ${}^* \mathbb R$ по $[(a_n)]$. Кроме того, напомним, что стандартное число$r$ в ${}^*\mathbb R$ задается классом эквивалентности постоянной последовательности $(r, r, r, \dots)$, и что если $[(a_n)], [(b_n)] \in {}^*\mathbb R$, тогда $$[(a_n)] < [(b_n)] \iff \{n \in \mathbb N: a_n < b_n \} \in \mathcal U. \tag {$\кинжал$}$$
Докажем теперь, что для всех $n \in \mathbb N$ если $(x_1,x_2, \dots, x_n) \leq_{\text{lex}} (y_1, y_2, \dots, y_n)$ в $\mathbb R^n$, тогда $g(x_1, x_2, \dots, x_n) \leq g(y_1, y_2, \dots, y_n)$ в ${}^*\mathbb R$. Сделаем это сильной индукцией по$n$; дело$n=1$ тривиально, поэтому предположим, что существует $ k \in \mathbb N^{>1}$ такой, что результат верен для всех $n \leq k$ и предположим, что $(x_1, x_2 \dots, x_{k}, x_{k+1}) \leq_{\text{lex}} (y_1, y_2, \dots, y_k, y_{k+1})$. У нас есть два основных случая:
- $\underline{x_1 < y_1}$. Мы покажем это всем$x_2, x_3, \dots, x_k, x_{k+1}, y_2, y_3, \dots, y_k, y_{k+1} \in \mathbb R$у нас есть это $$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{$\ звезда$}$$ Предположим не от противного, так что существуют $x_2, x_3, \dots, x_k, x_{k+1}, y_2, y_3, \dots, y_k, y_{k+1} \in \mathbb R$ такой, что $$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$}$$ поскольку $\omega = [(1,2,3, \dots)] = [(n)]$, по $(\dagger)$ у нас есть это $(\ast)$ эквивалентно утверждению, что множество \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} находится в нашем ультрафильтре $\mathcal U$. С другой стороны, обратите внимание, что поскольку$x_1 < y_1$у нас есть это $0 < (y_1 -x_1) n^k$ для всех $n \in \mathbb N$, так что $(y_1 -x_1)n^k$ в строго возрастающей функции по $n$. В частности, существует$N \in \mathbb N$ такой, что для всех $n \geq N$ у нас есть $(y_1-x_1)n^k \geq \sum_{i=2}^{k+1}(x_i-y_i)n^{k+1-i}$; следовательно, множество$$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\} $$ кофинитно, поэтому $S' \in \mathcal U$. Однако обратите внимание, что$S' = S \backslash \mathbb N$, так что у нас есть это $S \in \mathcal U$ и $S \backslash \mathbb N \in \mathcal U$, что противоречит тому, что $\mathcal U$это ультрафильтр; поэтому наше предположение ложно и$(\star)$ следует, как требуется.
- $\underline{x_1 = y_1 \text{ and } x_2 < y_2}$. поскольку$x_1 = y_1$, показывая, что $$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} $$ упрощает демонстрацию того, что $$\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$}$$ Определить сейчас $(x'_1, x'_2, \dots, x'_k) = (x_2, x_3, \dots, x_{k+1})$ и $(y'_1, y'_2, \dots, y'_{k}) = (y_2, y_3, \dots, y_{k+1})$. поскольку$x_2 < y_2$у нас есть это $x'_1 <y'_1$, так $(x'_1, x'_2, \dots, x'_k) \leq_{\text{lex}} (y'_1, y'_2, \dots, y'_{k})$ по определению $\leq_{\text{lex}}$, и более того $(\ddagger)$ становится $$\sum_{i=1}^{k}x'_i\omega^{k-i} \leq \sum_{i=1}^{k}y'_i\omega^{k-i};\tag{$\ звезда \ звезда$}$$ по нашей индуктивной гипотезе, $(\star\star)$ имеет место, следовательно, также $(\ddagger)$ и мы закончили.
В других случаях (скажем, $x_1 = y_1$, $x_2= y_2$ и $x_3 < y_3$) следуют тем же аргументам, что и в предыдущем пункте, с использованием предположения сильной индукции.