Непротиворечива ли арифметика Пеано?

[nikov]

Непротиворечива ли арифметика Пеано? Интересно ваше мнение, доводы в его пользу, и следствия из ее противоречивости/непротиворечивости.

[epros]

nikov писал(а):

Непротиворечива ли арифметика Пеано? Интересно ваше мнение, доводы в его пользу, и следствия из ее противоречивости/непротиворечивости.

Интересно, что тут можно сказать кроме: достоверно неизвестно, но принято считать, что непротиворечива? Или есть уже доказательство непротиворечивости без опоры на предположение непротиворечивости чего-то ещё?

Кстати, было бы интересно уточнить, о каком определении непротиворечивости теории $T$ идёт речь? Я знаю два:
$\forall A \in T ((T \vdash A) \to A)$
и
$\forall A \in T ((T \vdash \neg A) \to \neg (T \vdash A))$

Насколько я понимаю, они несводимы друг к другу.

[epros]

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

Стандартным выходом из ситуации является использование схемы аксиом вместо одной аксиомы. Но дело в том, что для определения схемы аксиом для теории необходимо сначала пронумеровать все её соответствующие предикаты. Допустим, что мы в метатеории пронумеровали одноместные арифметические предикаты, т.е. имеем последовательность:
$P_k(n)$, где $k$ - номер предиката, а $n$ - его аргумент.
Тогда мы можем формализовать схему индукции таким образом:
$P_k(1) \to (\forall n \in \mathbb{N}(P_k(n) \to P_k(n+1)) \to \forall n \in \mathbb{N}(P_k(n)))$
где для каждого значения $k$ порождается своя аксиома.
Этот трюк позволяет обойтись без квантификации арифметических предикатов.

А теперь вопрос: Можно ли быть уверенным в том, что нам удастся пронумеровать действительно все одноместные арифметические предикаты? Ведь если найдётся непронумерованный предикат, это будет означать, что аксиома индукции для него не определена...

[bot]

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

Можно ли быть уверенным в том, что нам удастся пронумеровать действительно все одноместные арифметические предикаты?

А и в самом деле, всех одноместных предикатов континууум, а арифметических - счётно, а почему? А потому что они определяются рекурсивно, то есть фактически нумеруем их используя индукцию ... - круг замкнулся.

[AGu]

epros писал(а):

Можно ли быть уверенным в том, что нам удастся пронумеровать действительно все одноместные арифметические предикаты?

В данном случае возможность нумерации, наверное, означает существование алгоритма, который на входе принимает натуральные числа, по входному числу $k$ возвращает предикат $P_k$, причем $\{P_k : k\in\mathbb N\}$ является множеством всех предикатов.
Тогда, насколько я понимаю, вопрос сводится к возможности нумерации множества всех слов некоторого счетного (и уже пронумерованного) алфавита (учитывая разрешимость множества предикатов во множестве всех слов). Соответствующий алгоритм, очевидно, есть. (Слова "очевидно, есть" здесь употреблены приблизительно на том же уровне строгости, что и слово "алгоритм".)

Или тут подразумевалась какая-то более глубокая и тонкая философия?

[вздымщик Цыпа]

bot в сообщении #154732 писал(а):

А и в самом деле, всех одноместных предикатов континууум,

Откуда континуум? Предикат — конечная последовательность символов из конечного алфавита. Таких последовательностей не более чем счетное количество.

[epros]

AGu писал(а):

В данном случае возможность нумерации, наверное, означает существование алгоритма, который на входе принимает натуральные числа, по входному числу $k$ возвращает предикат $P_k$, причем $\{P_k : k\in\mathbb N\}$ является множеством всех предикатов.

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

AGu писал(а):

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

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

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

AGu писал(а):

Или тут подразумевалась какая-то более глубокая и тонкая философия?

"Философия" заключается в том, что либо аналитическая грамматика, распознающая в строке формулу одноместного арифметического предиката, либо процедура проверки того, что ни один из таких предикатов "не пропущен", могут не иметь точек останова.

Добавлено спустя 32 минуты 1 секунду:

вздымщик Цыпа писал(а):

bot в сообщении #154732 писал(а):

А и в самом деле, всех одноместных предикатов континууум,

Откуда континуум? Предикат — конечная последовательность символов из конечного алфавита. Таких последовательностей не более чем счетное количество.

Наверное, имеется в виду вот что. Рассмотрим одноместный предикат следующего вида:
$P_a(x) \leftrightarrow a=x$, где $a$ - произвольное действительное число.
Очевидно, что таких предикатов континуум. Попробуйте опровергнуть.

[AGu]

epros писал(а):

"Философия" заключается в том, что либо аналитическая грамматика, распознающая в строке формулу одноместного арифметического предиката, либо процедура проверки того, что ни один из таких предикатов "не пропущен", могут не иметь точек останова.

Будучи языком контекстно свободной грамматики, множество всех предикатов разрешимо во множестве всех слов, т.е. существует алгоритм, принимающий на входе слова и возвращающий 1 для предикатов и 0 для остальных слов. Встроив этот алгоритм в алгоритм нумерации слов, легко построить алгоритм нумерации предикатов. (Например, приняв на входе $k$, тупо перебираем подряд слова и возвращаем $k$-е слово, являющееся предикатом.)

Теперь о проверке того, что ни один предикат не пропущен... Что в данном случае понимается под алгоритмом проверки того, что два каких-то множества слов совпадают? Да и зачем вообще как-то проверять, что $\{P_k : k\in\mathbb N\}$ равно множеству всех предикатов, если это можно доказать?

[вздымщик Цыпа]

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

Наверное, имеется в виду вот что. Рассмотрим одноместный предикат следующего вида:
$P_a(x) \leftrightarrow a=x$, где $a$ - произвольное действительное число.
Очевидно, что таких предикатов континуум. Попробуйте опровергнуть. Smile

Эт врядли. Такие предикаты в схеме индукции не участвуют. Скорее другое: если рассматривать предикат как произвольную функцию $\mathbb{N}\to\{0,1\}$, то таких функций действительно континуум. Другое дело, что большинство из них не записываются конечными формулами и потому в теории отсутствуют.

[bot]

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

AGu в сообщении #154733 писал(а):

Тогда, насколько я понимаю, вопрос сводится к возможности нумерации множества всех слов некоторого счетного (и уже пронумерованного) алфавита

Вот. Берём и нумеруем все слова в счётном алфавите, в том числе и абракадабру. Например так. Берём расширяющийся алфавит $A_n=\{a_1, \dots, a_n\}$ и нумеруем последовательно слова длины 1 в алфавите $A_1$, затем слова длины 2 в алфавите $A_2$ и т.д., смиряясь с неизбежными повторами, но ни один из арифметических предикатов пропущен не будет.

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

Неочевидна, как это ни странно, возможность нумерации подмножества слов, являющихся одноместными арифметическими предикатами.

А оно нам надо? Главное не пропустить, а повторы слов с разными номерами - пусть будут.

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

"Философия" заключается в том, что либо аналитическая грамматика, распознающая в строке формулу одноместного арифметического предиката, либо процедура проверки того, что ни один из таких предикатов "не пропущен", могут не иметь точек останова.

Первая проблема решена, остаётся проблема остановки. А это тоже не проблема, так как для конечного слова это задача конечного перебора

AGu в сообщении #154768 писал(а):

Будучи языком контекстно свободной грамматики, множество всех предикатов разрешимо во множестве всех слов, т.е. существует алгоритм, принимающий на входе слова и возвращающий 1 для предикатов (bot: арифметических) и 0 для остальных слов. Встроив этот алгоритм в алгоритм нумерации слов, легко построить алгоритм нумерации предикатов.

Если очень хочется, то сюда же или ещё раньше можно встроить алгоритм устранения повторов.

вздымщик Цыпа в сообщении #154736 писал(а):

bot в сообщении #154732 писал(а):
А и в самом деле, всех одноместных предикатов континууум,
Откуда континуум? Предикат — конечная последовательность символов из конечного алфавита. Таких последовательностей не более чем счетное количество.

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

вздымщик Цыпа в сообщении #154769 писал(а):

Эт врядли.

Так что угадали.

[epros]

AGu писал(а):

Теперь о проверке того, что ни один предикат не пропущен... Что в данном случае понимается под алгоритмом проверки того, что два каких-то множества слов совпадают? Да и зачем вообще как-то проверять, что $\{P_k : k\in\mathbb N\}$ равно множеству всех предикатов, если это можно доказать?

Ну, я и имел в виду, что нужно доказать. Только не в терминах теории множеств, ибо она уже есть расширение арифметики.

AGu писал(а):

приняв на входе $k$, тупо перебираем подряд слова и возвращаем $k$-е слово, являющееся предикатом

ОК, а наоборот? Чтобы, приняв на входе строку, получить на выходе либо номер аксиомы индукции, либо признак, что эта строка - не формула одноместного предиката?

Впрочем, не отвечайте, понятно, что можно

AGu писал(а):

Главное не пропустить, а повторы слов с разными номерами - пусть будут.

Повторы - фиг с ними. И пропустить при полном переборе слов мы ничего не пропустим. Главное - не воткнуть в схему аксиому индукции, построенную для выражения, которое не является одноместным арифметическим предикатом.

[AGu]

epros писал(а):

AGu писал(а):

Да и зачем вообще как-то проверять, что $\{P_k : k\in\mathbb N\}$ равно множеству всех предикатов, если это можно доказать?

Ну, я и имел в виду, что нужно доказать. Только не в терминах теории множеств, ибо она уже есть расширение арифметики.

Совпадение двух множеств (слов) -- это, как мне всегда казалось, утверждение в рамках теории множеств. В какой же еще теории его доказывать, как не в (мета)теории множеств? Если же Вы это намерены запретить, то предложите другую адекватную теорию и сформулируйте в ней гипотезу, подлежащую доказательству, а мы уж тогда поразмышляем, можно ли ее доказать.

[маткиб]

Непротиворечива.
Доводы в пользу: конструктивизм - зло.
Следствия: можно ей пользоваться

Интереснее вопрос о непротиворечивости ZFC - недоказуемый в ZFC факт (если правда), и интуитивно далеко не очевидный (если пытаться в этом разобраться).

[epros]

AGu писал(а):

epros писал(а):

AGu писал(а):

Да и зачем вообще как-то проверять, что $\{P_k : k\in\mathbb N\}$ равно множеству всех предикатов, если это можно доказать?

Ну, я и имел в виду, что нужно доказать. Только не в терминах теории множеств, ибо она уже есть расширение арифметики.

Совпадение двух множеств (слов) -- это, как мне всегда казалось, утверждение в рамках теории множеств. В какой же еще теории его доказывать, как не в (мета)теории множеств? Если же Вы это намерены запретить, то предложите другую адекватную теорию и сформулируйте в ней гипотезу, подлежащую доказательству, а мы уж тогда поразмышляем, можно ли ее доказать.

Это Вы привели формулировку в терминах множеств. А я задал вопрос о существовании предиката, для которого не определена аксиома индукции. Ответ "нет" на него подразумевает сведение к противоречию предположения о существовании и не требует привлечения понятия "множество", т.е. каких бы то ни было теоретико-множественных аксиом.

Ладно, с этим всё понятно, гарантировать определение аксиомы индукции для каждого одноместного арифметического предиката теории возможно. Но осталась ещё одна вещь, которая меня беспокоит: Мы определяем аксиоматику арифметики в метатеории, которая сама использует арифметику. Это не добавляет арифметике убедительности. Получается, что формализуя понятие натурального числа, мы опираемся на факт существования последовательности аксиом индукции, т.е. опять же на понятие натурального числа (ибо последовательность определяется с использованием понятия натурального числа).

маткиб писал(а):

Непротиворечива.
Доводы в пользу: конструктивизм - зло.

Интересно, что Вам в нём так не понравилось?

маткиб писал(а):

Следствия: можно ей пользоваться

И какое отношение конструктивизм имеет к непротиворечивости арифметики? Мне бы, конечно, было более интересно конструктивное доказательство непротиворечивости арифметики, но и его отсутствие не означает запрет на использование арифметики.

маткиб писал(а):

Интереснее вопрос о непротиворечивости ZFC - недоказуемый в ZFC факт (если правда), и интуитивно далеко не очевидный (если пытаться в этом разобраться).

С моей точки зрения ZFC - это всего лишь один из возможных вариантов тупого расширения понятия "множество" на бесконечности разного рода. Почему остановились именно на этом, а не пошли дальше, понять невозможно. Известно, что понятие "множество" можно расширить до понятия "класса" (множество множеств противоречиво, но можно определить класс множеств). Точно так же можно расширить понятие класса до понятия "суперкласса", или далее - до понятия "суперкласса уровня N". А обобщив понятия суперклассов всех возможных уровней, можно ввести какое-нибудь понятие мега-класса... В общем, конца здесь не видно и зачем всё это нужно - тоже непонятно.

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

В схеме индукции не предикаты, а формулы с одной свободной переменной.

Друзья! Вы всегда так бурно развиваете эти темы и такие объёмные сообщения лепите! А я вот всегда вроде и хочу сказать своё веское слово, а потом хоп --- там уже несколько страниц написано и читать их лень. Ну а вдруг там уже написали то, что ты собираешься сказать?

Странно, откуда такое неравнодушие к математической логике? Причём даже не к самой матлогике, а к философской мути, поднятой вокруг неё.