Существуют ли неразрешимые множества натуральных чисел?

[Sycamore]

Распрощаться с нестандартными моделями PA не собираюсь, конечно, может ошибаюсь, но показалось, что можно узнать ту модель, где других натуральных окромя 1, 2, 3, ... $\omega$ не будет.

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

по идее не должно быть проблем сделать для натуральных.

Удивительно как-то, что ZF(C) можно расширять почти неограниченно большущими множествами/кардиналами и в то же время вроде остаются арифметические предложения типа G/~G или даже диофантовые уравнения, что как-бы неразрешимы в ZF(C).

[mihaild]

Sycamore в сообщении #1447598 писал(а):

можно узнать ту модель, где других натуральных окромя 1, 2, 3, ... $\omega$ не будет

Вопрос - в каком смысле "узнать"? В любом языке первого порядка проходит стандартная конструкция: добавим к теории символ $x$ и скажем $x \in \mathbb N$, $x \neq 0$, $x \neq 1$, $x \neq 2$, ... - получится что в нашей теории бывают нестандартные натуральные числа.

Sycamore в сообщении #1447598 писал(а):

остаются арифметические предложения типа G/~G или даже диофантовые уравнения, что как-бы неразрешимы в ZF(C).

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

[Someone]

Sycamore в сообщении #1447588 писал(а):

за $\mathbb N$/$\omega$ не будет других "нестандартных" натуральных

Sycamore в сообщении #1447598 писал(а):

можно узнать ту модель, где других натуральных окромя 1, 2, 3, ... $\omega$ не будет.

$\omega$ — не натуральное число. И $\mathbb N$ — тоже.

[Sycamore]

да, я поколебался об этом, но решил оставить первый счётный ординал (первое нестандартное натуральное?) в конце как обозначение множества стандартных натуральных :)

[Sycamore]

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

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

интересно было бы указать на нестандартные модели собственно ZF(С), о них как-будто не упоминают часто - рассматривают всякие расширения с дополнительными аксиомами больших кардиналов, АD, самой АС и пр.; похоже, что расширяют эти расширения некоторую подразумеваемую/стандартную модель ZF(C)...

[mihaild]

Sycamore в сообщении #1447703 писал(а):

похоже, что расширяют эти расширения некоторую подразумеваемую/стандартную модель ZF(C)

Эти расширения расширяют теорию ZF - это теории, представляющие объединение ZF и еще каких-то аксиом. Их модели, естественно, будут моделями и самой ZF.
Аналогично прием с добавлением набора аксиом, утверждающего вместе (неформально) "существуют нестандартные натуральные числа", показывает, что и у обычной ZF есть нестандартные модели.

[Sycamore]

а как насчёт нестандартного анализа?

[mihaild]

Нестандартный анализ - про другое (использует гипервещественные числа вместо вещественных), он прекрасно формализуется в ZF, и отличим там от стандартного.

[Someone]

Sycamore в сообщении #1447688 писал(а):

первый счётный ординал (первое нестандартное натуральное?)

Первый бесконечный ординал никакого отношения к нестандартным натуральным числам не имеет.
Для нестандартной модели арифметики выполняются все аксиомы арифметики Пеано, а из них следует, что для каждого натурального числа, кроме самого первого ($0$ или $1$, в зависимости от варианта аксиоматики), существует непосредственно предшествующее натуральное число. Для $\omega$ такого числа нет.

[Sycamore]

ничего не скажешь, спасибо)

-- 27.03.2020, 13:30 --

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

Нестандартный анализ - про другое (использует гипервещественные числа вместо вещественных), он прекрасно формализуется в ZF, и отличим там от стандартного.

сложности-то какие... )

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

а вот континуум (геометрический или действительных чисел), хоть интуитивно/визуально как-бы фиксированный, но плавучая мощность его не удивляет: по сравнению с сугубо минимальным +1 прыжок выглядит довольно неопределённым и "с потолка"/произвольным, так сказать (П.Коэн вроде ожидал, что гипотеза Кантора окажется ложной).

похоже на некую "пропасть" между счётным и всеми высшими кардиналами.

[arseniiv]

Sycamore в сообщении #1447598 писал(а):

Удивительно как-то, что ZF(C) можно расширять почти неограниченно большущими множествами/кардиналами

Как раз-таки полна коробушка аксиом больших кардиналов, не выводимых из ZFC. А расширять ровно так же мы можем PA, добавить аксиому существования нестандартного числа (ладно, на самом деле просто так не можем, зато другие независимые от PA утверждения можем добавлять).

Sycamore в сообщении #1447688 писал(а):

да, я поколебался об этом, но решил оставить первый счётный ординал (первое нестандартное натуральное?)

Именно что важно, что ординалы в одной тарелке, а нестандартные натуральные в другой. Кроме того, что уже сказал Someone, для каждого нестандартного натурального $N$ например существует и такое нестандартное $M < N$, что $N-M$ не стандартно. И вообще если доопределить порядок с чисел на классы вида $\{N+n\mid n\in\mathbb Z\}$ для нестандартных $N$, порядок будет плотным без границ (между двумя любыми различными классами всегда сидит ещё третий, и не существует ни наименьшего, ни наибольшего); для самых простых нестандартных моделей порядок изоморфен порядку на $\mathbb Q$.

Sycamore в сообщении #1447739 писал(а):

похоже на некую "пропасть" между счётным и всеми высшими кардиналами.

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

[Sycamore]

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

полна коробушка аксиом больших кардиналов, не выводимых из ZFC.

недавно где-то встретилось, что выдумают наконец самый большой, хотя такое идёт как-бы в пику "множеству всех множеств" Рассела и показалось забавным)

зато продуктивный Шелах (S.Shelah) набрел в самой ZFC (!) на совершенно с дуба рухнувшее $2^{\aleph_{\omega}}<\;\aleph_{\omega_{4}}$ , где $\aleph_{\omega}$ силно предельный кардинал, $2^{\aleph_{n}}<\;\aleph_{\omega}$ для всех $n$.

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

Счётный кардинал тоже не лыком шит... счётных ординалов громада невероятная.

тем не менее громаду эту можно легко переупорядочить, дабы пришла в соответствие с простым исходным 1, 2, 3, ... Первый несчётный ординал $\omega_{1}$ будет бОльше всей этой громады, а индекс $\omega_{4}$ выше в теореме Шелаха и подавно); вообще думаю, что как концепция кардиналы намного значимее ординалов.

[Someone]

Sycamore в сообщении #1447815 писал(а):

зато продуктивный Шелах (S.Shelah) набрел в самой ZFC (!) на совершенно с дуба рухнувшее $2^{\aleph_{\omega}}<\;\aleph_{\omega_{4}}$ , где $\aleph_{\omega}$ силно предельный кардинал, $2^{\aleph_{n}}<\;\aleph_{\omega}$ для всех $n$.

Нельзя ли ссылку на статью? Мне было бы интересно. Потому что функция $\aleph_{\alpha}\to 2^{\aleph_{\alpha}}$, насколько мне известно, имеет весьма слабые ограничения. Хотя предельные алефы, конечно, имеют свои особенности.

Sycamore в сообщении #1447815 писал(а):

тем не менее громаду эту можно легко переупорядочить, дабы пришла в соответствие с простым исходным 1, 2, 3, ...

Нельзя. Ни легко, ни тяжело. По определению, каждый ординал есть множество всех меньших ординалов. Соответственно, первый несчётный ординал $\omega_1$ есть множество всех конечных и счётных ординалов. Опять же по определению иерархии алефов, мощность $\omega_1$ равна $\aleph_1>\aleph_0$. Поэтому множество конечных и счётных ординалов никак нельзя занумеровать натуральными числами.

[Sycamore]

о да, разумеется) - я как-то поимел в виду те уходящие в бесконечность суммы многоступенчатых степеней, скажем $\omega^{\omega^{\omega^{...}}}+\omega^{127}+...$ , что всё ещё остаются счётными, но и довольно тривиальными, к сожалению.

эту скуку приходится опрокинуть (мутным и критическим, надо признать, по части континуум-гипотезы) прыжком к первому несчётному ординалу $\omega_{1}$, все элементы которого не более, чем счётные.

насчёт предельных алефов Вы угадали): вот обзор книги Шелаха в Bulletin of the American Mathematical Society, https://www.ams.org/journals/bull/1996-33-03/S0273-0979-96-00673-8/S0273-0979-96-00673-8.pdf: "Why the HELL Is It Four?"

[Someone]

Sycamore в сообщении #1449000 писал(а):

я как-то поимел в виду те уходящие в бесконечность суммы многоступенчатых степеней, скажем $\omega^{\omega^{\omega^{...}}}+\omega^{127}+...$ , что всё ещё остаются счётными, но и довольно тривиальными, к сожалению.

Да? Вы берётесь наглядно описать структуру написанного Вами ординала в терминах, доступных школьникам?
Да, где-то там есть наименьший ординал, невыразимый средствами арифметики Пеано. Всё ещё счётный.

Sycamore в сообщении #1449000 писал(а):

эту скуку приходится опрокинуть (мутным и критическим, надо признать, по части континуум-гипотезы) прыжком к первому несчётному ординалу $\omega_{1}$

Нет там никакого "прыжка". $\omega_1$ есть точная верхняя грань множества всех счётных ординалов. Нет никакого промежутка между множеством счётных ординалов и $\omega_1$.

А причём тут континуум-гипотеза, вообще непонятно. "Величина" $\omega_1$ никак от континуум-гипотезы не зависит.

Sycamore в сообщении #1449000 писал(а):

насчёт предельных алефов Вы угадали

А зачем мне было гадать? Я об этом просто знал. Давно уже. Из учебников.

За ссылку спасибо. Взглянув на обзор, я нашёл и книгу в свободном доступе.