Теорема Лёвенгейма-Сколема

[nikov]

Теорема Лёвенгейма-Сколема утверждает, что любая теория, имеющая бесконечную модель, имеет счетную модель (поправьте меня, если я ошибся в формулировке). Какая счетная модель существует у теории действительных чисел?

[Brukvalub]

А эта теорема доказывается конструктивно, или это "чисто" теорема существования?

[Someone]

nikov в сообщении #176557 писал(а):

(поправьте меня, если я ошибся в формулировке)

Уточняю: множества символов отношений (или предикатов, как тут часто говорят) и констант должны быть не более чем счётными.

Brukvalub в сообщении #176561 писал(а):

А эта теорема доказывается конструктивно, или это "чисто" теорема существования?

"Конструктивно". С помощью аксиомы выбора. Идея такая. Пусть $M$ - та самая бесконечная модель, о которой говорится в условии.
В качестве $N_0$ возьмём множество всех констант. Если множество $N_k$ уже определено, то для каждой формулы $A(y,x_1,x_2,\ldots,x_n)$ и для каждого набора элементов $\bar x_1,\bar x_2,\ldots,\bar x_n$ множества $N_k$, для которых существует хотя бы один такой $\bar y\in M$, что $A(\bar y,\bar x_1,\bar x_2,\ldots,\bar x_n)$ истинно, выберем один такой $\bar y$ и присоединим его к $N_k$. Получим множество $N_{k+1}$. Тогда $N=\bigcup\limits_{k=0}^{\infty}N_k$ даёт искомую модель.

nikov в сообщении #176557 писал(а):

Какая счетная модель существует у теории действительных чисел?

Дело в том, что понятие мощности не абсолютно. Одно и то же множество может быть в одной модели счётным, а в другой - несчётным, просто из-за того, что ни одно из взаимно однозначных отображений этого множества на натуральный ряд во вторую модель не попало. То есть, то, что в модели $N$ является (несчётным) множеством действительных чисел, в более широкой модели $M$ таковым не является и может быть счётным просто потому, что в модели $M$ больше отображений, чем в $N$, и среди них могут оказаться взаимно однозначные отображения на натуральный ряд, отсутствующие в $N$.

[маткиб]

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

"Конструктивно". С помощью аксиомы выбора.

Если несчётные алфавиты считать извращением, то вроде и без аксиомы выбора можно. Вроде можно даже в арифметике Пеано доказать (если правильно сформулировать: если теория непротиворечива, то имеет модель ограниченной арифметической сложности).

Добавлено спустя 8 минут 21 секунду:

И если сама теория ограниченной сложности.

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

nikov писал(а):

Теорема Лёвенгейма-Сколема утверждает, что любая теория, имеющая бесконечную модель, имеет счетную модель (поправьте меня, если я ошибся в формулировке).

Поправляю: не любая теория, а любая теория не более чем счётной сигнатуры.

Кроме того, это утверждение есть не сама теорема Левенгейма-Сколема, а её следствие. Сама теорема Левенгейма-Сколема утверждает следующее: в любой бесконечной модели для любого подмножества носителя этой модели найдётся элементарная подмодель, носитель которой содержит это множество и мощность которой не превосходит максимума из мощности выбранного множества, мощности сигнатуры и $\aleph_0$.

nikov писал(а):

Какая счетная модель существует у теории действительных чисел?

Вы элементарную теорию действительных чисел рассматриваете? Если да, то в какой сигнатуре?

Если Вас интересует счётная модель теории упорядоченного поля действительных чисел $\mathrm{Th}\langle \mathbb{R}, +, \cdot, 0, 1, \leqslant \rangle$, то она, безусловно, существует (по теореме Левенгейма-Сколема). На вопрос "какова она" я даже не знаю, что ответить. Могу предложить такие ответы:

1) Она счётная
2) Она не единственна с точностью до изоморфизма
3) Она является упорядоченным полем
4) В ней не выполняется аксиома Кантора (которая не может быть записана формулой первого порядка и, естественно, не входит в указанную выше теорию).
5) Аксиома Архимеда может в ней как выполняться, так и не выполняться. Но если Вы в качестве интересующей Вас модели выбираете элементарную подмодель действительных чисел, то аксиома Архимеда в ней, естественно, выполняется.

Что Вам ещё хотелось бы узнать про такую модель?

Brukvalub писал(а):

А эта теорема доказывается конструктивно, или это "чисто" теорема существования?

Достаточно "конструктивно", хотя и с использованием аксиомы выбора. Носитель элементарной подмодели строится явно, как объединение некоторой последовательности множеств. Someone этот вопрос уже довольно подробно раскрыл.

Добавлено спустя 11 минут 9 секунд:

Someone писал(а):

nikov в сообщении #176557 писал(а):

Какая счетная модель существует у теории действительных чисел?

Дело в том, что понятие мощности не абсолютно. Одно и то же множество может быть в одной модели счётным, а в другой - несчётным, просто из-за того, что ни одно из взаимно однозначных отображений этого множества на натуральный ряд во вторую модель не попало. То есть, то, что в модели $N$ является (несчётным) множеством действительных чисел, в более широкой модели $M$ таковым не является и может быть счётным просто потому, что в модели $M$ больше отображений, чем в $N$, и среди них могут оказаться взаимно однозначные отображения на натуральный ряд, отсутствующие в $N$.

Someone, здесь я Вас, честно говоря, плохо понял. В каком смысле "счётность" зависит от рассматриваемой модели? Вы разные модели ZFC что ли рассматриваете? Если да, то причём здесь они? Если нет, то я вообще ничего не понимаю. Поясните, пожалуйста, более подробно, что Вы имели в виду.

Добавлено спустя 3 минуты 27 секунд:

маткиб писал(а):

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

"Конструктивно". С помощью аксиомы выбора.

Если несчётные алфавиты считать извращением, то вроде и без аксиомы выбора можно. Вроде можно даже в арифметике Пеано доказать (если правильно сформулировать: если теория непротиворечива, то имеет модель ограниченной арифметической сложности).

Добавлено спустя 8 минут 21 секунду:

И если сама теория ограниченной сложности.

Бр-р-р... Вообще ничего не понял! Что у Вас за "сложность модели" такая? Вы тьюрингову степень диаграммы что ли рассматриваете (приняв носитель модели за $\mathbb{N}$)? Или что-то другое?

[маткиб]

Профессор Снэйп писал(а):

Бр-р-р... Вообще ничего не понял! Что у Вас за "сложность модели" такая? Вы тьюрингову степень диаграммы что ли рассматриваете (приняв носитель модели за $\mathbb{N}$)? Или что-то другое?

Что-то типа того. Я правда не понял, что Вы подразумеваете под диаграммой.
Я рассматриваю сложность (пусть это будет $T$-степень) функции, которая вычисляет значение нужного предиката, функции или константы сигнатуры на заданных элементах универсума (которым является $\mathbb{N}$).

Для перечислимых теорий вроде бы достаточно искать модель среди $T$-сводящихся к перечислимым множествам.

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

маткиб писал(а):

Я правда не понял, что Вы подразумеваете под диаграммой.

Пусть $\mathfrak{M}$ --- модель. Через $\mathfrak{M}^\ast$ обозначим естественное обогащение модели $\mathfrak{M}$ до сигнатуры, в которой для каждого элемента $a$ модели $\mathfrak{M}$ введена новая константа $c_a$. Тогда диаграммой модели $\mathfrak{M}$ называется множество бескванторных предложений, истинных на $\mathfrak{M}^\ast$ (полной диаграммой называется множество всех предложений, истинных на $\mathfrak{M}^\ast$, то есть элементарная теория модели $\mathfrak{M}^\ast$).

Если говорить о $T$-степенях, то это да, по сути то же самое, что и у Вас. Непонятно, правда, зачем Вы полезли в эти дебри, не имеющие отношения к теореме Левенгейма-Сколема. Просто чтоб свою эрудицию показать?

маткиб писал(а):

Для перечислимых теорий вроде бы достаточно искать модель среди $T$-сводящихся к перечислимым множествам.

Зачем их искать? Для чего достаточно?

$T$-сводимые к перечислимым --- это $\Delta^0_2$ что ли? Зачем так замысловато выражаться?

[маткиб]

Профессор Снэйп писал(а):

Если говорить о $T$-степенях, то это да, по сути то же самое, что и у Вас. Непонятно, правда, зачем Вы полезли в эти дебри, не имеющие отношения к теореме Левенгейма-Сколема. Просто чтоб свою эрудицию показать?

Потому что тут вспомнили про аксиому выбора. И тут у меня возникла мысль, что аксиома выбора не особо и нужна.

Профессор Снэйп писал(а):

Зачем их искать? Для чего достаточно?

Затем, чтобы доказать аналог теоремы Левенгейма-Сколема (или скорее её следствия) в арифметике Пеано (с которой у меня тоже возникла ассоциация при упоминании аксиомы выбора).

Профессор Снэйп писал(а):

$T$-сводимые к перечислимым --- это $\Delta^0_2$ что ли? Зачем так замысловато выражаться?

Видимо, так. Замысловато выражаюсь исключительно из-за того, что мне лень лезть в книжку и искать, каким значком оно обозначается (а в памяти у меня это не откладывается).

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

маткиб писал(а):

Затем, чтобы доказать аналог теоремы Левенгейма-Сколема (или скорее её следствия) в арифметике Пеано (с которой у меня тоже возникла ассоциация при упоминании аксиомы выбора).

По моему, в арифметике Пеано доказываются лишь утверждения о натуральных числах. Как можно в арифметике Пеано доказывать какие-то аналоги теоремы Левенгейма-Сколема, я не понимаю.

Сформулируйте утверждение, которое вы называете "аналогом теоремы Левенгейма-Сколема" и которое собираетесь доказывать в арифметике Пеано.

P. S. Ассоциации --- это, конечно, хорошо. Но не в математике. Хотя у альтов всё основано исключительно на ассоциациях... Но мы же не они!

[Someone]

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

Если Вас интересует счётная модель теории упорядоченного поля действительных чисел $\mathrm{Th}\langle \mathbb{R}, +, \cdot, 0, 1, \leqslant \rangle$, то она, безусловно, существует (по теореме Левенгейма-Сколема).

Если говорить просто о линейно упорядоченном поле, то годится поле рациональных чисел, но в нём не выполняются некоторые утверждения, которые верны в поле действительных чисел. Например, $\exists x(x^2=2)$. Я не вижу сразу, как в этой сигнатуре записать что-нибудь сложнее многочлена с неотрицательными целыми коэффициентами, поэтому поле алгебраических чисел, видимо, будет минимальной моделью. Или я что-то упустил?

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

Someone, здесь я Вас, честно говоря, плохо понял. В каком смысле "счётность" зависит от рассматриваемой модели? Вы разные модели ZFC что ли рассматриваете? Если да, то причём здесь они?

Они самые. На меня давят дискуссии о счётности множества действительных чисел, которые тут бушевали. Я склонен думать, что nikov имеет в виду теорему о несчётности множества действительных чисел. Поэтому счётную модель поля действительных чисел нужно строить вместе с моделью теории множеств, в которой эти действительные числа определяются.

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

Someone писал(а):

Если говорить просто о линейно упорядоченном поле, то годится поле рациональных чисел, но в нём не выполняются некоторые утверждения, которые верны в поле действительных чисел. Например, $\exists x(x^2=2)$. Я не вижу сразу, как в этой сигнатуре записать что-нибудь сложнее многочлена с неотрицательными целыми коэффициентами, поэтому поле алгебраических чисел, видимо, будет минимальной моделью. Или я что-то упустил?

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

Я пока тоже не вижу, что там можно записать в этой сигнатуре. Надо посмотреть доказательство теоремы Тарского о разрешимости элементарной теории поля действительных чисел. Может, там какая-нибудь элиминация кванторов и ничего сверх указанного записать в этой сигнатуре действительно нельзя

[маткиб]

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

Сформулируйте утверждение, которое вы называете "аналогом теоремы Левенгейма-Сколема" и которое собираетесь доказывать в арифметике Пеано.

Ну на пальцах можно так. Зафиксируем некоторый счётный алфавит (в котором будут символы предикатов, функций, переменных, констант, логических операций, кванторов, скобок), зафиксируем нумерацию строк этого алфавита.

Тогда для любой перечислимой непротиворечивой теории $T$ некоторой конечной сигнатуры (соответствующей выбранному алфавиту) существует $\Delta^0_2$-множество выражений $M$ вида $\Phi[\overline{x}_1,\ldots,\overline{x}_n]$, где $\Phi$ - некоторая формула заданной сигнатуры с $n$ свободными переменными, $\overline{x}_1,\ldots,\overline{x}_n\in\mathbb{N}$, для которого выполняются свойства:
1) для любой $\Phi\in T$ с $n$ свободными переменными и любого набора $\overline{x}_1,\ldots,\overline{x}_n\in\mathbb{N}$ имеет место $\Phi[\overline{x}_1,\ldots,\overline{x}_n]\in M$;
2) $M$ обладает всеми свойствами множества всех истинных формул в интерпретации с носителем $\mathbb{N}$ (например, $((\exists x)\Phi(x,y)[\overline{y}])\in M\Leftrightarrow(\exists\overline{x}\in\mathbb{N})(\Phi(x,y)[\overline{x},\overline{y}]\in M)$ и др. для всех логических операций и кванторов).

Все утверждения о бесконечных множествах записываются как утверждения о номерах соответствующих машин Тьюринга.

[Someone]

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

Вероятно, Вы имели в виду поле действительных алгебраических чисел.

Ну да, следовало оговориться, конечно.

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

Someone писал(а):

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

Вероятно, Вы имели в виду поле действительных алгебраических чисел.

Ну да, следовало оговориться, конечно.

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

А может, верно более сильное утверждение: действительные алгебраические числа являются элементарной подмоделью действительных чисел (в нашей сигнатуре)? Я пока не вижу, как это опровергнуть.

Добавлено спустя 9 минут 17 секунд:

маткиб писал(а):

для любой $\Phi\in T$ с $n$ свободными переменными

Да вроде как теория по определению содержит только предложения, то есть формулы без свободных переменных

Я опять не понял, какое отношение имеет это Ваше множество $M$ (которое, если я правильно понял, по сути является диаграммой модели с носителем $\mathbb{N}$, и Вы поэтому, если я опять же правильно понял, хотите наделить его свойствами, схожими со свойствами теории Хенкина) к теореме Левенгейма-Сколема. Теорема Левенгейма-Сколема, я напомню, утверждает о существовании элементарной подмодели с определёнными свойствами!

Вы хотите аналог теоремы о существовании модели? Он есть и давно доказан! Разрешимая теория имеет разрешимую модель (есть такая теорема)! То, что Вы пытаетесь сделать --- это релятивизация этой теоремы относительно $\mathbf{0}'$. Зачем только приплетать туда перечислимость, непонятно?

[маткиб]

Профессор Снэйп писал(а):

Теорема Левенгейма-Сколема, я напомню, утверждает о существовании элементарной подмодели с определёнными свойствами!

Ну это возможно. Я заранее написал, что говорю о следствии (потому что автор темы сформулировал именно это, без всяких подмоделей).

Профессор Снэйп писал(а):

Вы хотите аналог теоремы о существовании модели? Он есть и давно доказан! Разрешимая теория имеет разрешимую модель (есть такая теорема)!

Я догадываюсь, что это давно доказано (когда мой дедушка пешком под стол ходил, либо его вообще не существовало).

А про разрешимую модель - это интересно, я этого не знал.