October 26th, 2006

moose, transparent

шесть слов

Wired попросила писателей в жанрах фантастики, фентези и хоррора написать рассказ из шести слов. Результаты в основном не впечатляют, но есть несколько неплохих.

Gown removed carelessly. Head, less so.
- Joss Whedon

Longed for him. Got him. Shit.
- Margaret Atwood

Lie detector eyeglasses perfected: Civilization collapses.
- Richard Powers

God to Earth: “Cry more, noobs!”
- Marc Laidlaw

Epitaph: He shouldn't have fed it.
- Brian Herbert

moose, transparent

о теореме геделя

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

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


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

А что если мы попробуем исхитриться и попытаться рассуждать о рассуждениях в рамках самих же рассуждений, как бы сделав мета-уровень частью обычного уровня? Но как? - просто: замаскировав их под объекты, которые мы изучаем. Ведь в конечном итоге нас интересует не то, из чего "сделаны" наши рассуждения - например, буквы русского алфавита, или интонации во время их высказывания; а их смысл - а их смысл зависит от структурных связей между ними, и от тех объектов, о которых они говорят. Скажем, утверждение A следует из утверждения B, но не следует из утверждения C. Или утверждение A связывает между собой такой-то и такой-то объекты. Это примеры структурных связей, которые нас интересуют больше, чем буквы слов "с-л-е-д-у-е-т" или "у-т-в-е-р-ж-д-е-н-и-е".

Что если мы найдем способ построить наши утверждения из кирпичиков-объектов (например, чисел, или сортов сыра) так, чтобы интересующие нас отношения между ними сохранялись в нашем "переводе" на язык объектов - только назывались по-другому? Может, если утверждение A следует из утверждения B, а мы их оба выразили числами, то это будет то же самое, что сказать, что одно из чисел больше другого (это специально слишком упрощенный пример). Если отношение "больше" между числами будет вести себя, как мы ожидаем от отношения "следует из" между утверждениями, то такой "перевод" будет верным и обоснованным. И это будет означать, что мы "схлопнули" мета-уровень в обычный уровень, перевели утверждения (которые мы раньше формулировали на нестрогом языке букв, звуков, мыслей) в объекты, которые мы умеем изучать с помощью нашей теории.

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

Есть только одна важная особенность. Поскольку нас интересует сейчас не просто истинность каких-то утверждений, а возможность их доказать в нашей исходной теории, процесс "перевода" мета-уровня в обычный уровень, описанный выше, должен быть не просто "верным" переводом, то есть сохраняющим структурные свойства утверждений при их переносе в объекты. Нам еще необходимо, чтобы наша исходная теория могла доказать, что эти самые структурные свойства сохраняются - могла в рамках своих рассуждений проследить эту связь туда-и-обратно между мета-уровнем и уровнем. Действительно, если мы, скажем, перевели "A логически следует из B" на мета-уровне утверждений в "20 больше, чем 10" на уровне чисел, чем это нам поможет, если наша исходная теория настолько "слаба", настолько тривиальна, что даже такую простую истину, как "20 больше, чем 10" она доказать не может?

Поэтому нам необходимо потребовать от нашей исходной теории определенной мощности, возможности доказать определенные базовые истины, позволяющие подтвердить, в рамках нашей теории, адекватность "перевода" из мета-уровня в уровень. Оказывается, что, если в качестве наших объектов мы берем обычные числа, и переводим из мета-уровня утверждений в уровень чисел, то нам и не надо так уж многого требовать от нашей теории: она всего лишь должна включать несколько простых аксиом, позволяющих, условно говоря, доказать такие истины, как "дважды два - четыре" и "десять меньше, чем двадцать". Несмотря на то, что истины эти очень просты, они все же нетривиальны с логической точки зрения, и следуют из этого небольшого набора простых аксиом; когда говорят, что исходная теория должна "включать арифметику", подразумевают именно наличие этих простых аксиом.

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

moose, transparent

мимоходом

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