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

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

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

281

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

Последовательность

бесконечное число раз принимает

значение 0.

Теорема 10.4. Стандартная последовательность a

бесконечное чи-

сло раз принимает значение 0 ттт есть такое бесконечно большое на-

туральное число ω, что a

= 0.

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

ное число раз принимать значение 0.

∀n ∃m(m > n & a

= 0). (10.3)

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

частности, для любого бесконечно большого

∃m(m > $ & a

= 0).

Это m и будет искомым ω.

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

= 0.

Утверждение (10.3) стандартное и начинается с всеобщности, поэто-

му по принципу переноса его можно обосновывать лишь для стандарт-

ных n. Но для любого стандартного n существует искомое m, а имен-

но — ω.

Итак, несколько неформально выражаясь, нестандартное число ак-

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

сел

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

формулировками, дадим несколько контрпримеров. Контрпримеры бу-

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

строению и свойствам к стандартным — почти стандартные. Функция

называется почти стандартной, если она представляется как λx f (ξ, x),

где ξ — нестандартное число, f — стандартная функция. Аналогично,

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

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

вания. Такое соображение является прекрасным нестрогим приемом, но не может быть

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

лировку теорем, но не когда их доказываете!

282

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

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

нестандартному значению аргумента.

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

эквивалентностей.

Пример 10.4.1.

Непрерывность. Функция

ε ∙sgn

бесконечно мало изме-

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

ω ∙ x

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

Пример 10.4.2.

Нули. Последовательность



1, n 6= ω

0, n = ω

принимает значение 0в единственной,но бесконечной точке.Обратного

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

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

один бесконечный нуль. Докажем это.

Пусть имеется внутренняя последовательность

, бесконечно мно-

го раз принимающая значение

, все нули которой конечны и, следова-

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

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

N = {i | i ∈ N

∗

& ∃j(a

= 0 & j > i)}.

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

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

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

стандартным (все явно упомянутые объекты стандартны):

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.5. СУПЕРСТРУКТУРЫ И ТЕОРЕМА ЛОСЯ

283

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. Последовательность

бесконечно большая.

10.4.17. Последовательность

стабилизируется.

10.4.18. Последовательность

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

10.4.19. Последовательность

имеет 1 предельной точкой.

10.4.20. Последовательность

растет быстрее, чем b

10.4.21. Функция

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

10.4.22. Функция

f неограничена вблизи точки b.

10.4.23. Функция

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

10.4.24. Функция

f интегрируема на [a, b].

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

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

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

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

Для специалистов заметим, что здесь приведена более слабая форма тео-

ремы Лося, чем приведенная, например, в [15]. Мы, следуя нашему базовому

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

284

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

классической математики, — берем здесь ту ее форму, которая может быть пе-

ренесена на кое-какие модели неклассических систем. Другое дело, что дока-

зательство и этой формы теоремы зависит от специфических принципов клас-

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

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

ничуть не хуже любой другой

10.5.1. Аксиома выбора, некоторые ее следствия

и альтернативы

Поскольку в доказательстве теоремы Лося и, соответственно, в построении не-

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

(упомянутая ранее на стр. 104), мы начнем с ее обсуждения.

Аксиома выбора имеет внешне весьма привлекательную и простую фор-

мулировку, настолько естественную, что ее применение до начала XX века не

осознавалось явно.

∀x(x ∈ X ⇒ ∃y(y ∈ Y & (x, y) ∈ R)) ⇒

∃f(f : X → Y & ∀x(x ∈ X ⇒ (x, f(x)) ∈ R)).

(10.4)

Таким образом, она утверждает, что для каждого всюду определенного соответ-

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

ления. Как говорят, функция f выбирает по элементу из каждого из множеств

{y | (x, y) ∈ R}. Поэтому ее часто называют функцией выбора.

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

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

ведем три самые важные из них.

Первая из формулировок связана с обобщением понятия прямого произве-

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

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

ции,результатами которой являются множества.Часто семейство обозначается

выражением типа

)

i∈I

вместо λi X(i). Аналогом n-ки, в которой i-тый элемент принадлежит множе-

ству X

, для произвольного множества индексов I служит функция с областью

определения I, такая, что f(i) ∈ X

. Таким образом, получаем еще одну фор-

мулировку аксиомы выбора, еще более естественную:

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

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

слим часть из них и докажем их эквивалентность.

Хотя и не лучше.

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

285

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

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

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

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

i∈I

и сопоставить каждому i

наименьший элемент X

. Докажем обратное утверждение.

Пусть дано множество X. Рассмотрим множество всех его непустых под-

множеств

X =

X \ ∅. Построим для него функцию выбора f (Y ) ∈ Y для

всех Y ∈

X. Построим трансфинитной рекурсией функцию ϕ : X → On,

где On — класс всех ординалов.

ϕ(α) =



f(X \ {ϕ(β) | β ≺ α}), X \ {ϕ(β) | β ≺ α} 6= ∅

α, X \ {ϕ(β) | β ≺ α} = ∅

Найдется такой минимальный ординал α

, при котором X \{ϕ(β) | β ≺ α} =

∅, в противном случае существовала бы инъекция из класса ординалов в X,

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

ограничение функции f на {β | β ≺ α

} является искомым вполне упорядоче-

нием.

Предложение 10.5.2. (Лемма Цорна) Если в частично-упорядоченном мно-

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

няя грань, то в множестве X существует максимальный элемент.

Доказательство. Рассуждаем от противного. Допустим, что в X нет макси-

мальных элементов. Тогда для каждого элемента x ∈ X множество {y | y ∈

X & y  x} непусто. Вполне упорядочим элементы множества X (это вполне

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

им теперь трансфинитной индукцией функцию

f(α) = минимальное x такое, что x  f(β) для всех β ≺ α.

При каждом α множество {f (β) | β ≺ α} — линейно упорядоченное подмно-

жество X. Соответственно, оно имеет максимальный элемент, и поскольку он

не наибольший, f(α) будет определено. Итак, мы построили инъекцию класса

ординалов в множество X, чего быть не может. Таким образом, в множестве

X должен быть хотя бы один максимальный элемент.

Осталось вывести аксиому выбора из леммы Цорна. Для этого докажем

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

отрезков ординалов в множество X. Оно естественно частично упорядочено

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

ний, то его объединение также будет таким отображением. Значит, согласно

лемме Цорна, существует хотя бы одна максимальная инъекция ϕ. Покажем,

что она будет и сюръекцией. Если множество X \ Val ϕ непусто и α — наи-

меньший ординал, не принадлежащий Dom ϕ, то

∃x x ∈ {X \ Val ϕ}.

286

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

Возьмем такое x и положим ϕ

(α) = x и ϕ

(β) = ϕ(β) при β ≺ α. Полученное

расширяет ϕ, а, по предположению, ϕ — максимальная инъекция. Итак,

любая максимальная инъекция дает вполне упорядочение X.

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

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

Доказательство. Определим для семейства непустых множеств (X

)

i∈I

функ-

цию χ :

i∈I

→ I, сопоставляющую каждой паре (i, x) ее первый ком-

понент. Эта функция является сюръекцией. Соответствующая ей ретракция и

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

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

мулировкам.

Аксиома зависимого выбора. [17]

∀x(x ∈ X ⇒ ∃y(y ∈ X & (x, y) ∈ R)) ⇒

∀x(x ∈ X ⇒ ∃a(a : N → X & ∀i(i ∈ N ⇒ (a(i), a(i + 1)) ∈ R))).

Итак, если отношение всюду определено, то для каждого элемента найдется

бесконечная последовательность элементов, начинающихся с данного и свя-

занных этим отношением.

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

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

по Расселу и неконечности множества и то, что каждое бесконечное множе-

ство содержит счетное подмножество.

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

но продолжить до линейного.

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

Доказательство. Обозначим исходное отношение порядка 

. Вполне упо-

рядочим исходное множество X

. После этого полного упорядочивания мож-

но считать, что элементы X занумерованы ординальными числами, меньшими

некоторого β. Построим теперь ординальную последовательность отношений

порядка 

, где при γ < δ 

⊆

. Пусть 

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

ком. Теперь возьмем элемент a с наименьшим номером, для которого имеются

несравнимые с ним элементы. Среди элементов,несравнимых с a,возьмем эле-

мент b с наименьшим номером. Возьмем отношение 

∪{(a, b)} (т. е. поло-

жим b 

α⊕1

a). Возьмем транзитивное замыкание этого отношения и положим



α+1

= (

∪{(a, b)})

∞

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

нас частичным.

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

287

Если порядок уже линейный, то положим 

α+1

=

. Для предельных γ поло-

жим



[

δ<γ



Найдется такое α ≺ β, что 

α+1

=

. Соответствующее отношение порядка

и будет расширением нашего отношения порядка до линейного.

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

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

моделей.

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

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

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

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

Пример 10.5.1.

Рассмотрим следующую игру.На отрезке

[0, 1]

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

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

. Двое игроков делают ходы по очереди, каждый

из них называет очередную цифру двоичного разложения действительного чи-

сла. Итог подводится после светопреставления (т. е. через бесконечное число

ходов): если получившееся число принадлежит множеству

,выигрывает пер-

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

ций

(f, g)

, перерабатывающих номер хода в

[0, 1]

, определено действительное

число

f ? g

, получающееся в результате игры.

Чтобы точно сформулировать один из наиболее противоречащих интуиции

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

тежами:

a ? b

является кортежом, в котором на четных местах стоят элементы

кортежа

в том же порядке, а на нечетных — элементы кортежа

. Если один

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

пусть

f(n)

— кортеж значений функции

[f(0), . . . , f (n)]

f(−1)

считается

пустым кортежом.

Выигрывающей стратегией первого игрока называется такая функция

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

{0, 1}

, что

∀g



g : N → [0, 1] ⇒ λn



f(˜g(n/2 − 1)) n

четно

g((n − 1)/2) n

нечетно

∈ X



. (10.5)

Для второго игрока определение аналогично. Доказано, что существует мно-

жество

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

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

Аксиома детерминированности.

В любой детерминированной игре один из игроков

имеет выигрывающую стратегию.

(10.6)

288

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

Пока не найдено никаких противоречий между аксиомой детерминирован-

ности и аксиомой зависимого выбора, и поэтому обычно они рассматриваются

вместе.

Рассмотрим некоторые результаты теории множеств с аксиомой детерми-

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

держит счетное подмножество.Во-вторых,сохраняется теорема Кантора-Берн-

штейна и множества можно предупорядочить по мощности. Но теперь уже

имеются множества несравнимой мощности.

В самом деле, пусть некоторое множество X не может быть вполне упо-

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

мальной мощности. Обозначим его Y . Но множество X

всех ординалов мощ-

ности множества Y имеет мощность большую, чем само Y . Таким образом,

мощности X и X

несравнимы.

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

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

ществование эквивалентно аксиоме выбора. А вот как насчет прямых

сумм?

10.5.2. Как Вам кажется, что важнее в существовании ненормальных игр без

выигрывающих стратегий: бесконечность числа ходов или же бесконеч-

ность выбора альтернатив на каждом шагу? Можете ли Вы доказать де-

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

жеств без использования аксиомы выбора?

10.5.3. В определении (10.5) создается впечатление,что второй игрок (модели-

руемый функцией g) играет без учета ходов первого. Объясните, почему

не нужно усложнять данное определение.

10.5.4. Д. Гильберт предложил следующую переформулировку классической

логики,чтобы избавиться от логических кванторов.Он рассмотрел кван-

торное выражение εx A(x), означающее такой объект x

, для которого

выполнено A(x

), если существует такой x, для которого A(x), и про-

извольный объект, если A(x) тождественно ложно. ε-символ Гильберта

может быть описан следующими аксиомами:

A(t) ⇒ A(εx A(x)),

(A ⇔ B) ⇒ εx A = εx B.

Какое следствие влекут эти аксиомы в теории множеств? Изменится ли

положение, если опустить вторую из них?

10.5.2. Ультрафильтры и структуры

Прежде всего определим язык конечных типов следующим образом. Исходны-

ми типами являются объектные типы и тип

“логический”

.Переменные имеются

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

289

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

объектных типов фиксированы. Определим три вида интерпретаций — стан-

дартные, полустандартные и произвольные. При стандартной интерпретации

универс сложного типа однозначно определяется через универсы его составля-

ющих:

(τ

,...,τ

→π)

= Func(U

, . . . , U

→ U

Очевидно, что если значениями функций является логический тип, то множе-

ство таких функций эквивалентно множеству соответствующих подмножеств.

При полустандартной интерпретации от равенства остается лишь вложе-

ние:

(τ

,...,τ

→π)

⊂ Func(U

, . . . , U

→ U

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

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

влены в нашей модели. Модели нестандартного анализа мы будем строить по-

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

в том числе и терминологическое, обоснование.

При произвольной интерпретации универсы для всех типов задаются неза-

висимо, и для каждого сложного типа применение функций (предикатов) дан-

ного типа определяется отдельно через операцию

Appl

(применения функции

к аргументам):

ζ(F(X

, . . . , X

)) = Appl(ζ(F ), ζ(X

), . . . , ζ(X

))

Произвольная интерпретация является у нас первым шагом на пути к полу-

стандартной

Теорема 10.5. (Теорема Лося) Пусть A — множество формул языка конеч-

ных типов, такое, что для каждого конечного подмножества B ⊂ A мож-

но построить стандартную интерпретацию, где все B ∈ B истинны. Тогда

имеется полустандартная интерпретация, в которой истинны все A ∈ A.

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

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

Определение 10.5.1. Фильтр

— множество

подмножеств некоторого мно-

жества

, такое, что:

X ∈ F & X ⊂ Y ⇒ Y ∈ F

X ∈ F & Y ∈ F ⇒ X ∩ Y ∈ F

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

жет быть ценно из данного параграфа в последующих главах книги. Разбирая функцио-

нальный язык

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

дартные интерпретации.

290

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

∅ /∈ F

Ультрафильтр

— такой фильтр, что для любого

X ⊂ I X ∈ F ∨

X ∈ F

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

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

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

ния — как маленькие.

Предложение 10.5.4. Любой фильтр можно пополнить до ультрафильтра.

Будем говорить,что множество X не противоречит фильтру F, если ни для

какого Y ∈ F X ∩ Y 6= ∅.

Доказательство. Начнем с лемм.

Лемма 10.5.5. Если F — фильтр, X ⊂ I, то либо X, либо

X не противоречит

Доказательство. В самом деле, пусть и X, и

X противоречат F. Тогда най-

дутся такие Y, Z ∈ F, что X ∩Y = ∅,

X ∩Z = ∅. Но тогда найдется одно такое

U = Y ∩Z, что U ∈ F, X ∩U = ∅и

X ∩U = ∅. Значит, (X ∩U ) ∪(

X ∩U) = ∅,

но тогда по дистрибутивности

(X ∪

X) ∩ U = I ∩ U = ∅.

Но пустое множество в пересечении с универсом может давать лишь пустое

множество, значит, U = ∅, чего не может быть, поскольку ∅ /∈ F

Лемма 10.5.6. Если F — фильтр, X — множество, не противоречащее F, то

найдется минимальный ультрафильтр, содержащий X и все элементы F.

Доказательство. Этот ультрафильтр строится элементарно: как множество мно-

жеств F ∪ {X ∩ Y | Y ∈ F}

Вполне упорядочим

множество 2

.Теперь трансфинитной индукцией по-

строим ультрафильтр, расширяющий F. Пусть F

= F. На шаге α + 1 берем

первый элемент X ∈ 2

(т. е. первое из подмножеств I),такой, что ни он, ни его

дополнение не входят в F

. Тогда, по лемме 10.5.5, либо он, либо его допол-

нение не противоречат F

. И по лемме 10.5.6 можно построить минимальный

фильтр, расширяющий F

и содержащий либо X, либо

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

Рассмотрим ультрафильтры над множеством натуральных чисел. Постро-

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

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

мым от конкретной формы теории множеств! Установлено, что избавиться от подобно-

го шага невозможно в принципе, даже если

I счетно.