Небольшой наезд на 1-ую теорему Гёделя о неполноте

[epros]

Может быть, конечно, я чего-то не понимаю, но мне кое-какие моменты доказательства кажутся довольно спорными. Как я понял, основная часть доказательства сводится к тому, чтобы построить утверждение $G$, декларирующее собственную недоказуемость: $G : \sim Provable(G)$. Хотя "построить" - это слишком сильно сказано: на самом деле речь идёт о некоем доказательстве существования такого утверждения. Поскольку теория предполагается непротиворечивой, ложное утверждение в ней не может быть доказуемо, т.е. $G$ не может быть ложным, ибо тогда оно было бы автоматически доказуемым. Значит оно истинно, но при этом недоказуемо, т.е. теория неполна.

Доказательство существования $G$ основано на том факте, что все логические формулы теории, содержащие одну свободную переменную (т.е. одноместные предикаты), могут быть пронумерованы. Наверное, здесь следует уточнить, что под "формулами теории" понимаются только конечные (по числу использованных в них символов) строки. Т.е. "бесконечные" формулы как таковые не рассматриваются (это и понятно, ибо работать с ними невозможно). Или нет? Собственно, скорее всего именно к ответу на этот вопрос и сводится проблема. Во всяком случае, я исхожу из первого. Почему? Потому что предположение о том, что все формулы (включая бесконечные), "имеющие смысл" одноместного предиката, можно пронумеровать, противоречиво. Это нетрудно продемонстрировать следующим образом:

1. Предположим, что все одноместные предикаты теории пронумерованы: $F_1(x), F_2(x), ...$.
2. Определим одноместный предикат $H(n) : \sim F_n(n)$.
3. Согласно предположению существует такой номер $m$, что $H(n) = F_m(n)$.
4. Однако $H(m) = \sim F_m(m)$ и в то же время $H(m) = F_m(m)$. Противоречие.

Выход отсюда я вижу один: речь идёт только о конечных формулах. Они, очевидно, могут быть пронумерованы (в рамках метатеории). Но $H(n) : \sim F_n(n)$ не является конечной формулой, а поэтому предложение 3 вышеприведённого доказательства к нему не относится.

Теперь вернёмся к доказательству теоремы Гёделя. Насколько я понимаю, схема доказательства существования утверждения $G$ примерно такова:

1. Определим формулу $G(n)$ как $G(n) : \sim Provable(F_n(n))$. (Здесь $Provable(...)$ - это утверждение о доказуемости утверждения, приведённого в аргументе. Само по себе существование такого предиката в рамках рассматриваемой теории вызывает у меня некие сомнения, но сейчас речь не об этом.)
2. Согласно предположению о пронумерованности всех формул теории существует такой номер $m$, что $G(n) = F_m(n)$.
3. Определим утверждение $G$ как $G : G(m)$.
4. Видим, что с одной стороны $G = F_m(m)$, а с другой стороны - $G = \sim Provable(F_m(m))$, т.е. $G$ утверждает собственную недоказуемость.

Вопрос состоит в том, откуда взято, что $G(n)$ является конечной формулой теории, т.е. что к ней можно применить предложение 2 приведённого выше доказательства?

[berezuev]

Мало того, у меня получается что кроме бесконечных математических формул еще должны быть нематематичесие понятия:

viewtopic.php?p=77810#77810

Причем если Теорема Геделя верна (Предположим), то попытавшись применить любое описание при получении модели сознания получаем что в реальности должны находиться ненаблюдаемые объекты, а существование ненаблюдаемых объектов (из существования ...) следует существования таких объектов, которые нельзя описать математически. Вот.

PAV:

[PAV]

PAV:

berezuev
Строгое замечание за оффтопик. Ваша тема не имеет никакого отношения к конкретному вопросу автора. Нечего заниматься саморекламой.

[berezuev]

Прикалываешся?

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

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

Если связь по парадоксу лжеца не очевидна, то тогда модераторы и должны отвечать на все вопросы.

Добавлено спустя 19 минут 26 секунд:

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

Как мне надоели эти модераторы которые думают что все знают!

PAV:

[PAV]

PAV:

berezuev
Строгое замечание за пререкания с модератором в тематическом разделе.

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

dm:

berezuev
2 недели

[epros]

berezuev писал(а):

Выразить точно математически нематематическую формулировку ...

berezuev, я говорил только о математических формулировках, использованных в доказательстве теоремы Гёделя. Если я их понял/изложил неправильно, - поправьте меня. А "физический смысл" теоремы меня сейчас не интересует, меня интересует математическая корректность доказательства.

[epros]

Хм. Тема не вызвала содержательных откликов. Надеюсь, не из-за того, что автор спросил такую глупость, на которую и отвечать-то никому неохота.

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

Итак, суть вопроса состояла в том, откуда взято, что утверждение о доказуемости можно записать формулой самой теории (т.е. арифметическим предикатом). Если бы это было так, т.е. утверждение о доказуемости формулы $F_n(x)$ при заданном $x$ можно было записать арифметическим предикатом, то соответствующей подстановкой значений $n$ и $x$ можно было бы построить утверждение, декларирующее собственную недоказуемость.

Как я выяснил, этому посвящена существенная часть Гёделевского доказательства. В нём вводится специальная схема нумерации всех символов, выражений и доказательств теории. Затем показывается, что утверждения типа: "$n$ является Гёделевым номером символа" или "$n$ является Гёделевым номером строки символов" равносильны арифметическим предикатам. Я с этим соглашаюсь. Я также убедился, что утверждение: "$n$ - Гёделев номер выражения, следующего по правилу modus ponens из выражений с Гёделевыми номерами $k$ и $m$", также равносильно некоторому арифметическому предикату.

Это наводит на мысли о том, что все утверждения о выводимости по правилам теории можно записать равносильными им арифметическими предикатами. Однако чтобы конечная последовательность выражений могла считаться доказательством, она должна обладать следующим свойством:
Каждая строка последовательности должна получаться из предыдущих строк по правилу вывода теории ИЛИ являться аксиомой.

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

Я утверждаю, что утверждение: "$n$ - Гёделев номер предиката теории", не может быть выражено равносильным ему арифметическим предикатом. На то есть тривиальное доказательство (на примере одноместных предикатов):
1. Предположим, что утверждение "$n$ - Гёделев номер одноместного предиката теории" выражено равносильным ему арифметическим предикатом.
2. Тогда арифметическим предикатом является и отрицание этого утверждения: "$n$ - не Гёделев номер одноместного предиката теории".
3. В силу того, что все арифметические предикаты пронумерованы (вместе со всеми выражениями теории), существует такое натуральное $m$, которое является Гёделевым номером арифметического выражения, равносильного утверждению из п.2 .
4. Подставив этот номер $m$ вместо $n$ в утверждение п.2, получаем высказывание из классического парадокса лжеца, которое не может быть ни истинным, ни ложным. Противоречие.

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

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

[epros]

Разобрался, возражение (предыдущий пост) снимается. Ошибка состояла в формулировке утверждения, которое не может быть выражено арифметическим предикатом. Вместо "$n$ - Гёделев номер предиката теории", следует записать: "Для предиката с номером $n$ есть значения аргумента, при которых он истинен" (упоминание значений истинности существенно). Вот для такого утверждения нет предиката теории, т.е. мы можем утверждать, что в теории, содержащей арифметику, нет предиката разрешимости её предикатов. Собственно, это соответствует теореме Гёделя...

Очередной оффтопик berezuev перенесен сюда. (dm)