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

[Феликс Шмидель]

Существование неразрешимого множества натуральных чисел легко доказать, например, рассматривая множество индексов зацикливающихся программ.
Существование этого множества следует из аксиомы подмножеств и из существования множества всех натуральных чисел.
Но если рассматривать множества в качестве объектов счётной модели, то все подмножества не могут существовать, потому что их несчётное колличество.
Что будет если заменить аксиому подмножеств на аксиому существования только разрешимых множеств?
В такой теории множеств, каждому множеству соответствует некоторое натуральное число, и подмножество существует только если соответствующее ему множество натуральных чисел разрешимо.
Какие трудности могут возникнуть в такой теории множеств с определением действительных чисел и доказательством теорем математического анализа?

[Феликс Шмидель]

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

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

Феликс Шмидель в сообщении #581684 писал(а):

Но если рассматривать множества в качестве объектов счётной модели...

Вот это место подробнее, пожалуйста. Что за счётная модель?

[Феликс Шмидель]

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

Феликс Шмидель в сообщении #581684 писал(а):

Но если рассматривать множества в качестве объектов счётной модели...

Вот это место подробнее, пожалуйста. Что за счётная модель?

Я имел ввиду какую-либо счётную модель теории множеств $ZFC$. Существование счётной модели является следствием теоремы Лёвенгейма-Сколема.
Возникает вопрос, каким образом можно определить на счётном множестве всех объектов модели отношение принадлежности $x\in y$, чтобы выполнялись аксиомы $ZFC$?
Если бы это удалось, то мы бы доказали непротиворечивость $ZFC$ относительно арифметики, что невозможно.
Поэтому я предложил заменить аксиому подмножеств в $ZFC$ на существование разрешимых множеств.

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

По-моему, Вы пишите какой-то бред. В целом. Я, пожалуй, уйду отсюда быстро-быстро...

[Феликс Шмидель]

Спасибо. В таком случае тему следует удалить.

[Феликс Шмидель]

Я попытаюсь развить эту теорию множеств.
Пусть имеется занумерованное счётное множество объектов $U$.
Занумеруем все программы, вычисляющие функции из $\mathbb{N}$ в $\mathbb{N}$.
Часть этих программ вычисляет возрастающие последовательности и определяют разрешимые множества натуральных чисел.
Обозначим совокупность индексов этих программ через $M$.
Определим на множестве $U$ отношение $x\in y$, как истинное только если индекс объекта $y$ принадлежит $M$, а индекс объекта $x$ принадлежит последовательности, которую вычисляет программа с индексом объекта $y$.
Отношение $x\in y$ определяет на $U$ теорию множеств, в которой существуют только разрешимые множества.
В этой теории множеств объединение, пересечение и дополнение множеств являются множеством.
Все конечные совокупности объектов из $U$ являются множествами.
Совокупность всех объектов $U$ является множеством, поэтому в этой теории множеств существует бесконечное множество.
В этой теории множеств можно определить вычислимые действительные числа и вычислимые последовательности этих чисел.
Можно доказать, что предел ограниченной монотонной вычислимой последовательности вычислимых действительных чисел является вычислимым действительным числом.

[Xaositect]

1) Это не разрешимые множества, а перечислимые
2) По этой причине не всегда можно построить разность двух бесконечных множеств. Так что насчет действительных чисел у меня тоже возникают сомнения
3) В этой теории нет экстенсиональности (существуют разлиные программы $y_1$ и $y_2$, порождающие одни и те же числа).

[Феликс Шмидель]

Xaositect в сообщении #582315 писал(а):

1) Это не разрешимые множества, а перечислимые
2) По этой причине не всегда можно построить разность двух бесконечных множеств. Так что насчет действительных чисел у меня тоже возникают сомнения
3) В этой теории нет экстенсиональности (существуют разлиные программы $y_1$ и $y_2$, порождающие одни и те же числа).

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

[Xaositect]

Феликс Шмидель в сообщении #582324 писал(а):

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

Да, Вы правы.

Феликс Шмидель в сообщении #582324 писал(а):

Поэтому внесём изменение в определение совокупности индексов $M$.
Исключим из этой совокупности индексы программ, вычисляющих последовательности, которые вычисляются программой с меньшим индексом.
Тогда аксиома экстенциональности выполняется.

Тогда нет аксиомы степени - множество таких индексов для всех разрешимых множеств неразрешимо, так что $2^{\omega}$ в вашей модели не существует.

[Феликс Шмидель]

Xaositect в сообщении #582325 писал(а):

Тогда нет аксиомы степени - множество таких индексов для всех разрешимых множеств неразрешимо, так что $2^{\omega}$ в вашей модели не существует.

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

[Someone]

Феликс Шмидель в сообщении #582334 писал(а):

Аксиомы степени, действительно нет.

Аксиомы выделения нет...

[Феликс Шмидель]

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

Феликс Шмидель в сообщении #582334 писал(а):

Аксиомы степени, действительно нет.

Аксиомы выделения нет...

Я об этом писал:

Цитата:

я предложил заменить аксиому подмножеств в $ZFC$ на существование разрешимых множеств.

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

[Someone]

Феликс Шмидель в сообщении #582349 писал(а):

Я об этом писал:

Вы странно называете аксиому выделения. Под названием "аксиома подмножеств" я её не узнал. Я подумал, что речь идёт об аксиоме степени. Кстати, заодно нет и аксиомы подстановки.

Также сильно подозреваю, что нет и аксиомы объединения.

Вообще, какие-то непонятные у Вас идеи. Зачем это?

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

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

Вообще, какие-то непонятные у Вас идеи. Зачем это?

Да идеи, вообще говоря, не новые, и не его. Роджерс, \S 11.4