Непейвода Н.Н. Прикладная логика

Подождите немного. Документ загружается.

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

271

Интересно, что после полета в области идеальных понятий матема-

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

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

а теория сложности вычислений — к современным надежным шифрам.

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

интегральных схем и т. п.

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

Пользуясь теоремой Мальцева о компактности, построим несколько не-

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

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

и 1, операцию сложения натуральных чисел и, возможно, другие опера-

ции.Пусть задана некоторая арифметическая теория Ar в данном языке

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

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

отношений соответствуют их содержательному смыслу. Такую модель

будем называть стандартной

Мы уже видели на примере теории Q из упражнения 8.2.5, как стро-

ятся нестандартные модели для слабых подсистем арифметики. Для

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

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

материальной деятельности.

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

условие об истинности аксиом на стандартной модели содержит глубоко спрятанный

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

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

скольку любая попытка его обоснования ведет к порочному кругу — мы неявно пользу-

емся другой формой этого же принципа. Но степень уверенности математиков в истин-

ности арифметических теорем на стандартной модели, конечно же, неизмеримо выше

степени обоснованности любого естественнонаучного утверждения. Все последующие

рассмотрения затрагиваются данным замечанием лишь в том отношении, что нестан-

дартная модель гораздо сильнее привязана к конкретной форме математики, изучаемой

Вами в стандартных курсах, — классической математике, чем до сих пор рассмотрен-

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

красивые методы нестандартных моделей быстро перестают действовать. Это не дис-

кредитирует их. Если бы Вам комментировали переносимость других математических

результатов, то Вы были бы “приятно” изумлены, насколько тонка грань, отделяющая

устойчивые по отношению к пересмотру основ математики теоремы от столь же не-

устойчивых, как приведенные в данной главе, и насколько много таких неабсолютных

теорем.

272

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

сильных систем (например, с индукцией) нестандартную модель явно

не построишь (и доказано,что вообще нет нестандартных моделей с вы-

числимыми операциями сложения и умножения). Но их существование

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

доплатонистский миф о том, что математика имеет дело с абсолютными

понятиями, и открывающим путь к новому классу методов — методам

нестандартных моделей.

Казалось бы, что уж теория, составленная из всех формул, истинных

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

что это не так.

Пусть

— теория, состоящая из всех формул данной сигнатуры,

истинных на множестве натуральных чисел. Пополним сигнатуру кон-

стантой ω и зададим следующие аксиомы (их бесконечное число; если

в сигнатуре имеются константа для данного натурального числа, то n

означает такую константу; в противном случае это терм 1 + ∙∙∙ + 1

| {z }

n раз

ω > 0, ω > 1, . . . , ω > n, . . . (10.1)

Дополнительные аксиомы обозначим Th

. Рассмотрим вопрос о не-

противоречивости теории Tr

. Сама по себе Tr

, очевидно, не-

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

чисел. Точно так же непротиворечива и теория Th

, поскольку она не

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

личия 0, 1 и операции сложения, и в качестве ее модели можно взять,

скажем, N ∪ {ω}, а + доопределить для ω следующим образом:

x + ω = ω + x = x.

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

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

Для доказательства непротиворечивости

воспользуемся

теоремой о взаимной непротиворечивости. Если к Tr

добавить конеч-

ное число аксиом Th

, то получившаяся теория будет непротиворечива.

В самом деле, в этом конечном подмножестве аксиом имеется аксиома с

наибольшим n.Обозначим его n

.Тогда, если придать ω значение n

+1,

то данный фрагмент Tr

имеет моделью просто стандартный на-

туральный ряд!

Итак,

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

Эта модель называется нестандартным натуральным рядом и обозна-

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

273

чается N

∗

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

ствами.

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

ные на стандартной модели, будут истинны и на

∗

А как же с существованием бесконечно большого числа

ω? Но по-

нятие «бесконечно большое» задается не одной формулой, а их беско-

нечной последовательностью, так что его просто не существовало в ис-

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

шиеся в исходном языке, носят в нестандартной модели название “стан-

дартных”.

А теперь вопрос: существует ли наименьшее бесконечно большое

натуральное число? Конечно же, нет. Ведь

ω 6= 0, а для всякого нату-

рального числа n, отличного от 0, существует число n − 1. Так что не-

стандартный натуральный ряд принципиально отличается от ординаль-

ных чисел, лишь обозначение бесконечно большого числа у них одно и

то же. Если в ряду ординальных чисел существуют лишь все б

ольшие

и б

ольшие бесконечности типа ω

, то здесь иерархия бесконечностей

продолжается в обе стороны. Для ω существуют и 2 ∙ ω, и [ω/2]

, и

[

√

ω ]

Итак, в принципе нестандартный натуральный ряд открывает воз-

можность использовать бесконечно большие числа как идеальные эле-

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

нем тогда и только тогда, когда они истинны на исходном натуральном

ряду. Но не зря в XVII–XVIII вв. пользовались не бесконечно большими

натуральными числами, а бесконечно малыми и бесконечно большими

действительными. Нестандартный натуральный ряд заработал лишь в

сочетании с нестандартной действительной осью.

Упражнения к § 10.2

10.2.1. Что получится в результате деления нацело бесконечно большо-

го числа на бесконечно большое?А конечного на бесконечно боль-

шое? А бесконечно большого на конечное? А умножения нуля на

бесконечно большое?

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

элемента.

274

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

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

∙∙∙

n раз?

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

В принципе построение нестандартной действительной оси точно такое

же, как нестандартного натурального ряда. Берем какую-либо теорию,

состоящую из истинных утверждений об R и пополняем ее новой кон-

стантой ω, представляющей бесконечно большое число. Но здесь име-

ется одна скрытая ловушка, делающая такое построение зависимым от

тонких гипотез современной классической математики и начисто разру-

шающая его при переходе к чуть-чуть нетрадиционной математике.

Если натуральных чисел счетное множество и вполне можно иметь

константы для них всех, то действительных чисел — несчетное множе-

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

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

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

так не из лени и не из упрощенства

, а потому, что логический статус

теоремы полноты для счетных и более чем счетных теорий совершен-

но различный: первая доказывается практически абсолютно, а вторая

зависит от одной из самых сомнительных аксиом теории множеств —

аксиомы выбора, либо же от ее следствия, что каждое множество можно

вполне упорядочить.

Применение в полную силу всех особенностей традиционной мате-

матики при построении нестандартной действительной оси связано с

тем, что в математическом анализе интенсивно используются и множе-

ства, и семейства множеств, так что нужно позаботиться о сохранении

Плоское возражение о том, что на практике все равно не встречается более чем счет-

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

счетности действительных чисел, приведенное на стр.109, как говорят, абсолютно, оно

не зависит ни от каких гипотез теории множеств и переносится практически в какую

угодно другую известную математику, так что несчетные множества не слишком боль-

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

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

одними конечными объектами! Вспомните, что говорилось об идеальных объектах.

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

275

не только суждений первого порядка, но и других, говорящих о структу-

рах, составленных из стандартных объектов. К вопросу об этом мы вер-

немся ниже, в параграфе 10.5, который может быть опущен без всякого

ущерба для дальнейшего, если Вы готовы принять на веру, что такое

обоснование есть.

Итак, мы считаем, что в число стандартных объектов в математиче-

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

в анализе множества и т. д.

Нестандартная действительная ось строится таким образом, что все

свойства, выразимые на языке многосортной логики предикатов с пе-

ременными по действительным числам как исходному множеству и по

всевозможным функциям и множествам из ранее построенных типов

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

действительной оси

∗

принцип сохранения выглядит следующим обра-

зом:

Принцип переноса

Пусть

A — произвольная формула логики предикатов с пе-

ременными и кванторами по числам, их функциям и мно-

жествам и т.п., имеющая свободными переменными x

, ...,

, где τ

— тип переменной x

. Пусть a

, ..., a

— произ-

вольные объекты из стандартной интерпретации, соответ-

ствующие по типам переменным x

. Тогда

R |= A(a

, . . . , a

) ⇔ R

∗

|= A(a

, . . . , a

Подытожим:

1. При построении нестандартной модели множество действитель-

ных чисел пополняется до R

∗

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

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

∗

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

жества функций и т. д.

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

сопоставляется в нестандартной модели множество нестандартных чи-

сел,каждая функция продолжается на соответствующее ее области опре-

деления подмножество нестандартной оси.

276

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

Пример 10.3.1.

Множеству всех действительных чисел

соответствует

в нестандартной модели множество всех нестандартных действитель-

ных чисел

∗

. Множеству всех действительных чисел без нуля

R \ {0}

соответствует

∗

\ {0}

, поскольку сохраняется его характеристическое

свойство

{x ∈ R | x 6= 0}.

Начнем с терминологии, касающейся нестандартной модели.

Определение 10.3.1. (Объекты нестандартной модели)

Объект назы-

вается

стандартным

, если он имелся в исходной модели. Множество

или функция называются

внутренними

, если они входят в нестандарт-

ную модель. Множество или функция —

внешние

, если они не входят в

нестандартную модель.

Число

конечное

, если оно меньше по модулю некоторого стандарт-

ного числа. Число

бесконечно большое

, если оно по модулю больше лю-

бого стандартного числа. Число

бесконечно малое

, если оно по модулю

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

Прежде всего отметим некоторые свойства этих понятий, отнюдь не

являющиеся сюрпризом. Сюрпризы еще будут!

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

над конечными числами конечные.

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

3. При делении конечного числа

a на бесконечно большое ω получа-

ется бесконечно малое число

4. При делении конечного числа

a 6= 0 на бесконечно малое ε 6= 0

получается бесконечно большое число

Итак, стандартные объекты переносятся из стандартной модели в

расширенную. Если сами по себе числа либо другие стандартные ба-

зовые объекты можно просто отождествить с их нестандартными обра-

В отличие от того, что может случиться в теории пределов, если a 6= 0, то

6= 0.

В отличие от того, что может случиться в теории пределов, если ε 6= 0, то

= 0. А

выражения

остаются бессмысленными.

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

277

зами

, то для множеств и функций (и вообще объектов высших типов)

ситуация сложнее. Ясно, например, что нестандартным образом множе-

ства натуральных чисел N служит множество нестандартных натураль-

ных чисел N

∗

. Функция sin при переносе на нестандартную ось должна

быть доопределена для всех нестандартных значений. А уж если поду-

мать, что же должно соответствовать операции интегрирования...

Далее, если любое нестандартное число — полноправный объект

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

и для которого сохраняются все выразимые на логическом языке свой-

ства, то для множеств и функций это уже не так. Часть из них, являю-

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

стандартными, хотя, как было показано выше, их содержание уже дру-

гое

. Часть — нестандартные — сохраняют общие свойства и входят в

нестандартную модель (например, множество всех чисел, б

ольших ω).

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

Критерием для установления того, что множества или функции —

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

жеств либо функций в обычном анализе. Например, покажем, что мно-

жество стандартных действительных чисел (взятое как подмножество

нестандартной действительной оси) является внешним.

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

сел внешнее.

Доказательство. Все стандартные действительные числа меньше по

модулю бесконечно большого числа

ω. Значит, это подмножество не-

стандартной действительной оси ограничено. Значит, оно имеет точную

верхнюю грань. Эта грань является либо наибольшим элементом самого

множества (но в R такого нет), либо наименьшим элементом множества

его верхних границ

Z = {x | x ∈ R

∗

& ∀z(z ∈ R ⇒ x > z)},

т. е. множества бесконечно больших чисел. Но наименьшего бесконечно

большого числа также нет.

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

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

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

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

278

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

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

Теорема 10.1. [A. Robinson, 1960] Любое конечное число однозначно

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

Доказательство. Пусть

a — конечное число. Это значит, что имеется

такое стандартное n ∈ N, что |a| < n. Следовательно, множество стан-

дартных чисел

= {x | x ∈ R & x < a} (10.2)

ограничено сверху

. Любое ограниченное сверху множество действи-

тельных чисел имеет верхнюю грань. Обозначим верхнюю грань X

че-

рез st a. st a — стандартное число. Далее, ε = a − st a — бесконечно

малое число, поскольку иначе st a не было бы верхней гранью X

Теперь рассмотрим две конкретизации принципа переноса, важные

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

Предложение 10.3.3. (

∀-перенос) Пусть A(x) — стандартная форму-

ла со свободной переменной x. Тогда

∗

|= ∀x A(x) ⇔ ∀x

∈ R ⇒ R

∗

|= A(x

)).

Предложение 10.3.4. (∃-перенос) Пусть A(x) — стандартная форму-

ла со свободной переменной x. Тогда

∗

|= ∃x A(x) ⇔ ∃x

∈ R & R

∗

|= A(x

)).

Заметим, что в обоих этих утверждениях ⇔связывает не формулы,а

записанные при помощи логических средств предложения более общего

языка,являющиеся внешними для нестандартной модели, и в них обоих

для всех стандартных значений x

имеет место

∗

|= A(x

) ⇔ R |= A(x

Поскольку все множества стандартных действительных чисел входят в исходную мо-

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

условием.

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

279

Упражнения к § 10.3

10.3.1. Студент Классиков дал следующее доказательство, что функция

λx ∈ [0, 1]. st x внутренняя. Проанализируйте его.

Множество

, определенное формулой 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, и значит, |f(x + δ

) − f(x)| < ε для любого стандартного ε > 0.

А это и есть определение того, что |f(x + δ

) − f(x)| бесконечно мало.

280

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

А теперь докажем, что из нестандартного следует стандартное. В

самом деле, возьмем произвольное стандартное ε > 0. Если взять про-

извольное бесконечно малое δ > 0, то для всех y, таких, что |x −y| < δ,

разность f(x)−f (y) бесконечно мала,по нестандартному определению,

и, следовательно, заведомо меньше

по модулю. Значит,

ε > 0 ⇒ ∃δ(δ > 0 & ∀y(|x − y| < δ ⇒ |f(x) − f(y)| < ε)).

Но данная формула стандартна и обоснована при произвольном стан-

дартном ε. Значит, она по принципу переноса верна и для любого ε.

Следовательно,

∀ε (ε > 0 ⇒ ∃δ(δ > 0 & ∀y(|x − y| < δ ⇒ |f(x) − f(y)| < ε))) .

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

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

мерной непрерывности.

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

ется от непрерывности перестановкой одного квантора. Сравните:

∀x(x ∈ Dom f ⇒ ∀ε(ε > 0 ⇒

∃δ(δ > 0 & ∀y(y ∈ Dom f ⇒ |x − y| < δ ⇒ |f(x) − f(y)| < ε))))

∀ε(ε > 0 ⇒ ∃δ(δ > 0 &

∀x ∀y(x ∈ Dom f & y ∈ Dom f ⇒ |x − y| < δ ⇒ |f(x) − f(y)| < ε))).

Как влияет эта перестановка на нестандартную формулировку? Рань-

ше x стояло снаружи, и поэтому мы утверждали нестандартную фор-

мулировку для стандартного x. Теперь же квантор по x упрятан далеко

внутрь, и условие должно быть выполнено для всех x.

Теорема 10.3. Стандартная функция

f равномерно непрерывна на стан-

дартном множестве X тогда и только тогда, когда для любых x, y ∈

Dom f, бесконечно мало отличающихся друг от друга, f(y) бесконечно

мало отличается от f(x).

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

вопроса