Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

О теоркате, говорите, рассказать?

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

В начале я узнал об алгебраичесих структурах вообще. В школе говорили «множество натуральных чисел», «множество целых чисел», «множество рациональных чисел». А дома говорили по-другому: «ряд* натуральных чисел», «кольцо целых чисел», «поле рациональных чисел». Я спросил и мне сказали, что дело в том, что если рассматривать натуральные или ещё какие-нибудь числа просто как множества, забывая об операциях над числами и отношениях между числами, то мы теряем всё то, что делает числа числами. Нет никакого способа узнать какое число какое, а множество целых чисел неотличимо от множества натуральных: оба можно себе представить, как бесконечно большую кучу шариков, беспорядочно лежащих в мешке.
[* Ряд в смысле «линейно-упорядоченное множество».]

А вот если рассматривать множество вместе с некоторыми операциями и отношениями на нём, то в мешке уже не просто куча шариков, а шарики, соединённые между собой жёсткими стержнями в какую-то объёмную структуру. А главное, операции и отношения позволяют нам взять такой вот незнакомый мешок и идентифицировать шарики единственно правильным образом. Если мы возьмём натуральный ряд, то даже не зная, что он натуральный, сможем в этом убедиться: нужно найти начальный элемент ряда, это будет ноль. Потом посмотреть следующий — это будет 1. Следующий — 2. Если мы таким образом не исчерпаем весь ряд, значит он натуральный. Или вот поле рациональных чисел: найдём нейтральный элемент сложения, то есть такой, что сколько его к числу не прибавляй, число не изменится. Это будет ноль. Потом найдём нейтральный элемент умнжения, то есть такой, что сколько число на него не умножай, оно не изменится. Это единица. Складывая и отнимая единицу от нуля мы найдём и подпишем все целые числа, деля целые друг на друга найдём и подпишем все рациональные. Если на этом не встретимся с коллизией (это когда мы собрались подписать шарик, а он уже подписан, причём каким-то другим, неравным образом) и исчерпаем всё поле — это было поле рациональных чисел.*
[* Позже я ещё узнал, что числа несут на себе туеву хучу структур. Натуральные числа это ряд, если рассматривать операцию incr или порядок. Если рассматривать сложение и умножение, то это полукольцо. Если min и max или gcd (НОК) и lcm (НОД), то решётка.]

Так я встретился с понятием алгебраической структуры и понял, что вся соль не в элементах, а в отношениях и операциях.

Потом я убедился в огромной пользой изучения алгебраических структур в народном хозяйстве. Дело было так: я узнал, что симметрии разных штук образуют алгебраические структуры под названием «группы симметрии». Есть группы симметрии многоугольников и многогранников, многочленов и уравнений, кристаллов и обоев (двумерных) кристаллов, геометрий и физик.

И если изучать эти самые группы, то можно кучу всего классифицировать! Во-первых, можно классифицировать все правильные многогранники (их пять, это сделал ещё Платон), все виды обоев (их 17), все виды кристаллов (их 230) и квазикристаллов (ещё около 400 видов, точное число не помню, а искать лень), выделить среди полиномиальных уравнений разрешимые в радикалах (сделал Галуа — разрешимы в точности те, у которых группа симметрии обладает опредлённым красивым свойством), классифицировать однородные геометрии (эвклидова, лобачевского и т.д. — придумал и сделал Клейн), а также классифицировать элементарные частицы (в известном смысле, work in progress).

Симметрия — это такая операция (поворот/отражение/сдвиг/масштабирование пространства или перестановка местами переменных/корней уравнения), которая сохраняет определённый объект (многогранник, уравнение) неизменным. Так вот если у нас есть две таких операции, то их можно произвести последовательно, и тогда мы получим третью с тем же свойством. Ну и кроме того такая операция обязательно обратима, на то ведь она и симметрия. Так и возникло определение группы симметрий: группа симметрий — набор обратимых операций, замкнутый относительно их последовательного комбинирования. Ну и от операций требуется, чтобы они были обратимыми (на то они и симметрии), а от комбинирование, чтобы оно было ассоциативным (на то оно и комбинирование).

А дальше мы абстрагируемся от того, что элементами групп симметрии являются какие-то операции и даём чисто аксиоматическое определение: множество, снабженное ассоциативной бинарной операцией композиции, причём у этой операции есть нейтральный элемент (тривиальная симметрия) и у каждого элемента есть относительно неё обратный. К сожалению, для полученного обратного объекта в математике укоренилось название «группа», а не, скажем, «симметроид». Гораздо более говорящее было бы название. Тем более, что объект, который имеет аналогичное определение без требования обратимости называется моноидом.

Категория как алгебраическая структура это просто обобщение моноида. Так вот дальше, в чуть более взрослом возрасте я узнал, что обратимые квадратные матрицы n×n с элементами из кольца K образуют по умножению группу GLn(K). Все квадратные матрицы n×n образуют моноид MLn(K). А вот как же быть с прямоугольными матрицами? Не любые прямоугольные матрицы можно умножать, а только если ширина первой соответствует высоте второй.

Всевозможные конечномерные матрицы с элементами из кольца K образуют так называемую категорию Mat(K). В моноиде было одно множество M элементов и для любых двух была определена композиция. В категории наличествуют не просто элементы, а переходы (Transitions, Übergänge), и совмещать их можно только когда они стыкуются. У переходов определены источник (source) и цель (target), и переходы стыкуются тогда и только тогда когда target одного совпадает с source другого.

Вернёмся к примерам: В Mat(K) у нас переходы это матрицы, а «стыкуются» они когда высота одной равна ширине другой, т.е. в качестве source надо использовать натуральное число «ширина», а в качестве target натуральное число «высота».

Пример с матрицами элементарно обобщается на типизированные лямбда-исчисления и конструктивные теории типов! Вся суть любой такой типизированной теории T выражается в категории Func(T), где переходы суть конструктивные (конструируемые в данной теории) функции а стыкуются они тогда, когда входной тип первой соответствует выходному типу второй.
[Внимание: Очень важно помнить, что в конструктивных теориях типов в Func(T) действительно обитают вычислимые функции (причём не все), а в тьюринг-полных теориях типов (большинство типизированных лямбда-исчислений) обитают вычислимые частичные функции (причём все). Частичность означает, что на некоторых входных функция «входит в бесконечный цикл» и результата не производит.]

Другой важнейший для логиков и информатиков пример категории — это категория Prf(L), где переходы это доказательства, их target это утверждение, которое они доказывают, их source это утверждение, которое принимается в качестве допущения. (L — логика, которая используется в этих доказательствах.)

Вернёмся к теории: Множество переходов между A и B по новой моде обозначают (A => B), такое обозначение одинаково интуитивно и для случая Prf(L), и для случая Func(T), и для случая Mat(K), и для всех известных мне других случаев.

Очень важно понять, что «концы» переходов это просто метки, призванные обозначить какие стрелки стыкуются, а какие нет. От этих меток не требуется даже чтобы они образовывали множество*, просто какие-то метки и всё.
Тем не менее, эти метки по причинам, которые станут понятны ниже, они называются объектами категории.
[Чтоб работать удобнее, обычно требуют, чтобы метки являлись множествами, но не требуют чтобы они образовывали множество; им вполне позволительно образовывать большой класс.]

Кроме наличия ассоциативной операции композиции (f: A => B, g: B => C) ↦ f ○ g: A => C, от категории ещё требуется чтобы в каждом (A => A) был нейтральный элемент idA. Таким образом моноид это просто категория с одним объектом.

Геометрическое применение категорий.
Категории имеют применения в дифференциальной топологии: там в качестве объектов рассматривают замкнутые многообразия (в одномерном случае это один или несколько кружочков), а в качестве переходов, многообразия более высокой размерности, у которых концевые объекты являются краями (в двумерном случае это такие колготки, соединяющие кружочки). Называется эта штука категорией кобордизмов.

Если в категории все переходы обратимы, она называется группоидом. Как моноид это категория с одним объектом, так группа это группоид с одним объектом. Самый естественный пример — т.н. фундаментальный группоид пространства/графа: метки там это точки пространства или вершины графа, а переходы — это пути между этими точками, самые что ни на есть переходы — пешком из пункта A в пункт B.

Для геометрических нужд Lawvere придумал ещё и обобщение категории: «категории над X». В обычных категориях (A => B) это всегда множество. А в «категориях над Х» (A => B) это X. Характерный пример: метрическое пространство можно рассматривать как категорию над R+. Метки это точки, (A => B) это числа, а именно расстояния от A до B, а закон композиции превращается в неравенство треугольника.

Вообще обобщённая категория — это настолько общая структура, что какую хрень в математике не возьми, под определённым углом зрения окажется что это оно.

Категории как высшие структуры. Мы уже рассмотрели категории как алгебраические структуры: совокупность матриц с операцией умножения, совокупность всяческих конструируемых функций или частичных функций с операцией композиции. Это, однако, лишь одна сторона дела. Самая интересная информатикам, но не самая интересная математикам.

Дело в том, что вместо того чтобы рассматривать конструируемые функции для какой-нибудь конструктивной теории типов (их всегда счётное множество, мы же рассматриваем только штуковины, которые можно записать при помощи конечного числа символов), можно рассмотреть вообще все возможные множества и все функции между ними. Получится категория Set. Можно рассмотреть все топологические пространства и непрерывные отображения между ними; получится Top. Можно рассмотреть все конечномерные векторные пространства над K и все линейные отображения между ними; получится категория K-Vect. Её конечномерная часть это почти то же самое, что Mat(K), т.к. любое линейное отображение между конечномерными векторными пространствами можно представить в виде матрицы однозначным образом, если выбрать в этих пространствах базисы, т.е. закрепить изоморфизмы с Kn.

Так вот, для любой алгебраической структуры можно построить категорию, где объекты это реализации этой алгебраической структуры, а переходы — функции между ними, сохраняющие структуру, т.н. гомоморфизмы. Выясняется, что это исследование таких категорий — весьма плодотворный способ исследовать структуры, и блестяще плодотворный способ для ведения «бухгалтерии» в алгебре, т.е. записывать доказанные самыми разными способами результаты так, чтобы проявлялась их общность.

Можно вообще забыть, что объекты это какие-то множества, состоящие из каких-то элементов. Можно рассматривать их просто как метки source и target переходов. А всю остальную информацию можно восстановить из переходов. Например, если рассматривать категорию Set, то элементы любого множества X это в точности функции из одноэлементного множества в X. Вообще в любой категории, состоящей из алгебраических структур на основе множества, элементы этого множества можно совершенно спокойно «забыть», а затем восстановить «внутрекатегорными методами» при помощи т.н. леммы Йонеды.

Плодотворность категорного подходя подводит к весьма глубокой с точки зрения философии математики мысли: морфизмы (переходы) важнее объектов. Вся информация о внутренней структуре объектов хранится в сети переходов между объектами.


[Дальше информатикам можно не читать]


Пояснение: Я не объяснил, почему в таком случае категория перестаёт быть алгебраической структурой. Что-ж, объясню.

Алгебраические структуры вроде группы или кольца это всегда множество (или несколько множеств), снабженные какими-то дополнительными операциями и отношениями. А функции и отношения как известно можно задать их графиком, то есть множеством пар. Иными словами, алгебраическая структура всегда может быть задана набором множеств, удовлетворяющим определённому набору отношений. Т.е. совокупность всех реализаций определённой алгебраической структуры это подкласс класса (Set, Set,.., Set), где класс всех множеств Set взят нужное количество раз (пара классов всегда образует класс, и любой класс может быть отфильтрован любым предикатом, так что такая конструкция всегда возможна). И так как по меньшей мере первый Set в этом кортеже ничем не ограничен, то это класс большой, т.е. в качестве множества не представимый.

Краткий вывод: существует класс всех групп, класс всех колец, класс всех топологических пространств и т.д., и эти классы всегда большие.

Теперь напомню, как можно определить категорию:
– В начале берут прямое произведение класса троек (S: Set, T: Set, f: Set) и класса троек (f: Set, g: Set, f ○ g: Set).
Первый множитель произведения — класс переходов, там S и T это метки source и target, а f сам переход как-нибудь представленный в виде множества. Второй множитель — представление операции композиции.
– Потом фильтруют этот класс, чтобы были выполнена ассоциативность и унитальность, а также чтобы для каждой выбранной пары S и Е соответствующее фильтрование класса переходов было представимо множеством (это свойство называется локальной малостью и необходимо для сколько-нибудь осмысленной работы с категорией).

Так вот, если первый множитель произведения является множеством, то и всё произведение тоже является множеством. Категория называется малой и можно построить класс всех малых категорий. Малые категории — обычная алгебраическая структура.
Однако же если первый множитель является большми классом, то вся категория целиком тоже является большим классом. А большие классы никакой совокупности не образуют. То есть никакого класса «всех категорий», к сожалению, не существует.

В то время как категория малых категорий милейшая штука, категория всех категорий — объект, которому весьма затруднительно дать определение.

Категории (большие) относятся к семейству т.н. гигантских структур. В него входят сами классы (гигантские множества), ряд ординалов (гигантский ряд), поле сюрреальных чисел (гигантское поле).

В последние годы достигнут значительный прогресс в характеризации таких объектов. Классы возникают как идеалы категории множеств, гигантские ряды как идеалы категории Ord (в частности, ряд ординалов является универсальным идеалом), гигантские поля как идеалы категории полей (сюрреальные числа являются универсальным идеалом категории упорядоченных полей), а категория всех категорий как универсальный идеал категории малых категорий.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 37 comments