Истинность и доказуемость

Введение

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

В любой, достаточно содержательной теории, существуют истинные формулы, которые невозможно доказать.

В этой формулировке ключевыми являются два утверждения: а) "существуют недоказуемые утверждения" и, не смотря на это, б) "эти утверждения являются истинными".

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

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

И теорема Геделя, и теорема Кантора являются существенно косвенными результатами, полученными при помощи метода рассуждений от противного. Поэтому, с его анализа и начнем.

Доказательство от противного

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

Теорема Евклида о бесконечности простых чисел {P₁,P₂,...} является классическим примером таких рассуждений:

Theorem: Не существует самого большого простого числа P_max.

Proof: Пусть это не так и самое большое простое число P_max существует. Построим число (P₁*P₂* .. *P_max) + 1. Очевидно, что оно не делится ни на одно P_n и больше чем P_max. Мы пришли к противоречию, следовательно, самого большого простого числа (как объекта!) не существует и простых чисел бесконечно много.

Проблема Библиотекаря. Существует некоторая библиотека с книгами. Любая книга может внутри своего текста упомянуть сама себя (например, в списке литературы привести свое название). Соответственно все книги можно разделить на две группы в первую попадают книги, которые на себя не ссылаются, а во вторую те, которые на себя ссылаются. Кроме того, существуют две книги являющиеся каталогами всех книг библиотеки. Первый каталог перечисляет все те книги, которые на себя не ссылаются, а второй, наоборот, все ссылающиеся на себя книги. Теперь рассмотрим следующую теорему:

Theorem: Второй каталог содержит в своем перечне книг первый каталог.

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

Если мы остановимся на этом этапе, то получим заведомо не верный вывод. Дело в том, что второй каталог не может содержать первый, так как он упоминает только те книги, которые на себя ссылаются, что первый каталог не делает. Вообще, в данном случае мы можем провести как обратное доказательство (от противного) так и прямое. И в том и в другом случае мы получаем противоречие, которое на самом деле, говорит не об истинности или ложности теоремы, а свидетельствует о том, что объект Библиотека, c заданными свойствами, существовать не может. Этот пример является некоторой переформулировкой известного парадокса Рассела [Пенроуз].

Парадокс лжеца. Сформулируем его в более формализованном виде. Введем обозначение того, что некое логическое утверждение является истинным:

True(A) : A

Определим теперь следующий предикат, не содержащий предметных переменных:

L : ~True(L)

Theorem: Утверждение L является истинным: L=И.

Proof 1: пусть L=Л => True(L)=Л => L=~True(L)=И

В доказательстве от противного, мы пришли к противоречию. Поэтому исходная посылка L=Л не верна и, следовательно, теорема верна. Однако понятно, что это не так. Мы можем провести доказательство и в прямом направлении:

Proof 2: пусть L=И => True(L)=И => L=~True(L)=Л,

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

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

1) исходная теорема верна;
2) объекты, участвующие в формулировке теоремы, противоречивы.

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

Теорема Геделя о неполноте

Как ни странно, существование формул которые невозможно ни доказать ни опровергнуть на самом деле достаточно естественно. Легко видеть, что в математике нет ограничения на длину доказательства. Действительно, определяя правильно построенную формулу, мы не делаем ограничений на ее возможную длину. Формальное доказательство также является формулой и, следовательно, может быть сколь угодно длинным (хотя бы по тому, что для доказательства формулы требуется более длинное доказательство чем сама формула). Более того, весь опыт математики говорит о том, что минимально возможная длина доказательства данной формулы на прямую не связана с длиной этой формулы. Многие очень простые формулы (теоремы) имеют очень сложные (==длинные) доказательства.

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

Гедель в 1931 г. предложил формальное доказательство этого факта. Введем логическую функцию "Proof(A)" обозначающую то, что существует доказательство формулы "A". Если доказательство "A" существует, то "Proof(A)=И=истина", а если нет то "Proof(A)=Л=ложь". Обычно при доказательстве теоремы Геделя, "конструктивным" образом строится самореферирующее утверждение (формула) G, определяемое как утверждение о том, что оно недоказуемо:

G : ~Proof(G)

Theorem: "Если теория непротиворечива, то формула G истинна, но ее нельзя доказать: Proof(G)=Л"

Непротиворечивость означает, что доказать ложное утверждение нельзя: F=Л => Proof(F)=Л, а если утверждение доказуемо, то оно истинно: Proof(F)=И => F=И. Поэтому, обычно строится такое доказательство от противного:

Proof1: пусть Proof(G)=И => G=И, G=~Proof(G)=Л.

Можно было бы построить доказательство в обратную сторону:

Proof2: пусть Proof(G)=Л => G=Л, G=~Proof(G)=И

Нумерология Геделя

Для придания "конструктивного" характера самореферирующему утверждению "G : ~Proof(G)" Гедель использует следующие рассуждения. Рассматривается подмножество всех формул теории чисел, которые зависят от одной переменной:

F₁(x): x+1=1+x
F₂(x): x-1=2
F₃(x): Prime(2*x)
...

Доказательство - это такая же формула (последовательность символов) как и любая другая. Следовательно, каждое доказательство также имеет свой порядковый номер. Обозначим через D(n, k, x) или D(n, F_k(x)) логическое утверждение о том, что доказательство под номером "n" является доказательством формулы с номером "к" при некотором значении "х". Всегда можно построить алгоритм (написать программу для компьютера) который будет проверять истинность или ложность данного утверждения при построенном (уже существующем) n-ом доказательстве. Если доказательство формулы F_k(x) существует в принципе, то следующий предикат:

Proof(F_k(х)) : $z D(z, F_k(х))

D(1, F_k(х)) Ú D(2, F_k(х)) Ú D(3, F_k(х)) Ú ...,

т.е. или первое доказательство или второе и т.д. Запишем теперь утверждение, о том, что некоторая произвольная формула F_k(х) при x=k не доказуема: ~Proof(F_k(k)). Так как эта формула является обычной формулой зависящей только от одной свободной переменной k она также является формулой теории из спиcка F_n(x). Пусть ее номер равен m:

F_m(k) : ~Proof(F_k(k))

Так как число "k" было выбрано произвольно, мы можем положить k=m и прийти к необходимому нам самореферирующему определению с G = F_m(m) .

Является ли такой способ введения утверждения "G" конструктивным и не содержащим бесконечной рекурсии? Вряд ли. Например, на языке С++ можно написать отлично работающую программу, которая суммирует рекурсионным образом числа от х до 1, с шагом a:

int F(int x, int a)
{
   if(x==1) return 1;       // точка выхода из рекурсии
   return x+F(x-a,a);       // рекурсия 
}

Заметим также, что аналогичным "конструктивным" геделевским образом легко поcтроить и утверждение "L" из парадокса лжеца, проведя соответствующее рассуждение для предиката True(n). Вообще, наиболее скользкое место это, на самом деле, определение предиката Proof(F_k(х)): $z D(z, F_k(х)). Как мы видели, оно эквивалентно бесконечной цепочке логических или. Каждый предикат D(i, F_k(х)) входящий в эту цепочку является вполне хорошо определенным. По данным числам i и k мы всегда можем построить i-е доказательство и k-ю формулу. Имея их можно алгоритмическим образом проверить, является ли это i-е доказательство доказательством данной k-й формулы. Проблема в том, что для того, чтобы вычислить предикат Proof нам потребуется применить эти алгоритмы бесконечное число раз.

Что такое истина?

В исчислении предикатов мы не имеем эффективного метода проверки истинности или ложности некоторых формул. Для бесконечной предметной области, многие формулы содержащие кванторы существования и всеобщности не могут быть вычислены, так же как мы это делаем для остальных логических операторов, например в булевой алгебре. Единственный путь проверки истинности утверждения это построить его формальный вывод из исходных аксиом. В этом смысле, истинность или ложность в исчислении предикатов отходят, в отличие от булевой алгебры, на задний план, а в перед выходит понятие доказуемости. Мы можем, при помощи аксиом и правил вывода, получать новые формулы. Всё множество выведенных таким образом формул мы называем истинными. Если в это множество попадает формула вида ~F, тогда формулу F мы называем ложной. Если теория непротиворечива, то формула не может быть одновременно ложной и истинной, т.е. в множество выводимых формул не может попасть F вместе с её отрицанием ~F.

Таким образом, по определению, истинными являются выводимые формулы, и априорно рассуждать об истинности или ложности мы не можем. Некоторая формула F может оказаться принципиально недоказуемой, т.е. во множество выводимых из аксиом формул не попадет ни F ни ~F. Утверждать, что такая формула ложна или истинна мы не имеем ни какого права. Она просто не обладает этим свойством.

Вообще сейчас мы вступаем на скользкую дорогу философских размышлений. Для платонически настроенного математика мир математических объектов реально существует - а он его только изучает. Поэтому истинность или ложность любого утверждения является объективным и не зависящим от человеческого сознания или процедуры вывода, реально существующим фактом. Этим такой математик отождествляет себя с физиком, изучающим внешний по отношению к его сознанию объективный мир. Он верит, что этот мир непротиворечив и познаваем. Вообще говоря, такое отождествление сомнительно. В реальном мире нет комплексных и даже отрицательных чисел, а уж тем более множества всех множеств. Как известно, Бог создал натуральные числа, а все остальное придумал человек. Это позволяет ему достаточно эффективно применять математику к окружающему миру для его познания. Однако вера в то, что порождение человеческого разума должно обязательно оказаться полным и непротиворечивым, а истинность утверждения не требовать доказательств, является проявлением повышенного самомнения. То, что придумал человек, вообще не может быть объективно - оно субъективно по определению.

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

Вернемся к теореме Гёделя и рассмотрим четыре различных утверждения:

(1) F=Л => Proof(F)=Л
(2) F=И => Proof(F)=И
(3) Proof(F)=И => F=И
(4) Proof(F)=Л => F=Л

Формула является истинной если она выводима: Proof(F)=И => F=И (3), и наоборот истинная формула должна быть выводима: F=И => Proof(F)=И(2).

Построим теперь прямое и обратное доказательства теоремы Геделя несколько иным способом:

Proof1: пусть G=Л => Proof(G)=Л => G=~Proof(G)=И
Proof2: пусть G=И => Proof(G)=И => G=~Proof(G)=Л

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

Большинство ранее приведенных рассуждений опиралось на бинарный характер логики. Если доказуемо некоторое утверждение Proof(A), то A - истинно, если доказуемо Proof(~A), то А-ложно и третьего не дано. В ситуации, когда мы принимаем, что для некоторых утверждений ни доказательство, ни его опровержение не может построено в принципе, логика уже не может быть бинарной. Помимо истины и лжи, существует третье значение - "не известно". В этом случае полагаться на наличие противоречия в доказательствах от противного необходимо очень осторожно, а по платоновски верить в истинность или ложность утверждений вообще не стоит. Неудивительно, что в интуиционализме Брауэра возникает сомнение в справедливости, в общем случае, закона "исключения третьего": ~P(~P) <=> P.

Таким образом, возможно два различных взгляда на теорему Гёделя. В их основе лежит разное определение понятия истинности. При традиционном подходе считается естественным, когда истинное утверждение может не иметь доказательства и построение от противного в обе стороны теоремы Гёделя не проводится. При этом, неявным образом, верят в существование объективной истинности или ложность утверждения безотносительно к факту его доказуемости. Можно же, однако, стать на точку зрения, что априорная истина без доказательства лишена смысла и истинное утверждение всегда доказуемо и наоборот доказуемое утверждение является истинным. Если же для некоторых формул F теории в множество теорем не попадает ни F, ни ~F, то формула F, в принципе, не обладает свойством истинности или ложности. В этом случае, как было показано выше, формула Гёделя G приводит к двойному противоречию, и, как непротиворечивый объект, не может существовать.

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

Теорема Тьюринга об остановке.

Машина Тьюринга, по сути это современный компьютер с бесконечной памятью. Компьютер является универсальным устройством которое способно, помимо всего прочего, вычислять значение целочисленных функций "F(x)". Каким образом функция y=F(x) вычисляется определяется алгоритмом (программой). Программа естественно является некоторой строкой, поэтому все возможные программы, как и в случае с формулами, можно пронумеровать.

Хорошо известно, что бывают программы хорошие и плохие. В частности, среди плохих была, приведенная ранее, функция F(x,0). Начав работать этот алгоритм никогда не останавливается и не выдает результата.

Поэтому Тьюринг поставил вопрос - можно ли написать универсальный алгоритм по проверке того, остановится ли данная программа или нет. Т.е. на вход этого алгоритма должен поступать текст программы (достаточно передать ее номер) и значение ее данных. Мы без ограничения общности будем считать, что и номер программы и номер ее входных данных и результаты работы являются целыми числами начиная c 1. Алгоритм должен выдать или результат работы данной программы (число > 0) или (в случае если программа никогда не останавливается) число 0. На самом деле понятно, что для очень многих программ можно сказать останавливаются они или нет. Простейший способ это запустить программу (протестировать ее). Если она остановилась то все нормально. Однако если она не останавливается то не известно - остановится ли она когда ни будь или будет работать бесконечно долго. Для некоторых плохих программ типа F(x,0) легко понять, что они ни когда не остановятся даже не запуская их. Однако мы пытаемся понять существует ли универсальный алгоритм, который способен решить проблему остановки для любой программы. Тьюринг доказал что объект с такими свойствами не существует:

Theorem: Не существует функции (программы) T(n, x) со следующими свойствами: если n-я функция (n-тая программа) F_n(x) останавливается и выдает k при данном x то T(n,x) выводит число k. Если же F_n(x) ни когда не останавливается то T(n, x) печатает 0.

Proof: Если T(n,x) существует, то она применима ко всем программам, (в том числе и к себе самой). Определим функцию F(x) = T(x,x)+1. Она принимает значения при x=1,2,.. не равные значениям ни одной из функций F_n(x). Действительно, T(1,1) равно или F₁(1) или 0 если F₁(1) не останавливается, поэтому F(1) = T(1,1)+1 не совпадает с F₁(1). Аналогично для значения x=2, F(x) не совпадает с F₂(x) и т.д. Таким образом, мы построили функцию (программу) которая отсутствует в списке F_n(x), а это противоречит утверждению, что все программы были пронумерованы.

Доказательство от противного в данном случае вполне уместно, так как мы доказываем, что объект с сформулированными в теореме свойствами противоречив, и следовательно не может существовать.

Не сложно адаптировать это доказательство к теореме Геделя и доказать, что не существует функции Proof(n,k). Однако мы применим метод Тьюринга к доказательству того, что существуют формулы для которых невозможно установить истинны они или ложны. Действительно, пусть мы всегда способны установить истинен или ложен данный предикат F_n(x). Это означает, что мы владеем предикатом (алгоритмом) True(n,x) который равен "И" если F_n(x) истинен и "Л" в противоположном случае. Но тогда мы можем построить предикат F(x)=~True(x,x) который не совпадает ни с одной F_n(x). А это означает, что True(n,x) работающая при любых n,x невозможна.

Все это означает, что существуют математические формулы истинность которых не возможно установить при помощи универсального алгоритма True. Эти же формулы не могут быть доказаны (выведены) при помощи универсального алгоритма Proof (в противном случае мы бы заключили что они истинны). Наглядно, алгоритм Proof можно представить как последовательный перебор номеров доказательств n=1,2,.. и проверки D(n, k, x) того, что они доказывают k-ю формулу. Так вот, существуют формулы для которых этот алгоритм (и любой другой) никогда не остановится!

Завершая анализ теоремы Геделя о неполноте сформулируем, как нам кажется, ее более точную формулировку:

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

Алгоритмы и теория множеств

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

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

После установления счетности множества рациональных и алгебраических чисел, Кантор, при помощи знаменитого диагонального рассуждения показал, что множество действительных чисел несчетно. Часто, на основании этого, говорят, что иррациональных чисел "больше" чем рациональных. Это в корне не верно.

Во-первых между двумя сколь угодно близкими иррациональными числами, всегда расположено бесконечно много рациональных чисел. Это легко увидеть, представив иррациональные числа в виде бесконечных десятичных дробей. У двух близких, но не равных иррациональных чисел a,b первые n цифр десятичного разложения совпадут. Мы всегда можем выбрать рациональное число в виде конечной десятичной дроби у которой n+1 цифр совпадают с первыми n+1 цифрами числа "b" и дальше идут нули. Очевидно, что это рациональное число будет больше "a" и меньше "b". Если ли бы иррациональных чисел было "больше" чем рациональных, то мы получили бы довольно неприятную ситуацию: между любыми двумя иррациональными числами всегда путается бесконечное число рациональных, которых меньше!? Хотя с актуально бесконечными объектами, конечно и не то может происходить :).

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

Как появляются (определяются) в математике те или иные конкретные числа? Прежде всего - как решения каких либо уравнений. Например, корень из двух это обозначение (имя!) числа являющегося решением уравнения x²=2. Это пример алгебраического числа. Далее, числа можно определить при помощи бесконечных рядов. Так, мы определяем "e" как 1/1! + 1/2! + 1/3! + .. Не смотря на то, что этот ряд бесконечен, формула, определяющая число "e", конечна. Многоточие лишь обозначает, что у нас есть конечный алгоритм позволяющий получить любой, наперед заданный, член этого ряда. Еще одним, похожим, способом определения вещественного числа является задание алгоритма вычисления любой цифры в его десятичном представлении. Таким является трансцендентное число Лиувилля: 0.1100010000000000000000010.. (n-я единица стоит в позиции n!). Можно определять вещественное число при помощи предела к которому стремятся рекурсивные соотношения и т.д.

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

А существуют ли несчетные множества?

Математика наука точная. Математическое рассуждение корректно только тогда, когда его логическая структура истинна в не зависимости от содержательного смысла объектов в нем участвующих. Проанализируем структуру двух рассуждений:

(1) Рассмотрим множество всех целочисленных функций k=F(m), которые можно определить при помощи некоторого алгоритма. Предположим, что эти функции представляют собой счетное множество, т.е. каждая функция определяется своим номером n: F_n(m). Построим функцию F(m) = F_m(m)+1. Она тоже определяется алгоритмом. Она не совпадает ни с одной функцией из F_n(m). Мы пришли к противоречию. Поэтому, множество таких функций несчетно.

(2) Рассмотрим множество всех вещественных чисел R, которые можно определить в виде бесконечной десятичной дроби. Предположим, что эти числа представляют собой счетное множество, т.е. каждое число определяется своим номером n и значением m-той цифры его десятичного разложения: R_n(m). Построим число m-я цифра которого R(m) = R_m(m)+1 mod 10. Оно тоже определяется бесконечным десятичным разложением. Оно не совпадает ни с одним числом из R_n(m). Мы пришли к противоречию. Поэтому, множество таких чисел несчетно.

Не возникает ли того же эффекта в доказательстве Кантора (2)? В случае функций мы твердо знали, что их множество счетно, так как получили этот результат прямым а не косвенным рассуждением. Поэтому причину получившегося противоречия (1) ищем в другом (в проблеме остановки). Счетны ли вещественные числа мы не знаем, поэтому, получив противоречие с радостью делаем вывод что они несчетны. Но также как и в (1), мы, при рассуждениях (2), делаем не единственное предположение о том, что множество вещественных чисел счетно. Мы также верим, что мы можем для любого такого числа получить m-ю цифру и благодаря этому построить число отличное от всех в уже упорядоченной последовательности.

Каждая вычислимая функция, определенная для всего множества значений аргумента m, определяет некоторое вещественное число. Такими функциями были упомянутые в (2) R_n(m). Можно расширить это определение вещественного числа на все возможные алгоритмы. Но тогда мы получим множество невычислимых вещественных чисел. Простейший пример такого числа следующий. Рассмотрим бесконечное множество всех возможных алгоритмов для машины Тьюринга. Определим действительное число, как число m-тая цифра десятичного разложения которого равна 1 если m-тый алгоритм останавливается и 0 если нет:

0.1011?1..

Конечно, можно рассуждать по другому. Пусть множество конструктивных вещественных чисел задается только при помощи всюду определенных вычислимых функций (позволяющих получить любую цифру десятичного представления R_n(m)). И пусть еще существуют числа которые не задаются ни одним алгоритмом, не являются решением ни одного уравнения или предела произвольного ряда. Десятичное представление этих чисел есть "просто" произвольное (случайное?) бесконечное множество цифр 0-9. Именно этот довесок и оказывается несчетным.

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

Несчетность множества всех подмножеств

Несчетным множеством, как всем известно, является множество Z всех подмножеств множества натуральных чисел N. Доказательство этого факта, как и положено, ведется от противного. Забавно, что по своей логической структуре это рассуждение совпадает с парадоксом Библиотекаря, однако на это, обычно, не обращают внимания:

Предположим, что между множествами N (названия книг) и Z (списки ссылок книг) существует взаимооднозначное соответствие z=F(n). Тогда, все числа (элементы множества N) можно разделить на два класса: правильные и особые. К правильным относятся те, и только те числа, которые принадлежат подмножеству z, которому они соответствуют: n Î z=F(n) (в библиотеке - те книги, которые на себя ссылаются). Особые числа, соответственно те, которые связаны соответствием с множеством z их не содержащих: n Ï z=F(n) (не ссылающиеся на себя книги). Рассмотрим теперь множество всех особых чисел D. Это множество чисел, поэтому оно является элементом множества Z. Следовательно, существует число d (каталог всех нессылающихся на себя книг) с которым D связано соответствием D=F(d). Вопрос - является d правильным или особым числом? Очевидно, что оно не то, и ни другое. Действительно, d не может быть правильным числом, так как оно не может находится в D, которое содержит только особые числа. Но d не может быть и особым числом, так как оно попало бы в D по самому его построению, а особое число не может быть связано с множеством его содержащим.

Множество всех подмножеств, как известно, связано с проблемой счетности действительных чисел. Действительно, элементы множества Z мы можем задавать в виде дробных частей действительных чисел в двоичной форме:

0.00110101101..
0.11100011011..
0.11?000?10??..
...,

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

Искусственный интеллект и основания математики

Замечательный математик и физик Роджер Пенроуз в книге "Новый Ум Короля" (1989 г.) в связи с самореферирующим доказательством теоремы Геделя пишет (выделение Пенроуза):

"Если ум математика работает полностью алгоритмически, то алгоритм (или формальная система), которые он обычно использует для построения своих суждений Proof(k,k), оказываются не в состоянии справиться с утверждением полученным с помощью его собственного алгоритма. Тем не менее, мы можем (в принципе) понять что Proof(k,k) на самом деле истинно! Этот факт, по всей видимости, должен был бы указать ему на противоречие, поскольку он, как и мы, не может не заметить его. А это в свою очередь, может свидетельствовать о неалгоритмическом характере его рассуждений!"

Стоит вспомнить, что говорил по этому поводу сам Тьюринг, который кое-что понимал в алгоритмах и теореме Геделя:

"Ответ на это возражение вкратце состоит в следующем. Установлено, что возможности любой конкретной машины ограничены, однако в разбираемом возражении содержится голословное, без какого бы то ни было доказательства, утверждение, что подобные ограничения не применимы к разуму человека. Я не думаю, чтобы можно было так легко игнорировать эту сторону дела. Когда какой-либо из такого рода машин задают соответствующий критический вопрос и она дает определенный ответ, мы заранее знаем, что ответ будет неверным, и это дает нам чувство известного превосходства. Не является ли это чувство иллюзорным? Несомненно, оно бывает довольно искренним, но я не думаю, чтобы ему следовало придавать слишком большое значение. Мы сами слишком часто даем неверные ответы на вопросы, чтобы то чувство удовлетворения, которое возникает у нас при виде погрешимости машин, имело оправдание." ["Могут ли машины мыслить?" 1950 г.]

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

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

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

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

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

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

(c) 2004, 2007 Сергей Степанов
@synset.com (sci)