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

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

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

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

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

Неправда, зависит. Другое дело, что аксиомы Пеано сформулированы именно так, чтобы этот алгоритм из них следовал. Ну, мы ведь хотим аксиоматизировать именно знакомую со школы арифметику натуральных чисел, а не что-то другое.

Истинность арифметического утверждения в действительности зависит от модели арифметики Пеано. В любой модели 1) аксиомы должны быть истинными утверждениями и 2) логические правила вывода должны преобразовывать истинные утверждения в истинные. Поэтому любое доказуемое утверждение будет истинным в любой модели.
Что касается утверждений, которые нельзя ни доказать, ни опровергнуть, то они в разных моделях могут иметь разное значение истинности.

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

[epros]

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

Можно принять все такие истинные (согласно алгоритму проверки) равенства за аксиомы

Не нужно принимать ВСЕ такие удовлетворяющие "алгоритму проверки" равенства за аксиомы! Достаточно всего лишь принять аксиомы Пеано - все такие равенства будут из них выводимы. Они (аксиомы Пеано) для того и были придуманы: чтобы определить ту модель вычислений, которую Вы именуете "алгоритмом проверки" равенств без переменных.

Тем более, что принять их ВСЕ за аксиомы - технически затруднительно. В отличие от аксиом Пеано, которые можно все выписать (кроме аксиом индукции, которые все выписать нельзя, но всё же можно определить простое правило их проверки).

(Оффтоп)

Вы меня просто не слушаете, надоедает уже по пятому разу повторять одно и то же.

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

Тогда оно всё равно истинно, я же доказал это.

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

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

Его теорема это теорема арифметики Пеано, а не мета-теории.
Он доказал, что из утверждения о непротиворечивости системы аксиом следует $G$.

Утверждения о непротиворечивости арифметики Пеано нет в арифметике Пеано. Но оно есть в мета-теории. Поэтому $G$ доказуемо в мета-теории (но недоказуемо в арифметике Пеано). Не надо путать теоремы арифметики с мета-теоремами.

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

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

Это бессмысленно. Говорить не о чем, пока не сформулирована конкретная теория. Уже сейчас помимо арифметики Пеано первого порядка существует с дюжину различных теорий натуральных чисел. И невозможно обобщённо говорить о какой-то "истинности" утверждений о натуральных числах - без привязки к конкретной аксиоматике.

-- Чт июл 05, 2012 11:32:04 --

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

Назовём эту теорию MA (минимальная арифметика).

Вас устроит теория, которая помимо стандартных законов логики содержит только такие аксиомы:

1) $x+1 \ne 0$
2) $x+1=y+1 \to x=y$
3) $x+0=x$
4) $x+(y+1)=(x+y)+1$
5) $x \times 0=0$
6) $x \times (y+1)=x \times y+x$



В такой теории доказуемы или опровержимы все Ваши "равенства без переменных со знаками сложения и умножения".

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

Цитата:

Вас устроит теория, которая помимо стандартных законов логики содержит только такие аксиомы:

По-моему, можно обойтись без нуля и пятью аксиомами:
1. $x+1\ne 1$
2. если $x+1=y+1$, то $x=y$
3. $x+(y+1)=(x+y)+1$
4. $x\cdot 1=x$
5. $x\cdot(y+1)=x\cdot y+x$

Кроме этого, я бы ввёл именующее понятие: "$x$ - натуральное число" и аксиомы области определения и значений понятий $1$, $x+y$, $x\cdot y$:

A1. 1 - натуральное число.
А2. если $z=x+y$ то $x$, $y$ и $z$ - натуральные числа
А3. если $z=x\cdot y$ то $x$, $y$ и $z$ - натуральные числа

Если добавить к этой системе аксиом, аксиомную схему индукции получится версия арифметики Пеано.

Меня устраивает и эта система и система аксиом Пеано.

Цитата:

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

Ничего подобного. Такая аксиома неочевидна, и полученная система аксиом может быть противоречивой. Другое дело если доказать это утверждение в $ZFC$ или какой-либо другой теории с очевидными аксиомами. Даже если в $ZFC$ обнаружится противоречие, это вряд ли повлияет на найденное доказательство.

Цитата:

Утверждения о непротиворечивости арифметики Пеано нет в арифметике Пеано. Но оно есть в мета-теории.
Поэтому $G$ доказуемо в мета-теории (но недоказуемо в арифметике Пеано). Не надо путать теоремы арифметики с мета-теоремами.

Я согласен с этим, но Гёдель не утверждал, что $G$ истинно или недоказуемо в арифметике Пеано. Он утверждал это при условии, что арифметика Пеано непротиворечива. А это теорема арифметики Пеано, точнее это утверждение мета-теории можно выразить доказуемым в арифметике Пеано утверждением.

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

Цитата:

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

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

[epros]

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

По-моему, можно обойтись без нуля и пятью аксиомами:

Ну, если извратиться, то без нуля можно обойтись.

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

Кроме этого, я бы ввёл именующее понятие: "$x$ - натуральное число" и аксиомы области определения и значений понятий $1$, $x+y$, $x\cdot y$:

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

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

Меня устраивает и эта система и система аксиом Пеано

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

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

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

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

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

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

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

Нет, это "не другое дело". Для меня, например, аксиомы ZFC куда менее "очевидны", чем аксиомы Пеано. А аксиомы бесконечности или выбора, например, кажутся мне менее "очевидными", чем даже аксиома о несуществовании нечётного совершенного числа: Последнее, по крайней мере, пытались найти (и безуспешно), а бесконечное множество даже выписать поэлементно никто всерьёз не пытался.

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

Гёдель не утверждал, что $G$ истинно или недоказуемо в арифметике Пеано. Он утверждал это при условии, что арифметика Пеано непротиворечива

Он утверждал, что из непротиворечивости арифметики следует и истинность, и недоказуемость $G$.

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

А это теорема арифметики Пеано, точнее это утверждение мета-теории можно выразить доказуемым в арифметике Пеано утверждением.

Нет, это не теорема арифметики и это нельзя выразить доказуемым в ней утверждением. Это синтаксически корректное предложение в языке арифметики, и всё.

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

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

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

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

Цитата:

Он утверждал, что из непротиворечивости арифметики следует и истинность, и недоказуемость $G$.

Я сказал то же самое.

Цитата:

Нет, это не теорема арифметики и это нельзя выразить доказуемым в ней утверждением. Это синтаксически корректное предложение в языке арифметики, и всё.

Утверждение: "Если не $Prov(\#(1=0))$ то $G$" является теоремой арифметики Пеано. Почему Вы это отрицаете?

[epros]

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

Утверждение: "Если не $Prov(\#(1=0))$ то $G$" является теоремой арифметики Пеано. Почему Вы это отрицаете?

Я отрицал не это, а то, что $G$ является теоремой арифметики. Возможно, что я неправильно Вас понял, но фраза была построена так...

Да, $\neg Prov(\#(1=0)) \to G$ - теорема арифметики. Только я не понимаю, что Вы этим хотели сказать и зачем.

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

Цитата:

Ну, если извратиться, то без нуля можно обойтись.

Почему Вы называете это извращением? Меня учили, что 0 не является натуральным числом.

[epros]

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

Почему Вы называете это извращением? Меня учили, что 0 не является натуральным числом.

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

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

Цитата:

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

Я же сказал, введем понятие "$x$-натуральное число", формально предикатный символ "$NAT(x)$".
В логике первого порядка это вполне возможно.
А нужно это для того, чтобы утверждения "1 - натуральное число", "2 - натуральное" число, и т.д. можно было формализовать.
Кстати, Пеано включил в свою систему аксиом две аксиомы с этим понятием.

[epros]

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

Я же сказал, введем понятие "$x$-натуральное число", формально предикатный символ "$NAT(x)$".
В логике первого порядка это вполне возможно.
А нужно это для того, чтобы утверждения "1 - натуральное число", "2 - натуральное" число, и т.д. можно было формализовать.
Кстати, Пеано включил в свою систему аксиом две аксиомы с этим понятием.

То, что включил Пеано, не было ещё формальной системой. Потом ещё долго думали, как это формализовать.

Разумеется, одноместный предикатный символ $\mathbb{N}$ в теорию можно ввести, вот только в теории натуральных чисел он не нужен. Нужен он может оказаться в чём-то большем, чем в теории натуральных чисел. Например, в теории целых чисел, где введение данного предикатного символа может сопровождаться следующей определяющей его аксиомой:
$\mathbb{N}(x) \leftrightarrow x>0$

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

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

Цитата:

="epros в сообщении #592750"]Да, $Prov(\#(1=0)) \to G$ - теорема арифметики. Только я не понимаю, что Вы этим хотели сказать и зачем.

В одном вопросе я понял свою ошибку: нельзя принимать непротиворечивость аксиом Пеано на веру, её нужно доказывать в мета-теории.
Что и сделал Генцен.

[epros]

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

В одном вопросе я понял свою ошибку: нельзя принимать непротиворечивость аксиом Пеано на веру, её нужно доказывать в мета-теории.
Что и сделал Генцен.

Это несколько странный вывод. Что значит "нельзя принимать на веру"? Многое приходится принимать на веру и ничего с этим не поделаешь. Генцен, конечно, доказал (трансфинитной индукцией до ординала $\varepsilon_0$), только вот дело-то в том, что мета-теория, в которой это доказано, сама может оказаться противоречивой. Причём эта метатеория целиком включает в себя арифметику Пеано, так что её утверждение о непротиворечивости арифметики звучит как-то неубедительно: Было бы очень странно, если бы теория утверждала противоречивость своей части.

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

Цитата:

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

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

Цитата:

Для меня, например, аксиомы $ZFC$ куда менее "очевидны", чем аксиомы Пеано. А аксиомы бесконечности или выбора, например, кажутся мне менее "очевидными", чем даже аксиома о несуществовании нечётного совершенного числа: Последнее, по крайней мере, пытались найти (и безуспешно), а бесконечное множество даже выписать поэлементно никто всерьёз не пытался.

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

Цитата:

Что значит "нельзя принимать на веру"? Многое приходится принимать на веру и ничего с этим не поделаешь. Генцен, конечно, доказал (трансфинитной индукцией до ординала $\varepsilon_0$), только вот дело-то в том, что мета-теория, в которой это доказано, сама может оказаться противоречивой. Причём эта метатеория целиком включает в себя арифметику Пеано, так что её утверждение о непротиворечивости арифметики звучит как-то неубедительно

Даже если мета-теория противоречива, это может не затронуть доказательство о непротиворечивости арифметики.
Любая теорема арифметики Пеано тоже не абсолютно убедительна, потому что не исключена возможность противоречивости этой арифметики.
Тем не менее, истинность утверждения о несуществовании натуральных решений уравнения "$2x=5$" это не вопрос веры.

Цитата:

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

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

Цитата:

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

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

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

Цитата:

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

Именующие понятия (предикатные символы) нужны для того, чтобы можно было пользоваться различными теориями одновременно.
Допустим у нас имеется теория натуральных чисел, и мы хотим определить теорию целых чисел.
Введём первоначальные понятия: "$x$ - целое число", "$0$", "$-x$" и аксиомы:

1. Если $x$ - натуральное число, то $x$ - целое число
2. Если $x$ - целое число, то $x$ - натуральное число или $x=0$ или существует натуральное число $y$, такое, что $x=-y$

Аксиомы области определения и значений первоначальных понятий:

А1. $0$ - целое число
А2. если $z=-x$ то $x$ - натуральное число и $z$ - целое число.

Далее можно определить непервоначальные понятия суммы и произведения целых чисел через первоначальные понятия суммы и произведения теории натуральных чисел.