Можно ли привести пример бесконечно большого числа?

[AGu]

Эта задача — для крутых логиков. К барьеру, господа.

Существует ли модель ZFC, содержащая определимое нестандартное натуральное число?

Во избежание разночтений уточним все формальности.

Разумеется, вопрос формулируется в предположении, что теория ZFC непротиворечива.

Пусть $M$ — произвольная модель ZFC. Говорят, что формула $\varphi(x)$ сигнатуры $\{{=},{\in}\}$ с одной свободной переменной $x$ определяет $\mu$ в $M$, если $\mu$ является единственным элементом модели $M$, обладающим внутри этой модели свойством $\varphi$, т.е. $\mu\in M$ и

$(\exists!\,m\in M)\bigl(M\vDash\varphi(m)\bigr)
\ \&\ M\vDash\varphi(\mu)$

или, что то же самое,

$M\vDash\bigl((\exists!\,x)\,\varphi(x)\ \&\ \varphi(\mu)\bigr)$.

Элемент $\mu\in M$ называется определимым, если существует формула, определяющая $\mu$ в $M$.

Для каждого метанатурального $n\in\omega$ рассмотрим формулу $\color{blue}\delta_n(x)$, определяющую в ZFC нумерал ${\color{blue}\ulcorner n\urcorner}$:

$\delta_0(x)\ :=\ (x=\ulcorner 0\urcorner)\ :=\ (\forall\,y)(y\notin x)$;
$\delta_{n+1}(x)\ :=\ (x=\ulcorner n\urcorner+1)\ :=\ (\exists\,y)\bigl(\,\delta_n(y)\ \&\ x=y+1\,
\bigr),$

где ${\color{blue}y+1} := y\cup\{y\}$.

Рассмотрим формулу $\color{blue}\nu(x)$, определяющую понятие натурального числа:

$\nu(x)\ :=\ (\forall\,y)\bigl(\,\ulcorner 0\urcorner\in y\ \&\ (\forall\,z)(z\in y\Rightarrow z+1\in y)\Rightarrow x\in y\,\bigr)$.

Элемент $\mu\in M$, обладающий в $M$ свойством $\nu$ (т.е. $M\vDash\nu(\mu)$), называется натуральным числом в $M$.

Для любого $n\in\omega$ любая модель $M$ теории ZFC содержит элемент ${\color{blue}n_M}\in M$, определяемый формулой $\delta_n(x)$. Элементы $n_M\in M$ $(n\in\omega)$ являются натуральными числами в $M$ и называются стандартными натуральными числами в $M$. Элемент $\mu\in M$ называется нестандартным натуральным числом в $M$, если $\mu$ является натуральным числом в $M$ и не является стандартным натуральным числом в $M$.

Вот, пожалуй, и всё. Все упомянутые понятия уточнены, и рассматриваемый вопрос обрел четкий смысл. Звучит вопрос ровно так же, как и в самом начале:

Существует ли модель ZFC, содержащая определимое нестандартное натуральное число?

P.S. Если что-то осталось неуточненным, я к вашим услугам.

[Update] По просьбе читателей убрал насильственное форматирование. Также поясняю: синим цветом выделены определяемые понятия и вводимые обозначения.

[Nik_Nikols]

Я правильно понимаю, что $z+1$ в формуле для $\nu(x)$ означает $z\cup \{z\}$?

[AGu]

Nik_Nikols в сообщении #1007266 писал(а):

Я правильно понимаю, что $z+1$ в формуле для $\nu(x)$ означает $z\cup \{z\}$?

Да.
(Т.е. это самое обычное классическое определение натуральных чисел. Я его привел на всякий случай — чтобы не было разночтений.)

[Nemiroff]

Что-то страшное.
Интуитивно: надо что-то придумать.
Например, какое-нибудь недоказуемое в ZFC утверждение, которое точно истинно или ложно, если натуральные числа в модели только стандартные.

[Dan B-Yallay]

Nemiroff в сообщении #1007433 писал(а):

Интуитивно: надо что-то придумать.
Например, какое-нибудь недоказуемое в ZFC утверждение, которое точно истинно или ложно, если натуральные числа в модели только стандартные.

По моему Вы его только что сформулировали.

[AGu]

Nemiroff в сообщении #1007433 писал(а):

недоказуемое в ZFC утверждение, которое точно истинно или ложно, если натуральные числа в модели только стандартные.

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

[AGu]

Ну ладно, поугадываю.

Nemiroff в сообщении #1007433 писал(а):

какое-нибудь недоказуемое в ZFC утверждение, которое точно
истинно или ложно, если натуральные числа в модели только стандартные.

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

Для произвольной модели $M$ теории ZFC положим ${\color{blue}\Omega_M}:=\{m\in M:M\vDash\nu(m)\}$, ${\color{blue}\Omega^\circ_M}:=\{n_M:n\in\omega\}\subseteq\Omega_M$. Таким образом, $\Omega_M$ — множество всех натуральных чисел в $M$, а $\Omega^\circ_M$ — множество всех стандартных натуральных чисел в $M$. Модель $M$ называется $\color{blue}\omega$-стандартной, если $\Omega_M=\Omega^\circ_M$.

Притворимся, будто процитированная выше мысль заключается в отыскании такого предложения $\tau$, что для любой модели $M$

$M\vDash\tau\ \Leftrightarrow\ M$ $\omega$-стандартна.

Такое предложение $\tau$ назовем $\color{blue}\omega$-тестом. (В приведенной цитате дополнительно требуется, чтобы $\omega$-тест был еще и недоказуем в ZFC, но это заведомо так, поскольку не все модели ZFC $\omega$-стандартны.)

Спрашивается, каким боком наличие $\omega$-теста способно помочь нам ответить на поставленный вопрос? Возможно, я полохой танцор, но ответ не вытанцовывается. Ну, допустим, есть у нас $\omega$-тест $\tau$. И что нам с ним делать? У нас есть модель $M$, для которой множество $\Omega_M\backslash \Omega^\circ_M$ всех нестнадртных натуральных чисел в $M$ непусто. А еще в этой модели $\tau$ ложно. Ну и что дальше? Как с помощью $\tau$ определить какой-то элемент $\Omega_M\backslash \Omega^\circ_M$? Непонятно...

Но даже если бы танец удался и с помощью $\omega$-теста можно было бы определить нестандартное натуральное число, возникают большие сомнения в существовании $\omega$-теста.

Для начала стоит иметь в виду, что существование $\omega$-стандартных моделей ZFC находится под вопросом. Нельзя сказать, что наука пребывает в отчаянном поиске $\omega$-стандартных моделей, но доказывать их наличие она не умеет. Логики при желании предполагают, что такие модели есть, и время от времени намекают, что будут крайне удивлены, если в какой-то момент вдруг окажется, что таких моделей нет.

Итак, в принципе допустимы два случая:

(0) $\omega$-стандартных моделей ZFC нет;
(1) $\omega$-стандартные модели ZFC есть.

В случае (0), который считается очень маловероятным, $\omega$-тест, конечно же, существует, и на его роль подходит любая «чушь» вроде $2\times 2=5$ или $(\exists\,x)(x\ne x)$. Такая «чушь» едва ли способна помочь в решении задачи, а значит, в случае (0) наличие $\omega$-теста ничего нам не дает.

Что же касается (1), то в этом случае $\omega$-тест не существует. Действительно, пусть $M$ — $\omega$-стандартная модель ZFC. Рассмотрим ультрастепень ${\color{blue}M^*}:=M^\omega/u$ модели $M$ по любому свободному (неглавному) ультрафильтру $u\subset\mathcal P(\omega)$. Поскольку класс «диагонали» $(n_M)_{n\in\omega}$ является нестандартным натуральным числом в $M^*$, эта модель не является $\omega$-стандартной. Стало быть, модель $M$ $\omega$-стандартна, а модель $M^*$ — нет. С другой стороны, модели $M$ и $M^*$ элементарно эквивалентны, т.е. в них истинны одни и те же предложения (по теореме Лося). Следовательно, $\omega$-теста в случае (1) быть не может.

[AGu]

В качестве первой подсказки сообщаю ответ: «да».

[AGu]

Итак, было бы славно отыскать такую формулу $\varphi(x)$ и такую модель $M$ теории ZFC, чтобы формула $\varphi(x)$ определяла в $M$ натуральное число, отличное от $n_M$, $n\in\omega$. Это означает, что в $M$ должны быть истинны следующие формулы:

$(\exists!\,x)\,\varphi(x)$,
$(\exists\,x)\bigl(\nu(x)\ \&\ \varphi(x)\bigr)$,
$\neg\varphi(\ulcorner n\urcorner)$  для всех $n\in\omega$,

где ${\color{blue}\varphi(\ulcorner n\urcorner)} := (\exists\,x)\bigl(\delta_n(x)\ \&\ \varphi(x)\bigr)$.

Допустим, нам удалось доказать такую лемму:

Лемма 1.  Существуют формула $\psi(x)$ и модель $M$ теории ZFC такие, что в $M$ истинны формулы

$(\exists\,x)\bigl(\nu(x)\ \&\ \psi(x)\bigr)$,
$\neg\psi(\ulcorner n\urcorner)$  для всех $n\in\omega$.

Как с помощью $\psi(x)$ получить искомую $\varphi(x)$?

[kp9r4d]

Некрутой нелогик у барьера. Я не понимаю почему не прокатывает такое.
Найдём по теореме Гёделя недоказуемое утверждение $G$ в $PA$. рассмотрим в нашей $ZFC$ все арифметические утверждения (которые можно сформулировать на языке $L_1$) смотрим, выполняется там $G$ или нет. Пусть выполняется. Берём все аксиомы $ZFC$ прибавляем $\neg G$, строим модель по теореме о полноте, в этой модели выберем любой элемент из $\omega \setminus \bigcup_{n=0}^\infty n$, вот он-то и будет.
Я ведь правильно понимаю, что в нестандартной модели $ZFC$ наименьшее индуктивное множество не обязано совпадать с $\bigcup_{n=0}^\infty n$?

[AGu]

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

kp9r4d в сообщении #1009725 писал(а):

Найдём по теореме Гёделя недоказуемое утверждение $G$ в $PA$. рассмотрим в нашей $ZFC$ все арифметические утверждения (которые можно сформулировать на языке $L_1$) смотрим, выполняется там $G$ или нет. Пусть выполняется. Берём все аксиомы $ZFC$ прибавляем $\neg G$, строим модель по теореме о полноте, в этой модели выберем любой элемент из $\omega \setminus \bigcup_{n=0}^\infty n$, вот он-то и будет.

Мне кажется, что почти все сказанное — бессмысленно и безыдейно. Если тут и есть какие-то идеи, то они присутствуют лишь в виде намеков, далеких до реализации. Я в меру сил попробую сейчас все уточнить и осмыслить, но заранее предупреждаю: у меня ничего путного не получилось. (Признаюсь, кое-какие неясности я мог бы раскрыть по-другому, но тогда я бы сразу много подсказал, а мне этого делать пока не хочется. )

Итак, пусть $\color{blue}G$ — «утверждение» (сторого говоря — формула, а точнее — предложение, т.е. формула без свободных переменных), недоказуемое в PA, т.е. ${\rm PA}\nvdash G$. Чтобы можно было говорить о (не)доказуемости $G$ в PA, формула $G$ должна принадлежать языку арифметики, имеющем сигнатуру $\{{=},0,{}',{+},{\cdot}\}$ (или аналогичную). Стало быть, $G$ — предложение сигнатуры арифметики, недоказуемое в PA. (Вероятно, годится не любая такая формула: еще надо чтобы $G$ была неопровержима в PA. Это не было сказано явно, но, возможно, подразумевалось.)

Далее предлагается рассмотреть в ZFC «все арифметические утверждения (которые можно сформулировать на языке $L_1$)». Будем угадывать. Что такое «язык $L_1$»? Видимо, это какой-то язык логики первого порядка. Поскольку на сей раз речь идет о ZFC, это должен быть язык теории множеств, имеющий сигнатуру $\{{=},{\in}\}$. Что можно понимать под «арифметическими утверждениями», записанными на этом языке? Видимо, речь идет об интерпретации формул языка арифметики в классической теоретико-множественной модели арифметики ${\color{blue}\omega}=(\omega,0,{}',{+},{\cdot})$. [Не путать с метанатуральными числами, совокупность которых у нас тоже обозначалась $\omega$!] Точнее говоря, это утверждения вида $\omega\vDash\varphi$, где $\varphi$ — формулы языка арифметики. Для краткости вместо $\omega\vDash\varphi$ будем иногда писать $\color{blue}{}^{\omega}\varphi$.

Теперь предлагается посмотреть, «выполняется там $G$ или нет». Стало быть, надо посмотреть, «выполняется» ли «там» формула ${\color{blue}{}^{\omega}G}:=(\omega\vDash G)$. Где «там»? И что значит «выполняется»? «Там» — это, видимо, в ZFC, потому что больше, вроде, негде. Значит, надо посмотреть, «выполняется» ли формула ${}^{\omega}G$ в ZFC. У нас ZFC — это теория, а в ней формулы «выполняться» не могут. (Выполняться или не выполняться, т.е. быть истинными или ложными, формулы могут в моделях, а не в теориях. Слова «выполняться» и «истинно» иногда также употребляются всуе в рассуждениях, проводимых в рамках теории, где фраза «выполняется утверждение $\varphi$» заменяет само утверждение $\varphi$. Но это, похоже, не наш случай.) Итак, в ZFC, как и в любой теории, формулы не могут выполняться или не выполняться. Они могут там быть, например, доказуемыми, недоказуемыми, опровержимыми или неопровержимыми. Стало быть, под «выполнением» формулы в ZFC, наверное, понимается ее доказуемость в ZFC. Таким образом, предлагается посмотреть, доказуема ли формула ${}^{\omega}G$ в ZFC.

Фразу «Пусть выполняется» в данном случае следует понимать так: пусть формула ${}^{\omega}G$ доказуема в ZFC, т.е. пусть ${\rm ZFC}\vdash(\omega\vDash G)$. Хорошо, пусть. (Кстати, а что делать, если «не пусть»? Что делать, если формула ${}^{\omega}G$ окажется все же недоказуемой или даже опровержимой в ZFC? Искать другую подходящую формулу $G$? А почему такая найдется? Короче, непонятки. Но пока — ладно, «пусть».)

Далее предлагается «прибавить $\neg G$» к аксиомам ZFC, т.е. рассмотреть теорию ${\color{blue}\rm ZFC'}:={\rm ZFC}\cup\{\neg({}^{\omega}G)\}={\rm ZFC}\cup\{\omega\nvDash G\}$. После этого нам предлагают «строить модель по теореме о полноте». Увы, теория ${\rm ZFC}'$ не имеет модель, потому что эта теория противоречива. Действительно, поскольку ${\rm ZFC}\vdash(\omega\vDash G)$, мы имеем ${\rm ZFC}'\vdash(\omega\vDash G)$, а с другой стороны, ${\rm ZFC}'\vdash(\omega\nvDash G)$, так как $(\omega\nvDash G)$ — это одна из аксиом ${\rm ZFC}'$. Вероятно, мы имеем дело с опечаткой, и вместо «прибавить $\neg G$» подразумевалось «прибавить $G$». Возможно также, что мы как-то неправильно интерпретировали слово «выполняется» или слово «пусть». Но все это, как ни странно, совершенно не важно, поскольку $G$ в дальнейших рассуждениях вообще никак не участвует, и мы можем с чистой совестью игнорировать все, что было сказано к этому моменту.

Итак, как бы то ни было, рассматривается некоторая модель $\color{blue}M$ некоторой теории ${\rm ZFC}'$, как-то расширяющей ZFC. После этого нам предлагают «выбрать любой элемент из $\omega \setminus \bigcup_{n=0}^\infty n$». Опять непонятки. Что в этот момент обозначает символ $\omega$? Ясно, что сейчас это уже не прежнее $\omega$, и у этого символа теперь есть какая-то связь с $M$. Вероятно, это то, что мы раньше обозначали $\Omega_M$, т.е. совокупность всех натуральных чисел в $M$. А может быть, это тот элемент $M$, который внутри $M$ является множеством натуральных чисел. Далее, что такое $\bigcup_{n=0}^\infty n$? Вероятно, запись $\bigcup_{n=0}^\infty$ означает $\bigcup_{n\in\omega}$, где $\omega$ — это, опять-таки, нечто связанное с $M$. Далее, что это за $n$, которые предлагается объединять? Это те самые $n$, которые в индексе или это $n_M$? Если это те, которые в индексе, то разность $\omega \setminus \bigcup_{n=0}^\infty n$, очевидно, пуста. А если это $n_M$, то тогда запись $\bigcup_{n=0}^\infty$ должна олицетворять объединение по метанатуральным числам, и возникает вопрос о том, почему разность $\omega \setminus \bigcup_{n=0}^\infty n$ непуста. Непуста она будет ровно тогда, когда модель $M$ не является $\omega$-стандартной. Почему она не является $\omega$-стандартной, не понятно. Но ладно, пусть она такой будет. И пусть разность $\omega \setminus \bigcup_{n=0}^\infty n$ непуста. Нам предлагают «выбрать» в ней любой элемент. Что значит «выбрать»? Просто рассмотреть любой ее элемент? Едва ли, так как в этом случае непонятно, с какой стати он будет определимым. Видимо, фраза «вот он-то и будет» оначает, что такой элемент должен быть выделен какой-то формулой. Какой формулой — непонятно.

Итог: ничего не понятно и идей не видно.

[kp9r4d]

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

[ivvan]

AGu в сообщении #1009521 писал(а):

Как с помощью $\psi(x)$ получить искомую $\varphi(x)$?

Это возможно без изменения $M$?

[AGu]

ivvan в сообщении #1010122 писал(а):

Это возможно без изменения $M$?

Да.