О парадоксе Скулема

[Tcirkubakin]

Ознакомился с парадоксом Скулема (в книге Раутенберга конец 4 параграфа третьей главы). Прочитал его объяснение в учебнике, википедии, но мозг от него "вскипает" до сих пор. Можно ли при должном усердии как-то его понять?
P.S. Думаю, надо прежде всего разобраться с объяснением в учебнике.

[Утундрий]

Tcirkubakin в сообщении #1586244 писал(а):

Можно ли при должном усердии как-то его понять?

Вообще не представляю, как можно ответить на этот вопрос.

[Tcirkubakin]

Да, я ответил весьма размыто. Сложности возникают при попытке отделить внешние и внутренние рассуждения по отношению к теории(у объяснения из русской википедии). Из английской википедии непонятно, как логика первого порядка не в состоянии обнаружить отсутствие моделей у некоторых термов. Сейчас пытаюсь понять доказательство из учебника(иногда кажется, что начинаю понимать). Возможно поспешил с написанием вопроса, в таком случае извиняюсь за скоропалительность.

[mihaild]

Очень просто, если принять, что модель теории, в том числе теории множеств - это не "объективная реальность", это просто опять же какое-то множество с какими-то отношениями.
Пусть у нас есть внутренняя счетная модель $M$ и внешняя ("нормальная", хотя она может быть тоже счетной) $N$. У нас есть множество натуральных чисел $X$ внутри $M$, множество $P_M(X)$ всех его подмножеств относительно $M$, и множество $P_N(X)$ всех его подмножеств относительно $N$.
С точки зрения $M$ множество $P_M(X)$ несчётно. Т.е. в $M$ нет биекции между $X$ и $P_M(X)$.
С точки зрения $N$ такая биекция есть, но элементом $M$ она не является. А еще с точки зрения $N$ множество $P_M(X)$ на самом деле не является множеством всех подмножеств $X$, потому что у $X$ с точки зрения $N$ есть подмножества, не принадлежащие $M$.

Tcirkubakin в сообщении #1586246 писал(а):

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

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

[Tcirkubakin]

mihaild в сообщении #1586251 писал(а):

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

Да, написал некорректно, имел ввиду, что есть(многие) элементы в множестве u которые не имеют соответствующего элемента в модели (возможно, перевожу вольно - вот оригинал: "From an interpretation of the model into our conventional notions of these sets, this means that although u maps to an uncountable set, there are many elements in our intuitive notion of u that do not have a corresponding element in the model." https://en.wikipedia.org/wiki/Skolem%27s_paradox ).
С остальным попробую разобраться.

[Tcirkubakin]

Если будут вопросы, возможно, напишу ещё. Я правильно понял, что модель $N$ оценивает не только $X$, но и модель $M$?

[mihaild]

Tcirkubakin в сообщении #1586330 писал(а):

Я правильно понял, что модель $N$ оценивает не только $X$, но и модель $M$?

Да. Чтобы говорить о мощности модели $M$, нам нужно саму модель рассматривать как множество в какой-то модели.

[Tcirkubakin]

Здесь, кроме определения модели, указывается, что каждому терму при оценке сопоставляется некоторый элемент модели. (https://archive.org/details/a-concise-i ... ew=theater). Из ответа в этом топике следует, как я понял(если не ошибся), что с точки зрения модели $N$ в модели $M$ некоторым элементам термов не сопоставляется элемент из $M$. Правильно ли я понимаю(если я не ошибся ранее), что если в рамках внутренней модели $M$ нельзя показать отсутствие оценки у некоторых элементов термов(например, у несчётных множеств), то такая модель имеет право на существование?

[mihaild]

Нет, если у нас есть модель, то всем термам (последовательностям символов нужного вида) обязательно должен быть сопоставлен элемент модели. Например пусть в модели $M$ терму $\mathbb N$ сопоставлено множество $X$, терму $P(\mathbb N)$ тоже должно быть что-то из $M$ сопоставлено (пусть будет $Z$), причем это что-то должно удовлетворять стандартным аксиомам: например что если какой-то элемент $Y$ модели $M$ такой, что в этой модели формула $Y \subset X$ оценивается истиной, то $Y \in Z$ тоже должно оцениваться истиной (тут некоторая вольность речи - строго говоря, $Y \subset X$ это не формула, т.к. $X$ и $Y$ это элементы модели, а не термы).
(для простоты считаем, что в языке теории множеств есть константа $\mathbb N$ и функциональный символ $P$)
С точки зрения $N$ множество $Z$ не будет "настоящим" булеаном $X$. Но поймать $M$ на этой ненастоящести за руку не удастся.

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

[Tcirkubakin]

Давайте я проведу рассуждение, чтобы было понятно, где именно я ошибаюсь:
1. Из теоремы Лёвенгейма-Скулема следуют существование счётной модели $M$ у ZFC.
2. Из аксиомы теории множеств(AI) вытекает существование множества $\omega$, играющее роль множества натуральных чисел.
3. Из аксиомы булеана следует существование у множества $\omega$ множества всех подмножеств $u$.
4. В рамках теории ZFC в модели $M$ доказывается несчётность $u$.
5. Я представляю, что терму $u$ принадлежит несчетный набор термов, которые надо как-то оценить.
6. В рамках внешней модели $N$ доказывается, что оценка внутренней модели $M$ множества $u$ счётна.
7. Из пункта 6 я делаю вывод, что несчётный набор термов из пункта 5 не получится оценить, так как оценка внутренней модели $M$ множества $u$ счётна, следовательно то, что мы называем моделью $M$ таковой не является(она оценивает не все термы, принадлежащие $u$).
Сейчас возникло предположение, что я ошибся в пункте 5, так как мы можем построить только счётное множество термов, принадлежащих $u$(каждый терм, принадлежащий $u$ будет иметь вид конечного множества(за исключением $\omega$), множество всех этих конечных множеств будет, максимум, счётным), следовательно можно из счётной модели $M$ каждому терму, принадлежащему $u$ сопоставить оценку.
P.S.(каждый терм, принадлежащий $u$ будет иметь вид конечного множества(за исключением $\omega$, и объединением $\omega$ с каким то конечным набором конечных множеств).

-- 23.03.2023, 19:03 --

P.P.S. (каждый терм, принадлежащий $u$ будет иметь вид конечного множества(за исключением не только $\omega$, и объединением $\omega$ с каким то конечным набором конечных множеств, но и счётного набора счётных множеств,(так как можно из конечных множеств, согласно какому-нибудь правилу построения(алгоритму), построить лишь счётное множество счётных множеств) )

[mihaild]

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

Чтобы было совсем интересно - можно построить модель ZF, в которой каждое множество будет задаваться какой-то формулой. К противоречию это не приводит, потому что модель не обязана знать (и не будет знать), что вот такое её множество задается вот такой формулой (и что эта формула вообще задает множество).

Tcirkubakin в сообщении #1586456 писал(а):

каждый терм, принадлежащий $u$ будет иметь вид конечного множества

Терм имеет вид последовательности символов, а не множества. Оценка терма - это множество, и это множество конечным быть совершенно не обязано.

[Tcirkubakin]

mihaild в сообщении #1586458 писал(а):

Терм имеет вид последовательности символов, а не множества. Оценка терма - это множество, и это множество конечным быть совершенно не обязано.

Я имел в виду(не знаю, может быть опять ошибаюсь) следующее:
В ZFC можно, например вывести следующие формулы: $\left\{ \emptyset ,\left\{ \emptyset \right\} \right\}\in u$, $\left\{ \emptyset \right\}\in u$. $\left\{ \emptyset ,\left\{ \emptyset \right\} \right\}$ и $\left\{ \emptyset \right\}$ имеют вид множеств, но в учебнике, кажется, называются $\omega-\text{термами}$ (прилагаю страницу: https://archive.org/details/a-concise-i ... 5/mode/1up). Этим термам нужно присвоить оценку из $M$. И мы можем это сделать, т.к. множество всех термов такого рода не более, чем счётно(каждый терм получается согласно какому-нибудь правилу построения(алгоритму), а таких алгоритмов- не более, чем счётно).

[mihaild]

Tcirkubakin в сообщении #1586465 писал(а):

В ZFC можно, например вывести следующие формулы: $\left\{ \emptyset ,\left\{ \emptyset \right\} \right\}\in u$, $\left\{ \emptyset \right\}\in u$. $\left\{ \emptyset ,\left\{ \emptyset \right\} \right\}$ и $\left\{ \emptyset \right\}$ имеют вид множеств, но в учебнике, кажется, называются $\omega-\text{термами}$ (прилагаю страницу: https://archive.org/details/a-concise-i ... 5/mode/1up ).

Они "имеют вид множеств", но на самом деле - это термы. Т.е. строчки языка.
Если говорить совсем формально, то нужно ввести бесконечное количество функциональных символов $\{\}_0, \{\}_1, \ldots, \{\}_n, $ (чтобы была известна валентность), и писать не $\{a, b, c\}$ а $\{\}_3(a, b, c)$. Но это обычно даже явно не проговаривают (и фигурные скобки как формальную конструкцию не вводят).
Еще полезно учитывать, что $\varnothing$ может означать как просто константный символ языка теории множеств, так и множество (элемент модели теории множеств).

Tcirkubakin в сообщении #1586465 писал(а):

Этим термам нужно присвоить оценку из $M$. И мы можем это сделать, т.к. множество всех термов такого рода не более, чем счётно

Тут, возможно, тоже путаница. Термов счетно просто потому, что терм - это конечная строчка в не более чем счетном алфавите, а таких строчек не более чем счётно.
Но что значит "можем присвоить оценку" - непонятно. Алгоритмически - нет, не можем, вычислимой счетной модели у ZF нет. Если просто "существует оценка" - непонятно, зачем тут счетность.

[Tcirkubakin]

mihaild в сообщении #1586478 писал(а):

Тут, возможно, тоже путаница. Термов счетно просто потому, что терм - это конечная строчка в не более чем счетном алфавите, а таких строчек не более чем счётно.

Да, только сейчас понял, что можно не "идти кривым путём", и что количество термов счётно из-за свойств алфавита. Ну что ж, благодарю за ответы, кажется(надеюсь) всё понял.