«Прикладная логика Учебное пособие Рекомендовано Государственным комитетом Российской Федерации по высшему образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям ...»

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

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

Уже на данном примере видно, что идеальность бывает разной степени, и введя идеальные понятия, мы часто вынуждены вводить еще И правильно мучают! Если Вы ими не овладели, Вам нечего и читать эту главу дальше.

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

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

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

более идеальные, чтобы успешно работать с уже имеющимися. Далее чувствуется, что плоская10 прикладная точка зрения в чем-то ущербна, поскольку основные математические результаты, оказывается, касаются именно идеальных понятий.

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

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

Поэтому неудивительно, что среди ученых, занимающихся точными науками, популярна точка зрения Платона: на самом деле именно идеальные понятия первичны, а так называемые “реальные” служат лишь их несовершенными и бледными отражениями, их тенями. Если хорошенько вдуматься, то поймешь, что этот взгляд достаточно обоснован: в частности, одно из самых “реальных и материальных” понятий, по сути дела породившее весь мировоззренческий материализм, — деньги — на самом деле ирреально, оно является лишь результатом соглашения между людьми, что доказали события в Камбодже, когда захватившие власть ультракоммунисты отменили деньги и никто не поднимал даже доллары. Удивительная эффективность и красота идеальных понятий и неэффективность и безобразие ползучего, эмпирического мышления просто провоцируют этот взгляд11.

Подчеркиваю, плоская! Плоская теоретическая точка зрения на самом деле столь же ущербна.

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

Результаты алгебраической топологии используются при оптимизации интегральных схем и т. п.

НЕСТАНДАРТНАЯ МОДЕЛЬ

§ 10.2.

Пользуясь теоремой Мальцева о компактности, построим несколько необычную модель теории, описывающей натуральные числа.

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

Мы уже видели на примере теории Q из упражнения 8.2.5, как строятся нестандартные модели для слабых подсистем арифметики. Для теряют видимую связь с ним, сохраняя тем не менее глубинные. С данной точки зрения идеальные понятия такие же орудия человеческой мысли, как механизмы — орудия его материальной деятельности.

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

';

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

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

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

Пусть TrN — теория, состоящая из всех формул данной сигнатуры, истинных на множестве натуральных чисел. Пополним сигнатуру константой и зададим следующие аксиомы (их бесконечное число; если в сигнатуре имеются константа для данного натурального числа, то n означает такую константу; в противном случае это терм 1 + + 1):

Дополнительные аксиомы обозначим Th. Рассмотрим вопрос о непротиворечивости теории TrN Th. Сама по себе TrN, очевидно, непротиворечива, поскольку ее моделью является множество натуральных чисел. Точно так же непротиворечива и теория Th, поскольку она не постулирует никаких свойств обычных натуральных чисел, кроме наличия 0, 1 и операции сложения, и в качестве ее модели можно взять, скажем, N {}, а + доопределить для следующим образом:

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

Для доказательства непротиворечивости TrN Th воспользуемся теоремой о взаимной непротиворечивости. Если к TrN добавить конечное число аксиом Th, то получившаяся теория будет непротиворечива.

В самом деле, в этом конечном подмножестве аксиом имеется аксиома с наибольшим n. Обозначим его n0. Тогда, если придать значение n0 +1, то данный фрагмент TrN Th имеет моделью просто стандартный натуральный ряд!

Итак, TrN Th непротиворечива и, следовательно, имеет модель.

чается N. Нестандартный натуральный ряд обладает любопытными свойствами.

Все утверждения, формулируемые на языке логики и истинные на стандартной модели, будут истинны и на N.

А как же с существованием бесконечно большого числа ? Но понятие «бесконечно большое» задается не одной формулой, а их бесконечной последовательностью, так что его просто не существовало в исходном языке. Все свойства, предметы, функции, множества, определявшиеся в исходном языке, носят в нестандартной модели название “стандартных”.

А теперь вопрос: существует ли наименьшее бесконечно большое натуральное число? Конечно же, нет. Ведь = 0, а для всякого натурального числа n, отличного от 0, существует число n 1. Так что нестандартный натуральный ряд принципиально отличается от ординальных чисел, лишь обозначение бесконечно большого числа у них одно и то же. Если в ряду ординальных чисел существуют лишь все большие и б льшие бесконечности типа, то здесь иерархия бесконечностей продолжается в обе стороны. Для существуют и 2, и [/2]13, и Итак, в принципе нестандартный натуральный ряд открывает возможность использовать бесконечно большие числа как идеальные элементы, пользуясь тем, что все стандартные утверждения истинны на нем тогда и только тогда, когда они истинны на исходном натуральном ряду. Но не зря в XVII–XVIII вв. пользовались не бесконечно большими натуральными числами, а бесконечно малыми и бесконечно большими действительными. Нестандартный натуральный ряд заработал лишь в сочетании с нестандартной действительной осью.

Упражнения к § 10. 10.2.1. Что получится в результате деления нацело бесконечно большого числа на бесконечно большое? А конечного на бесконечно большое? А бесконечно большого на конечное? А умножения нуля на бесконечно большое?

Как принято в анализе, [x] здесь обозначает целую часть x, а не кортеж из одного элемента.

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

10.2.2. Есть ли бесконечно большое число, превосходящее все

НЕСТАНДАРТНАЯ ДЕЙСТВИТЕЛЬНАЯ ОСЬ

§ 10.3.

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

Если натуральных чисел счетное множество и вполне можно иметь константы для них всех, то действительных чисел — несчетное множество. Вспомним, что мы доказали теорему полноты лишь для счетных теорий, а для несчетных дали сноску, указывающую, каким способом можно было бы перенести наше доказательство и на них. Сделали мы так не из лени и не из упрощенства14, а потому, что логический статус теоремы полноты для счетных и более чем счетных теорий совершенно различный: первая доказывается практически абсолютно, а вторая зависит от одной из самых сомнительных аксиом теории множеств — аксиомы выбора, либо же от ее следствия, что каждое множество можно вполне упорядочить.

Применение в полную силу всех особенностей традиционной математики при построении нестандартной действительной оси связано с тем, что в математическом анализе интенсивно используются и множества, и семейства множеств, так что нужно позаботиться о сохранении Плоское возражение о том, что на практике все равно не встречается более чем счетных множеств, безжалостно парируется с двух сторон. Во-первых, доказательство несчетности действительных чисел, приведенное на стр. 109, как говорят, абсолютно, оно не зависит ни от каких гипотез теории множеств и переносится практически в какую угодно другую известную математику, так что несчетные множества не слишком большие, а просто слишком плохие, а уж гадостей исключать заранее нельзя. Во-вторых, на самом деле и счетных множеств не бывает, все конечно, но попробуйте-ка обойтись одними конечными объектами! Вспомните, что говорилось об идеальных объектах.

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

Итак, мы считаем, что в число стандартных объектов в математическом анализе входят все действительные числа, все их рассматриваемые в анализе множества и т. д.

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

Пусть A — произвольная формула логики предикатов с переменными и кванторами по числам, их функциям и множествам и т.п., имеющая свободными переменными x1,..., xn, где i — тип переменной xi. Пусть a1,..., an — произвольные объекты из стандартной интерпретации, соответn ствующие по типам переменным xi. Тогда 1. При построении нестандартной модели множество действительных чисел пополняется до R.

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

3. Множество функций становится подклассом соответствующего множества функций и т. д.

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

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

Пример 10.3.1. Множеству всех действительных чисел R соответствует в нестандартной модели множество всех нестандартных действительных чисел R. Множеству всех действительных чисел без нуля R \ {0} соответствует R \ {0}, поскольку сохраняется его характеристическое свойство Начнем с терминологии, касающейся нестандартной модели.

Определение 10.3.1. (Объекты нестандартной модели) Объект называется стандартным, если он имелся в исходной модели. Множество или функция называются внутренними, если они входят в нестандартную модель. Множество или функция — внешние, если они не входят в нестандартную модель.

Число конечное, если оно меньше по модулю некоторого стандартного числа. Число бесконечно большое, если оно по модулю больше любого стандартного числа. Число бесконечно малое, если оно по модулю меньше любого отличного от нуля стандартного числа.

Прежде всего отметим некоторые свойства этих понятий, отнюдь не являющиеся сюрпризом. Сюрпризы еще будут!

Предложение 10.3.1. 1. Результаты всех алгебраических действий над конечными числами конечные.

2. Единственное бесконечно малое стандартное число — ноль.

3. При делении конечного числа a на бесконечно большое получается бесконечно малое число15.

4. При делении конечного числа a = 0 на бесконечно малое = получается бесконечно большое число16.

Итак, стандартные объекты переносятся из стандартной модели в расширенную. Если сами по себе числа либо другие стандартные базовые объекты можно просто отождествить с их нестандартными обраВ отличие от того, что может случиться в теории пределов, если a = 0, то a В отличие от того, что может случиться в теории пределов, если = 0, то = 0. А выражения 0 и 0 остаются бессмысленными.

зами17, то для множеств и функций (и вообще объектов высших типов) ситуация сложнее. Ясно, например, что нестандартным образом множества натуральных чисел N служит множество нестандартных натуральных чисел N. Функция sin при переносе на нестандартную ось должна быть доопределена для всех нестандартных значений. А уж если подумать, что же должно соответствовать операции интегрирования...

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

Часть из них — внешние — в нестандартную модель вообще не входят.

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

Предложение 10.3.2. Множество стандартных действительных чисел внешнее.

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

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

Зато свойства те же, в частности, характеристические свойства для множеств.

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

Докажем теорему, с которой начался нестандартный анализ.

Теорема 10.1. [A. Robinson, 1960] Любое конечное число однозначно представляется в виде суммы стандартного и бесконечно малого.

Доказательство. Пусть a — конечное число. Это значит, что имеется такое стандартное n N, что |a| < n. Следовательно, множество стандартных чисел ограничено сверху19. Любое ограниченное сверху множество действительных чисел имеет верхнюю грань. Обозначим верхнюю грань Xa через st a. st a — стандартное число. Далее, = a st a — бесконечно малое число, поскольку иначе st a не было бы верхней гранью Xa.

Теперь рассмотрим две конкретизации принципа переноса, важные для проверки многих утверждений нестандартного анализа.

Предложение 10.3.3. (-перенос) Пусть A(x) — стандартная формула со свободной переменной x. Тогда Предложение 10.3.4. (-перенос) Пусть A(x) — стандартная формула со свободной переменной x. Тогда Заметим, что в обоих этих утверждениях связывает не формулы, а записанные при помощи логических средств предложения более общего языка, являющиеся внешними для нестандартной модели, и в них обоих для всех стандартных значений x0 имеет место Поскольку все множества стандартных действительных чисел входят в исходную модель, то не имеет никакого значения, что данное множество определено нестандартным условием.

Упражнения к § 10. 10.3.1. Студент Классиков дал следующее доказательство, что функция x [0, 1]. st x внутренняя. Проанализируйте его.

Множество Xx, определенное формулой 10.2, — внутреннее (и даже стандартное). Но st a определено как верхняя грань данного множества. Таким образом, st a для каждого a определено стандартным образом, и значит, сама функция внутренняя.

10.3.2. Студент Гениалькис дал доказательство того, что в нестандартном анализе может существовать конечное нестандартное множество, содержащее все стандартные действительные числа. Студент Лыцаренко опроверг его следующим образом:

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

Услышав такое возражение, Гениалькис порвал свое доказательство и убежал. Кто же из спорщиков прав? Если Вы считаете, что прав Гениалькис, попытайтесь восстановить его доказательство.

НЕСТАНДАРТНЫЕ ПЕРЕФОРМУЛИРОВКИ

§ 10.4.

Начнем с того, как А. Робинсон возродил определение непрерывности, использовавшееся основателями математического анализа, и какие новые тонкости здесь выявились.

Теорема 10.2. Стандартная функция f непрерывна в стандартной точке x тогда и только тогда, когда для любого y Dom f, бесконечно мало отличающегося от x, f (y) бесконечно мало отличается от f (x).

Доказательство. Докажем, что из стандартного определения следует нестандартное. Для любого стандартного > 0 найдется стандартное > 0, такое, что при |y x| < |f (y) f (x)| <. Возьмем теперь произвольное бесконечно малое 0. Оно меньше любого стандартного > 0, и значит, |f (x + 0 ) f (x)| < для любого стандартного > 0.

А это и есть определение того, что |f (x + 0 ) f (x)| бесконечно мало.

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

А теперь докажем, что из нестандартного следует стандартное. В самом деле, возьмем произвольное стандартное > 0. Если взять произвольное бесконечно малое > 0, то для всех y, таких, что |x y| <, разность f (x)f (y) бесконечно мала, по нестандартному определению, и, следовательно, заведомо меньше по модулю. Значит, Но данная формула стандартна и обоснована при произвольном стандартном. Значит, она по принципу переноса верна и для любого.

Следовательно, А это и есть классическое определение непрерывности.

Теперь переформулируем на нестандартный язык понятие равномерной непрерывности.

В стандартной формулировке равномерная непрерывность отличается от непрерывности перестановкой одного квантора. Сравните:

Как влияет эта перестановка на нестандартную формулировку? Раньше x стояло снаружи, и поэтому мы утверждали нестандартную формулировку для стандартного x. Теперь же квантор по x упрятан далеко внутрь, и условие должно быть выполнено для всех x.

Теорема 10.3. Стандартная функция f равномерно непрерывна на стандартном множестве X тогда и только тогда, когда для любых x, y Dom f, бесконечно мало отличающихся друг от друга, f (y) бесконечно мало отличается от f (x).

Доказательство. Остается в качестве упражнения и экзаменационного вопроса.

А теперь переформулируем следующее утверждение:

Последовательность an бесконечное число раз принимает Теорема 10.4. Стандартная последовательность an бесконечное число раз принимает значение 0 ттт есть такое бесконечно большое натуральное число, что a = 0.

Доказательство. Прежде всего разберемся, что же означает бесконечное число раз принимать значение 0.

Поскольку это предложение выполнено и в нестандартной модели то, в частности, для любого бесконечно большого Это m и будет искомым.

Теперь пусть существует бесконечно большое, такое, что a = 0.

Утверждение (10.3) стандартное и начинается с всеобщности, поэтому по принципу переноса его можно обосновывать лишь для стандартных n. Но для любого стандартного n существует искомое m, а именно —.

Итак, несколько неформально выражаясь, нестандартное число аккумулирует в себе свойства целой последовательности стандартных чисел20.

Чтобы точнее установить опасности, связанные с нестандартными формулировками, дадим несколько контрпримеров. Контрпримеры будут использовать те нестандартные объекты, которые ближе всего по построению и свойствам к стандартным — почти стандартные. Функция называется почти стандартной, если она представляется как x f (, x), где — нестандартное число, f — стандартная функция. Аналогично, Самая популярная конструкция нестандартных моделей — через ультрапроизведения — делает это замечание несколько более точным, но не дает ему полного обоснования. Такое соображение является прекрасным нестрогим приемом, но не может быть использовано в доказательствах. Таким образом, применяйте его, когда ищете формулировку теорем, но не когда их доказываете!

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

почти стандартное множество — сечение стандартного отношения по нестандартному значению аргумента.

Приведем почти стандартные контрпримеры к двум из доказанных эквивалентностей.

Пример 10.4.1. Непрерывность. Функция sgn бесконечно мало изменяется в окрестности нуля, но разрывна в ней. Наоборот, функция x бесконечно изменяется в окрестности нуля, но непрерывна в нуле.

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

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

Упражнения к § 10. Дать нестандартные определения и доказать их эквивалентность стандартным (все явно упомянутые объекты стандартны):

10.4.1. x — изолированная точка множества X.

10.4.2. x — предельная точка множества X.

10.4.3. — предельная точка множества X.

10.4.4. Множество X конечно.

10.4.5. Множество X бесконечно.

10.4.6. Множество X ограничено.

10.4.7. Множество X неограничено.

10.4.8. Множество X всюду плотно.

10.4.9. Множество X открыто.

10.4.10. Множество X замкнуто.

10.4.11. Множество X компактно.

10.4.12. Уравнение f (x) = 0 имеет бесконечно много решений.

10.4.13. Уравнение f (x) = 0 имеет конечное число решений.

10.4.14. Уравнение f (x) = 0 имеет сколь угодно большие решения.

10.4.15. Уравнение f (x) = 0 имеет сколь угодно малые решения.

10.4.16. Последовательность an бесконечно большая.

10.4.17. Последовательность an стабилизируется.

10.4.18. Последовательность an принимает конечное число значений.

10.4.19. Последовательность an имеет 1 предельной точкой.

10.4.20. Последовательность an растет быстрее, чем bn.

10.4.21. Функция f дифференцируема в точке 0.

10.4.22. Функция f неограничена вблизи точки b.

10.4.23. Функция f ограничена на действительной оси.

10.4.24. Функция f интегрируема на [a, b].

Ко всем примерам привести почти стандартные контрпримеры.

СУПЕРСТРУКТУРЫ И ТЕОРЕМА ЛОСЯ

§ 10.5.

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

Для специалистов заметим, что здесь приведена более слабая форма теоремы Лося, чем приведенная, например, в [15]. Мы, следуя нашему базовому принципу — всячески отмежевываться от результатов, выполненных лишь для

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

классической математики, — берем здесь ту ее форму, которая может быть перенесена на кое-какие модели неклассических систем. Другое дело, что доказательство и этой формы теоремы зависит от специфических принципов классической теории множеств, но здесь уж ничего не поделаешь: как аппарат для анализа других концепций и для их представления классическая математика ничуть не хуже любой другой21.

10.5.1. Аксиома выбора, некоторые ее следствия Поскольку в доказательстве теоремы Лося и, соответственно, в построении нестандартной модели существеннейшим образом используется аксиома выбора (упомянутая ранее на стр. 104), мы начнем с ее обсуждения.

Аксиома выбора имеет внешне весьма привлекательную и простую формулировку, настолько естественную, что ее применение до начала XX века не осознавалось явно.

Таким образом, она утверждает, что для каждого всюду определенного соответствия существует вложенное в него функциональное с той же областью определения. Как говорят, функция f выбирает по элементу из каждого из множеств {y | (x, y) R}. Поэтому ее часто называют функцией выбора.

Как и любое важное математическое утверждение, аксиома выбора имеет много эквивалентных, но внешне совершенно различных формулировок. Приведем три самые важные из них.

Первая из формулировок связана с обобщением понятия прямого произведения на бесконечные семейства сомножителей. Прежде всего определим, что такое семейство. Семейство множеств — просто другое название для функции, результатами которой являются множества. Часто семейство обозначается выражением типа вместо i X(i). Аналогом n-ки, в которой i-тый элемент принадлежит множеству Xi, для произвольного множества индексов I служит функция с областью определения I, такая, что f (i) Xi. Таким образом, получаем еще одну формулировку аксиомы выбора, еще более естественную:

Прямое произведение семейства непустых множеств непусто.

Известны многие утверждения, эквивалентные аксиоме выбора. Перечислим часть из них и докажем их эквивалентность.

Предложение 10.5.1. (Теорема о вполне упорядочении) Каждое множество можно вполне упорядочить.

Доказательство. Из вполне упорядочения очевидно следует аксиома выбора, поскольку достаточно вполне упорядочить iI Xi и сопоставить каждому i наименьший элемент Xi. Докажем обратное утверждение.

Пусть дано множество X. Рассмотрим множество всех его непустых подмножеств P X = P X \. Построим для него функцию выбора f (Y ) Y для всех Y P X. Построим трансфинитной рекурсией функцию : X On, где On — класс всех ординалов.

Найдется такой минимальный ординал 0, при котором X \ {() | } =, в противном случае существовала бы инъекция из класса ординалов в X, что невозможно, поскольку класс ординалов не является множеством. Тогда ограничение функции f на { | 0 } является искомым вполне упорядочением.

Предложение 10.5.2. (Лемма Цорна) Если в частично-упорядоченном множестве X у каждого линейно упорядоченного подмножества имеется верхняя грань, то в множестве X существует максимальный элемент.

Доказательство. Рассуждаем от противного. Допустим, что в X нет максимальных элементов. Тогда для каждого элемента x X множество {y | y X & y x} непусто. Вполне упорядочим элементы множества X (это вполне упорядочение не обязано быть как-то связано с линейным порядком). Построим теперь трансфинитной индукцией функцию При каждом множество {f () | } — линейно упорядоченное подмножество X. Соответственно, оно имеет максимальный элемент, и поскольку он не наибольший, f () будет определено. Итак, мы построили инъекцию класса ординалов в множество X, чего быть не может. Таким образом, в множестве X должен быть хотя бы один максимальный элемент.

Осталось вывести аксиому выбора из леммы Цорна. Для этого докажем теорему о вполне упорядочении. Рассмотрим множество инъекций начальных отрезков ординалов в множество X. Оно естественно частично упорядочено вложением, если задано линейно упорядоченное семейство таких отображений, то его объединение также будет таким отображением. Значит, согласно лемме Цорна, существует хотя бы одна максимальная инъекция. Покажем, что она будет и сюръекцией. Если множество X \ Val непусто и — наименьший ординал, не принадлежащий Dom, то

ГЛАВА 10. НЕСТАНДАРТНЫЙ АНАЛИЗ

Возьмем такое x и положим () = x и () = () при. Полученное расширяет, а, по предположению, — максимальная инъекция. Итак, любая максимальная инъекция дает вполне упорядочение X.

Предложение 10.5.3. (Существование ретракций) Для любой сюръекции f :

X Y найдется ретракция g : Y X, такая, что g f = idY.

Доказательство. Определим для семейства непустых множеств (Xi )iI функцию : iI Xi I, сопоставляющую каждой паре (i, x) ее первый компонент. Эта функция является сюръекцией. Соответствующая ей ретракция и будет функцией выбора. Обратная импликация доказана ранее.

Теперь перейдем к более нетривиально связанным с аксиомой выбора формулировкам.

Аксиома зависимого выбора. [17] Итак, если отношение всюду определено, то для каждого элемента найдется бесконечная последовательность элементов, начинающихся с данного и связанных этим отношением.

Эта форма аксиомы выбора использована, в частности, в предложении 5.4.6.

От нее зависит, таким образом, эквивалентность определения бесконечности по Расселу и неконечности множества и то, что каждое бесконечное множество содержит счетное подмножество.

Принцип линейного упорядочивания. Каждый частичный порядок можно продолжить до линейного.

Выведем принцип линейного упорядочения из аксиомы выбора.

Доказательство. Обозначим исходное отношение порядка 0. Вполне упорядочим исходное множество X 22. После этого полного упорядочивания можно считать, что элементы X занумерованы ординальными числами, меньшими некоторого. Построим теперь ординальную последовательность отношений порядка, где при <. Пусть не является линейным порядком. Теперь возьмем элемент a с наименьшим номером, для которого имеются несравнимые с ним элементы. Среди элементов, несравнимых с a, возьмем элемент b с наименьшим номером. Возьмем отношение {(a, b)} (т. е. положим b 1 a). Возьмем транзитивное замыкание этого отношения и положим Не предполагается, что введенный полный порядок как-то связан с имеющимся у нас частичным.

Если порядок уже линейный, то положим Для предельных положим Общая схема таких определений следующая.

Имеется формула A(x1,..., xn ), не содержащая других свободных переменных, кроме явно указанных. Тогда можно ввести новый nместный предикат P посредством определения:

Очевидно, что такое определение в некотором смысле ничего нового не добавляет к старой теории. Но что значит “ничего нового”, полагается уточнить. Это может быть уточнено двумя способами — семантическим, через модели, и синтаксическим, через перевод утверждений новой теории в утверждения старой. Оба уточнения работают с двумя теориями Th1 и Th2, такими, что сигнатура 2 второй теории шире сигнатуры первой 1 и все аксиомы первой теории являются аксиомами второй. В таком случае Th2 называется расширением Th1.

Определение 12.2.1. 1. Th2 сигнатуры 1 называется консервативным расширением теории Th1 сигнатуры, если формула сигнатуры является теоремой Th2 ттт она является теоремой Th1.

2. Th2 называется несущественным расширением Th1, если имеется способ 1 перевода формул второй теории в формулы первой, сохраняющий все логические связки (т. е. (A & B) = (A) & Пример 12.2.1. Рассмотрим теорию коммутативных групп, операции в которой обозначим x + y и x. Добавим умножение и аксиомы, определяющие поле. Полученная теория является консервативным расширением теории групп, поскольку все, касающееся лишь аддитивных операций, остается без изменения, но не является ее несущественным расширением, поскольку нет средств выразить умножение через сложение.

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

Определение 12.2.2. Th2 — семантическое распространение теории Th сигнатуры на сигнатуру 1, если всякая модель Th1 может быть без изменения универса и интерпретаций понятий из продолжена до модели Th2. Th2 — семантическое несущественное расширение, если такое продолжение модели единственно.

Предложение 12.2.1. 1. Каждое несущественное расширение является семантическим распространением.

2. Каждое семантическое распространение является консервативным расширением.

Доказательство. Пункт 1. Поскольку все новые понятия определимы через старые, пункт очевиден.

Пункт 2. Поскольку всякая модель Th1 продолжается до модели Th2, очевидно, что формула исходной сигнатуры, опровергаемая на какойлибо модели Th1, опровергается и на продолжающей ее модели Th2.

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

ГЛАВА 12. ОСНОВЫ ТЕОРИИ ОПРЕДЕЛЕНИЙ

Таким образом, Th2 не добавляет новых теорем в старой сигнатуре, что и требовалось доказать.

ТЕОРЕМА КРЕЙГА ОБ ИНТЕРПОЛЯЦИИ

§ 12.3.

Рассмотрим один из важнейших результатов математической логики.

Покажем, что, если в логике доказуема импликация от A к B, то имеется промежуточная формула C, содержащая лишь общие для них понятия.

Формулировка данного результата представляется интуитивно очевидной, но на самом деле эта “очевидность” — показатель того, что мы склонны потребовать выполнения такого свойства для логической системы. Во втором томе Вы увидите, насколько легко разрушается теорема интерполяции для неклассических логик.

Пусть имеются две сигнатуры 1 и 2. Пусть сигнатура (возможно, пустая) является их пересечением. Если сигнатура пустая, то элементарными формулами данной сигнатуры будем считать и.

Теорема 12.1. (Теорема Крейга (Craig) об интерполяции) Если в классической логике доказуема формула A B, где A — формула сигнатуры 1, B — формула 2, то найдется формула C сигнатуры, такая, что в логике доказуемы импликации A C и C B.

Такая формула называется интерполяционной формулой, или интерполянтом.

Доказательство. Воспользуемся аппаратом семантических таблиц. У доказуемой формулы есть замкнутая семантическая таблица. Внесем в ее определение лишь маленькое видоизменение: противоречиями будут считаться формулы |= и =. Интерполянт построим, исходя из данной таблицы, рекурсией по дереву таблицы. Естественно, для индуктивного доказательства теорему придется несколько обобщить, сформулировав инвариант индукции.

Пусть 1, 2 — произвольные сигнатуры, — их пересечение. Секвенция такова, что формулы из подсеквенции записаны в сигнатуре 1, а формулы из подсеквенции — в 2. Пусть — вывод данной секвенции. Тогда найдется формула сигнатуры, такая, что с увеличением количества применяемых правил не более чем в два раза перестраивается в выводы секвенций { = C} и {|= C}.

Строим C рекурсией по и одновременно даем способ перестройки в два соответствующих вывода 1 и 2.

Базис. Пусть секвенция, является противоречием. Тогда противоречие |= A, = A может быть одного из четырех видов:

1. Оба его члена принадлежат.

2. Оба его члена принадлежат.

3. |= A принадлежит, а = A —.

4. = A принадлежит, а |= A —.

Противоречия последних двух типов будем называть перекрестными.

В перекрестных противоречиях формула A принадлежит сигнатуре.

Если противоречие принадлежит п. 3, то интерполянтом C будет A, а если п. 4, то ¬A. В случае 3 выводом секвенций, = C и, |= C строятся легко: будет само исходное противоречие, а в случае 4 — результат разбиения формулы ¬A.

В случае противоречия вида 1 в качестве C берем, а в случае 2 —. Один из выводов обеспечивается исходным противоречием, а другой добавленной логической константой с несоответствующей ей спецификацией.

Шаг рекурсии. Пусть индуктивное утверждение обосновано для любых выводов с числом применений правил n. Докажем его для вывода с n + 1 правилом. Рассмотрим различные применения правил и перестроим для них интерполянт.

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

Если правило — двухпосылочное, то для каждой из его посылок мы, по предположению индукции, сопоставили интерполянты C1, C2. Создадим из них новый интерполянт таким образом, чтобы применение данного правила не пропадало ни в одном из перестраиваемых выводов. Соответственно, если правило применялось к формуле из, пишем

ГЛАВА 12. ОСНОВЫ ТЕОРИИ ОПРЕДЕЛЕНИЙ

C1 C2, если к — C1 & C2. Опишем теперь перестройку вывода.

Здесь 1 и 2 — два построенных ранее модифицированных вывода, A и A2 — две части, на которые разбивается специфицированная формула A, входящая в, 1 — то, что остается от после удаления данного экземпляра A. 10 и 20 получаются ослаблениями выводов 1 и 2 соответственно. 2 получается непосредственным применением правила |= к двум построенным выводам.

И наконец, если правилом вводилась новая вспомогательная константа, опять-таки действуем таким образом, чтобы данная вспомогательная константа ввелась в обоих перестроенных выводах. Поэтому, если cn+1 вводилась формулой, то заменяем C(cn+1 ) на x C(x), где x — переменная, не входящая в C (ни свободно, ни связанно). Если же cn+1 вводилась в формуле из, заменяем C(cn+1 ) на x C(x). При перестройке вывода возможное вхождение cn+1 в интерполянт, которое может помешать введению вспомогательной константы, устраняется:

Упражнения к § 12. 12.3.1. Постройте интерполянты для следующих формул:

12.3.2. А каков же будет интерполянт, если A и B вообще не имеют общих понятий? Что можно сказать в данном случае про формулу 12.3.3. В индуктивном утверждении мы позаботились о кванторах всеобщности для сигнатур. В каком пункте нашего доказательства сигнатуры изменяются?

12.3.4. Студент Гениалькис сформулировал новую аксиоматику арифметики, в которой понятия сложения и умножения не встречаются в одной и той же аксиоме, а других операций нет (естественно, в данной аксиоматике есть принцип математической индукции).

Он, исходя из этого, установил следующий результат:

Если в арифметике доказано утверждение вида A B, где A не содержит умножения, а B не содержит сложения, то найдется формула C, содержащая лишь предикат равенства и константы, которая является интерполянтом.

Что Вы ему ответите?

ТЕОРЕМА БЕТА ОБ ОПРЕДЕЛИМОСТИ

§ 12.4.

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

Определение 12.4.1. Пусть даны сигнатура 1 и ее подсигнатура. Предикат P называется определимым через в теории Th, если в сигнатуре есть такая формула A(x1,..., xn ), свободные переменные которой x1,..., xn, что в теории Th доказуемо Теорема 12.2. (Теорема Бета (Beth, 1952) об определимости) P определим через тогда и только тогда, когда в любых двух моделях M1, M2 теории Th с одинаковыми универсами и одинаковыми значениями понятий из значения P совпадают.

Доказательство. Очевидно, что определимое понятие сохраняет свои значения во всех интерпретациях, где одинаковы значения определяющей его сигнатуры.

Чтобы доказать обратную импликацию, проведем следующее преобразование теории Th. Отдублируем все предикаты и константы, не

ГЛАВА 12. ОСНОВЫ ТЕОРИИ ОПРЕДЕЛЕНИЙ

входящие в, двойник каждого предиката обозначим Q, двойник константы — c. Двойником формулы назовем результат замены всех понятий, не входящих в, на их двойники. Теперь заменим все аксиомы теории Th, содержащие понятия, не входящие в, на их двойники. Получившуюся теорию обозначим Th. Очевидно, что всякую модель Th можно изоморфно преобразовать в модель Th и что двойник формулы выводим в Th ттт формула выводима в Th. Последнее легче усмотреть даже не из теоретико-модельных соображений, а непосредственно построив преобразование вывода.

Далее, если теория Th непротиворечива, то непротиворечива и теория Th Th. Ее модель получается просто удвоением интерпретаций понятий, не входящих в, в модели исходной теории. Теперь выведем важное следствие из предположения теоремы:

В самом деле, возьмем произвольную модель теории Th Th. Из нее естественно получаются две модели теории Th, в которых совпадают универсы и интерпретации понятий из. Значит, согласно допущению, в них совпадают и интерпретации предикатов P и P. А совпадение интерпретаций и означает истинность эквивалентности.

Теперь применяем теорему полноты и получим, что имеется вывод формулы x(P (x) P (x)) в теории Th Th. Возьмем все аксиомы, участвующие в этом выводе. Тогда в классической логике выводима формула где Ai — все задействованные аксиомы теории Th, а Bj — все аксиомы теории Th, не являющиеся аксиомами исходной теории и участвующие в выводе эквивалентности. Значит, выводима импликация являющаяся эквивалентным преобразованием формулы 12.1. Тогда выводимы следующие две формулы, которые являются переформулировками обеих импликаций данной условной эквивалентности:

Для первой из этих формул применим теорему Крейга и построим интерполянт C, такой, что Этот C и является искомым выражением P через понятия. В самом деле, C записано в сигнатуре, поскольку оно находится в общем словаре посылки и заключения импликации 12.3. Далее, в теории Th доказуемо а в теории Th — Но по изоморфизму между Th и исходной теорией тогда в теории Th. Искомая эквивалентность доказана.

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

Упражнения к § 12. 12.4.1. Покажите, что операция умножения неопределима через сложение.

12.4.2. Покажите, что деление неопределимо через сложение и умножение.

Глава 13. Неполнота и неформализуемость

ТЕОРЕМА ТАРСКОГО О НЕВЫРАЗИМОСТИ ИСТИНЫ

§ 13.1.

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

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

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

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

Заметьте, что в данном рассуждении нет никакой оценки числа шагов, необходимых для выдачи результата. Более того, оно опирается на один принцип, безусловно, приемлемый в традиционной математике, но достаточно часто оспариваемый в конструктивной, интересующейся не только истинностью формул, но и реализуемостью получающихся конструкций. Этот принцип был явно сформулирован русским математиком Тщетность надежд на полноту традиционных математических теорий доказал в 1931 г. австрийский математик Курт Гёдель, тот самый, который доказал до этого полноту классической логики. Доказательство Гёделя было весьма трудным технически, но к нынешнему времени появилась возможность дать более прозрачное его изложение. Мы начнем с результата, доказанного польским логиком А. Тарским в 1928 г., который может считаться идейной основой результата Гёделя4.

Как известно, определение истинности формул логического языка дается индуктивно. Пусть у нас зафиксировано некоторое кодирование формул логического языка термами нашего языка (в частности, такое кодирование может иметься в языках, содержащих натуральные числа, поскольку слова в данном конечном алфавите естественно кодируются как натуральные числа в соответствующей системе счисления: см. стр. 137.) Пусть, далее, кодирование настолько удобное, что мы можем выразить подстановку, т. е. построить формулу Subst(x, y, z), такую, что для любого кода a формулы A(x) с одной свободной переменной x и для любого объекта b объект zA(a, b, z) является кодом A(b). Тогда, согласно результату об описательных определениях, мы можем ввести функцию sub(A, b), вычисляющую по коду формулы A, имеющей свободную переменную, и по объекту b код формулы, являющейся подстановкой b вместо x в данную формулу. Код формулы A обозначим A.

Определением истинности по Тарскому называется такая формула Tr, что для любого кода замкнутой формулы A А. А. Марковым и носит название принцип Маркова.

Если алгоритм построен, то доказывать конечность числа его шагов можно и косвенными методами.

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

Конечно, во втором случае их поменьше, но это — разница типа разницы и ! в нестандартном анализе: одно бесконечно, а другое — невообразимо бесконечно.

Взаимосвязь между этими результатами не была очевидна ни самим Гёделю и Тарскому, ни остальным логикам до середины 40-х гг.

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Теорема 13.1. (Тарский, 1928) Если в языке теории имеется отрицание и она достаточно богата, чтобы выразить подстановку, то истинность неопределима по Тарскому.

Доказательство. В самом деле, пусть имеется определение истины Tr(x). Рассмотрим формулу B = ¬ Tr(sub(x, x)). Содержательно она утверждает, что формула ложна на своем коде. Тогда по определению и по свойству (13.1) имеем:

Таким образом, пришли к противоречию.

Конец доказательства.

Далее возникает соблазн заявить, что (хотя бы в случае полной теории) доказуемость является определением истинности по Тарскому и поэтому если в теории можно определить понятие доказательства, то она не может быть полна. Но Гёдель уловил важную ловушку, которая кроется здесь: для того чтобы доказуемость могла считаться определением истины, необходимо, чтобы можно было доказать в теории Здесь Proof(x, A ) — формула, выражающая доказуемость. Сам Тарский в эту ловушку не попался, а Гёдель показал, что такое свойство на самом деле намного сильнее непротиворечивости и не может быть выполнено для достаточно богатых непротиворечивых теорий. Тем не менее некоторое ослабление данного свойства выполнено для арифметики, если только вся наша традиционная математика имеет смысл5 :

x Proof(x, x Proof(x, A ) )ттт x Proof(x, A ).

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

Содержательно это означает, что доказать доказуемость A то же самое, что доказать само A.

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

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

Упражнения к § 13. 13.1.1. Можно ли внутри теории множеств построить определение истинности для формул, все кванторы в которых ограничены некоторым множеством?

13.1.2. А произвольным конечным множеством (возможно, своим для каждого квантора)?

АКСИОМАТИЧЕСКОЕ ОПИСАНИЕ ВЫЧИСЛИМОСТИ

§ 13.2.

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

Именно такая ситуация является практически наиболее распространенной и требует теоретического осмысления.

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

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

(Аксиома универсального алгоритма) Имеется такой алгоритм, что для любого другого алгоритма найдется его код, такой, что результаты вычисления (x) и ([, x]) совпадают для любого x.

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

Прежде всего, что является входными данными и результатами алгоритма? Из анализа аксиомы универсального алгоритма видно, что несколько неудобно брать в качестве таких данных сами объекты. Лучше пользоваться их структурами. Таким образом, лучше брать не универс U, а множество кортежей над ним U. Из технических соображений к U целесообразно добавить два логических значения ИСТИНА и ЛОЖЬ (если их там не было).

Раз у нас есть множество кортежей, то нужно иметь элементарные операции над кортежами. Практика и теория совместно показали, что достаточно иметь одну двуместную операцию APPEND (см. (5.3)), присоединяющую свой второй аргумент к первому. Кроме того, нужны несколько одноместных операций: две, значением которых являются произвольные кортежи либо объекты, — TAIL(x), выделяющая последний элемент кортежа x, BODY(x), удаляющая из кортежа его хвост, т. е. последний элемент;

и четыре предиката:

ATOM Проверяет, является ли x элементом исходного множества U.

SIMPLE Проверяет, что x — кортеж из одного элемента.

Проверяет, что x — атом, равный ИСТИНА.

Проверяет, что x — пустой кортеж [ ].

TRUE NIL Пустой кортеж будем обозначать NULL. Через эти операции выражение, стоящее в аксиоме об универсальном алгоритме, записывается следующим образом:

Конечно, мы не будем писать в стиле (13.4); это выражение просто показывает, как записать кортеж через имеющиеся у нас операции, и дает возможность в дальнейшем спокойно использовать конечные кортежи с фиксированным числом элементом, пользуясь следующим соглашением:

Выражение APPEND( (APPEND(NULL, t1 ), ), tn ) обозначается [t1,..., tn ].

Термы, построенные из заданных известных алгоритмов и предикатов при помощи перечисленных выше операций и имеющие лишь одну свободную переменную x, называются простейшими композициями алгоритмов. В компьютерах, как Вы знаете, исполняется только тот алгоритм, который переведен программой-транслятором с языка описаний алгоритмов на язык самой машины. Программа-транслятор — универсальный алгоритм в смысле нашей аксиомы, а алгоритмический язык — кодирование алгоритмов. Из рассмотрения данного частного случая кодирования видно, что некоторые простые операции над программами тоже должны быть алгоритмичны, а именно:

(Аксиома композиций) Если имеется простейшая композиция T (1,..., n ) переменных алгоритмов 1,..., n, то имеется алгоритм, выдающий для кортежа кодов Докажем Предложение 13.2.1. Из двух принятых выше аксиом следует невозможность построить всюду определенный универсальный алгоритм.

Примечание для математиков. Такие кодирования алгоритмов являются главными вычислимыми нумерациями (см. [16]), но мы не прикладывали никаких усилий к тому, чтобы минимизировать требования и получить в точности это понятие.

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Доказательство. Рассмотрим выражение Это — простейшая композиция, и она является алгоритмом. Пусть — ее код. Тогда ([, ]) есть по определению универсального алгоритма (). По определению, последнее выражение записывается как [([, ]), NULL]. Таким образом, мы получили, что кортеж ([, ]) не меняется после добавления еще одного элемента, чего не может быть.

Значит, значение ([, ]) не определено.

Итак, мы видим, насколько увязываются между собой элементы формализации понятий. Приняв две естественных аксиомы вычислимости, мы уже не имеем права делать понятие функции математическим представлением понятия алгоритма. Мы должны рассматривать, как минимум, частично определенные функции. Таким образом, слишком рано заменив слова естественного языка на “точные” математические термины, мы можем зайти в тупик. Сначала уясняйте задачу и ситуацию, минимально пользуясь символами, а затем уже подставляйте действительно точные, но подходящие к случаю, понятия.

Заметим, что результат о неопределенности не запрещает возможности недетерминированных алгоритмов, которые при одних и тех же начальных данных могут давать разные результаты. Поэтому мы везде старались не использовать знак равенства, а говорить осторожнее: дает тот же результат. Утверждение, что алгоритм на входных данных a может давать результат b, обозначается Равенство будем использовать лишь в том случае, если результат имеется, и только один.

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

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

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

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

Определение 13.2.1. Если t — простейшая композиция, то t — условный терм.

Если P — простейший алгоритмический предикат, а t и u — условные термы сигнатуры, то условный терм той же сигнатуры. Его значения определяются следующим образом:

Таким образом, если условие не определено, то условный терм тоже не определен, а вот если одно из выражений не определено, то условный терм может быть определен.

(Аксиома о рекурсивном определении) Если все функции сигнатуры проинтерпретированы как алгоритмы, не входит в, а t(, x) — условный терм со свободной переменной x в сигнатуре, пополненной, то имеется алгоритм, такой, что Его определение записывается в форме Пример 13.2.1. Рекурсивное определение функции, выделяющей из кортежа первый элемент, может быть задано следующим образом:

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

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

Пример 13.2.2. Поскольку мы доказали, что не все алгоритмы определены на всех значениях, естественно ожидать, что наша главная операция рекурсивного определения приводит к неопределенным функциям.

И в самом деле, рассмотрим ERR(x) APPEND(ERR(APPEND(x, NULL)), NULL).

Вычисление данного алгоритма не может привести ни к какому результату ни при каком значении x. В самом деле, результат должен быть кортежом, поскольку последней применяется функция APPEND. Тогда результат для [x, NULL] должен быть на один элемент короче, и так далее. Получается бесконечный спуск в длинах значений.

Заметим, что при стандартной семантике рекурсивных процедур не определен гораздо более простой алгоритм:

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

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

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

такой алгоритм называется вычислимым предикатом). Множество называется перечислимым, если имеется однозначный алгоритм, дающий значение ИСТИНА тогда и только тогда, когда элемент принадлежит данному множеству8.

Например, множество троек A, a, b, где A — код алгоритма, таких, что алгоритм с кодом A дает значение b на входных данных a, является перечислимым, но не разрешимым.

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

(Аксиома перечислимости) Имеется такой разрешимый предикат, что для любого алгоритма (a) b тогда и только тогда, когда имеется кортеж C, первым членом которого является пара [, a], все последующие члены имеют вид [ i, ai ], где i — некоторый алгоритм, а последний — [NULL, b], на котором (C) = ИСТИНА.

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

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

Порою нужна не разрешимость, а более слабое понятие: отделимость.

Но, конечно же, этот алгоритм может не давать никакого значения, если элемент множеству не принадлежит.

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Определение 13.2.3. Множество Z отделяет два непересекающихся множества X и Y, если X Z, Y Z.

Таким образом, отделимость — понятие относительное. Она зависит от рассматриваемой системы множеств и универса.

Теорема 13.2. (Теорема о неотделимости) Имеются два перечислимых множества X и Y, таких, что нет разрешимого множества Z, отделяющего их.

Идея доказательства. В качестве таких двух множеств можно взять Если предикат равенства вычислим, то любые два одноэлементных множества отделимы. Но, скажем, для действительных чисел естественно, в частности, рассматривать вычислимость на базисе некоторых стандартных непрерывных аналитических функций (, +,, \, exp, sin, cos, ln... ) и предиката 0 n 1, a для 0 — NULL;

Z(n), предикат, проверяющий, равен ли его аргумент 0.

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

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

PLUS([m, n]) if Z(n) then m else PLUS([m, Pd(n)]) fi.

Другой способ определения алгоритмов дан в определении оператора Mu, строящего минимальное значение n, при котором ([m, n]) = 0.

Muk(, [m, k]) if Z(m, k) then k else Muk(, [m, S(k)]) fi;

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Здесь сначала вводится вспомогательный алгоритм, а сама рекурсия идет в другом направлении, чем обычно. Такая операция часто обозначается квантором минимизации, введенным Д. Гильбертом:

где P — алгоритмический предикат.

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

Алан Тьюринг — английский математик, в конце 30-х гг. создавший математическую модель простейшей вычислительной машины, пригодной для вычисления всего того, что можно фактически сделать в математике. Эта машина имеет память в виде ленты, в каждой ячейке которой стоит символ 0 либо 1, и программу, записанную в постоянной памяти и неизменяемую в момент вычисления, каждая команда в которой состоит в анализе одной из ячеек ленты, записи туда нового значения, сдвиге на одну ячейку влево или вправо и переходе к явно указанной следующей команде. Во время второй мировой войны он внес немалый вклад в победу союзников, обеспечив нечитаемость английских шифров для немцев и дешифровку немецких, а также улучшив методы расшифровки сигналов радиолокаторов. После войны он опубликовал небольшую книгу о только что появившихся тогда компьютерах, в которой, в частности, заявил, что вопрос «Может ли машина мыслить?» должен решаться не на эмоциональном уровне, а при помощи точных критериев того, что такое мышление. Он предложил в качестве одного из таких критериев тест Тьюринга:

Если машина может длительное время поддерживать телетайпный диалог с человеком, сидящим в другом помещении и не знающим, кто его партнер, и тот уверен, что разговаривал с человеком, то она может считаться разумной.

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

Из этого тезиса следует строгое утверждение, которое доказано для всех используемых в математике понятий алгоритма: все они эквивалентны в том смысле, что алгоритмически определимые функции над минимальным базисом понятий совпадают10. Но еще более важно то, что для всех явно выделенных в математике способов построения алгоритмов найдено их представление, согласующееся с тезисом Черча11.

Упражнения к § 13. 13.2.1. А почему мы не взяли в качестве множества структур более простое множество U ?

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

Почти сразу после публикации книги А. Тьюринг умер.

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

Рекурсивные схемы — один из мощнейших в смысле относительной определимости аппаратов теории алгоритмов.

Есть одно исключение, найденное автором. Если имеются вращающиеся черные дыры, то в принципе можно организовать вычислительный процесс таким образом, чтобы получить ответ на неразрешимую задачу, но при этом нужно самому успешно совершить путешествие сквозь такую черную дыру в другую вселенную. Таким образом, в некотором смысле тезис Черча и общая теория относительности друг другу противоречат. На самом деле именно логики порою выдвигали обоснованные возражения против теории относительности, слишком часто подвергавшейся неквалифицированной критике. Так, Курт Гёдель построил пример вселенной, в которой время может идти по кругу, и тем самым опроверг мнение Эйнштейна, что из общей теории относительности должна следовать однонаправленность времени (после чего сам А. Эйнштейн выдвинул эту работу на одну из самых престижных научных премий). Серьезная теория требует глубоких возражений, а глубинные взаимосвязи научного знания гораздо сильнее, чем можно вообразить, наблюдая современную науку, разделенную на почти невзаимодействующие отрасли.

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

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

13.2.3. А почему это мы не потрудились ввести логические связки в аксиоматику алгоритмов? Можно ли их там выразить?

13.2.4. Верно ли, что разрешимые множества образуют булеву алгебру?

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

13.2.6. Постройте алгоритм, вычисляющий соединение кортежей.

13.2.7. Пусть алгоритм ADD([n, m]) определен тогда и только тогда, когда n, m — атомы, являющиеся целыми числами, и выдает их сумму. Постройте алгоритм SUM суммирования всех членов кортежа.

13.2.8. Постройте алгоритм умножения двух натуральных чисел.

13.2.9. Постройте предикат, проверяющий равенство двух натуральных 13.2.10. В наших последних примерах была одна вольность речи: мы определяли рекурсией не (x), а ([m, n]). Как ее устранить? Намного ли удлинятся при этом определения?

13.2.11. Студент Лыцаренко дал следующее доказательство того, что при выполнении аксиомы перечислимости любое перечислимое множество с перечислимым дополнением разрешимо:

Пусть алгоритм перечисляет само множество, а — его дополнением. Рассмотрим алгоритм типа алгоритма британского музея. Будем перебирать все кортежи из пар, первая пара в которых [, a] либо [, a], и проверять каждый из них универсальным интерпретатором, не является ли он вычислением, и если является, получилась ли в результате истина. Поскольку один из алгоритмов перечисляет множество, а другой — его дополнение, в конце концов один из них выдаст истину.

Можете ли Вы найти слабое место в данном рассуждении, и когда 13.2.12. Студент Классиков заявил, что не всюду определенные функции — это извращение конструктивистов и информатиков, без них всегда можно обойтись. В самом деле, дополним наш универс элементом ОШИБКА. Положим, что любой кортеж, содержащий такой элемент, равен ему, и что любой алгоритм на аргументе ОШИБКА выдает значение ОШИБКА, и тогда все становится на свои места. Неопределенный в данной точке алгоритм просто выдает в ней значение ОШИБКА. Можете ли Вы что-нибудь возразить?

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

13.2.14. Обобщите по возможности теорему Райса на случай, когда экстенсиональный алгоритм дает на различных функциях два отделимых значения.

ПРЕДСТАВИМОСТЬ ЧЕРЕЗ ДОКАЗУЕМОСТЬ

§ 13.3.

В данном параграфе и далее до конца главы теории, если иное явно не оговорено, имеют разрешимое множество аксиом12.

Выразимости понятий порою недостаточно для того, чтобы корректно работать с ними формальными методами. Дело в том, что даже выразимые понятия могут находиться в достаточно сложных отношениях с понятием доказательства. Если нечто — истина, это не обязательно можно доказать принятыми формальными средствами13. Поэтому наНа практике неясно, как использовать теорию, если даже понятие ‘быть аксиомой’ нельзя проверить.

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

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

до посмотреть, для каких же классов понятий доказуемость совпадает с истинностью.

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

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

Сигнатура содержит предикат равенства, константу 0 и три функциональных символа:

одноместный S, интерпретируемый как прибавление 1;

два двуместных — сложение и умножение, с обычной интерпретацией.

Сложение и умножение будем записывать как бинарные операции.

Теория имеет бесконечно много аксиом, но почти все они14 выражаются единой формулой со свободной предикатной переменной: принципом математической индукции.

Следующая аксиома утверждает, что 0 — начальный элемент натурального ряда:

Далее идет свойство, утверждающее его линейность:

Далее — свойства сложения, умножения и возведения в степень15, а на самом деле их рекурсивные определения через S:

В математике слова ‘почти все’, как правило, имеют точный смысл. В частности, для счетного множества это почти всегда (уже в обыденном смысле) означает ‘всегда, за исключением конечного числа элементов’. Тем не менее на математическое ‘почти всегда’ тоже нужно полагаться с оглядкой: ведь конечное число исключений может быть больше, скажем, 1010.

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

А теперь легко увидеть, что любое число n представляется как Такое выражение будем называть изображением числа и обозначать просто n. Содержательной индукцией легко показать, что доказывается, и даже без помощи аксиомы математической индукции16, n = m для всех отличных друг от друга чисел, что, если P — замкнутый терм, а n — его значение, то доказывается P = n, а если n не является его значением, то доказывается P = n. Итак, на замкнутых элементарных формулах арифметики в любой непротиворечивой теории, содержащей перечисленные выше аксиомы, истинность совпадает с доказуемостью, а ложность — с доказуемостью отрицания.

Определение 13.3.1. Формула A() арифметически разрешима, если при каждом наборе значений n A( ) либо ¬ A( ) доказуемо в арифx метике.

Очевидно, что пропозициональная комбинация арифметически разрешимых формул арифметически разрешима.

Поскольку понятие вывода алгоритмически проверяемо и, значит, задается рекурсивным предикатом, можно построить такие полиномы PP и QP, что формула выражает отношение ‘n является кодом вывода формулы с кодом A’.

S(x) = n. Следующая группа результатов уже доказывается математической индукцией:

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

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Из них следует, что из арифметической разрешимости A(x, y ) следует арифметическая разрешимость т. н. конечных квантификаций:

Итак, арифметическая разрешимость замкнута еще и относительно кванторов по конечным отрезкам натурального ряда. Таким образом, свойство ‘быть простым числом’, выразимое формулой арифметически разрешимо. В связи с данным предикатом нам понадобится и известная теорема Евклида о бесконечности множества простых чисел. Она, конечно же, доказывается в формальной арифметике, хотя тот метод доказательства, который приводится учебниках:

Пусть p — наибольшее простое число. Возьмем число p! + 1. Оно не может делиться ни на одно из простых чисел до p, поскольку дает для каждого из них остаток единица.

Значит, оно либо само простое, либо делится на простое число, большее p. Полученное противоречие доказывает теорему.

в формальной арифметике прямо не проходит из-за отсутствия функции факториал17.

Докажем сначала лемму о том, что для каждого числа n имеется m, делящееся на все числа от 1 до n. Для 0 таким числом является, например, 1. Теперь пусть такое число есть для n. Умножая его на n + 1, получаем искомое число для n + 1.

Пусть p — произвольное простое число. По лемме возьмем число, делящееся на все числа до p. Обозначим его kp. Добавив к нему 1, получаем число, не делящееся ни на одно простое число до p. Но kp + 1 либо само является простым числом, либо делится на некоторое простое число. И в том, и в другом случае получающееся простое число больше p.

По разбору случаев теорема доказана.

На самом деле функция факториал, как и практически все другие используемые в математике вычислимые функции, определима в арифметике, но путь к этому определению идет через теорему Евклида.

Теперь можно заметить, что любое натуральное число может рассматриваться как кортеж натуральных чисел. В самом деле, возьмем разложение n > 1 на простые множители. Оно имеет вид Поскольку степень максимального простого числа, входящего в разложение n, больше 0, мы добавили 1 к ak. Так что 1 естественно считать кодом пустого кортежа, а n — кодом Еще одно важное свойство арифметической разрешимости — возможность использовать без ее нарушения определимые функции с арифметически разрешимым графиком. В самом деле, докажем следующее.

Определение 13.3.2. Функция f называется арифметически представимой, если имеется формула A(x, y), для которой:

3. На стандартном натуральном ряде истинно x 1y A(x, y).

4. A(x, y) арифметически разрешимо.

Предложение 13.3.1. Если формула B(x, y) арифметически разрешима, а функция f — арифметически представима, то арифметически разрешима и формула B(f (x), y).

Доказательство. Рассмотрим расшифровку A(f (x), y), а именно, A(n, m) для любых изображений чисел истинна в любой модели тогда и только тогда, когда m = f (n) (это следует из арифметической разрешимости). Далее, вообще для любого элемента a модели арифметики A(n, a) истинно тогда и только тогда, когда f (n) = a (это следует из однозначности). Значит, A(f (n), k) доказуемо тогда и только тогда, когда доказуемо A(m, k) для соответствующего значения m = f (n).

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Теперь легко обосновать арифметическую представимость нескольких функций.

Цифры в позиционном представлении числа мы начинаем нумеровать с последней, в соответствии со степенями основания системы. Так что последняя цифра — нулевая, предшествующая ей — первая, и т. д18.

Предложение 13.3.2. Пусть A(x) — арифметически разрешимая формула, для которой задана определимая в арифметике возрастающая функция с арифметически разрешимым графиком, такая, что в промежутке от (n) до (n+1) по крайней мере одно число m удовлетворяет A(m). Тогда свойство “Быть k-тым числом, для которого выполнено A” арифметически разрешимо.

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

Доказательство. Рассмотрим формулу & j(j < dig(n, (n), m) & A(j) i(i < n & dig(i, (n), m) = j)) Она утверждает, что число m кодирует в системе с основанием (n) первые n последовательных чисел, для которых выполнено A. Формула (13.10) удовлетворяет условиям определения 13.3.2. Следовательно, можно определить функцию CODE(n), выдающую по n код первых n элементов множества {i | A(i)}. Искомый элемент представляется как dig(n, (n), CODE(n)).

Следствие. Функция Prim(n), вычисляющая n-тое простое число, представима в арифметике.

Для доказательства следствия достаточно сослаться на известный в теории чисел факт, что между n и n2 обязательно имеется хотя бы одно простое число, и взять в качестве, скажем, n n4.

А теперь можно построить арифметически разрешимый предикат утверждающий, что n является кодом вывода в нашей теории Th формулы A(m). Мы не будем проводить это построение явно, поскольку его осуществимость следует из тезиса Черча.

Упражнения к § 13. 13.3.1. Почему мы не сделали напрашивающегося вывода, что в условиях определения 13.3.2 формула x 1y A(x, y) истинна на любой модели арифметики и, следовательно, по теореме полноты, 13.3.2. Почему мы не ослабили в определении 13.3.2 требование доказуемости x 1y A(x, y) до ее истинности на стандартном натуральном ряду, ведь все равно A арифметически разрешимо?

13.3.3. Студент Гениалькис обвинил автора в устарелости изложения и предложил следующий подход:

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Воспользуемся для установления арифметической разрешимости одним тонким результатом, установленным российским ученым А. Матиясевичем, доказательство которого приводить не будем.

Диофантово уравнение — равенство двух многочленов (возможно, от многих переменных) с положительными коэффициентами.

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

Теорема 13.4. Для любого рекурсивно перечислимого множества X найдутся два многочлена PX (n, m), QX (n, m), такие, что Таким образом, найдется многочлен с целыми коэффициентами, для которого данное множество является проекцией множества его корней на первую координату19 и формула (13.11) представляет данное множество в арифметике, поскольку, очевидно, если она истинна, она доказуема.

Можете ли Вы что-нибудь возразить?

13.3.4. А почему мы не взяли в качестве для простых чисел n. n2 ?

НЕПОЛНОТА

§ 13.4.

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

Поскольку данный многочлен, как правило, содержит немало вспомогательных переменных, неточно выражаться, что X представляется как его множество корней.

Далее, если можно доказать ее отрицание, то отсюда будет следовать существование ее доказательства, но теория непротиворечива, и отрицание ее тоже не может быть доказано.

Но последняя часть данного рассуждения содержит скрытую ловушку: существование доказательства следует лишь семантически в стандартной модели арифметики, и поэтому мало, чтобы теория была непротиворечива, нужно, чтобы ее арифметические теоремы были истинны на стандартном натуральном ряду. Сам Гёдель заметил эту ловушку и явно ее указал, а через несколько лет американский логик Дж. Россер привел более тонкую конструкцию, которая действует в любой непротиворечивой теории и позволяет получить ряд обобщений результатов о неполноте.

Rosser(n, A ) = Proof(n, A, A ) Эта формула устанавливает недоказуемость самой себя более тонким способом: она утверждает для своего вывода существование вывода собственного отрицания с более коротким кодом.

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

Пусть теперь имеется доказательство отрицания формулы (13.14).

Тогда это доказательство имеет код n0. Для произвольного k > n0 доказывается заключение импликации из формулы Россера, а k n0 лишь конечное число, и по арифметической разрешимости и по непротиворечивости рассматриваемой теории для них можно установить, что ложна посылка. Итак, из доказуемости отрицания формулы Россера следует сама формула Россера.

Теорема 13.5. (Теорема Гёделя о неполноте в форме Россера) По любой непротиворечивой теории Th, содержащей арифметику, можно построить такую формулу RT h, что ни она сама, ни ее отрицание не доказуемы в Th.

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Есть одно любопытное неформальное следствие теоремы о неполноте, на фундаментальный логический характер которого впервые обратил внимание Брауэр20 в 1908 г.

Пусть некий институт математики взял заказ на вычисление оптимального значения некоего параметра, который может изменяться от до 1. После годичных глубоких исследований выдана теорема о том, что искомое оптимальное значение есть 0, если не существует максимального простого числа-близнеца, и sin p, если таким числом является p.

Поскольку число иррациональное, sin p может оказаться где угодно на отрезке (1, 1). Спрашивается, получил ли заказчик хоть какую-то информацию в результате данного, с точки зрения классической логики, однозначного и полностью определенного ответа?

Упражнения к § 13. 13.4.1. А как же теория, рассматривавшаяся нами в главе, посвященной нестандартному анализу, аксиомами которой являются все истинные формулы арифметики? Она ведь содержит формальную арифметику, непротиворечива, но полна.

Это было сделано в его диссертации, носившей вызывающее название: «О недостоверности логических принципов». В ней обосновывалось положение, что классическая логика была создана для конечных объектов, и поэтому при ее применении к бесконечным, идеальным объектам должны обязательно возникать несоответствия тому, чего мы могли бы ожидать при прямом переносе примитивных результатов. В частности, он обратил внимание на то, что если мы желаем, чтобы доказанное утверждение с квантором существования x A(x) действительно давало построение такого x, и при этом допускаем бесконечные множества (хотя бы совокупность натуральных чисел), то необходимо отказаться от закона исключенного третьего A ¬ A и от закона двойного отрицания ¬ ¬ A A. В 1908 г. уже было известно, что некоторые математические теоремы о существовании не дают построений, но такие теоремы имелись лишь в теории множеств и использовали аксиому выбора, и поэтому бытовало общее мнение, что избавиться от них можно пересмотром математических аксиом. Брауэр же подчеркнул, что никакой пересмотр конкретных аксиом здесь не поможет, что и подтвердилось через два десятилетия.

ВОКРУГ ТЕОРЕМЫ ГЁДЕЛЯ

§ 13.5.

Название данного параграфа заимствовано у К. Подниекса, который так назвал свою книгу [24]21. Кроме того, в главе существенно использованы идеи книги [14].

Теорема Гёделя о неполноте — результат, плохо приемлемый психологически для многих математиков и гуманитариев. Она подрывает вульгарно понимаемую веру в познаваемость мира научными методами, являющуюся одной из догм ‘религии прогресса’: оказывается, что даже самая точная из наук не может познать даже простейшее множество объектов — натуральные числа. Поэтому весьма распространенной являлась реакция, когда теорема Гёделя игнорировалась как не имеющая отношения к реально используемым в математике утверждениям.

Первую брешь на данном пути пробил результат Коэна о неразрешимости континуум-гипотезы в традиционной системе теории множеств.

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

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

В 20-х гг. английский математик П. Рамсей доказал интересную теорему, вариант которой для конечных множеств мы приведем:

Теорема 13.6. (Теорема Рамсея) Для каждого k найдется такое число l, что в произвольном графе с l вершинами найдется либо полный подЗначительная часть материала также ведет начало от данной книги, являвшейся одним из самых глубоких комментариев к теореме Гёделя. Интересно, что ее постигла судьба многих умных работ: рецензия на нее (весьма авторитетного логика, славившегося дотошностью) была просто разгромной. Более того, в книге Подниекса автор заметил элементы того, что он пытается проводить как систему здесь: многоуровневого критического мышления, когда положительный результат на одном уровне часто означает отрицательный на другом, и наоборот. Видимо, эта особенность книги и вызвала раздражение мощного, но одноуровневого ума рецензента.

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

граф с k вершинами, либо такие k вершин, что никакая пара из них не связана дугой.

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

В середине 70-х гг. было доказано, что имеется такая оценка, которая не может быть обоснована в арифметике, но обосновывается в теории множеств. А далее пошла целая серия результатов, которые установили, что оценку можно улучшать и улучшать, но каждое улучшение требует все более и более сильных фрагментов, а затем и расширений, традиционной теории множеств.

Но ведь теорема Рамсея может использоваться (и на самом деле неоднократно использовалась) для обоснования вычислительных алгоритмов, и здесь вопрос о величине числа l приобретает важное значение.