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

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

Утверждение о здравости аксиом Пеано сильнее, чем утверждение о непротиворечивости. Здравость можно формализовать в виде: $Prov(\#A)\rightarrow A$, где A - любое арифметическое утверждение.
Из утверждения о здравости аксиом Пеано сразу следует истинность утверждения Гёделя $G$: $Prov(\#G)\Rightarrow G\Longleftrightarrow \neg Prov(\#G)$.

-- Вс июн 10, 2012 15:33:16 --

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

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

Когда я работаю с натуральным рядом 1, 2, 3, ... я вовсе не думаю о модели аксиом Пеано на языке логики первого порядка.

Тогда разговор о "стандартной" или "нестандартной" модели становится бессмысленным.

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

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

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

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

Первый раз в жизни вижу термин "здравость". Не могли бы Вы пояснить, что он означает?

[Someone]

Тяжёлый случай. Я, пожалуй, удалюсь.

[Xaositect]

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

Здравость можно формализовать в виде: $Prov(\#A)\rightarrow A$, где A - любое арифметическое утверждение.

Почитайте про теорему Лёба.

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

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

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

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

Первый раз в жизни вижу термин "здравость". Не могли бы Вы пояснить, что он означает?

Система аксиом арифметики называется здравой, если все доказуемые в ней арифметические утверждения истинны.

[VPopov]

(Оффтоп)

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

Тяжёлый случай. Я, пожалуй, удалюсь

А меня ... удалили

.

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

Итак, истинность арифметических утверждений объективна и не зависит от системы аксиом. Можно объяснить это тем, что арифметические утверждения либо проверяемы, либо представимы множеством проверяемых утверждений.
Если это так, то истинность части утверждений теории множеств тоже объективна и не зависит от системы аксиом. Среди них находятся утверждения, которые либо проверяемы, либо представимы множеством проверяемых утверждений.

[epros]

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

Примем за аксиому утверждение о непротиворечивости аксиом Пеано

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

Итак, истинность арифметических утверждений объективна и не зависит от системы аксиом. Можно объяснить это тем, что арифметические утверждения либо проверяемы, либо представимы множеством проверяемых утверждений.

1) В арифметике Пеано нет и не может быть аксиомы о непротиворечивости её аксиом (см. теорему Гёделя о неполноте).
2) Теория, которая получается добавлением к арифметике Пеано аксиомы о непротиворечивости аксиом Пеано, отличается от арифметики Пеано (в частности, в этой теории можно доказать множество вещей, в арифметике Пеано недоказуемых).
3) По этой причине утверждение о том, что "истинность арифметических утверждений объективна и не зависит от системы аксиом" - неверно.

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

Цитата:

утверждение о том, что "истинность арифметических утверждений объективна и не зависит от системы аксиом" - неверно.

Система аксиом Пеано либо противоречива, либо нет, и только одна из этих возможностей имеет место. Если утверждение о её непротиворечивости доказуемо в одной системе аксиом и опровержимо в другой, то какая-то из этих двух систем аксиом ошибочна.
Если, в какой-то системе аксиом, можно опровергнуть, что уравнение "$2x=5$" не имеет решений в натуральных числах, то эта система аксиом ошибочна.
Вы с этим несогласны?

[epros]

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

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

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

Так что из этих рассуждений никак не следует что "истинность арифметических утверждений объективна и не зависит от системы аксиом".

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

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

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

Так что из этих рассуждений никак не следует что "истинность арифметических утверждений объективна и не зависит от системы аксиом".

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

-- Вт июл 03, 2012 12:00:43 --

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

[epros]

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

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

Нет, это значит, что истинность не следует из доказуемости в какой бы то ни было системе аксиом. Отсюда возникает вопрос: Что Вы понимаете под "истинностью"? Вы ведь, вроде, полагаете, что она существует (раз утверждаете, что она "объективна")?

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

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

Для того чтобы из доказуемости утверждения о непротиворечивости системы аксиом Пеано следовала его истинность, система аксиом, в которой оно доказуемо должно удовлетворять двум условиям: во-первых, она должна быть непротиворечива

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

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

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

Что такое "проверяемое равенство"? Типичное истинное недоказуемое арифметическое утверждение обычно звучит примерно так: "Не существует такого натурального числа, которое удовлетворяет ...", - и далее вместо троеточия идёт некое условие. Вы будете перебирать ВСЕ натуральные числа, чтобы проверить это утверждение?

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

Цитата:

Что такое "проверяемое равенство"?

Я имел ввиду равенства, содержащие числа и знаки сложения, умножения и равенства (например $2\cdot 2=4$).

-- Вт июл 03, 2012 13:05:32 --

Цитата:

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

Я согласен, если писать "истинным" и "истинность" в кавычках. Потому что, эта "истинность" не означает истинности, а означает доказуемость.

-- Вт июл 03, 2012 13:13:50 --

Цитата:

Отсюда возникает вопрос: Что Вы понимаете под "истинностью"? Вы ведь, вроде, полагаете, что она существует (раз утверждаете, что она "объективна")?

Цитата:

Вы будете перебирать ВСЕ натуральные числа, чтобы проверить это утверждение?

Я не вижу в бесконечном переборе невозможное. Почему невозможен прибор, который его осуществляет? Любой непрерывный процесс проходит бесконечное множество состояний.

[epros]

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

Я имел ввиду равенства, содержащие числа и знаки сложения, умножения и равенства (например $2\cdot 2 = 4$).

Т.е. без переменных и кванторов? Насколько я понимаю, любое такое высказывание либо доказуемо, либо опровержимо в арифметике Пеано.

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

Потому что, эта "истинность" не означает истинности, а означает доказуемость.

А какая "истинность" означает истинность? Например, теорема Гудстейна истинна? В арифметике первого порядка она недоказуема (вот Вам зависимость от аксиоматики).

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

Я не вижу в бесконечном переборе невозможное. Почему невозможен прибор, который его осуществляет? Любой непрерывный процесс проходит бесконечное множество состояний.

Я не знаю, через что там на самом деле проходит непрерывный процесс (ибо - "непрерывный процесс" - это математическавя абстракция и я не знаю способа проверить, является ли процесс действительно непрерывным). Так что я не знаю ни одного примера устройства, которое бы действительно проверяло бесконечное количество условий. Зато я знаю множество примеров того, что некоторые утверждения для натуральных чисел пока не удалось проверить. Например, утверждение: "Существует чётное нечётное совершенное число", - пока что никак не "проверено". Так "проверяемо" оно или нет?

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

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

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

Я имел ввиду равенства, содержащие числа и знаки сложения, умножения и равенства (например $2\cdot 2 = 4$).

Т.е. без переменных и кванторов? Насколько я понимаю, любое такое высказывание либо доказуемо, либо опровержимо в арифметике Пеано.

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

Цитата:

А какая "истинность" означает истинность? Например, теорема Гудстейна истинна? В арифметике первого порядка она недоказуема (вот Вам зависимость от аксиоматики).

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

Цитата:

Например, утверждение: "Существует чётное совершенное число", - пока что никак не "проверено". Так "проверяемо" оно или нет?

Пока мы не умеем проверять такие утверждения. Мы не умеем проверять даже утверждение о несуществовании натуральных решений уравнения $2x=5$.
Но это не означает, что эти утверждения принципиально непроверяемы никаким образом.