Книги по разным темам Pages:     | 1 |   ...   | 12 | 13 | 14 | 15 | 16 |   ...   | 54 |

В любой творческой деятельности человека просматриваются два компонента Ц - систематический и интуитивный, кухня и лозарение. Математика доставляет непревзойденные образцы систематической работы ума, поразительные по сложности архитектуры дедуктивные построения, исходящие из минимума посылок и, после длинной вязи умозаключений, венчающиеся важными выводами. Успехи математики и математизированных областей знания приводили многих глубоких мыслителей к надежде на существование нескольких универсальных законов, из которых все остальные истины могут быть выведены чисто теоретически. В европейской традиции эти надежды связаны с именами Лейбница и Декарта. До сих пор их продолжают высказывать некоторые физики, задумывающиеся над структурой наших знаний о природе. После работы Гёделя, однако, мы можем быть уверенными в беспочвенности этих надежд. Если даже оставить в стороне вопрос, насколько сложен мир, мы знаем, что метод дедуктивных выводов недостаточно мощен. Его не хватает даже на то, чтобы вывести из конечного числа принципов все истинВпервые опубликовано: Природа. 975. № 2.

Т Г ные утверждения о целых числах, формулируемые на языке школьной алгебры: таков смысл теоремы Гёделя.

Это осознание глубокой ограниченности дедуктивных рассуждений и вообще механических методов поиска истины стало особенно актуальным в эпоху экспансии ЭВМ.

Изложенная точка зрения на теорему Гёделя дает основание считать ее существенным вкладом естественных наук в фонд гуманитарных. По значению и глубине с ним можно сравнивать, пожалуй, только анализ квантовомеханических представлений о дополнительности и неопределенности, распространенный Нильсом Бором далеко за пределы физики микромира. Не исключено, что оба этих круга идей Ц - логики и квантовой механики Ц - в применении к теории познания имеют глубинную связь. Дело в том, что принципы запрета Гёделя относятся к строго детерминированным процессам рассуждения, тогда как квантовая механика как раз очерчивает границы наивного детерминизма. Вероятно, работа мозга проходит вне этих границ.

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

2. Основные понятия I: Язык В этом и следующем разделах описаны основные определения, необходимые для формулировки и понимания теоремы Гёделя. Слова, которыми мы оперируем здесь, допускают разные уровни терминологической определенности. Лишь начиная с некоторой степени уточнения они могут войти в настоящий математический текст. Коегде мы эту степень будем указывать.

Язык. Мы будем понимать под (формальным) языком L задание некоторого конечного алфавита и правил образования текстов Ц - последовательностей букв этого алфавита, которые обладают в системе языка L синтаксической правильностью и осмысленностью. (Различие между последними двумя понятиями, важное для лингвистики естественных языков, в наших моделях отсутствует.) Основной пример, который должен представлять себе читатель, Ц - язык элементарной арифметики LAr. Опишем его на двух уровнях.

Первый уровень. Алфавит LAr включает: буквы русского и латинского шрифтов с индексами, цифры, скобки, знаки арифметических операций: + (сложение); , или (умножение); (возвышение 94 Ч I. М в степень: в линейном тексте лучше писать a b, чем ab); = (знак равенства). Типичный текст на LAr состоит из смеси обычных формул школьной арифметики и алгебры и минимума русской лексики, необходимого для выражения логических понятий (слов-связок лесли..., то, ли, лили, не; слов-кванторов для всех и существует и их синонимов). Текст должен быть организован по правилам, принятым в стандартном математическом жаргоне. Примеры текстов на языке LAr:

таблица умножения;

формула (x + y)2 = x2 + 2xy + y2 (точнее, (x + y) (x + y) = x x + + 2 x y + y y);

формулы 0 = 1 или 2 2 = 5 Ц - они хотя и не истинны, но осмысленны (см. ниже).

Латинские буквы означают неизвестные или переменные, которые могут принимать значения во множестве неотрицательных целых чисел 0, 1, 2, Е Продемонстрируем некоторые особенности языка LAr на примере следующего более сложного текста:

для всех x существует y и существует z ( y = x + z и если y = u v, то u = 1 или u = y).

Это Ц - теорема Евклида о бесконечности множества простых чисел. Действительно, утверждение лесли y = u v, то u = 1 или u = y означает в области целых чисел, что y = 1 или y Ц - простое число.

Утверждение существует z ( y = x + z) означает, что y x. Все вместе: лесть простые числа ( y), большие любого наперед заданного числа (x). Скобки стоят вместо слов такие, что или чего-нибудь и этом роде.

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

Этот уровень описания языка арифметики достаточен для понимания последующих качественных объяснений теоремы Гёделя. Читатель с большей математической подготовкой сможет пользоваться вторым уровнем, который пригоден уже для точных формулировок и доказательств. Мы отмечаем звездочками в начале и конце фрагменты статьи, которые можно опустить без ущерба для понимания дальнейшего.

*Второй уровень. Опишем так называемый формальный язык арифметики по Шмульяну SAr.

Т Г Алфавит SAr состоит из девяти знаков: x (переменная); (штрих для формирования любого числа разных переменных x, x, x, x, Е );

(умножение); (возведение в степень); = (равенство); (логическая связка конъюнкция отрицаний); (, ) (открывающая и закрывающая скобки); 1 (единица).

Тексты на SAr являются последовательностями выражений; выражения Ц - это некоторые последовательности знаков алфавита. Выражения бывают трех типов: числовые термы, классовые термы и формулы.

Числовые термы Ц - это выражения x, x, x, Е; 1, 11, 111, Е Кроме того, если t1, t2 Ц - числовые термы, то (t1) (t2) и (t1) (t2) Ц - тоже числовые термы. Интуитивно, числовые термы Ц - это всевозможные вы ражения, которые можно получить из целых чисел (11 Ц - это 2, 111 Ц - это 3...) и переменных с помощью операций умножения и возвышения в степень.

Формулы первого ранга. Это выражения вида t1 = t2; кроме того, если P1 и P2 Ц - две формулы, то (P1) (P2) Ц - не P1 и не P2 Ц - тоже формула. Интуитивно, t1 = t2 Ц - это мультипликативно-экспоненциальные уравнения. Соединяя их связкой в разных сочетаниях, мы можем, например, записать утверждение большой теоремы Ферма. Вот указания читателю, который пожелает это сделать. Удобно исходить из следующей полусловесной формулировки: если x 3, то неверно, что xx + xx = xx. Посылку x 3 мож но написать в SAr, например, так: (11) (x) = ((11) (111)) (x) (т. е. 2x делится на 23 = 8). Само уравнение Ферма можно записать так: ((11) ((x) (x))) ((11) ((x) (x))) = (11) ((x) (x)), т. е.

x x x 2x 2x = 2x (это трюк, чтобы обойтись без знака +, которого нет в алфавите SAr).

Выражение неверно, что P передается в SAr как (P) (P), а выражение лесли P, то Q как (((P) (Q)) (Q)) (((P) (Q)) (Q)) (снова околичности, связанные с экономией на основной лексике).

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

Если T1, T2 Ц - два классовых терма, выражение T1 = T2 есть формула.

Этот прием заменяет квантор общности, которого нет в алфавите:

96 Ч I. М x(P1) = x(P2) означает для всех x (x удовлетворяет P1, если и только если x удовлетворяет P2).

Если P1, P2 Ц - формулы, то (P1) (P2) Ц - формула.

Опытный читатель без труда превратит это описание в точное рекурсивное определение классовых термов и формул.* В наших объяснениях по поводу LAr и SAr полезно выявить еще несколько понятий. Перечислим их.

Синтаксис языка. Это Ц - правила образования текстов на языке.

Мы учимся родному языку, пользуясь им; изучаемые позже правила школьной грамматики не полны, недостаточно явны и лишь несколько нормализуют языковую практику. Полностью формализованный язык, такой как SAr, наоборот, описывается полной и явной системой правил. Исследовать язык математически можно, разумеется, лишь после его достаточной формализации.

Семантика языка. Это Ц - правила выявления смысла текстов, т. е.

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

Метаязык. Это язык, на котором мы описываем язык-объект (как LAr, SAr), его синтаксис и семантику. В нашем случае метаязык Ц - фрагмент русского языка (диалект научно-популярной литературы с философскими претензиями). В рамках наших задач ни его синтаксис, ни семантика не подлежат какому бы то ни было описанию.

Основные понятия II:

Истинность, выразимость и полнота Высказывания на языке LAr (и формулы языка SAr) могут быть истинными, ложными или неопределенными (в отношении истинности).

Фон Нейман Дж. Вычислительная машина и мозг. Кибернетический сборник. М.:

ИЛ, 960. №.

Т Г Неопределенными могут быть только те высказывания, в которых участвуют свободные символы переменных (x, y, z, Е ), т. е. не связанные словами для всех... или существует. Высказывание для всех x (x = 2) ложно, ибо есть натуральные числа, отличные от 2;

высказывание существует x (x + 1000 = 2000) истинно; высказывание x = 3 не определенно: оно станет определенным Ц - истинным или ложным, Ц - если вместо свободной переменной x мы подставим в него то или иное (целое неотрицательное) число; высказывание x = x истинно, хотя переменная x в нем свободна.

Очень существенно, что все высказывания, не содержащие свободных переменных, мы считаем заведомо определенными в отношении истинности или ложности, даже если мы не в состоянии действительно решить, истинны они или ложны. Типичный пример Ц - гипотеза Ферма; для всех x, y, z, n неверно, что (x + 1)n+3 + ( y + 1)n+3 = = (z + 1)n+3. Согласно нашим представлениям, она либо истинна, либо ложна. Вера в это основана на абстракции возможности произвести бесконечно много проверок числовых тождеств, которые получатся, если в уравнение Ферма подставлять всевозможные целые неотрицательные числа вместо x, y, z, n.

Среди специалистов по основаниям математики существуют школы, считающие такого рода абстракции неправомерными. Здесь мы не можем входить в этот вопрос.

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

Например, высказывание существует x ( y = x + 2) и для всех u, v (если y = uv, то u = 1 или u = y) содержит одну свободную переменную y и означает: y Ц - простое число.

Таким образом, оно является записью свойства быть простым числом на нашем языке.

Более общо: рассмотрим некоторое высказывание P(x, y, z), в которое входят, скажем, ровно три свободных переменных x, y, z (и, возможно, какие-то связанные). Будем говорить, что тройка чисел обладает свойством, выраженным высказыванием P, если после подстановки членов этой тройки вместо x, y, z соответственно мы получим истинное высказывание. (Заметим, что после подстановки оно станет определенным.) Результат подстановки в P чисел 1, 3, 7, вместо x, y, z удобно обозначить P(1, 3, 7).

Таким образом, каждое высказывание, содержащее ровно n свободных переменных, выражает некоторое свойство наборов из n чисел.

98 Ч I. М Существует другая, дополнительная, точка зрения на свойства.

Любое свойство, скажем, целого числа однозначно определяется множеством всех тех целых чисел, которые этим свойством обладают.

Аналогично, любое свойство набора из n целых чисел есть множество всех таких наборов, которые этим свойством обладают.

Мы часто будем отождествлять таким способом множества и свойства.

Разные высказывания языка могут выражать одно и то же свойство. Таковы пары x = 1 и л(x - 1)2 = 0; x = 1 или x = 2 и не x = и не существует y(x = y + 2).

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

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

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

Совокупность свойств, которые можно выразить средствами данного языка, Ц - его важнейшая характеристика. Она измеряет богатство, или выразительность, языка.

Вопрос Ц - является ли данное свойство целых чисел (выраженное, скажем, в метаязыке) выразимым в данном конкретном языке арифметики Ц - может оказаться высоконетривиальной математической задачей.

Дедуктивные средства языка. Любая задача элементарной теории чисел может быть сформулирована как вопрос: является ли данное высказывание P без свободных переменных на языке LAr (или формула языка SAr) истинным Проанализируем, как такие задачи решаются.

Pages:     | 1 |   ...   | 12 | 13 | 14 | 15 | 16 |   ...   | 54 |    Книги по разным темам