Вопрос по теореме Геделя

[tac14]

Послушал популярную лекцию Сосинский А. Б. на данную тему https://www.youtube.com/watch?v=vdzzTWQNbX4

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

1. Правильно ли я понимаю, что совершенно не каждая формальная система подчиняется теореме Геделя ?
2. Как пример, системы которая подчиняется теореме Геделя приводиться компьютер (скажем так видимо в выражении машины поста, например). Какие именно свойства такой формальной системы позволяют говорить о том, что теорема Геделя справедлива (а именно, что в системе существует некое утверждение которое невозможно ни доказать, ни опровергнуть) ?

3. Интуитивно это происходит когда отрицается некоторое утверждение, которое нечто говорит о себе же, но через другой набор доказательств. Встает вопрос такого рода рекурсия обязательна для выполнения теоремы Геделя, или это только частный случай, через которое делается док-во.

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

5. Не следует ли, как основной прикладной вывод из этого, что формальные системы которые подчиняются теореме Геделя - построенными с нарушением логики? Точнее то, что мы понимаем под логикой в данном случае ею не является в смысле правильности мышления. (исходя из определения того, что "логика есть форма правильного мышления"). То есть найдено благодаря тереме Геделя, такое условие для логики, которое не столь очевидно для интуиции, но такое что является необходимым для построения логических заключений, т.е. накладывает на формальные системы определенные ограничения.

[iifat]

Слушать видеолекции — увольте, так что попробую ответить исключительно на ваши вопросы, безотносительно к ней.

tac14 в сообщении #1036835 писал(а):

1. Правильно ли я понимаю, что совершенно не каждая формальная система подчиняется теореме Геделя?

Не каждая, конечно, а только удовлетворяющая условиям теоремы Гёделя. «Совершенно» тут не совсем уместно — не думаю, что таких, не удовлетворяющих теореме формальных систем так уж много.

tac14 в сообщении #1036835 писал(а):

Какие именно свойства такой формальной системы позволяют говорить о том, что теорема Геделя справедлива

В точности теорему не помню, но приблизительно — любая система, включающая арифметику натуральных чисел.

tac14 в сообщении #1036835 писал(а):

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

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

[kp9r4d]

tac14 в сообщении #1036835 писал(а):

3. Интуитивно это происходит когда отрицается некоторое утверждение, которое нечто говорит о себе же, но через другой набор доказательств. Встает вопрос такого рода рекурсия обязательна для выполнения теоремы Геделя, или это только частный случай, через которое делается док-во.

По моему мироощущению - нет. В каждой более-менее содержательной теории нашли естественные утверждения, которые являются недоказуемыми и неопровержимыми и не являют собой арифметизацию парадоксов (например, существование сильно недостижимых кардиналов в $ZFC$ и принцип Парриса-Харингтона в $I\Sigma_1$). В теории Рамсея вообще каждое второе утверждение недоказуемо.

[epros]

1. Да. Теоремы Гёделя о неполноте про достаточно содержательные теории. Есть примеры недостаточно содержательных теорий, которые полны. Например арифметика Пресбургера (арифметика натуральных чисел со сложением, но без умножения) -- полна.

2. Полнота по Тьюрингу. Если язык (программирования в том числе) тьюринг-полный, то на нём выразима любая вычислимая функция. Вычислимость функции понимается как возможность реализовать её на машине Тьюринга (или на машине Поста, или нормальным алгоритмом Маркова, или нетипизированным лямбда-исчислением и т.д., все эти определения эквивалентны).

3. Нет, "утверждение, которое говорит нечто о себе" использовал Гёдель в своём доказательстве, но недоказуемые и неопровержимые утверждения могут строиться и иначе.

4. Теорема Гудстейна -- пример утверждения, недоказуемого и неопровержимого в арифметике Пеано первого порядка. Гипотеза континуума -- пример утверждения, недоказуемого и неопровержимого в теории множеств Цемерло-Френкеля.

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

[Апис]

Цитата:

Результат нов, если он установлен впервые. По существу, а не по форме. При этом он должен быть строго обоснован и доказан. Как правило, именно то, насколько последнее верно, и составляет предмет дискуссии. Если же результат не нов - дискутировать не о чем.

[tac14]

> В точности теорему не помню, но приблизительно — любая система, включающая арифметику натуральных чисел.

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

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

-- Вт июл 14, 2015 22:15:21 --

epros

спасибо, за ответы - они наиболее полные.

Но не могу не заметить:

> Нет, неполнота -- это никакое не "нарушение логики" ...

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

и да упомянутый в лекции парадокс EPR, когда Эйнштейн обвинял квантовую механику в неполноте - думаю он имел введу именно "нарушение логики" как минимум в "объяснительной части" - интерпретации квантовой механики.

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


> 4. Теорема Гудстейна -- пример утверждения, недоказуемого и неопровержимого в арифметике Пеано первого порядка. Гипотеза континуума -- пример утверждения, недоказуемого и неопровержимого в теории множеств Цемерло-Френкеля.

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

[arseniiv]

tac14 в сообщении #1037087 писал(а):

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

Это ерунда какая-то. (Особенно словоупотребление «религиозное утверждение».) В «строгой логике» всё именно что строго, и того, что вы написали, автоматически не получается. Возможно, вам стоит почитать учебник по матлогике, чтобы разобраться в области точнее.

[tac14]

arseniiv в сообщении #1037098 писал(а):

tac14 в сообщении #1037087 писал(а):

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

Это ерунда какая-то. (Особенно словоупотребление «религиозное утверждение».) В «строгой логике» всё именно что строго, и того, что вы написали, автоматически не получается. Возможно, вам стоит почитать учебник по матлогике, чтобы разобраться в области точнее.

(Оффтоп)

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

[arseniiv]

Нет уж, Кант к матлогике никаким боком не относится.

[Lia]

Апис
Замечание за оффтоп. post1036935.html#p1036935

[tac14]

arseniiv в сообщении #1037104 писал(а):

Нет уж, Кант к матлогике никаким боком не относится.

(Оффтоп)

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

-- Вт июл 14, 2015 22:53:54 --

iifat в сообщении #1036873 писал(а):

Не каждая, конечно, а только удовлетворяющая условиям теоремы Гёделя.

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

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

про достаточно содержательные теории

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

[Lia]

tac14
Цитируйте нормально. Кнопки "Цитата" и Вставка" (для выборочного цитирования) к Вашим услугам.

[mihaild]

tac14 в сообщении #1037109 писал(а):

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

Например, "перечислимая теория, содержащая арифметику Пеано".

[epros]

tac14 в сообщении #1037087 писал(а):

Хотя другие ответили, что док-во Геделя не достаточно общее судя по всему, и существуют другие док-ва.

Оно достаточно общее. Но существуют более современные доказательства.

tac14 в сообщении #1037087 писал(а):

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

Вы какие-то странные вещи говорите. Религиозное мышление, как я понимаю, принимает за аксиомы некоторые непроверяемые экспериментом вещи. А то, что принято за аксиому -- уже доказуемо (в один ход).

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

tac14 в сообщении #1037087 писал(а):

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

Увы, я ничего не понял.

tac14 в сообщении #1037101 писал(а):

А значит и другие рассуждения в такой формальной системе могут ставится под сомнение.

С какой это стати из существования неразрешимых вопросов должно следовать, что разрешённые вопросы разрешены неверно?

tac14 в сообщении #1037109 писал(а):

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

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

tac14 в сообщении #1037109 писал(а):

а что "да" - не ответили

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

[Xaositect]

tac14 в сообщении #1037087 писал(а):

> В точности теорему не помню, но приблизительно — любая система, включающая арифметику натуральных чисел.

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

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

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

tac14 в сообщении #1037087 писал(а):

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

Нет, это значит ровно то, что значит - что утверждение нельзя ни доказать, ни опревргнуть в рамках рассматриваемой теории.

tac14 в сообщении #1037087 писал(а):

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

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

tac14 в сообщении #1037101 писал(а):

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

Я не вижу проблемы.
Мы хотим построить систему, которую можно использовать. Какая она должна быть?
Если мы смогли утверждение доказать - оно должно быть истинно.
Если мы смогли утверждение опровергнуть - оно должно быть ложно.
Если мы не можем ни доказать, ни опровергнуть утверждение - значит, это проблема системы, но проблема не фатальная - все доказанные утверждения все равно могут быть истинными, просто есть утверждения, для которых нашей системы не хватает. Это не значит, что доказанные утверждения ставятся под сомнение.
Если мы можем доказать, что какое-то утверждение нельзя ни доказать, ни опровергнуть, то это вообще замечательно, это значит, что мы можем строго говорить об ограничениях нашей системы внутри нее самой.