КАТЕГОРИЙ ТЕОРИЯ

— математическая теория, основным объектом изучения которой является понятие категории. Это понятие ввели амер. математики С. Маклейн и С. Эйленберг в 1945 г. применительно к проблемам алгебраической топологии. Позднее применение К. т. вышло далеко за пределы этих проблем и широко использовалось в алгебре, алгебр, геометрии, анализе, логике математической, матем. кибернетике и др.

Говорят, что задана категория К, если: а) задан класс ОЬ (К) элементов называемых объектами категории К; б) для каждой упорядоченной пары объектов задано мн-во Нотк . Элементы этого мн-ва наз. морфизмами А в В и записывается также в виде или . Объект А наз. областью морфизма а объект В — его кообласть для каждой упорядоченной тройки объектов задано отображение Нотк Образ где обозначается через или композицией морфизмов . Мн-во морфизмов Нотк и композиция морфизмов должны удовлетворять следующим аксиомам.

1) Композиция ассоциативна, т. е. для каждой тройки морфизмов

Для каждого объекта А из ОЬ (К) существует морфизм тождественным или единичным морфизмом объекта А, такой, что для произвольных морфизмов .

3) Если пары различны, то пересечение мн-в Нотк и Нотк пусто.

Отождествляя единичный морфизм произвольного объекта А с самим этим объектом, можно дать определение понятия категории, эквивалентное приведенному выше, пользуясь только понятием морфизма и не используя понятия объектов. Очень часто именно так и определяется категория. В качестве примера категории приведем категорию всех Объектами этой категории являются все мн-ва, морфизмами — все отображения мн-в друг в друга и композицией морфизмов — суперпозиции отображения. Другой пример категории — произвольный полный граф, имеющий в каждой вершине петлю. В этом случае объектами являются вершины графа, морфизмами — дуги, а композицией дуг и (b, с) — дуга . Морфизм изоморфизмом, если существует морфизм такой, что Категория К наз. малой, если ее объекты образуют мн-ва, напр., любой полный граф — малая категория ибо, говоря о графах, мы всегда подразумеваем, что совокупность всех вершин графа — мн-во. Подкатегорией категории К наз. категория К такая, что а) ; б) все тождественные морфизмы из К суть тождественные морфизмы в К; в) (А, В) и г) композиция морфизмов в К индуцируется их композицией в К. Подкатегория К наз. полной, если для каждой пары из

Каждой категории К можно поставить в соответствие дуальную категорию К. Объекты дуальной категории К суть объекты категории К. Для произвольной пары объектов мн-во морфизмов

Композиция морфизмов в категории К определяется следующим образом: в категории К равно в категории К, где . Можно увидеть, что Очевидно, что если некоторое утверждение верно для категории К, то дуальное ему утверждение верно для дуальной категории К.

Пусть две категории. Функтор (ковариантный) из категории в категорию определяется, во-первых, отображением сопоставляющем каждому объекту А категории объект из категории и, во-вторых, отображением сопоставляющем каждому морфизму . В категории морфизм из категории При этом выполняются следующие аксиомы:

Для двух функторов композиция определяется обычным способом . Аналогично понятию ковариантного функтора вводится понятие контравариантного функтора, которое является к нему дуальным. С каждым контравариантным функтором из естественно ассоциируются ковариантные функторы из и из обратно. Поэтому общее изучение контравариантных функторов может быть сведено к изучению ковариантных функторов. Говорят, что ковариантный функтор определяет изоморфизм между категорией и категорией если для каждого объекта А из существует единственный объект В из такой, что F (В) — А и отображение, сопоставляющее каждому морфизму категории морфизм категории биективно. В этом случае говорят, что категории изоморфны. Категория наз. конкретной, если она изоморфна подкатегории категории Если К — категория и малая категория, то функтор из также диаграммой в X (со схемой ).

Рассмотрим некоторые приложения К. т. к математической логике и кибернетике. Напр., на основе К. т. можно ввести общее понятие теории и алгебр, системы, т. е. развивать семантику логич. систем. Для этого прежде всего введем категорию Обозначим через мн-во так что и т. д. Объектами категории являются морфизмами — все отображения таких мн-в друг в друга, композицией морфизмов — суперпозиции отображений. Важную роль при этом будут играть морфизмы для пар объектов вида Очевидно, что для любого существует ровно различных отображений единица может отображаться либо в 1, либо в 2, либо в 3 и т. д. Если при отображении образом единицы является число , то и само отображение будем обозначать через или , и записывать в виде или

Теорией Г наз. такая категория, что 1) ОЬ есть подкатегория Г; 3) для произвольных данных морфизмов существует единственный морфизм такой, что есть композиция для каждого Таким образом любой морфизм может быть представлен Теория Г и мн-во А определяют Г-алгебру следующим образом. Каждый морфизм и каждый набор из элементов мн-ва А определяют элементов мн-ва следующим образом: 1) если принадлежит то если морфизм Г, то Отметим, что если морфизм Г, то , так, что 0 определяет -местную операцию в алгебре . Пусть мн-во всех морфизмов Превратим в Г-алгебру. По данным имеем и значит в Г, следовательно, композиция определена и является морфизмом в Г. Определим Отметим, что каждое отображение является элементом и, следовательно, есть подмн-во Морфизм двух Г-алгебр — это такое отображение , что Для введенной Г-алгебры на мн-ве верно следующее утверждение: какова бы ни была Г-алгебра , каждое отображение допускает единственное расширение до морфизма алгебр Таким образом, алгебра является свободной алгеброй с базой

Пусть последовательность мн-в и теория Г такова, что Пусть с каждым морфизмом связано положительное целое число такое, что если 0 из если со если то существует единственное и единственная факторизация из Г. Нетрудно убедиться, что теория Г с такими свойствами единственна и она наз. свободной теорией с базой Конгруэнция Q в теории Г — это такое семейство отношений эквивалентности, по одному в каждом мн-ве что, во-первых, если то для каждого для каждого во-вторых, если для всех , то в-третьих, для произвольных из тогда и только тогда, когда Конгруэнция Q в Г-алгебре такое отношение эквивалентности на мн-ве А, что

для любого из Г при условии, что Рассмотрим, напр., теорию алгебрами которой являются полугруппы. Ее можно описать следующим образом. Начинаем со свободной теории, порожденной единственным морфизмом где для Тогда все Г-алгебры этой теории — это мн-ва А с определенной на них бинарной операцией (умножением) . Для того, чтобы задать ассоциативность этой операции, необходимо задать конгруэнцию .

Конечные автоматы можно рассматривать как конечные Г-алгебры и таким образом в рамках К. т. изучать теорию конечных автоматов. Известны также попытки приложения К. т. к программированию. Пусть X — мн-во слов некоторого алфавита мн-во всех возможных исходных данных задачй, а мн-во всех возможных ее решений. Общий метод решения задачи заключается в том, чтобы с каждыми конкретными исходными данными (т. е. отдельными элементами из ) связать частное решение (т. е. отдельный элемент из ), которое этой задаче соответствует. Тогда категория задач — это категория отображения частей мн-ва X в части того же самого мн-ва. Вычислительная машина, алфавитом которой является алфавит X, соответствует некоторому набору задач (простейших машинных операций), т. е. некоторому набору морфизмов из категории задач. Решить задачу при помощи машины означает найти последовательность морфизмов, составленную единственным образом из такую, что произведение их равно Следовательно, морфизм необходимо разложить на «множители», которые все принадлежат множеству «элементарных» задач.

Лит.: Курош А. Г., Лифшиц А. X., Шульгейфер Е. Г. Основы теории категорий. «Успехи математических наук», 1960, т. 15, К I; Ляпунов А. А. К алгебраической трактовке программирования. «Проблемы кибернетики», 1962, Mi 8; Риге Ж. Программирование и теория категорий. В кн.: Кибернетический сборник, в. 9. М., 1964; Буку р И., Деляну А. Введение в теорию категорий и функторов. Пер. с англ. М., 1972; Е i 1 -enberg S., Wrigbt J. В. Automata in general algebras. «Information and control», 1967, т. 11, M 4.

М. И. Кратко.