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

[epros]

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

Принятие этого утверждения за аксиому не доказывает его.

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

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

Оно следует из непротиворечивости новой теории, но эта непротиворечивость требует доказательства.

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

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

Если бы аксиома бесконечности не была очевидной, её бы не включили в стандартную теорию множеств.

Это не математический аргумент: очевидно - не очевидно. Вам очевидно существование бесконечного множества - мне нет. Мне очевидно несуществование нечётного совершенного числа - Вам нет. Бессмысленно спорить об очевидностях - в этом нет математики.

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

Тем не менее, истинность утверждения о несуществовании натуральных решений уравнения "$2x=5$" это не вопрос веры.

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

Да, в арифметике Пеано существование такого числа исключено. Но арифметика Пеано - не есть что-то изначальное... Например, одной из моделей Вашей "минимальной арифметики" являются положительные действительные числа. В такой модели такое число существует.

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

Это Ваше понятие "истинности" привязано к конкретной аксиоматике арифметики. Оно не отличается от доказуемости в этой аксиоматике.
А моё понятие истинности утверждений допускает их доказательство в более сильной аксиоматике.

Я не въехал в "Ваше понятие истинности". Всё доказуемое в теории - доказуемо также и в "более сильной аксиоматике". Равно как и всё опровержимое в теории - опровержимо и в "более сильной аксиоматике". Просто в более сильной аксиоматике можно доказать или опровергнуть кое-что из неразрешимого в теории. Но тут "истинность" зависит от того, какой из вариантов "более сильной аксиоматики" мы выберем.

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

Пожалуйста, поподробнее, или ссылочку.

Может я неудачно выразился. Но положительные действительные числа в качестве модели "минимальной арифметики", например, Вас устраивают?

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

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

Да без проблем. Вводите в той метатеории, которая оперирует "несколькими теориями одновременно", предикат "является натуральным числом". После этого любое утверждение $P$ арифметики натуральных чисел про любое натуральное число $x$ в метатеории можно будет записать как $\mathbb{N}(x) \to P$. Но в самой теории натуральных чисел этот предикат совершенно не нужен.

[epros]

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

Итак, допустим, что есть некая "минимальная арифметика" $A$, всё доказуемое и всё опровержимое в которой мы автоматически принимаем соответственно за истинное и за ложное. Но есть некоторое множество утверждений, неразрешимых в $A$. Чтобы разобраться с их истинностью, мы поступаем так: Добавляем к $A$ аксиому о непротиворечивости $A$ (можете попробовать её доказать на основании чего-нибудь, но это - отдельный разговор), в результате получаем теорию $B$. Если в $B$ доказано, что некое утверждение с первым квантором существования неразрешимо в $A$, то мы автоматически считаем его ложным. (Аналогично, если в $B$ доказано, что некое утверждение с первым квантором всеобщности неразрешимо в $A$, то мы автоматически считаем его истинным).

Вопрос: Зачем это всё нужно? Это несколько расширяет множество тех утверждений, об истинности которых мы можем судить. Причём, мы не добавили никаких невесть откуда взятых дополнительных аксиом, мы только использовали "естественное" предположение о непротиворечивости "минимальной арифметики".

Почему же это всё-таки не имеет особого смысла? Да потому, что куча неразрешимых утверждений всё равно останется - Это все те утверждения, про разрешимость которых в $A$ теория $B$ ничего сказать не может.

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

Цитата:

Почему же это всё-таки не имеет особого смысла? Да потому, что куча неразрешимых утверждений всё равно останется - Это все те утверждения, про разрешимость которых в $A$ теория $B$ ничего сказать не может.

Правильно, поэтому я предлагаю другое: доказывать арифметические утверждения в теории множеств, добавляя аксиомы о существовании множеств с большими кардинальными числами.
Я вижу некоторую противоположность между арифметикой и теорией множеств:
к числам 1, 2, 3, ... нельзя добавлять другие объекты и объявлять их натуральными, а к существующим множествам, наоборот, можно и нужно.
Новые аксиомы о существовании множеств позволяют доказывать недоказуемые ранее арифметические утверждения о несуществовании.

[epros]

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

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

Чем Вам далась эта теория множеств? Суть ведь не в магическом слове «множество», а в силе аксиоматики. Есть слабые аксиоматики теории множеств. Например, в General Set Theory недоказуемо даже существование модели арифметики Пеано. А сильные аксиоматики как раз неочевидны - чем сильнее, тем менее очевидны.

Вообще, кто первый заговорил про «минимальную арифметику», не Вы ли? Зачем?

-- Пн июл 09, 2012 17:52:52 --

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

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

Цитата:

Чем Вам далась эта теория множеств? Суть ведь не в магическом слове «множество», а в силе аксиоматики.

Цитата:

Вообще, кто первый заговорил про «минимальную арифметику», не Вы ли? Зачем?

Подходят любые непротиворечивые теории, интерпретирующая минимальную арифметику. Нет никаких оснований полагать, что аксиомы бесконечности в теории множеств ведут к противоречиям.
Если на этом форуме, Вы предложите доказательство теоремы Ферма, приняв её за аксиому, Вас могут забанить.
Но если Вы докажите теорему Ферма в $ZFC$, это доказательство примут, подобно доказательству Уайлза и вряд ли, когда-нибудь опровергнут.

Цитата:

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

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

[epros]

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

Подходят любые непротиворечивые теории, интерпретирующая минимальную арифметику. Нет никаких оснований полагать, что аксиомы бесконечности в теории множеств ведут к противоречиям.
Если на этом форуме, Вы предложите доказательство теоремы Ферма, приняв её за аксиому, Вас могут забанить.
Но если Вы докажите теорему Ферма в ZFC, это доказательство примут, подобно доказательству Уайлза и вряд ли, когда-нибудь опровергнут.

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

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

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

А причём тут "доказать непротиворечивость" и "построение модели"? Да, некоторые теории могут "доказать непротиворечивость" некоторых других (но вовсе не любых!) теорий. Но доказательство существования модели арифметики не означает, что не существует неразрешимого в моделирующей теории арифметического утверждения. Почему? В силу теоремы Гёделя о неполноте.

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

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

Цитата:

Оснований полагать, что аксиомы Пеано приведут к противоречиям - ещё меньше.

Это так, но в теории меожеств можно доказывать недоказуемые а арифметике Пеано арифметические утверждения.

Цитата:

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

Нет. Достаточно непротиворечивости теории, доказуемости "равенств без переменных" и доказуемости в ней утверждения о несуществовании решений диофантового уравнения и вывод будет один: это утверждение истинно.

Цитата:

Но доказательство существования модели арифметики не означает, что не существует неразрешимого в моделирующей теории арифметического утверждения.

Отсюда не следует, что не всякое арифметическое утверждение можно доказать или опровергнуть в теории множеств с достаточно сильной аксиоматикой.

Цитата:

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

Это нельзя определить формально, так же как нельзя формально определить всех аксиом бесконечности в теории множеств.

[epros]

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

Нет. Достаточно непротиворечивости теории, доказуемости "равенств без переменных" и доказуемости в ней утверждения о несуществовании решений диофантового уравнения и вывод будет один: это утверждение истинно.

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

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

Отсюда не следует, что не всякое арифметическое утверждение можно доказать или опровергнуть в теории множеств с достаточно сильной аксиоматикой.

Разумеется не следует. Всякое арифметическое утверждение можно доказать или опровергнуть в какой-то теории, например, в теории принимающей его или его отрицание за аксиому. Ну и что?

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

Это нельзя определить формально

А что значит "определить неформально"? Можете ли Вы "неформально" определить существует ли нечётное совершенное число?

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

так же как нельзя формально определить всех аксиом бесконечности в теории множеств.

Не понял, каких "всех" аксиом бесконечности? Я знаю только одну аксиому бесконечности, она является утверждением о существовании: о существовании индуктивного множества.

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

Цитата:

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

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

Цитата:

Всякое арифметическое утверждение можно доказать или опровергнуть в какой-то теории, например, в теории принимающей его или его отрицание за аксиому. Ну и что?

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

Цитата:

А что значит "определить неформально"? Можете ли Вы "неформально" определить существует ли нечётное совершенное число?

"Определить неформально" ничего нельзя. Можно показать, как, неформально рассуждая, находить новые аксиомы бесконечности и, добавляя эти аксиомы, получать новые теории множеств. Что касается, утверждения о несуществовании нечётного совершенного числа, я думаю, для его доказательства достаточно $ZFC$. Если же нет, то возможно, оно доказуемо в каком-либо из расширений $ZFC$, полученном добавлением аксиом бесконечности.

Цитата:

Не понял, каких "всех" аксиом бесконечности? Я знаю только одну аксиому бесконечности, она является утверждением о существовании: о существовании индуктивного множества.

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

[epros]

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

существование простого числа равносильно существованию натуральных решений определённого диофантого уравнения, а это утверждение доказуемо в "минимальной арифметике"

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

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

С моей точки зрения, подходят теории множеств с аксиомами бесконечности

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

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

epros в сообщении #594462 писал(а):

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

существование простого числа равносильно существованию натуральных решений определённого диофантого уравнения, а это утверждение доказуемо в "минимальной арифметике"

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

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

[epros]

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

Объясните, пожалуйста. Почему существование решения некоторого диофантового уравнения может быть недоказуемым в "минимальной арифметике", если это решение легко найти?

Существование простого числа означает, что существует такое число, у которого нет делителей кроме него самого и единицы. В «минимальной арифметике» ни для какого числа нельзя доказать, что у него нет делителей. Угадайте почему.

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

Цитата:

Существование простого числа означает, что существует такое число, у которого нет делителей кроме него самого и единицы. В «минимальной арифметике» ни для какого числа нельзя доказать, что у него нет делителей. Угадайте почему.

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

[epros]

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

Цитата:

Существование простого числа означает, что существует такое число, у которого нет делителей кроме него самого и единицы. В «минимальной арифметике» ни для какого числа нельзя доказать, что у него нет делителей. Угадайте почему.

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

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

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

Цитата:

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

Нет, конечно. С какой стати? Я же доказал ложность только недоказуемых утверждений о существовании решений диофантовых уравнений.