Про теорию категорий в стиле фэнтези

[psilogic]

Тут пошла такая пьянка: a_shen помянул теорию категорий, avva помянул теорию категорий... причем, помянули в таком смысле, что это нечто жутко абстрактное, непонятно, как объяснить простым смертным.

Захотелось мне посмотреть, что за страшная такая теория категорий. То есть, попробовать объяснить хотя бы самому себе. :)

Начинать я люблю с определений: раз и два.

Ну что тут скажешь: видим образчики того, как составить определение так, "чтобы никто не догадался". Как нарочно, чтобы было непонятно. Значков много, разложены значки кривовато. Например, определение в вики содержит такое:

"задано множество морфизмов (или стрелок) Hom_C(A,B)..."

- ну и к чему относится "Hom" - к понятию "морфизм" или к понятию "множество морфизмов"? Я сначала подумал первое, потом стал читать дальше, оказалось - второе. Вот и получается: вроде как математика, формулы, а все-равно - двусмысленности.

Дальше пошли примеры, и, когда сопоставил примеры с определениями, стало более-менее ясно. Не так страшен черт, как его малюют. И объяснить, вроде бы, не так уж и сложно - по крайней мере себе. Можно даже в стиле фэнтези.



Объект

Во-первых, представьте себе некий "объект". Тут есть первая психологическая ловушка - для примера может прийти в голову что-то простое типа "число 5" или "точка A". Так вот, не берите простое, берите сразу сложное - и тогда (как ни парадоксально) понять будет проще.

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

Вот что такое объект. А в категории таких объектов много. То есть, клан магов-полиморфов например. Замечу: это вовсе НЕ аналогия и не художественная метафора, это - вполне корректный пример, частный случай, поскольку теория категорий почти не ограничивает, что именно считать объектами.

Морфизм = превращение

Во-вторых, понятие "морфизм" или "стрелка". Маг-полиморф говорит: "лупус-задрупус-мордус-впередус-жопус-в-хвостус" и превращается, скажем, в волка. Вот морфизм - это и есть превращение. Опять же, для понятности лучше представлять себе превращение сложного объекта в другой сложный объект. Дальше я буду часто говорить "превращение" - мне кажется, это "качественный" и интуитивно понятный перевод термина "морфизм" на русский язык.

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

Композиция = последовательное превращение

Есть один тонкий момент: может быть много заклинаний превращения мага в волка. Например, заклинание "лупус-задрупус..." заставляет хвост постепенно вырастать из задницы, а заклинание "хомо-дисперсус-конденсус-канис" запускает сложный процесс: сначала превращает мага в облако протоплазмы (первая часть - "хомо-дисперсус"), а потом из облака формируется матерый волчара (вторая часть - "конденсус-канис").

Последний пример называется "композиция". Композиция - это два превращения, идущих друг за другом: маг -> облако протоплазмы -> волк.

Еще одно извращение, мешающее пониманию: вместо того, чтобы писать превращения в порядке применения, их пишут наоборот:

("конденсус-канис" o "хомо-дисперсус")

- значок "o" - обозначает операцию композиции. Почему пишут наоборот - не знаю, может, изобретатель теории категорий был евреем, и ему так привычнее :)

Тождественный морфизм = превращение в себя

А теперь представим себе студента школы магии. Перепутал он "у" и "о" в астральных формулах. Начал балаболить: "лОпус-задрОпОс..." - и дело не пошло. Хвост начал отрастать, но отвалился и испарился. И вроде бы все на месте - лишних деталей не осталось. То есть, была некая попытка превращения, но объект вернулся в прежнее состояние. Вот вам тождественный морфизм.

Категория

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

Что за условия? Да ничего особенного - пара аксиом: ассоциативность и закон тождества.

- Ассоциативность. Пусть маг-полиморф может принимать 4 формы: человек, волк, собака, кот. И пусть есть 4 заклинания:
1. человек->волк
2. волк->собака->кот
3. человек->волк->собака
4. собака->кот
Так вот, закон ассоциативности утверждает, что в кота можно превратиться обоими возможными путями:
(заклинание 1) человек->волк, (заклинание 2) волк->собака->кот
все равно, что:
(заклинание 3) человек->волк->собака, (заклинание 4) собака->кот

- Закон тождества. Пусть есть заклинание превращения в самого себя (как "лОпус-задрОпОс"). Тогда неважно, когда его применять - до другого превращения или после:
человек->волк
все равно, что:
человек->человек, человек->волк
или:
волк->человек
все равно, что:
волк->человек, человек->человек

Всякие-разные морфизмы

Еще один студент с факультета полиморфизма обнаружил в Книге Заклинаний формулу превращения в дракона. Пробормотал: "драгонаутус-фойер-гросс-райзер!" - и превратился в огромное жЫвотное. Попробовал изрыгнуть пламя - вах! Получается! "Ладно", - подумал он, - "а теперь обратно". Обернулся к подставке, на которой лежала книга, а там - только пепел. Упс! Кажется, перестарался огнеметчик.

Вот когда для заданного превращения все-таки есть возможность превратиться обратно - тогда это превращение называется "изоморфизм".

Студент стал искать выход из своего затруднительного положения. Оказалось, что подходящего заклинания - чтобы превратиться из дракона прямиком в человека - никак не обнаруживается. Но нашлось нечто другое: куча заклинаний превращения из дракона в разных животных. Студент решил посмотреть, нельзя ли скомбинировать все эти заклинания так, чтобы найти путь к человеческому облику. Обнаружилось, что есть заклинание лемур->человек и длинная, сложная цепочка заклинаний, ведущих от дракона к лемуру. Причем, единственная цепочка.

Вот такая ситуёвина, когда для первой части превращения есть только один подходящий метод, называется "мономорфизмом".

А "эпиморфизм" – это когда есть только один подходящий вариант для заданной второй части. Скажем, обнаружилось, что из дракона можно превратиться в виверну, тогда студент стал искать путь превращения из виверны в человека, и нашел только один вариант.

"Биморфизм" – когда и для первой, и для второй части есть по одному подходящему варианту.

"Эндоморфизм" – когда одно превращение или серия превращений возвращает к исходной точке, например человек->волк->человек.

"Автоморфизм" – изоморфизм И эндоморфизм.

Тонкость, которую я НЕ понял: чем отличаются тождественный морфизм, эндоморфизм и автоморфизм? На первый взгляд – это одно и то же, в смысле определения эквивалентны. Может ли быть эндоморфизм, который НЕ является единичным? Может ли быть эндоморфизм, который НЕ является изоморфизмом?

Comments

[eterevsky.livejournal.com]

You're missing the point. Морфизм — не превращение, а маг-полиморф плохо подходит в качестве примера объекта категории.

Категория — это обычно класс математических объектов, являющихся множествами с какими-то определёнными на них операциями или структурами. Типа колец или групп, или полуколец, или полей, или топологических пространств.

Морфизм — это отображение из одного такого объекта в другой, сохраняющее внутреннюю структуру.

И вообще, всё это очень технические математические подробности. Мне сложно себе представить, как это может быть полезно не-математику.

[psilogic.livejournal.com]

[ You're missing the point ]

May be. Just show me :)

[ Морфизм — это отображение из одного такого объекта в другой, сохраняющее внутреннюю структуру. ]

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

[ не сложно себе представить, как это может быть полезно не-математику. ]

Прежде, чем думать полезно-бесполезно - хорошо бы понять, о чем речь.

Полезность, например, если отображение из A в B не является взаимно-однозначным, тогда нельзя его использовать в качестве шифра - обратно не расшифруешь.

[akuklev.livejournal.com]

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

А в других часто используемых категориях это совсем не так. Например, в категориях кобордизмов, узлов, кос, лент, группоидах, категорных представлениях формальных систем, порядковых категориях и категориях зависимостей, активно используемых в software engeneering.

есть примемения!

[dimmel.livejournal.com]

Одна из моих многочисленных дочек, надолго зависла, представляя себе превращение шарика в колечко... 8-)))

[akuklev.livejournal.com]

Гораздо более удачный русский перевод слову морфизм — “переход”.
Чаще всего конечно употребляются категории, где объекты — это множества, снабжённые дополнительной структурой, а переходы — отображения между ними, эту дополнительную структуру сохраняющие. Однако бывают другие очень нужные в народном хозяйстве категории, где переходы не отображения и не трансформации.

Пример 1: Категория множеств с включениями в качестве переходов. Т.е. между двумя множествами A и B всегда не более одного перехода и он есть тогда и только тогда, когда все элементы множества A также являются элементами множества B.

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

Пример 3: Категория кобордизмов. В простейшем одномерном случае её объекты — это гладкие замкнутые компактные кривые на плоскости, возможно из нескольких несвязных кусков. А переходы — “резиновые шланги”, соединяющие эти кривые.

На картинке нарисован переход из кривой “два кружочка” в кривую “один кружочек”.

Во всех случаях подходит название “переход”, но далеко не во всех “превращение”.

> Может ли быть эндоморфизм, который НЕ является единичным? Может ли быть эндоморфизм, который НЕ является изоморфизмом?
Конечно!

Вот давайте рассмотрим категорию множеств с отображениями в качестве переходов. Теперь рассмотрим множество целых чисел. Если мы будем отображать каждое число в себя, получится тождественный морфизм, он же единичный. Если мы будем отображать число n в (-n), то есть, отразим ось, мы получим автоморфизм, не являющийся единичным. Если мы будем каждое число n отображать в 2n, это эндоморфизм (отображает объект внутрь себя), не являющийся автоморфизмом.

[psilogic.livejournal.com]

[ Категория множеств с включениями в качестве переходов. ]

- маг превратился в меньшую часть себя, например, в ребенка или в говорящую голову профессора Доуэля или в бегающую руку из "семейки Адамсов" :)

[ Тут между двумя объектами обычно если есть хоть один переход, то их много неэквивалентных. ]

- много способов превратиться из человека в волка? задача доказательства теоремы как поиск превращения.

[ А переходы — “резиновые шланги”, соединяющие эти кривые. ]

High Templar + High templar -> Archon :)))

[ Если мы будем отображать число n в (-n), то есть, отразим ось, мы получим автоморфизм, не являющийся единичным. ]

Как так не являющийся? Допустим, я отобразил множество рациональных R в множество целых Z (функцией округления), потом применил этот автоморфизм - получилось множество целых Z (утверждение аксиомы R->Z->Z = R->Z выполняется). Теперь применил автоморфизм Z->Z, потом Z->R' (функцией деления на два) и опять (утверждение аксиомы Z->Z->R' = Z->R' выполняется)

[ Если мы будем каждое число n отображать в 2n, это эндоморфизм (отображает объект внутрь себя), не являющийся автоморфизмом. ]

Примеры, в общем, понятны, непонятно, где в Вики или algebraic.ru вообще упоминаются элементы множества? Там все определения оперируют "объектами", в ваших примерах объекты - это множества, а не числа, являющиеся элементами множеств.

[akuklev.livejournal.com]

Кстати, картинка-то почему в оригинальном комменте не отразилась? Та, что про кобордизм? Вот эта:

[akuklev.livejournal.com]

А, ещё один классический пример: объекты категории точки некоего топологического пространства, а переходы между ними — непрерывные кривые с началом в первой точке и концом во второй. Это получается специальная такая категория, в которой каждый переход обратим. Такие категории называются группоидами.

Если в моём примере отождествить гомотопически эквивалентные пути (пути, которые можно перевести один в другой непрерывным перемещением), то получится определение так называемого фундаментального группоида пространства.

[akuklev.livejournal.com]

От себя очень посоветую две вещи:
http://math.ucr.edu/home/baez/rosetta.pdf — автор делает экскурс в заросли категорий, встречающихся в логике, топологии, физике и информатике, анализируя параллели и вводя классификацию.
http://www.math.harvard.edu/~mazur/preprints/when_is_one.pdf — сильное введение в категорный взгляд на математику.

Вот в этой знаменитой книжке (http://en.wikipedia.org/wiki/Categories_for_the_Working_Mathematician) с тысячей примеров написано, зачем категории нужны в народном хозяйстве в математике. Т.е. вот не как какой-то там “удобный язык” или “категорный взгляд”, а как гибкий и сложный инструмент повседневной работы, дающий нетривиальные результаты.

К сожалению, я не знаю книги, где бы последовательно изложили применение теорката в информатике и software engeneering, хотя там шикарно и обильно с применениями. Ещё категории совершили революцию в логике и теории моделей, тут я тоже ничего не читал, просто семинары слушал, так что не знаю как с литературой.

Ну а я с теорией категорий серьёзно познакомился на примере топологических квантовых теорий поля, есть в мат.физике такой интересный объект исследования.

[psilogic.livejournal.com]

Большое спасибо, надо будет покопаться :) Черт с ним, если для информатики неважно.

[thedeemon.livejournal.com]

+1 к Розетте.
Там и про категории в программировании есть немножко (категория с объектами-типами данных и морфизмами-функциями).

[bsivko.livejournal.com]

Это все какой-то научный раздел или собранный велосипед?

[psilogic.livejournal.com]

Просто пытаюсь разобраться для себя на наглядном примере.

Граф стрелок

[gilgatech.livejournal.com]

Лучше уж стрелки чем вектора. Будем ждать тёрки по понятиям.

[metaclass.livejournal.com]

Теория категорий это ебаный ад, дальше первых нескольких глав у Пирса (Category Theory for Computer Sciencists) я не продвинулся. Т.е., вообще говоря, я вижу, что кое-где она бы пригодилась, но между обычным матаном вузовского уровня для прикладников и теорией категорией такой провал в математическом образовании, что, в отличие от очевидного применения теории множеств к DBMS, совсем непонятно как притащить ее в практику.

[psilogic.livejournal.com]

а теория групп у тебя в вузе была?

морфизмы с приставками

[falcao.livejournal.com]

Толкование слова "морфизм" как "превращение" мне кажется вполне адекватным. Но У Вас тут есть много смысловых неточностей.

Прежде всего, изоморфизм предполагает нечто большее. В Вашем примере было заклинание, превращающее человека в дракона. При этом существовало "обратное" заклинание, превращающее дракона в человека. Для того, чтобы можно было говорить об изоморфизме, нужно ещё одно условие. А именно, если изначально был дракон, который захотел стать человеком при помощи этого самого "обратного" заклинания, то он потом после превращения в человека обязан превратиться в "изначального" дракона при помощи самого первого из упомянутых заклинаний.

Я предпочитаю записывать композицию морфизмов в порядке их применения. В такой нотации, если f был морфизмом A в B, то должен существовать такой морфизм g из B в A, для которого не только f o g = id_A, но и g o f = id_B. Только в этом случае про f можно говорить, что это изоморфизм.

> чем отличаются тождественный морфизм, эндоморфизм и автоморфизм?

Рассмотрим категорию, объектами которой являются конечные множества, а морфизмами -- отображения этих множеств друг в друга. Тождественным морфизмом объекта A={1,2,3} в себя будет такой морфизм I, при котором I(1)=1, I(2)=2, I(3)=3. Это будет и автоморфизм, и эндоморфизм. Но обратное неверно.

А именно, если определить отображение f из A в A при помощи равенств f(1)=2, f(2)=3, f(3)=1, то это будет изоморфизм объекта A в себя, то есть автоморфизм. Он же будет и эндоморфизмом. А вот если взять что-то вроде h из A в A такого, что h(1)=1, h(2)=1, h(3)=2, то это уже не будет автоморфизм, но эндоморфизмом он является.

На мой взгляд, знакомство с терминологией теории категорий практически не даёт ничего полезного. Приходится заучивать много новых слов, мотивировка которых не всегда понятна. Употреблять же эти слова даже многим специалистам приходится редко. Скажем, я в своих статьях НИКОГДА не употребляю категорного языка.

Re: морфизмы с приставками

[psilogic.livejournal.com]

Сэр Тигр, Вас я оставлю "на сладкое", вечерком обдумаю :) akuklev мне уже частично мозги вправил, будет материал "на закрепление".

[thedeemon.livejournal.com]

Реквестирую иллюстрацию natural transformation и монады!

В помощь: http://www.pureanimegallery.com/v/ergoproxy/misc/monad2-proxy.jpg.html :)

[psilogic.livejournal.com]

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

Мебель Вам привезли?.. ;-)

[alisarin.livejournal.com]

"Категории обыденного сознания" - http://nounivers.narod.ru/ofir/coc.htm ...

Re: Мебель Вам привезли?.. ;-)

[psilogic.livejournal.com]

это не те категории. по ссылке категория = класс или категория = множество

[66george.livejournal.com]

Сам подход мне нравится, но конкретные примеры не все верны. Объяснять долго, но в обозримом будущем напишу учебник. Вот здесь было много книжек
http://community.livejournal.com/category_theory/2190.html
лично мне больше всего нравится книга Ламбека и Скотта. Теорию категорий придумали два человека (Эйленберг и Маклейн), кто из них еврей, не знаю. Запись композиции функций в обратном порядке - стандартная математическая запись. В теории категорий от неё часто отходят и записывают композицию в том порядке, в каком идут морфизмы на картинке.

[psilogic.livejournal.com]

[ Запись композиции функций в обратном порядке - стандартная математическая запись. ]

а, вот значит откуда оно взялось f(g(x)) - но все же операции записываются в прямом порядке, когда без скобок то

[drakoniha.livejournal.com]

А теперь представим себе студента школы магии. Перепутал он "у" и "о" в астральных формулах. Начал балаболить: "лОпус-задрОпОс..." - и дело не пошло. Хвост начал отрастать, но отвалился и испарился. И вроде бы все на месте - лишних деталей не осталось. То есть, была некая попытка превращения, но объект вернулся в прежнее состояние. Вот вам тождественный морфизм.


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

[drakoniha.livejournal.com]

впрочем, я не математик... и даже не физик.

[krol-hydrops.livejournal.com]

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

[migmit.livejournal.com]

"задано множество морфизмов (или стрелок) Hom_C(A,B)..."

- ну и к чему относится "Hom" - к понятию "морфизм" или к понятию "множество морфизмов"?

Написано же, русским языком - множество. Был бы один морфизм, так и написали бы: "морфизм".

Вот морфизм - это и есть превращение.

???
Вообще-то, морфизм - вещь сугубо статическая, исходный объект никуда не девается, целевой ниоткуда не появляется.

Почему пишут наоборот - не знаю, может, изобретатель теории категорий был евреем, и ему так привычнее :)

Потому что композицию обычных функций пишут, как правило, в таком порядке. А это потому, что тогда получается fog(x)=f(g(x)), очень удобно.

То есть, была некая попытка превращения, но объект вернулся в прежнее состояние. Вот вам тождественный морфизм.

Вообще, надо иметь в виду, что тождественный морфизм - это не любой морфизм с одинаковыми началом и концом. Метафора это явно смазывает.

Насчёт эпи- и мономорфизмов - вообще неправда. Это совершенно иные понятия.

Может ли быть эндоморфизм, который НЕ является единичным?

Да их дохрена.

Может ли быть эндоморфизм, который НЕ является изоморфизмом?

Да вы возьмите что-нибудь попроще, легче будет понимать. Возьмите объекты - множества (пусть даже конечные множества), морфизмы - функции между ними. И сразу получится: объект X={1,2}, функция из Hom(X,X), переводящая всё в 1. Такая себе const 1. Эндоморфизм, не изоморфизм (не биекция), не единичный уж всяко.

[psilogic.livejournal.com]

[ Написано же, русским языком - множество. ]

Ну "Hom" - это не русским языком :) Другой пример: "эскадрилья самолетов Thunder", Thunder - это название самолета или эскадрильи?

[ Вообще-то, морфизм - вещь сугубо статическая, исходный объект никуда не девается, целевой ниоткуда не появляется. ]

Математика вся статическая, но это не мешает в некоторых случаях использовать такого рода названия, например "производная". Тоже ведь при производстве исходный материал расходуется, а исходная функция никуда не девается.

[ А это потому, что тогда получается fog(x)=f(g(x)), очень удобно ]

Да, мне уже пояснили. Но для бинарных связок более привычен другой порядок.

[ Метафора это явно смазывает. ]

Согласен. Ну мне потом в комментах объяснили.

[beroal.livejournal.com]

А пример мне понравился. :) Хотя я встречал уже похожий, только вместо магов-полиморфов там были геометрические фигуры.

Я считаю, пример нужно уточнить. Множество объектов — это множество состояний мага-полиморфа. Для получения одной категории достаточно одного мага-полиморфа, поэтому о «клане магов-полиморфов» можно забыть. Важный момент, что из состояния A в состояние B могут быть разные заклинания. Если каждое hom-множество имеет ≤1 элементов, такая категория называется тонкой или категория-предпорядок. Этот момент важен именно для разницы эндоморфизм — тождественный морфизм, изоморфизм — два встречно направленных морфизма. В тонкой категории этой разницы нет. Изомофризм — это не просто два заклинания f0 и f1, такие что f1∘f0 возвращает в начальное состояние. f1∘f0 должен быть тождественным морфизмом. Здесь нужно придумать образ, который бы различал эндоморфизм и тождественный морфизм.

Ваше определение мономорфизма я не понял, но боюсь что оно совсем неправильное. Мономорфизм имеет смысл только если hom-множество имеет >1 элемента. В тонкой категории любой морфизм есть мономорфизм.

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

[beroal.livejournal.com]

Значков много, разложены значки кривовато. Например, определение в вики содержит такое:

"задано множество морфизмов (или стрелок) Hom_C(A,B)..."

Определение «для каждого a задано f(a)» означает лишь то, что задана функция f. Такая идиома. В данном примере задана Hom_C:ob×ob→Set. Язык математических текстов действительно неоднозначный во многих случаях, но в данном случае нужно просто знать идиому.