о теореме геделя
Oct. 26th, 2006 02:25 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif){kind=small}
dennett задал несколько вопросов о знаменитой теореме Геделя о неполноте. Я попытался ответить на один из них - почему в формулировке теоремы Геделя, говорящей - если упростить - о том, что любая формальная теория не может доказать все возможные истины, требуется еще в качестве условия, чтобы эта теория "включала арифметику"? При чем тут арифметика и отчего это важно?
Мой ответ превратился скорее в мини-изложение идеи Геделя образным и нематематическим языком; возможно, он будет еще кому-то полезен, поэтому привожу его здесь, с незначительной правкой.
Обычно у нас есть какая-то логическая теория (с аксиомами и следствиями из них), которая позволяет нам рассуждать о каких-то объектах. Например, о числах, или о звездах, или точках на плоскости, или еще о чем-то. При этом сами наши рассуждения, сами утверждения, которые мы доказываем или опровергаем, не являются предметом рассмотрения той же теории - они являются ее частью, но не предметом рассмотрения. По сравнению с изучаемыми объектами они находятся на мета-уровне.
А что если мы попробуем исхитриться и попытаться рассуждать о рассуждениях в рамках самих же рассуждений, как бы сделав мета-уровень частью обычного уровня? Но как? - просто: замаскировав их под объекты, которые мы изучаем. Ведь в конечном итоге нас интересует не то, из чего "сделаны" наши рассуждения - например, буквы русского алфавита, или интонации во время их высказывания; а их смысл - а их смысл зависит от структурных связей между ними, и от тех объектов, о которых они говорят. Скажем, утверждение A следует из утверждения B, но не следует из утверждения C. Или утверждение A связывает между собой такой-то и такой-то объекты. Это примеры структурных связей, которые нас интересуют больше, чем буквы слов "с-л-е-д-у-е-т" или "у-т-в-е-р-ж-д-е-н-и-е".
Что если мы найдем способ построить наши утверждения из кирпичиков-объектов (например, чисел, или сортов сыра) так, чтобы интересующие нас отношения между ними сохранялись в нашем "переводе" на язык объектов - только назывались по-другому? Может, если утверждение A следует из утверждения B, а мы их оба выразили числами, то это будет то же самое, что сказать, что одно из чисел больше другого (это специально слишком упрощенный пример). Если отношение "больше" между числами будет вести себя, как мы ожидаем от отношения "следует из" между утверждениями, то такой "перевод" будет верным и обоснованным. И это будет означать, что мы "схлопнули" мета-уровень в обычный уровень, перевели утверждения (которые мы раньше формулировали на нестрогом языке букв, звуков, мыслей) в объекты, которые мы умеем изучать с помощью нашей теории.
Теперь мы можем об этих объектах (по сути дела - утверждениях, только после "перевода"), и об отношениях между ними (по сути дела - логических связях, только после "перевода"), что-то доказать, пользуясь нашей теорией, то есть - пользуясь теми же утверждениями на их исходном мета-уровне. И в принципе должно быть ясно, что раз наши утверждения (на мета-уровне) могут теперь говорить "о самих себе" (в "переведенном" варианте, в виде объектов), то у нас может появиться шанс выразить с их помощью парадокс лжеца: "это утверждение ложно", основанный именно на возможности утверждения говорить о самом себе. Но - в нашем случае - этот парадокс будет сформулирован на строгом математическом уровне. Это и приведет нас к теореме Геделя о неполноте.
Есть только одна важная особенность. Поскольку нас интересует сейчас не просто истинность каких-то утверждений, а возможность их доказать в нашей исходной теории, процесс "перевода" мета-уровня в обычный уровень, описанный выше, должен быть не просто "верным" переводом, то есть сохраняющим структурные свойства утверждений при их переносе в объекты. Нам еще необходимо, чтобы наша исходная теория могла доказать, что эти самые структурные свойства сохраняются - могла в рамках своих рассуждений проследить эту связь туда-и-обратно между мета-уровнем и уровнем. Действительно, если мы, скажем, перевели "A логически следует из B" на мета-уровне утверждений в "20 больше, чем 10" на уровне чисел, чем это нам поможет, если наша исходная теория настолько "слаба", настолько тривиальна, что даже такую простую истину, как "20 больше, чем 10" она доказать не может?
Поэтому нам необходимо потребовать от нашей исходной теории определенной мощности, возможности доказать определенные базовые истины, позволяющие подтвердить, в рамках нашей теории, адекватность "перевода" из мета-уровня в уровень. Оказывается, что, если в качестве наших объектов мы берем обычные числа, и переводим из мета-уровня утверждений в уровень чисел, то нам и не надо так уж многого требовать от нашей теории: она всего лишь должна включать несколько простых аксиом, позволяющих, условно говоря, доказать такие истины, как "дважды два - четыре" и "десять меньше, чем двадцать". Несмотря на то, что истины эти очень просты, они все же нетривиальны с логической точки зрения, и следуют из этого небольшого набора простых аксиом; когда говорят, что исходная теория должна "включать арифметику", подразумевают именно наличие этих простых аксиом.
Наконец, важно отметить, что вообще говоря исходная теория необязательно должна включать в себя именно эти аксиомы и ее объектами необязательно должны быть именно числа. Подобно тому, как мы смогли "перевести" разговор о утверждениях мета-уровня в разговор о числах обычного уровня, мы можем перевести его еще раз - в разговор о каких-то других объектах - ну, скажем, треугольниках в геометрии. Важно только, чтобы, опять-таки, мы смогли так "перевести", чтобы сохранить при переводе интересующие нас структурные свойства, и чтобы наша новая теория могла сохранение этих структурных свойств доказать. Тогда математик все равно может сказать, что эта новая теория - например, рассуждающая о треугольниках - все равно "включает в себя арифметику", потому что, хоть числа вообще не являются ее объектами рассуждения, она достаточно мощна для того, чтобы доказать о треугольниках "те же свойства" (после перевода), что нам нужно было доказать между числами - и этого достаточно для того, чтобы аргумент теоремы Геделя сработал и здесь.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2006-10-26 12:33 pm (UTC)no subject
Date: 2006-10-26 12:49 pm (UTC)T.e., чтобы уж окончательно уяснить, грубо говоря - арифметический уровень есть уровень, начиная с которого язык может говорить о себе, т.е. делать свои утверждения своей предметной областью? Так? А почему это именно арифметический уровень - уровень натуральных чисел? Или это уже слишком технический вопрос?
no subject
Date: 2006-10-26 01:00 pm (UTC)Тут важно, как то, что отношения богатые - и поэтому на них можно смоделировать структурные связи утверждений мета-уровня - как и то, что они основаны на очень простых операциях (плюс, умножить) и их свойствах (дважды два-четыре, тысяча меньше миллиона) - поэтому их можно получить в виде следствия нескольких очень простых аксиом.
Почему именно натуральные числа? Перевод утверждений с мета-уровня на предметный уровень требует как минимум неограниченно просторного (бесконечного) предметного уровня, потому что утверждений может быть сколько угодно и они могут быть неограниченно сложными, длинными и запутанными. А натуральные числа являются, по сути дела, самой простой, самой базовой бесконечной структурой. Везде, где у вас есть неограниченное число чего бы то ни было - да хоть тех же треугольников - вы можете начать их пересчитывать, и получите таким образом натуральные числа, которые, получается, уже некоторым образом лежат в основе этого, что вы взяли.
no subject
Date: 2006-10-27 02:27 pm (UTC)Вот, например, если выкинуть из аксиом Пеано четвёртую - что единица ни за чем не следует - будет ли работать эта конструкция? А если будет, то бесконечность, получается, не особо-то и нужна...
no subject
Date: 2006-10-28 04:14 am (UTC)no subject
Date: 2006-10-28 04:20 am (UTC)Re: Reply to your comment...
Date: 2006-10-28 04:36 am (UTC)Re: Reply to your comment...
Date: 2006-10-28 04:39 am (UTC)С натуральными числами как раз всё по-другому. Интересно обсуждать их, как целое.
Re: Reply to your comment...
Date: 2006-10-28 05:01 am (UTC)Re: Reply to your comment...
Date: 2006-10-28 05:05 am (UTC)Re: Reply to your comment...
Date: 2006-10-28 05:22 am (UTC)Re: Reply to your comment...
Date: 2006-10-28 05:24 am (UTC)no subject
Date: 2006-10-26 08:09 pm (UTC)http://mathworld.wolfram.com/PresburgerArithmetic.html
no subject
Date: 2006-10-26 08:32 pm (UTC)no subject
Date: 2006-10-26 08:37 pm (UTC)Попробуйте это утверждение выразить на языке без умножения - не сможете.
no subject
Date: 2006-10-26 08:40 pm (UTC)no subject
Date: 2006-10-26 08:50 pm (UTC)no subject
Date: 2006-10-26 08:55 pm (UTC)По индукции
Date: 2006-10-26 09:03 pm (UTC)M(0,b,0)
M(a,b,c) => M(a+1,b,b+c)
M(a,0,0)
M(a,b,c) => M(a,b+1,a+c)
no subject
Date: 2006-10-26 09:07 pm (UTC)no subject
Date: 2006-10-27 05:13 pm (UTC)Иер.-Обл.
no subject
Date: 2006-10-27 12:15 pm (UTC)no subject
Date: 2006-10-27 12:52 pm (UTC)no subject
Date: 2006-10-27 08:37 pm (UTC)Иер.-Обл.
no subject
Date: 2006-10-28 12:58 pm (UTC)no subject
Date: 2006-10-26 01:44 pm (UTC)no subject
Date: 2006-10-26 02:36 pm (UTC)no subject
Date: 2006-10-26 03:03 pm (UTC)no subject
Date: 2006-10-26 03:20 pm (UTC)no subject
Date: 2006-10-26 06:53 pm (UTC)Всякую математическую теорию можно представить как теорию и практику эксплуатации некоего компьютера. Например, компьютера, который в цикле печатает теоремы одна за другой. С этой точки зрения т. Геделя говорит о том, чего от компьютеров можно ожидать.
Как это известно каждому программеру, начиная с некоторого порога сложности компьютеры обретают "полноту по Тьюрингу": становится возможным на них сэмулировать любой другой компьютер. В частности, оказывается, что компьютер, имплементирующй теорию арифметики Пеано обладает таким свойтвом.
С другой стороны, очевидно, что любая уважаемая полная по Тьюрингу программа должна уметь эмулировать в себе арифмерику.
Стало быть, "включает в себя арифметику" - это просто такое старомодное выражение, означающее "полна по Тьюрингу".
no subject
Date: 2006-10-26 08:45 pm (UTC)no subject
Date: 2006-10-27 12:11 pm (UTC)Можно тексту сопоставить номер ещё и так: буквы алфавиа у нас уже занумерованы, и тексту можно сопоставить номер по такому принципу: 2^{n_1}*3^{n_2}*5^{n_3}*..., идя по простым числам, где n_i -- номер i-й буквы алфавита.
Если текст T доказывает теорему A, и номера этих текстов равны n и m соответственно, то надо найти такое арифметическое выражение P(x,y) -- формулу от двух переменных -- чтобы утверждение P(n,m) было одной из теорем арифметики тогда и только тогда, когда текст T с номером n на самом деле доказывает теорему A с номером m (из какой-то теории).
Проблема здесь в том, чтобы научиться выражать в арифметике как можно больше свойств, а это строится при помощи такого приёма как "кодирование конечных последовательностей".
Спасибо
no subject
Date: 2006-10-27 02:13 pm (UTC)Вот
Вопрос мой был вот в чём. Само по себе рассуждение - это же последовательность утверждений. Вот они сами по себе - включаются в этот объединённый уровень? (Ну, и правила перевода - они тоже, включаются?) Или само по себе рассуждение - оно на мета-мета-уровне происходит?
Тут тогда получается, что если это гёделевское рассуждение - вне нашего Уровня, то мы не можем _исходя_из_него_ определить его истинность.
no subject
Date: 2006-10-27 10:49 pm (UTC)Сами правила перехода просты и не принадлежат, строго говоря, ни к одному из уровней. Они не могут быть ни истинными, ни ложными. Например, если мы зафиксировали способ нумерации текстов, то это ведь не есть какое-то утверждение. Просто мы намерены пользоваться этими правилами как правилами перевода с одного "языка" на другой. Но в принципе это приём того же порядка как решение школьных задач при помощи "иксов", если такое сравнение правомерно.
Не знаю, ответил ли на Ваши вопросы.
no subject
Date: 2006-10-28 12:46 am (UTC)"Сами правила перехода просты и не принадлежат, строго говоря, ни к одному из уровней. Они не могут быть ни истинными, ни ложными."
Мне кажется, это не совсем так. Ведь они участвуют в наших рассуждениях, мы опираемся на них, как на факты. Если угодно, это такие же определения, что и 2=1+1 - мы постулируем это, а потом пользуемся.
Ситуация вот какая. Какие бы объекты мы не взяли, формальная теория, которой мы пользуемся, всегда будет внешней по отношению к множеству этих объектов. Если мы рассматриваем некое множество утверждений, как объектов, и поверх него производим "гёделево рассуждение", то это рассуждение будет внешним по отношению к этому множеству.
А, вот, наверно, как надо сказать - если понятие истинности определено "внутри" этого множества, то автоматическое распространение его "наружу" не выглядит особенно корректным. Особенно когда мы это самое понятие истинности и обсуждаем.
Прошу прощения, трудно формулировать свои мысли. Я ещё подумаю, как лучше сказать.
no subject
Date: 2006-10-28 11:44 am (UTC)Это не обязательно так. Например, если наша теория это теория множеств, то естественно рассматривать и утверждения этой теории как ее объекты (множества).
no subject
Date: 2006-10-28 11:45 am (UTC)no subject
Date: 2006-10-28 12:10 pm (UTC)no subject
Date: 2006-10-28 01:14 am (UTC)В формулировке теоремы вводится понятие алфавита доказательств и множества доказательств. Как я понимаю, доказательство теоремы Гёделя не является элементом этого множества доказательств, поскольку проводится "над ним". Значит, какую бы мы систему не взяли, удовлетворяющую условиям теоремы Гёделя, в её рамках она недоказуема.
непротиворечивость
Date: 2006-10-28 02:14 am (UTC)Попробую ответить на Ваши вопросы. Давайте задумаемся вот над чем. Если Вы привлекаете понятие истинности, то тем самым Ваше основное рассуждение происходит в теории множеств или её фрагменте. Теорема Гёделя -- это вполне конкретное утверждение. Его можно сформулировать и доказать в рамках теории множеств. Она применима к любой достаточно сильной непротиворечивой теории.
Если принять, что теория множеств непротиворечива, то теорема Гёделя окажется применимой и к формальной теории множеств. Тем самым можно считать, что среди рассматриваемых формальных доказательств есть и наше только что проведённое доказательство самой теоремы, а точнее -- её формализованный вариант. Если проанализировать доказательство первой теоремы Гёделя чуть дальше, то этот путь ведёт к доказательству второй теоремы Гёделя -- о том, что утверждение о непротиворечивости теории (достаточно сильной и непротиворечивой) можно сформулировать в рамках такой теории, но нельзя доказать.
Восстановление всех деталей здесь требует некоторых усилий, поэтому я лишь сообщаю, куда ведёт направление Вашей мысли. На самом деле связь между этими теоремами -- вопрос весьма тонкий, и эту тему в своё время хорошо осветил в ЖЖ сам хозяин этого журнала.
Что касается формальной теории множеств (в любой из её классических версий), то её непротиворечивость принимается просто на веру. Коль скоро считается, что любое математическое рассуждение, кем-либо проводимое, формализуемо в теории множеств (здесь есть одна тонкость, но я её опущу), то можно сказать о невозможности доказательства непротиворечивости формальной теории множеств при помощи имеющихся на данный момент традиционных математических средств. Конечно, лишь в том случае, если она непротиворечива на самом деле (в противоречивой теории доказуемо всё).
Мне бы очень хотелось написать отдельный пост по поводу веры в непротиворечивость формальной теории множеств. Там есть много чего обсудить.
no subject
Date: 2006-10-28 01:50 am (UTC)no subject
Date: 2006-10-29 01:47 am (UTC)Это построение является ключевым шагом в доказательстве второй теоремы о неполноте Геделя - той, которая гласит, что любая теория (отвечающая некоторым условиям итд.) не может доказать свою непротиворечивость, если она действительно непротиворечива.
Я ответил на ваш вопрос?
no subject
Date: 2006-10-30 05:25 pm (UTC)Не знаю, насколько это Вам интересно... Я вот о чём думаю. Что в математике неявно считается, что вот есть некоторые факты, которые есть "вечно", и они "вечно" истинны или ложны. И мы лишь открываем эти факты (присваиваем утверждениям значения по некоторым правилам вывода). И в принципе считается, что время, в течение которого происходит это присвоение, не имеет значения.
Здесь же появляется некий объект - алгоритм, который в данную схему не вкладывается. Т.е. здесь явно указано, что мы _получаем_ результат работы алгоритма, а не имеем его с самого начала. При этом алгорим работает тоже не сам по себе, а с неявным использованием "движка" - компьютера, машины, мозга...
Это всё достаточно смутно, но мне кажется, что если порыть, можно здесь много чего вырыть.
Каждый мнит себя правым,но прав лишь Единственный Бог!
Date: 2006-10-27 07:21 pm (UTC)Я любым способом конструирую работающую модель, которая удовлетворяет требованиям заказчика и за которую я получу реальные деньги в другой модели отношений и еще деньги за ее сопровождение, потому что сложную модель придется дорабатывать до тех пор, пока она еще нужна заказчику. Яркий пример - Windows или Linux.
А что вы думаете про Новую парадигму Нового мировоззрения Нового тысячелетия, которая является моделью любой цивилизации, осознанно вставшей на Путь вечного и бесконечного развития (http://alexlotov.livejournal.com/93525.html) (http://alexlotov.livejournal.com/100290.html) (http://alexlotov.livejournal.com/108198.html), (http://alexlotov.livejournal.com/134823.html), (http://alexlotov.livejournal.com/150451.html), ...
Re: Каждый мнит себя правым,но прав лишь Единственный Бо
Date: 2006-10-28 09:59 am (UTC)вот что таблица умножения животворящая делает!
Date: 2006-10-28 11:06 am (UTC)no subject
Date: 2006-10-29 12:21 am (UTC)