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

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

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

161

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

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

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

налу. В самом деле, если X — начальный отрезок ординала α и X 6= α,

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

∈ α

, такой, что

γ ∈ β

для всех

γ ∈ X

Но тогда, поскольку

6= X, имеем такое β

∈ β

, которое обладает

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

щую последовательность, что противоречит вполне упорядоченности.

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

чальными отрезками.

Следующий пункт вытекает из второго.

Последний пункт легко доказать самим.

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

1. Ординал

называется

предельным

, если нет

наибольшего ординала

, такого, что

β ≺ α

;

непредельным

, если

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

2. Наименьший ординал

, такой, что

α ≺ β

, называется

следующим

за α

и обозначается

Sα

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

Ординал

называется единицей и обозначается

. Соответствен-

но для остальных натуральных чисел. Наименьший предельный

ординал, б

ольший

, обозначается

3. Пределом возрастающей ординальной последовательности орди-

налов

lim

β→γ

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

, такой, что

∀β(β ≺ γ ⇒ α

≺ δ).

4. Суммой ординальной последовательности ординалов

(α

)

i∈β

на-

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

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

сти обозначается

i∈β

Таким образом, в теории множеств Sα = α ∪ {α}.

Таким образом, ординальный 0 — это ∅.

162

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

либо просто

+ ∙∙∙ + α

для конечных последовательностей.

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

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

Произведение обозначается

i∈β

либо просто

∙ ∙∙∙ ∙α

для конечных последовательностей.

6. Степенью ординала

называется ординал

i∈β

α,

где все члены произведения одинаковые.

Рассмотрим некоторые свойства введенных операций. Для их фор-

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

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

щиеся отрезки, если дано такое его разбиение (X

)

i∈I

, что из α ∈ X

β ∈ X

, α ≺ γ ≺ β следует γ ∈ X

. То, что разные X

не пересекаются,

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

Предложение 6.3.6. 1.

Sα = α + 1, 0 + α = α + 0 = α.

0 ∙ α = α ∙ 0 = 0, 1 ∙ α = α ∙ 1 = α.

3. Если

α  β, то γ + α  γ + β.

4. Сумма ассоциативна, и, более того, бесконечно ассоциативна. А

именно, если

)

j∈γ

— такое разбиение β на непересекающиеся

отрезки, что

∀δ

, δ

(δ

≺ γ & δ

≺ δ

⇒ ∀ζ

, ζ

(ζ

∈ Y

& ζ

∈ Y

⇒ ζ

≺ ζ

)),

то

i∈β

j∈γ

i∈Y

5. Если α  β, то γ ∙ α  γ ∙ β.

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

163

6. Произведение бесконечно ассоциативно. А именно, если (Y

)

j∈γ

—

такое разбиение β на непересекающиеся отрезки, что

∀δ

, δ

(δ

≺ γ & δ

≺ δ

⇒ ∀ζ

, ζ

(ζ

∈ Y

& ζ

∈ Y

⇒ ζ

≺ ζ

)),

то

i∈β

j∈γ

i∈Y

7. α

= 1, α

= α, 1

= 1.

Доказательство. Самые нетривиальные пункты здесь — 4 и аналогич-

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

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

(δ, (ι, κ)), где δ ∈ γ, ι ∈ Y

, κ ∈ α

. Но

δ однозначно определяется через ι и не влияет на порядок элементов.

Установленный изоморфизм доказывает равенство ординалов.

Для произведения мы имеем функцию, результатом которой также

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

ция, перерабатывающая каждое

j ∈ γ в функцию из Y

в ∪

i∈Y

. Но в

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

множеств троек того же вида, что и в предыдущем абзаце. В этом множе-

стве множеств лишь конечное число троек с отличным от нуля третьим

элементом, а первый элемент однозначно определяется вторым, так что

опять имеет место изоморфизм с одинарным произведением.

То, что операции над ординалами некоммутативны, легко увидеть на

следующем примере. Если

ω + 1 — следующий за ω ординал, который

мы так и обозначаем, то 1 + ω = ω. В самом деле, если к натуральному

ряду в начале присоединить еще один элемент, то полученное упорядо-

ченное множество изоморфно натуральному ряду. Если же этот един-

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

уже не будет, этот элемент будет тем, что называется ω.

Предложение 6.3.7. Функция сложения ординалов —единственная,удо-

164

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

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







α + 0 = α;

α +

β =

(α + β);

α + lim β

= lim(α + β

(6.8)

где (β

)

γ∈δ

— возрастающая ординальная последовательность орди-

налов.

Еще создатель теории ординалов Г. Кантор заметил, что каждое ор-

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

ω, т. е. предста-

вляется в виде

∙ n

+ ∙∙∙ + ω

∙ n

, (6.9)

где

 α

 ∙∙∙  α

, n

> 0. (Здесь учитывается, что ω

= 1.)

Польский математик К. Куратовский заметил, что в качестве основания

разложения может быть взят любой ординал > 1 (опять полная аналогия

с натуральными числами и системами счисления), но, считая ω-ичную

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

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

писанными в позиционной системе счисления. Определим сложение и

умножение по Куратовскому ⊕ и ⊗ (см. [20]). Прежде всего разрешим

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

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

совпадают (в случае необходимости до-

бавляем члены ω

∙ 0).

(ω

∙ n

+ ∙∙∙ + ω

∙ n

) ⊕ (ω

∙ m

+ ∙∙∙ + ω

∙ m

) =

∙ (n

+ m

) + ∙∙∙ + ω

∙ (n

+ m

(6.10)

(ω

∙ n

+ ∙∙∙ + ω

∙ n

) ⊗ (ω

∙ m

+ ∙∙∙ + ω

∙ m

) =

∙

⊕α

=β

∙ m

(6.11)

где

(β

) — конечная, упорядоченная в порядке возрастания последо-

вательность ординалов, представляемых в виде α

⊕ α

. Арифметика

ординалов по Куратовскому обладает следующими свойствами:

Предложение 6.3.8. 1.

α ⊕ β = β ⊕ α, α ⊗ β = β ⊗ α.

Уравнение (определение функции) называется рекурсивным, если оно прямо или

косвенно выражает значения функции через другие значения той же функции.

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

165

2. Обе эти операции ассоциативны.

(α ⊕ β) ⊗ γ = α ⊗ γ ⊕ β ⊗ γ.

α ⊕ β < α + β; α ⊗ β < α ∙ β.

 α

⇒ α

⊕ β  α

⊕ β.

 α

& β  0 ⇒ α

⊗ β  α

⊗ β.

Доказательство остается читателям.

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

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

скому все чаще применяются в литературе по информатике, вытесняя

обычные операции над ординалами. Но, конечно же, бесплатно ничего

не дается, и поэтому необходимо сделать следующее

Предупреждение

Возведение в ординальную степень по Куратовскому уже не

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

непрерывными и к пределу не перейдешь.

Обратим внимание на еще одно важное свойство ординальных функ-

ций.

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

Функция из ординалов в ординалы

называется

не-

прерывной

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

f( lim

β→γ

) = lim

β→γ

f(α

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

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

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

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

ру (в частности, открытость, замкнутость, окрестность).

Теорема 6.3. (Теорема Веблена) Для любой непрерывной возрастаю-

щей функции ординалов

f найдется неподвижная точка, т. е. такое

, что

f(α

) = α

166

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

Доказательство. Рассмотрим следующую возрастающую последова-

тельность:

= 0, α

= f(0), α

= f(f(0)), . . . , α

n+1

= f(α

) . . .

Ее предел и является искомой неподвижной точкой, поскольку

f( lim

n→ω

) = lim

n→ω

f(α

) = lim

n→ω

n+1

= lim

n→ω

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

точке, составивших в нынешнее время основу математической теории

функционального программирования. Но, конечно, когда Веблен дока-

зывал ее в 1912 г., он и не мог подумать о таком ее использовании. За-

то Веблен прекрасно понимал ее приложимость к построению больших

ординалов, намного б

ольших, чем ε

, являющийся всего лишь наимень-

шей неподвижной точкой функции λα.ω

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

в упражнениях.

6.3.4. Построение функций рекурсией

по определению либо параметру

В приведенных выше рассмотрениях нам встречались примеры постро-

ения значений функций по трансфинитной индукции. Естественно, для

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

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

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

ного сложения (6.8)).

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

мы просто определяем функцию рекурсией саму через себя либо через

другие функции.Да, в языке программирования так оно и записывается,

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

, приходится

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

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

вильная работа получившейся программы: она не зацикливается и не зависает, на при-

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

от нее хотели.

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

167

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

ректные способы индуктивного построения функций по параметрам-

ординалам (т. н. трансфинитная рекурсия).

Пример 6.3.2.

Система рекурсивных уравнений



f(x, 0) = x

f(x,

y) =

f(x, y)

(6.12)

определяет сложение натуральных чисел. Для сложения ординалов эту

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







f(x, 0) = x

f(x,

y) =

f(x, y)

f(x, lim

γ→δ

) = lim

γ→δ

f(x, α

)

(6.13)

Пример 6.3.3.

Система рекурсивных уравнений



f(x, 0) = 0

f(x,

y) = f(x, y) + x

(6.14)

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

эту систему нужно пополнить еще одним уравнением:

f(x, lim

γ→δ

) = lim

γ→δ

f(x, α

(6.15)

Таким образом,вид трансфинитной рекурсии,соответствующий про-

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

Примитивная трансфинитная рекурсия

Базис.

Задаем f(0, ˉx).

Шаг для непредельных ординалов.

Определяем f(

α, ˉx)

как g(f(α, ˉx), α, ˉx).

Шаг для предельных ординалов

Определяем f(α, ˉx) как



lim

β→α

f(β, ˉx)



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

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

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

ния f.

168

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

Из самой формулировки примитивной трансфинитной рекурсии сле-

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

правда, и ведет она к непрерывным.

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

6.3.1. Вычислите

lim sup N ∪ {ω}.

6.3.2. Проверьте недоказанные пункты из примера 6.3.6.

6.3.3. Верно ли, что

α ∙ β =

i∈β

α?

6.3.4. Всегда ли существует

lim

β→γ

6.3.5. Вычислите

ω ∙ 2 и 2 ∙ ω.

6.3.6. Имеет ли место закон дистрибутивности:

α ∙ (β + γ) = α ∙ β + α ∙ γ.

6.3.7. Проверьте, выполнено ли (α + β) ∙ γ = α ∙ γ + β ∙ γ

6.3.8. Студент Талантов заявил,что оговорка насчет конечных кортежей

совершенно излишняя и что множество

i∈I

вполне упорядочено лексикографическим порядком, если I и все

вполне упорядочены. Что Вы ему ответите?

6.3.9. Можно ли перенести ‘антилексикографический’ порядок на все

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

6.3.10. А всегда ли

=1? А как насчет 0

6.3.11. Докажите предложение Куратовского на стр. 164.

6.3.12. Можно ли обобщить операции по Куратовскому на ординальные

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

Подсказка. Здесь и в предыдущем упражнении рассмотрите (ω + 1) ∙ (ω + 1).

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

169

6.3.13. В одной работе как очевидное было упомянуть следующее то-

ждество:

= α ⊗ α.

Проверьте эту ‘очевидность’.

6.3.14. Являются ли сумма и произведение по Куратовскому непрерыв-

ными по какому-то из аргументов?

6.3.15. Дайте рекурсивное определение суммы по Куратовскому.

6.3.16. Какая функция удовлетворяет следующим рекурсивным уравне-

ниям:







f(α, 0) = 1

f(α,

β) = f(α, β) ×α

f(α, lim

δ→γ

= lim

δ→γ

f(α, β

)

(6.16)

6.3.17. Почему в определении сложения мы взяли произвольное

δ,

а не ограничились ω?

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

рывной возрастающей функции ординалов

f, превосходящей β.

6.3.19. Пусть

f — непрерывная возрастающая функция. Неперерывна

ли функция, преобразующая α в α-тую неподвижную точку f?

6.3.20. Для приведенных ниже пар ординалов вычислите

α + β, β + α,

α ⊕ β, α ∙ β, β ∙ α, α ⊗ β.

1) ω 2

2) ω ω

3) ω + 1 ω + 2

4) ω

+ ω + 2 ω

+ 2ω + 1

5) ω

+ 2ω + 1 ω

+ 5ω + 7

6) ε

+ ω

+ 3 ω

+ ω

+ 1

7) 2ω

ω+1

+ 5ω

+ 7ω + 4 ω

ω+2

+ 2ω

+ 3ω

+ 4ω

6.3.21. Вычислите (ω + 1)

при возведении в степень по Кантору и по

Куратовскому. Чему равно (ω + 1)

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

Глава 7. Введение в синтаксис

§ 7.1. СИНТАКСИС ЛОГИЧЕСКОГО ЯЗЫКА

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

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

тов, о распознавании объектов различных типов и их характеристик.

Синтаксически правильно построенные объекты могут в дальнейшем

интерпретироваться и преобразовываться в соответствии с интерпрета-

цией языка.

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

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

ного выражения — программирования.

Тот, кому приходится рецензировать достаточно много математиче-

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

кроется за словами «Очевидно» либо «Данный случай разбирается ана-

логично предыдущему».Ну,насчет “очевидности”все ясно

,а вот с ана-

логичностью приходится долго разбираться.

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

ки зрения логики построения) задачи, сталкивается с неприятностью:

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

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

ски: текст мог бы быть один и тот же, но изменяются типы данных и его

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

именем.

Программист высочайшего класса, обладавший, вдобавок,в лучших

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

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

рым нам придется заниматься далее. Но рецензенту здесь проще. Достаточно написать,

скажем: «А мне неочевидно».