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

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

5.7. ДИАГРАММЫ

131

мутативных диаграмм.

a∙

∙b

d∙ ∙c

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

Стрелки категории отнюдь не обязательно являются функциями.

Пример 5.7.2.

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

ство

. Оно может рассматриваться как категория, в которой объектами

служат элементы множества

, множество морфизмов из

непусто,

лишь если

a 6 b

, и в этом случае состоит из единственного морфизма,

называемого морфизмом порядка.

Пример 5.7.3. Полугруппа

— алгебраическая структура с одной ассоци-

ативной операцией умножения

◦

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

e ◦ x = x ◦ e = x.

Любая полугруппа становится категорией, в которой единственный объ-

ект — сама эта полугруппа, а морфизмы — ее элементы.

Одним из новых выразительных средств, предоставленных теорий

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

рассматриваться как новые объекты или морфизмы.

Пример 5.7.4.

(Навеян идеями [16]) Пусть мы построили математиче-

скую модель для некоторого класса объектов

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

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

ми объектами

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

(скажем, множества состояний двух систем) естественно кодируют-

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

неоднозначны: например, 24.30 и 00.30 кодируют одно и то же время).

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

: X → Y

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

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

и определить

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

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

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

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

а это как раз и есть аксиомы теории категорий.

132

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

их как

коммутативные квадраты

вида

∙ ∙

Приведенная конструкция похожа на следующую, весьма общую:

категорию морфизмов данной категории.Объектами категории морфиз-

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

. Морфизмом

на-

зывается коммутативная диаграмма исходной категории:

∙ ∙

Композиция морфизмов определяется следующим образом:

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

тегорий, связана с особыми объектами категорий. В категории может

быть начальный объект, из которого есть единственный морфизм в лю-

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

объект, в который есть единственный морфизм из любого объекта. Если

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

нулевым.

Пример 5.7.5.

Рассмотрим некоторые начальные и конечные объекты.

1. В теории множеств пустое множество — начальный объект, а лю-

бое одноэлементное — конечный.

2. Под

эквациональной системой

либо (простейшей)

алгебраической

системой

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

5.7. ДИАГРАММЫ

133

аксиом-равенств, например, как в теории групп:

x ◦ (y ◦z) = (x ◦y) ◦ z (5.18)

x ◦ x

−1

= e (5.19)

x ◦ e = x (5.20)

e ◦ x = x (5.21)

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

ременные связаны кванторами всеобщности. Эквациональные си-

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

горию (например, категория групп, категория полугрупп...). Мор-

физмами такой категории служат отображения, коммутирующие с

операциями:

ϕ(x ◦ y) = ϕ(x) ◦ϕ(y)

и т. д.

В любой такой категории есть нулевой объект: система из одного

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

венств у нас быть не может.

Уже из этого примера видно, что начальный и конечный объекты —

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

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

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

вида

= u

& ∙∙∙ & t

= u

⇒ r = s (5.22)

либо

& ∙∙∙P

⇒ Q, (5.23)

где

, Q — предикаты. Рассматриваются модели таких алгебраических

систем, объектами которых являются замкнутые термы, составленные в

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

в аксиомах операций (сколемовские модели). На термах нужно опреде-

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

ным способом определения равенства стало правило:

Если элементарное утверждение не дано и не следует из дан-

ных, то оно считается ложным. Следовательно, все термы,

134

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

ными

В категории сколемовских моделей алгебраической системы, аксио-

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

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

на любую другую сколемовскую модель. Обобщая определение, полу-

чаем: инициальный объект — объект, для которого имеется единствен-

ный эпиморфизм на любой другой объект.

Подытожим

Теория категорий стимулирует формулировку свойств мате-

матических объектов через их отображения, сохраняющие

структуру.

Само понятие отображения в теории категорий обобщается

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

Главным элементом языка теории категорий являются ком-

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

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

дают.

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

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

ме.

Все приведенные выше соглашения о диаграммах не абсо-

лютны, но их нарушение оговаривается явно, так что читай-

те тексты внимательнее!

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

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

тегории морфизмов. Через такие конструкции теория кате-

горий дает возможность задать весьма абстрактные объекты

высших порядков.

Теория категорий является, в частности, языком, на котором

выражено большинство наиболее тонких и важных резуль-

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

Это правило имеет в современном “логическом программировании” название

«Принцип замкнутости мира».

5.7. ДИАГРАММЫ

135

В отличие от теории множеств, доказательство в теории ка-

тегорий дает построение объектов, существование которых

утверждается.

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

5.7.1. Студент Цхалтубенко предложил следующее определение катего-

рии:

Категория — класс морфизмов, на котором задана

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

◦,удовлетво-

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

1. Если определено

f◦(g◦h),то определено и (f◦g)◦h

и их значения совпадают, и наоборот.

2. Для любого морфизма

f существуют такие единич-

ные морфизмы e

, e

, что e

◦ f = f , f ◦ e

= f.

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

ли оно исходному.Если оно неэквивалентно, то как его исправить?

5.7.2. Студент Талантов заявил, что объекты можно вообще изгнать из

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

ми. Уточните идею Талантова и дайте соответствующее ей опре-

деление категории.

5.7.3. Каким свойством обладает любой морфизм из начального объек-

та? А в конечный?

5.7.4. Дайте характеризацию на категорном языке функций, множества

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

5.7.5. То же для функций, таких, что задаваемые ими отношения экви-

валентности совпадают (т. е.

f(x) = f(y) ⇔ g(x) = g(y)).

5.7.6. Возможно ли, чтобы прямое произведение

a и b было изоморфно

их прямой сумме? Если это возможно, двиньтесь дальше: может

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

совпадать с прямой суммой?

5.7.7. Пусть

L — категория, порожденная некторым частично-упоря-

доченным множеством L. В каком случае два объекта a, b имеют

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

на языке частичного порядка?

136

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

5.7.8. То же для прямой суммы.

5.7.9. Рассмотрим категорию всех подмножеств конечного множества

X, отображениями в которой служат обычные функции. В каком

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

мую сумму?

5.7.10. Рассмотрим категорию частично-определенных теоретико-мно-

жественных функций (т. е. однозначных отношений). Функции,

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

ми. Сформулируйте эти свойства.

§ 5.8. СЛОВА

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

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

понятий. Известно (хотя на самом деле и нетривиально; в частности, в

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

таких объектов достаточно слов в конечном алфавите

Алфавит — исходное понятие.Его можно описать как конечную по-

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

буквами.

Определение 5.8.1. Слово

— конечная последовательность букв алфа-

вита

. Операция приписывания слова

к концу слова

называется

со-

единением

или

конкатенацией

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

. Слово

есть

начало (конец)

слова

, если

представимо в виде

(соответственно,

). Собственное начало (конец) — начало (конец), не являющееся пу-

стым словом или всем

. Слово

входит

в слово

, если

представимо

в виде

CAD

, т. е. если

— начало конца

. В этом случае

называется

подсловом

. Длина слова — количество входящих в него букв.

Заметим, что одно и то же слово может много раз входить в другое.

Например, ‘ба’ трижды входит в ‘баобаба’. Для точности употребляют

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

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

нельзя.

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

Λ.

5.8. СЛОВА

137

понятие (отмеченное) вхождение

, представляемое как слово фор-

мы C ? A ? D в алфавите, расширенном новым символом ?.

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

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

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

мирования называемого идентификатором) и разделение этих слов но-

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

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

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

входящих в него примитивов. Последовательность слов вида

Ξ, разде-

ленных символом ?, есть слово вида ξ

? ξ

? ∙∙∙? ξ

либо пустое слово.

В излишне алгебраизированных изложениях (в частности, матема-

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

ной алгебре с единственной ассоциативной операцией конкатенации,

или просто элементами конечнопорожденного свободного моноида.

Для избежания недоразумений (в особенности для необычно выгля-

дящих слов) мы порою будем заключать рассматриваемое слово в оди-

нарные кавычки, например, ‘Ст-т Чудаков! & (Co’.

Для дальнейшего потребуется однозначное и достаточно простое ко-

дирование слов алфавита натуральными числами.Если алфавит состоит

из n букв, то естественно сопоставить буквам цифры 1, ..., n соответ-

ственно и закодировать слова как числа в системе с основанием n + 1.

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

его будем называть просто позиционным.

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

5.8.1. Покажите, что множество слов в данном алфавите естественно

изоморфно множеству кортежей из букв этого алфавита.

5.8.2. Докажите, что множество систем слов естественно изоморфно

множеству кортежей из кортежей.

138

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Часть II

Классическая логика

139