Категоричность

[Sinoid]

Здравствуйте! В книге Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики есть такое место (стр. 92):

Пытаюсь решить первую задачу. Аксиомы теории DLO приведены в этой книге на стр. 57 и 60:
LO1 $\forall x\neg x<x$;
LO2 $\forall x\forall y\forall z(x<y\wedge y<z\supset x<z)$;
LO3 $\forall x\forall y(x<y\vee x=y\vee y<x)$;
$\forall x\exists y\, x<y$;
$\forall x\exists y\, y<x$;
$\forall x\forall y(x<y\supset\exists z(x<z\wedge z<y))$

Пример модели теории DLO мощности $\aleph_{0}$ подбирается без труда - это множество $\mathbb{Q}$. Но как доказать, что любая другая модель теории DLO изоморфна найденной модели? Была идея построить для этой другой модели подобие дерева Калкина—Уилфа или Штерна—Броко. Смотрите. Беру элемент $a_1$. Это - аналог дроби $\dfrac{1}{1}$ в дереве Штерна—Броко. Беру $a_2\ne a_1$. Если $a_1<a_2$, то $a_2$ - аналог $\dfrac{2}{1}$. Если же $a_2<a_1$, то $a_2$ - аналог $\dfrac{1}{2}$. Дальше беру такой $a_3$, что $a_3\ne a_1\wedge a_3\ne a_2$. Смотря по соотношениям между элементами множества $\left\{ a_{1},\, a_{2}\right\}$, ему тоже может быть указан аналог в этом дереве. Мне кажется, здесь попахивает индукцией, тем более, что индукция сама по себе определена для множества мощности $\aleph_{0}$. А каково ваше мнение?

[iifat]

Идея, имхо, вполне реальная. Полноту отображения доказать будет сложнее, но можно отобразить $Q$ в подмножество модели, потом наоборот и воспользоваться соответствующей теоремой.

[Someone]

Sinoid в сообщении #1295637 писал(а):

Была идея построить для этой другой модели подобие дерева Калкина—Уилфа или Штерна—Броко.

А зачем, собственно говоря? У Вас есть две счётные модели: $\mathbb Q_1$ и $\mathbb Q_2$. Нужно установить между ними взаимно-однозначное соответствие, сохраняющее отношение порядка. Нумеруем оба множества и поочерёдно подбираем соответствия элементам этих множеств в другом множестве: сначала — первому элементу первого множества, потом — первому элементу второго, потом — снова элементу первого, потом — второго, и так далее.

[Sinoid]

Someone в сообщении #1295679 писал(а):

Нумеруем оба множества

С сохранением порядка? А как это сделать?

[Someone]

Sinoid в сообщении #1295704 писал(а):

С сохранением порядка? А как это сделать?

Никак. Я разве говорил, что нужно нумеровать с сохранением порядка? Но если Вы считаете, что порядок на множестве натуральных чисел такой же, как на множестве рациональных…

[Sinoid]

iifat в сообщении #1295639 писал(а):

воспользоваться соответствующей теоремой.

Какой? На ум приходит только теорема Кантора-Бернштейна, но она здесь явно не при чем.

-- 06.03.2018, 18:48 --

Someone в сообщении #1295707 писал(а):

Но если Вы считаете, что порядок на множестве натуральных чисел такой же, как на множестве рациональных

Я так не считаю, потому и спросил.

-- 06.03.2018, 18:59 --

Someone в сообщении #1295679 писал(а):

поочерёдно подбираем соответствия элементам этих множеств в другом множестве: сначала — первому элементу первого множества

Так это полный произвол будет же только на этом шагу, на последующих же шагах выбор соответственных элементов будет подчинен определенным условиям?

[iifat]

Sinoid в сообщении #1295709 писал(а):

теорема Кантора-Бернштейна

Именно. Как она может быть ни при чём? Она позволяет заменить биекцию на две инъекции. В данном случае на одну, вторая строится симметрично. Сможете обойтись без неё — ради бога, разве ж я против!

[Someone]

Sinoid в сообщении #1295709 писал(а):

на последующих же шагах выбор соответственных элементов будет подчинен определенным условиям?

Ну Вы же хотите построить биекцию, сохраняющую порядок, вот это и будет требуемое условие. А нумерации нужны, чтобы не пропустить какие-нибудь элементы.

[Sinoid]

Someone в сообщении #1295679 писал(а):

Нумеруем оба множества и поочерёдно подбираем соответствия элементам этих множеств в другом множестве: сначала — первому элементу первого множества, потом — первому элементу второго, потом — снова элементу первого, потом — второго, и так далее.

Ну, то есть это моя догадка

Sinoid в сообщении #1295637 писал(а):

Беру элемент $a_1$. Это - аналог дроби $\dfrac{1}{1}$ в дереве Штерна—Броко. Беру $a_2\ne a_1$. Если $a_1<a_2$, то $a_2$ - аналог $\dfrac{2}{1}$. Если же $a_2<a_1$, то $a_2$ - аналог $\dfrac{1}{2}$. Дальше беру такой $a_3$, что $a_3\ne a_1\wedge a_3\ne a_2$. Смотря по соотношениям между элементами множества $\left\{ a_{1},\, a_{2}\right\}$, ему тоже может быть указан аналог в этом дереве.

Там я хотел продолжить так. Если для множества рациональных чисел $R=\left\{r_{1},\, r_{2},\ldots,\, r_{n}\right\}$, таких, что $r_1<r_2<\ldots<r_n$, я могу указать в другой модели множество элементов $A=\left\{a_{1},\, a_{2},\ldots,\, a_{n}\right\}$, таких, что $a_1<a_2<\ldots<a_n$, то, какое бы рациональное число $r_{n+1}\notin R$ я бы ни добавил к множеству $R$, во второй модели всегда можно указать такой элемент $a_{n+1}\notin A$, который соотносится с каждым элементом $a_i$ множества $A$ также, как $r_{n+1}$ соотносится с $r_i$

оказалась уместной? Только надо в обе стороны, да?

-- 06.03.2018, 22:38 --

Someone в сообщении #1295679 писал(а):

потом — первому элементу второго

При этом, если этот первый элемент второго оказался равен выбранному

Someone в сообщении #1295679 писал(а):

сначала — первому элементу первого множества

, то для него назначаем первый элемент первого множества?

[Someone]

Sinoid в сообщении #1295751 писал(а):

Someone в сообщении #1295679 писал(а):

потом — первому элементу второго

При этом, если этот первый элемент второго оказался равен выбранному

Someone в сообщении #1295679 писал(а):

сначала — первому элементу первого множества

, то для него назначаем первый элемент первого множества?

Да как хотите. Если для элемента, который Вы рассматриваете, соответствие уже определено, то проще всего его пропустить и перейти к следующему, либо можно просто подтвердить сделанный ранее выбор. Но лучше на каждом шаге выбирать элемент с наименьшим номером, для которого соответствие не определено. На нечётных шагах — в $\mathbb Q_1$, на чётных — в $\mathbb Q_2$. Тогда ломать голову над этим не придётся.

[Sinoid]

Someone в сообщении #1295759 писал(а):

На нечётных шагах — в $\mathbb Q_1$, на чётных — в $\mathbb Q_2$.

А, и за счет этого мы и перелопачиваем сразу элементы носителей обоих моделей?

[Sinoid]

А никто не знает, с какой стороны подойти к задаче 2? Вот тут прочитал следующее:

Цитата:

Дедуктивная система является полной, если при включении в число ее аксиом невыводимого в ней утверждения в качестве новой аксиомы теория становится противоречивой

Что вы думаете о применении этой идеи к этой задаче?

-- 08.03.2018, 16:58 --

Но опять же доказательство противоречивости, ИМХО, как правило, сложнее доказательства непротиворечивости.

[george66]

"Челночный метод" это называется. В книжке Верещагина и Шеня "Языки и исчисления".

[arseniiv]

Точнее, в первой, «Начала теории множеств», в главе об изоморфизме порядков. Во второй книге теорема об изоморфизме просто упоминается.

[Sinoid]

george66 в сообщении #1296530 писал(а):

"Челночный метод" это называется. В книжке Верещагина и Шеня "Языки и исчисления".

Не подскажите там страницу? Всю книгу перерыл, не увидел такого термина, да и в предметном указателе нет такого термина.

-- 10.03.2018, 21:51 --

arseniiv в сообщении #1296539 писал(а):

Точнее, в первой, «Начала теории множеств», в главе об изоморфизме порядков. Во второй книге теорема об изоморфизме просто упоминается.

А я и думаю...