Теорема Геделя о неполноте

[Anton_Peplov]

Назовем алфавитом языка арифметики алфавит, состоящий из:
1) десятичных цифр для записи натуральных чисел
2) символа $x$ и нижнего индекса для записи переменных (различные переменные, входящие в одно и то же выражение, можно обозначать $x_1$, $x_2$, ...).
3) знаков арифметических операций $+$, $\times$
4) скобок и знака равенства $=$
5) знаков логических операций "и", "или", "не", кванторов существования $\exists$ и всеобщности $\forall$.

Конечный упорядоченный набор символов языка арифметики назовем фразой языка арифметики.
Существует класс фраз, называемых суждениями. Его можно определить, определив индуктивно сначала терм, затем формулу, а уж затем - суждение как формулу без свободных параметров, но мне кажется, здесь это излишне. Понятие суждения в языке арифметике вполне совпадает с этим же понятием в логике. Например, $4 = 2 + 2$, $\forall x_1 \exists x_2 x_2 = x_1 + 1$ - суждения. На языке арифметики можно записать как вполне тривиальные суждения ("шесть делится на три"), так и очень нетривиальные (теорема Лагранжа - "всякое натуральное число представимо в виде суммы не более чем четырех квадратов натуральных чисел"), в том числе недоказанные (гипотеза Гольдбаха).

Теорема Геделя о неполноте утверждает:
Не существует алгоритма, который для каждого суждения языка арифметики определяет, истинно оно или ложно.

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

Вопрос:
Существует ли суждение языка арифметики, для которого ни один алгоритм не определяет, истинно оно или ложно?
Конечно, такая формулировка неудачна. Всегда можно взять два алгоритма, один из которых всегда печатает "оно ложно", а другой "оно истинно", и сказать, что уж один-то из этих алгоритмов истинность/ложность утверждения определяет. Я не об этом. Не знаю, как сформулировать корректнее. Приведу пример. Похожая теорема доказывается для алгоритмов: "не существует алгоритма, которых для всякого алгоритма $A$ и всяких входных данных $\alpha$ определял бы, остановится ли этот алгоритм при этих входных данных". Затем строится универсальный алгоритм $U(n, \alpha)$, который для каждой пары $(n, \alpha)$ реализует алгоритм $A_n (\alpha)$, где $n$ - номер алгоритма $A_n$ в эффективной нумерации всех алгоритмов. Получается, что для универсального алгоритма $U(n, \alpha)$ не существует алгоритма, который для любого $(n, \alpha)$ определял бы, остановится ли $U(n, \alpha)$ или нет.
Существует ли в языке арифметики "универсальное суждение", на проблеме истинности которого любой алгоритм споткнется так же, как на проблеме остановки универсального алгоритма?
Тут, конечно, есть разница. Универсальный алгоритм может принимать различные (да фактически любые) входные данные, и неразрешимость проблемы его остановки формулируется именно как "не существует алгоритма, который для любого $(n, \alpha)$ определял бы, остановится ли $U(n, \alpha)$ или нет". Суждение же свободных параметров не содержит. И все-таки мне кажется, что какое-то такое "алгоритмически недоказуемое и неопровержимое суждение" должно существовать.

Или мне кажется?

[Xaositect]

Ну, если искать что-то аналогичное универсальной машине, то существует формула $U(x)$ с одной свободной переменной, для которой не существует алгоритма, который по натуральному числу $n$ определяет, истинно ли суждение $U(n)$.

[Someone]

Что-то тут не то. Anton_Peplov, Вы точно знаете, что в теореме Гёделя речь идёт об истинности? Ничего, что истинность суждения зависит от модели? Ведь в вашей постановки никакая модель не предполагается.

[Anton_Peplov]

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

Вы точно знаете, что а теореме Гёделя речь идёт об истинности?

Существует синтаксическая и семантическая формулировка теоремы Геделя о неполноте. Я привел семантическую. В синтаксической понятие истинности не используется, но я с ней не знаком.

Доказательство данной формулировки теоремы Геделя базируется на понятии арифметического множества. Множество натуральных чисел $M$ называется арифметическим, если существует такая формула языка арифметики $U(x)$ с одной свободной переменной $x$, что для всякого $n \in M$ суждение $U(n)$ истинно.
Доказывается, что:
а) всякое перечислимое множество арифметично (доказательство долгое и сложное)
б) дополнение арифметического множества до всего натурального ряда арифметично

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

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

[Someone]

И всё-таки: не спутали ли Вы невыводимость с истинностью?

Anton_Peplov в сообщении #950085 писал(а):

Не знаю, как сформулировать корректнее.

А если посмотреть в учебнике?

Anton_Peplov в сообщении #950085 писал(а):

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

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

Но если речь идёт о теоремах Гёделя, то там рассматриваются вполне "конкретные" высказывания.

[Anton_Peplov]

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

А если посмотреть в учебнике?

Порекомендуйте учебник.

[Someone]

С. К. Клини. Математическая логика. "Мир", Москва, 1973.
П. Дж. Коэн. Теория множеств и континуум-гипотеза. "Мир", Москва, 1969. (Это не учебник.)

[Sycamore]

Присоединение Гёделева недоказуемого предложения "я недоказуемо" к аксиомам арифметики (Пеано) естественно, поскольку оно представляется "очевидно верным", хоть и вычурным и не очень интересным арифметическим фактом; на неформальном, интуитивном уровне оно будет "доказуемым" по построению, хоть и построено было (Гёделем) с целью остаться именно формально недоказуемым.

А вот в чём будут значение/смысл присоединения к арифметике отрицания (поскольку в равной степени невыводимого) Гёделева предложения, то бишь присоединения "заведомо неверного" арифметического предложения наподобие, скажем, 2+2=5? Какая будет польза от полученной нестандартной, насколько могу судить, модели?

[warlock66613]

Anton_Peplov в сообщении #951165 писал(а):

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

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

(Я же всё правильно сказал, да?)

[Dan B-Yallay]

warlock66613 в сообщении #1365159 писал(а):

(Я же всё правильно сказал, да?)

(Верно, только поздновато, года на 4.)

[Anton_Peplov]

Dan B-Yallay в сообщении #1365177 писал(а):

(Верно, только поздновато, года на 4.)

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

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

[Sycamore]

Sycamore в сообщении #1365158 писал(а):

Присоединение Гёделева недоказуемого предложения "я недоказуемо" к аксиомам арифметики (Пеано) естественно, поскольку оно представляется "очевидно верным", хоть и вычурным и не очень интересным арифметическим фактом; на неформальном, интуитивном уровне оно будет "доказуемым" по построению, хоть и построено было (Гёделем) с целью остаться именно формально недоказуемым.

А вот в чём будут значение/смысл присоединения к арифметике отрицания (поскольку в равной степени невыводимого) Гёделева предложения, то бишь присоединения "заведомо неверного" арифметического предложения наподобие, скажем, 2+2=5? Какая будет польза от полученной нестандартной, насколько могу судить, модели?

Сообщение сверху скорее неудачно отражает следующий вопрос о напрашивающемся различии между как-бы двумя классами аксиоматически/формально недоказуемых предложений. С одной стороны, это класс оригинальных Гёделевых предложений "я недоказуемо", арифметических теорем Рамсея (результат Пэриса - Харрингтона, https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BD%D0%B0) и Гудстейна, диофантова примера неполноты вслед за Матиясевичем (https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BC%D0%B0) и других подобных, видимо "истинных/доказанных" на экспертном, хоть и неформальном, уровне предложений.

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

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

[warlock66613]

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

[Sycamore]

Не встречал такой "непустой" редакции аксиомы выбора...)

Любое расширение (вкл. ZFC) арифметики Пеано будет неполным, потому исчерпать нашего первого класса не удаётся: в ZFC наверняка найдутся Гёделево "я недоказуемо" и диофантово уравнение с недоказуемым отсутствием решений, про Рамсея с Гудстейном не уверен.

[mihaild]

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

"Доказанные на экспертном уровне арифметические утверждения" - это, скорее всего, именно доказанные в ZF (даже аксиома выбора не нужна - арифметические утверждения, доказуемые в ZFC, доказуемы и в ZF).