WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 12 | 13 || 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 || 15 | 16 |   ...   | 54 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.