Теорема о неполноте
Dec. 19th, 2009 10:18 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
posicВ ленте разные юзеры обсуждают теорему Геделя. Запишу-ка и я свое соображение на эту тему, оно вполне примитивное.
Я изучал это дело к экзамену по логике, и, натурально, тут же все забыл. Но у меня осталась идея, что трудность традиционных изложений связана по большей части с тем, что в них соединены два разных рассуждения -- собственно аргументы на основе self-reference и техника нумерации формул натуральными числами. Если изолировать эту технику в отдельный результат, все может оказаться гораздо более доступным.
Простейший путь к этому -- заменить арифметику Пеано на теорию конечных множеств, то есть представить теорему Геделя в виде следствия двух утверждений "непротиворечивая теория, содержащая теорию конечных множеств, не доказывает свою непротиворечивость" и "теория конечных множеств эквивалентна арифметике Пеано". Нумерация формул конечными множествами не представляет трудности; а для нумерации конечных множеств натуральными числами есть простой трюк, основанный на двоичной экспоненте. Номер конечного множества равен сумме по всем его элементам чисел "два в степени номер этого элемента".
После этого остается изолированное утверждение "формула n = 2m выразима в языке арифметики Пеано", которое можно доказывать отдельно. С другой стороны, при наличии нумерации формул оставшаяся часть аргумента Геделя несложна. Я правильно понимаю?
Я изучал это дело к экзамену по логике, и, натурально, тут же все забыл. Но у меня осталась идея, что трудность традиционных изложений связана по большей части с тем, что в них соединены два разных рассуждения -- собственно аргументы на основе self-reference и техника нумерации формул натуральными числами. Если изолировать эту технику в отдельный результат, все может оказаться гораздо более доступным.
Простейший путь к этому -- заменить арифметику Пеано на теорию конечных множеств, то есть представить теорему Геделя в виде следствия двух утверждений "непротиворечивая теория, содержащая теорию конечных множеств, не доказывает свою непротиворечивость" и "теория конечных множеств эквивалентна арифметике Пеано". Нумерация формул конечными множествами не представляет трудности; а для нумерации конечных множеств натуральными числами есть простой трюк, основанный на двоичной экспоненте. Номер конечного множества равен сумме по всем его элементам чисел "два в степени номер этого элемента".
После этого остается изолированное утверждение "формула n = 2m выразима в языке арифметики Пеано", которое можно доказывать отдельно. С другой стороны, при наличии нумерации формул оставшаяся часть аргумента Геделя несложна. Я правильно понимаю?
