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

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

6.2. ОБ ИНДУКТИВНЫХ ОПРЕДЕЛЕНИЯХ

151

ми путями являются одним из мощных средств определять структуры

данных, по которым можно вести индукцию. Общую формулировку ин-

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

Брауэр (L. E. J. Brouwer) в 1928 г. средствами неклассической матема-

тики, а затем она была доказана и традиционными средствами, правда,

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

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

. Через a  b обозначим отно-

шение “b непосредственно следует за a”, т. е. дуга ведет из a в b; через

L(a) — предикат “быть листом”.

Теорема 6.2. (Теорема Брауэра, bar-индукция) Если

T — дерево с ко-

нечными путями и выполнены базис и шаг индукции:

∀x (L(x) ⇒ A(x))

∀x (x ∈ T & ∀y (x  y ⇒ A(y)) ⇒ A(x)) ,

то ∀x (x ∈ T ⇒ A(x)).

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

кое

∈ T, что ¬A(a

). По шагу индукции, тогда существует a

, такое,

что a

 a

и ¬A(a

). a

не может быть листом, поскольку для листьев

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

найти a

, a

 a

и ¬A(a

). Продолжая таким образом, получаем бес-

конечный путь в T, чего быть не может.

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

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

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

ветвлением. Следствием bar-индукции является следующий результат,

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

нетрадиционной математике, существенно неклассическими методами,

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

енигом.

Лемма 6.2.1 (Теорема о веерах). Любой веер конечен.

Доказательство. Если веер состоит из одного элемента, он конечен. В

противном случае веер представляется как на рисунке 6.3,где T

, . . . , T

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

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

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

пока что не хватит ни знаний, ни техники.

152

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

∙∙∙

Рис. 6.3: Структура веера

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

ние — достаточно опасный и тонкий прием. В частности, легко впасть в

парадокс лжеца, индуктивно определив

A(x) через ¬A(x). Поэтому на-

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

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

ответ, является ли E корректным выражением, зависит от самого себя.

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

Корректны ли следующие индуктивные определения? Если они

формально некорректны —как их исправить?Если корректны фор-

мально — что они определяют и хороши ли они содержательно?

6.2.1. Пусть 2 — хорошее число; 3 — плохое число. Если

n — хорошее,

то n + 5 — хорошее; если n — плохое, то n + 7 — плохое.

6.2.2. Пусть 0 — нужное число; если

n + 1 и n −1 — нужные числа, то

n — нужное число.

6.2.3. Элементарные формулы атомарны;если

¬A — атомарная форму-

ла, то и A — атомарна.

6.2.4. Пусть 0 — хорошее число; если

n — хорошее,то n+1 не является

хорошим числом;если n — не хорошее число, то n+1 — хорошее.

6.2.5. Один английский математик XIX в. в связи с широко обсуждав-

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

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

ществует вечно, но потомки по мужской линии любого мужчины

через конечное время исчезнут. Возможна ли такая модель? А как

по женской линии?

6.3. ТРАНСФИНИТНАЯ ИНДУКЦИЯ И ОРДИНАЛЫ

153

§ 6.3. ТРАНСФИНИТНАЯ ИНДУКЦИЯ И ОРДИНАЛЫ

6.3.1. Построение начального отрезка ординалов

Заметим, что индукция по индуктивному определению напоминает воз-

вратную индукцию. Еще до того, как были осознаны индуктивные опре-

деления, было замечено, что возвратная индукция — гораздо более об-

щий принцип,чем математическая,и переносится на многие другие мно-

жества.

Пример 6.3.1.

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

числом

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

N ∪{ω}

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

бесконечного спуска и принцип наименьшего числа.

В самом деле, для

n < ω

принцип возвратной индукции выполнен,

поскольку они — натуральные числа. Значит, если выполнен шаг воз-

вратной индукции, то выполнено

∀n(n < ω ⇒ A(n))

. Но тогда по шагу

индукции выполнено и

A(ω)

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

на более широкое множество чисел германский математик Г. Кантор

в третьей четверти XIX века. Он назвал пополнение натуральных чи-

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

ми (сверхконечными) или ординальными (порядковыми) числами

, а

принцип индукции для них — трансфинитной индукцией. Таким обра-

зом, трансфинитная индукция — обычная возвратная индукция, но для

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

тике, превратить важнейшее для нас свойство в определение.

Определение 6.3.1. Вполне упорядоченное

множество — линейно упо-

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

дукции.

Фундированное

(частично вполне упорядоченное)множество —

чум с возвратной индукцией.

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

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

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

Часто называют их просто трансфинитами или ординалами. В настоящее время

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

прежнему называют трансфинитной.

154

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Прежде всего, если добавить непосредственно следующий за ω ор-

динал ω+1,то получившееся множество чисел по-прежнему будет впол-

не упорядочено. Аналогично получится, если добавить конечное число

ординалов до ω + n с естественным упорядочением. А за всеми ω + n

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

2 ∙ω

. Итак, начальный отрезок ордина-

лов имеет следующую структуру:

0, 1, . . . , n, . . . ω, ω + 1, . . . , ω + n, . . . 2 ∙ ω.

Но за 2 ∙ ω можно продолжать в том же духе, получая:

2 ∙ ω, 2 ∙ ω + 1, . . . , 2 ∙ ω + n, . . . 3 ∙ ω.

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

0, 1, . . . , k, . . . ω, ω + 1, . . . , ω + k, . . . 2 ∙ ω, . . . n ∙ ω . . . .

Но вслед за всеми этими ординалами вида n ∙ ω + k естественно по-

ставить еще больший и назвать его ω

. А за ω

выстраивается ряд, изо-

морфный предыдущему:

, ω

+ 1, . . . , ω

+ k, . . . ω

+ ω, ω

+ ω + 1, . . . , ω

+ ω + k, . . .

+ 2 ∙ω, . . . ω

+ n ∙ω . . . 2 ∙ ω

А за всеми k ∙ ω

+ l ∙ ω + n стоит ω

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

возможные ординалы вида

∙ ω

+ k

n−1

∙ ω

n−1

+ ∙∙∙ + k

ω + k

За ними идет ординал, обозначаемый ω

. А за ним опять-таки цепочка

его “сумм” со всеми предыдущими ординалами:

+ k

∙ ω

+ k

n−1

∙ ω

n−1

+ ∙∙∙ + k

ω + k

Аналогично, мы приходим к 2 ∙ ω

, и далее к n ∙ ω

. Если считать, что

законы сложения степеней сохраняются (а уж мы постараемся их со-

хранить), то дальше идет ω

ω+1

. Таким образом приходим к ординалам

вида

∙ ω

ω+m

+ l

m−1

∙ ω

ω+(m−1)

+ ∙∙∙ + l

∙ ω

+ k

n−1

∙ ω

n−1

+ ∙∙∙ + k

∙ ω + k

6.3. ТРАНСФИНИТНАЯ ИНДУКЦИЯ И ОРДИНАЛЫ

155

А за ними идет ординал, который естественно обозначить ω

2∙ω

. Продол-

жая данный процесс, мы приходим к ординалам вида

∙∙∙

n раз.

А за всеми этими башнями стоит ординал, который Г. Кантор назвал

и определил как наименьшее решение уравнения ω

= α. Слава Богу,

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

значительно больших, чем ε

Теперь рассмотрим одно применение ординалов. Докажем, что лю-

бая программа вида

for i := 1 to k do begin

S; for j := 1 to S1 do S2;

end;

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

S1, S2 заканчиваются и они не изменяют значений переменных цикла.

Пусть

s — значение S1 к моменту начала нынешнего исполнения

внутреннего цикла. Построим следующую функцию:

ϕ(i, j) = (k − i) ∙ ω + (s − j). (6.3)

На каждом шаге любого цикла эта функция уменьшается и, по вполне

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

дет до 0, и программа закончится.

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

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

S1, зато

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

ние программы. Правда, мы не находим никакой явной оценки времени

работы программы, но это не всегда нужно.

Проиллюстрированный выше метод называется в теории алгорит-

мов и теоретической информатике методом сигнализирующих функций.

Чтобы доказать конечность некоторого процесса вычисления, достаточ-

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

вающую на каждом шагу процесса. Для построения сигнализирующих

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

тических программ хватает ординалов до

156

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

6.3.2. Свойства вполне упорядоченных множеств

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

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

меньший элемент и что каждая убывающая последовательность элемен-

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

X обозначается 0

или просто 0, если X однозначно определяется из

контекста. Далее, если некоторое подмножество X

вполне упорядочен-

ного множества X ограничено сверху, то оно имеет точную верхнюю

грань,а множество его строгих верхних границ — наименьший элемент,

являющийся наименьшим элементом,превосходящим все элементы X

Этот элемент обозначим lim sup X

и назовем верхним пределом X

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

Предложение 6.3.1. Если

X и Y — два вполне упорядоченных множе-

ства, то выполнена одна и только одна из альтернатив:

a) Существует монотонно возрастающая инъекция

X на началь-

ный отрезок Y .

b) Существует монотонно возрастающая инъекция

Y на началь-

ный отрезок X.

X и Y изоморфны.

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

ей две функции

f : X → Y , g : Y → X. Если уже определено f(α) для

всех α ≺ β, то

f(β) =



μγ (¬∃α(α ≺ β & f (α) = γ)) X \ f h{α | α ≺ β}i 6= ∅

μγ (γ ∈ Y ) X \ f h{α | α ≺ β}i = ∅

Аналогично определяем g.

Обозначим наименьший элемент всего множества

X — 0

, наи-

меньший элемент Y — 0

. Обозначим через X

следующее подмно-

жество X:

= {x | x = 0

∨ f (x) 6= 0

}. (6.4)

Аналогично определяем Y

По построению, если

α ∈ X

, f h{β | β ≺ α}i — начальный отре-

зок Y . Симметрично для g. Таким образом, множества X

, Y

являются

начальными отрезками X и Y соответственно.

6.3. ТРАНСФИНИТНАЯ ИНДУКЦИЯ И ОРДИНАЛЫ

157

Докажем, что f и g являются изоморфизмами между X

и Y

. В са-

мом деле, на X

f является инъекцией. Аналогично для g и Y

. Далее,

трансфинитной индукцией установим, что

∀α(α ∈ X

⇒ g(f (α)) = α). (6.5)

В самом деле, пусть эта импликация выполнена для всех

β ≺ α. Тогда,

если α ∈ X

, то

{β | β ≺ α} = {g(f(β)) | β ≺ α}.

Но f(α) = lim sup{f(β) | β ≺ α}. Значит,

g(f(α)) = lim sup{g(f(β)) | β ≺ α} = lim sup{β | β ≺ α} = α.

Таким образом, доказан изоморфизм начальных отрезков X и Y .

Теперь покажем, что если

X изоморфно начальному отрезку Y , то

этот отрезок определяется однозначно. Итак, пусть имеются два изо-

морфизма f

и f

вполне упорядоченного множества X на начальные

отрезки Y

и Y

соответственно. По трансфинитной индукции легко до-

казывается, что для всех x ∈ X f

(x) = f

(x), а из такого равенства

следует искомая однозначность.

Итак, если

X изоморфно собственному начальному отрезку Y , то

оно уже не может быть изоморфно самому Y , и наша трилемма доказа-

на.

Предложение 6.3.2. Между двумя изоморфными вполне упорядоченны-

ми множествами есть только один изоморфизм.

Доказательство. Рассмотрим два изоморфизма

X на Y : ϕ

и ϕ

. По

трансфинитной индукции докажем их тождество.

Пусть для всех

β ≺ α выполнено ϕ

(β) = ϕ

(β). Тогда, поскольку

эти функции — изоморфизмы,

(α) = lim sup{ϕ

(β) | β ≺ α}

= lim sup{ϕ

(β) | β ≺ α}

= ϕ

(α).

158

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

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

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

ченных множеств (X

)

i∈I

и множество индексов I также вполне упо-

рядочено. Тогда на их прямой сумме естественно вводится линейный

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

распо-

лагается после

, если i  j:

(i, α) ≺ (j, β) ⇔ i ≺ j ∨ (i = j & α ≺ β).

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

деле,возьмем произвольное непустое подмножество прямой суммы Y ⊂

i∈I

. Возьмем его проекцию на I. Она непуста, значит, в ней най-

дется наименьшее i

, такое, что ∃α(i

, α) ∈ Y . А теперь в X

найдет-

ся наименьшее α

, такое, что (i

, α

) ∈ Y . По определению порядка,

, α

) — наименьший элемент Y .

Функции, в которых область определения — некоторое стандартное

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

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

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

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

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

вый элемент, на котором они различаются.

Определение 6.3.2.

Ординальное произведение ординальной последо-

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

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

конечное число членов, упорядоченное следующим отношением (

—

множество индексов последовательности)

a ≺ b ⇔ ∃α(α ∈ I & a(α) ≺ b(α) &

∀β(β ∈ I & β  α ⇒ a(β) = b(β))). (6.6)

Предложение 6.3.3. Ординальное произведение произвольной ординаль-

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

рядочено.

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

6.3. ТРАНСФИНИТНАЯ ИНДУКЦИЯ И ОРДИНАЛЫ

159

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

нейный. Рассмотрим две не равных друг другу последовательности a

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

имеется наибольший элемент, имеется такое α, что при всех β  α

a(β) = a(α) = 0. Значит, множество

= {α ∈ I | ∀β(β  α ⇒ a(β) = b(β))}

непусто и имеет наименьший элемент α

. Но для α

a(α

) 6= b(α

). Этот

факт требует отдельного обоснования.

В самом деле, если

таково, что

∀β(β ∈ I & β ≺ α

⇒ a(β) = b(β)), (6.7)

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

всех меньших, и для всех б

ольших индексов они равны. Если же усло-

вие (6.7) не выполнено, то найдется наибольшее

≺ α

, на котором

они различаются, и для α

выполняется характеристическое свойство

множества I

, что противоречит определению α

6.3.3. Представления ординалов.

Действия над ординалами

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

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

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

аксиомы выбора и строить их явно. Здесь помогает аксиома фундиро-

ванности. Из нее вытекает следующее утверждение:

Предложение 6.3.4. Если множество

X линейно упорядочено отноше-

нием

{(x, y) | x ∈ X & y ∈ X & x ∈ y},

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

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

Y — непустое подмножество X. По аксиоме

фундированности, в Y имеется элемент, не пересекающийся с самим

Y . Значит, он минимален по отношению ∈. Следовательно, каждое не-

пустое подмножество X имеет наименьший элемент, что и требовалось

доказать.

160

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

Определение 6.3.3.

Множество называется

транзитивным

,если

∈

явля-

ется на нем отношением порядка.

Ординал

— транзитивное линейно

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

Считается, что ординал

меньше

(

α ≺ β

), если

изоморфен соб-

ственному начальному отрезку

Из сказанного выше видно, что данное определение ординала явля-

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

ординалов, а опыт вдобавок подсказывает, что такое представление —

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

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

ет и при малейших изменениях аксиоматической системы теории мно-

жеств. А вот сущности, которые стоят за ординалами, — классы изо-

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

пами вполне упорядочений, применимы гораздо шире, чем любое из их

конкретных представлений.

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

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

налов, может быть, не всех, но зато более применимые. Это — обычный

путь разработки понятий для нужд прикладной математики.

Следующие предложения касаются именно данного конкретного пред-

ставления ординалов. В них вовсю эксплуатируются некоторые удоб-

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

просто равенство множеств, отношение

α ≺ β выражается сразу двумя

способами: α ∈ β, α ⊂ β.

Предложение 6.3.5. 1. Если два ординала изоморфны, они равны.

2. Любой ординал совпадает с множеством всех м

еньших его орди-

налов.

α ≺ β ⇔ α ⊂ β.

4. Объединение произвольного множества ординалов является ор-

диналом.

Доказательство. Первый пункт легко доказывается трансфинитной ин-

дукцией.

Докажем второй пункт. Любой элемент ординала является ордина-

лом,и м

еньшим его.В самом деле, он является, по транзитивности, мно-

жеством, линейно упорядоченным отношением

∈. Далее, он определяет