Теория моделей, классика...

[Профессор Снэйп]

Напомню определение формулы первого порядка сигнатуры с одним бинарным предикатом $<$...

1) Если $x$ и $y$ переменные, то $(x=y)$ и $(x<y)$ --- формулы
2) Если $\Phi$ и $\Psi$ --- формулы, $x$ --- переменная, то $(\Phi \mathop{\&} \Psi)$, $(\Phi \vee \Psi)$, $(\Phi \rightarrow \Psi)$, $\neg \Phi$, $\forall x \Phi$, $\exists x \Phi$ --- тоже формулы.
3) Других формул нет.

Докажите, что если $\Phi(x_1, \ldots, x_k)$ --- формула, а $q_1, \ldots, q_k \in \mathbb{Q}$, то

$$ \mathbb{Q} \models \Phi(q_1, \ldots, q_k) \Leftrightarrow \mathbb{R} \models \Phi(q_1, \ldots, q_k) $$

[BapuK]

ну т.е. требуется доказать элементарную эквиваленстность этих двух алгебрических систем. Легко доказать равносильное утверждение: для любой формулы $\varphi$ данной сигнатуры и любых $q_1,\dots, q_n\in\mathbb{Q}$ верно:

$$\mathbb{R}\models\exists x_0\varphi(x_0, q_1,\dots, q_n) \Rightarrow(\mathbb{R}\models\varphi(q_0, q_1,\dots, q_n)\text{ для некоторого } q_0\in\mathbb{Q})$$

Ну а это верно, так как всякая формула $\varphi(x_0,\dots, x_n)$ данной сигнатуры просто устанавливает в каком порядке расположены числа $q_0, \dots, q_n$ на которых верна данная формула. Ну и тогда утверждение верно в силу того, что порядок на $\mathbb{Q}$ плотен.
Вроде так

[Профессор Снэйп]

BapuK в сообщении #428744 писал(а):

ну т.е. требуется доказать элементарную эквиваленстность этих двух алгебрических систем.

Нет, требуется доказать не это

Требуется доказать, что $\langle \mathbb{Q}, \leqslant \rangle$ является элементарной подмоделью в $\langle \mathbb{R}, \leqslant \rangle$. А это гораздо более сильное свойство, чем элементарная эквивалентность этих двух моделей!!!

Наглядный пример --- чётные целые числа со сложением являются подмоделью в целых числах со сложением. Подмодель, очевидно, не элементарна: формула $\exists y (y + y = 2)$ не выполнена на подмодели, но выполнена на исходной модели. Однако сами модели не то что элементарно эквивалентны, а ваще изоморфны

[BapuK]

Профессор Снэйп в сообщении #429398 писал(а):

BapuK в сообщении #428744 писал(а):

ну т.е. требуется доказать элементарную эквиваленстность этих двух алгебрических систем.

Нет, требуется доказать не это

Требуется доказать, что $\langle \mathbb{Q}, \leqslant \rangle$ является элементарной подмоделью в $\langle \mathbb{R}, \leqslant \rangle$. А это гораздо более сильное свойство, чем элементарная эквивалентность этих двух моделей!!!
...

Конечно же это, в тот момент похоже в голове какие-то другие мысли летали...
Но тем не менее, утверждение, которое я сформулировал как раз эквивалентно тому, что $\langle \mathbb{Q}, \leqslant \rangle$ является элементарной подмоделью в $\langle \mathbb{R}, \leqslant \rangle$

[Профессор Снэйп]

BapuK в сообщении #429412 писал(а):

утверждение, которое я сформулировал...

Сформулировать мало, надо ещё доказать

-- Ср апр 06, 2011 11:08:01 --

BapuK в сообщении #428744 писал(а):

всякая формула $\varphi(x_0,\dots, x_n)$ данной сигнатуры просто устанавливает в каком порядке расположены числа $q_0, \dots, q_n$ на которых верна данная формула.

Это не верно.

[BapuK]

нда.. действительно не верно, глупости говорю...
Попробуем тогда так:
Есть еще такое утверждение(сразу переформулирую его на нашу сигнатуру): Если для любых $b_1,\dots, b_n\in\mathbb{Q}$ и для любого $a\in\mathbb{R}$ существует автоморфизм $f$ системы $(\mathbb{R}, <)$ , для которого $f(b_1) = b_1, \dots, f(b_n)=b_n$ и $f(a)\in\mathbb{Q}$, то $(\mathbb{R}, <)$ является элементарным расширением $(\mathbb{Q}, <)$, т.е. то, что нам и нужно доказать.
Что же значит автоморфизм в нашем случае, что если $a < b$, то $f(a) < f(b)$. Пусть для определенности $b_1 < b_2 < \dots < b_n$. Если $a$ из условия теоремы принадлежит $\mathbb{Q}$ то все тривиально, если же нет, то либо $a<b_1$, либо $a>b_n$ либо $\exists i : b_i<a<b_{i+1}$
Рассмотрим последний случай(остальные рассматриваются аналогично.
Построим автоморфизм следующим образом $f(x)=x$ для $x\in\mathbb{R}\backslash (b_i, b_{i+1})$. По условию $b_i < b_{i+1}$ и $b_i, b_{i+1}\in\mathbb{Q}$ в силу плотности порядка существует $c\in\mathbb{Q}$ такой, что $b_i<c<b_{i+1}$, тогда положим $f(a)=c$. Ну а то, что $(b_i, a) \cong (b_i, c)$ и $(a, b_{i+1})\cong (a, c)$ очевидно.
Вроде все.
Можно было бы, конечно попробовать доказать первое мое утверждение, но что-то не очень хочется