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

[psilogic]

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

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

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

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

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

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

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



Объект

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Категория

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Comments

Крокодила так просто не возьмешь :)

[psilogic.livejournal.com]

В программировании равенство это такая же операция, как сложение и вычитание. Оно может быть и set-ом, но так никто не станет делать по причине "неинтересности" операций над такими множествами.

Пример двух разных равенств для одних и тех же объектов: сравнение строк. Оно может быть "с учетом регистра" или "без учета регистра".

[ При этом становится возможной ПРОЦЕДУРА проверки на то, находятся ли заданные элементы в рассматриваемом отношении. ]

Причем, становится возможной всегда. И также верно и обратное - когда есть процедура, можно построить отношение. Получается наличие отношения необходимо и достаточно для наличия операции.

Вы говорите, что мы можем задать бинарную операцию * как множество упорядоченных пар вида:
((x,y),z)
где x,y,z из M

Ну так с равенством то же самое, это множество упорядоченных пар вида:
((x,y),z)
где x,y,z из M

где M получается объединением {0,1} с множеством N, где x и y всегда оказываются из N, z всегда оказываются из {0,1}

[drakoniha.livejournal.com]

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


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

[drakoniha.livejournal.com]

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

оцифровка слонов

[falcao.livejournal.com]

Пример со сравнением строк наглядно показывает две вещи. Первая -- это то, что речь идёт не о равенстве, а о каком-то отношении эквивалентности, как я и говоил выше. Вторая: не надо путать равенство как отношение с процедурой сравнения.

У Вас постоянно делается акцент на идее "взаимозаменяемости", и я не могу отрицать того факта, что вместо рассмотрения какой-то операции можно ввести подходящее отношение. Например, в логике предикатов часто происходит отказ от функциональных символов (призванных обозначать операции) в пользу предикатных символов (которые интерпретируются как отношения). Это вполне стандартный приём, когда вместо f(x,y)=z начинают писать P(x,y,z). Возможны и другие эффекты "взаимозаменяемости", но это не даёт возможности отождествлять одно с другим.

Часто бывает можно ввести некое "кодирование", и вместо одних объектов говорить о других. Мы можем занумеровать слонов, и говорить о свойствах чисел, но это не делает ни слонов числами, ни чисел слонами :)

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

Re: оцифровка слонов

[psilogic.livejournal.com]

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

Ну вот видите. Вот функцию можно задать несколькими способами - таблицей, формулой, словесным описанием. Вас не напрягает, что все эти способы взаимозаменяемы, а функция по-прежнему называется функцией? Вот и меня не напрягает, что операцию равенства можно задать несколькими взаимозаменяемыми способами, а равенство всякий раз называеся операцией. При этом на работе я постоянно использую слово "операция" или "оператор" по отношению равенству - потому, что такая терминология принята у программистов. Так что, как бы оно там ни было корректно у математиков, мне это неудобно, и я все равно буду "сбиваться". Точно как у Вас с "совестью" ;)

мини-расследование

[falcao.livejournal.com]

Мне пришлось провести "мини-расследование" в связи с тем, что Вы сказали.

Прежде всего, мне в какой-то программистской литературе встретился термин "операция равенства" -- в качестве частного случая термина "операция отношения". Поскольку литература -- переводная, а качество переводов у нас сами знаете какое, то я решил посмотреть, что же изначально было в оригинале. Оказалось, что "relational operator". Такое словоупотребление у меня вряд ли вызвало бы возражение. По сути дела, это означает особый тип операторов, которые можно было бы назвать "реляционными", то есть связанными с отношениями типа равенства или "больше"/"меньше". Но их в силу тех или иных причин предпочли перевести по-другому. Здесь сыграли роль ещё какие-то явления типа того, что "операторами" по-русски принято было называть то, что по-английски называется "statement". Короче говоря, возникла некая "катавасия", и явно не от хорошей жизни. Так что следовать этой терминологии внутри "программистской кухни" ещё более или менее допустимо (в каждой профессиональной области есть свой жаргон, в конце концов), но вот за её пределами я бы этого делать уже не стал.

[psilogic.livejournal.com]

Да, "оператор" имеет два смысла "операция" или "инструкция", например "оператор условного перехода" (conditional statement), а "операция" используется, как более узкое понятие. Ну, как сложилось, так и сложилось, это не напрягает. А кого напрягает - всегда можно напомнить про "совесть" и, особенно, "гуманизм" ;))

Возвращаясь к категориям, обратите внимание, что отношение равенства между множествами имеет "процедурный" смысл: для установления равенства множеств надо убедиться, что каждый элемент, принадлежащий первому множеству, принадлежит также и второму, и наоборот. Это, в общем, процедура. А для того, чтобы "процедурно" установить отношение равенства морфизмов f:A->B и g:C->D, недостаточно процедурно установить, отношения A=C и B=D.

[krol-hydrops.livejournal.com]

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

рекурсия

[falcao.livejournal.com]

Со словом "гуманизм" как раз всё в порядке: я как-то цитировал статью из Википедии на этот счёт. Там сказано ровно то, что я понимаю под этим словом. Ошибочно как раз отождествлять "гуманизм" и "гуманность", как это нередко случается в "обиходной" речи.

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

Из этого следует, что вообще-то равенство множеств полагается чем-то "первичным" или "имманентным". То есть "хозяин" всей этой ситуации заранее должен знать, какие элементы равны, а какие -- нет. Скажем, могло быть так, что он сам "изготовлял" всё своё "хозяйство". И в каких-то случаях речь идёт о "точных копиях", где равенство как бы "гарантировано".

Последний факт насчёт морфизмов не вызывает сомнения, но это просто означает, что разных морфизмов из A в B может быть много. Это совершенно обычная ситуация: так же точно бывает с рёбрами графа. Кстати, я бы вообще при описании категорий привлёк бы понятие графа, если бы надо было донести эти сведения для тех, кто интересуется сутью понятия. Правда, сам этот интерес мне непонятен, так как человек ровным счётом ничего не теряет, если он об этом не имеет никакого представления. Такое понятие в математике могло вообще не возникнуть: оно мне кажется чисто "техническим" и "аппаратным". А ведь есть огромное количество вещей и важных, и интересных по содержанию. А категории часто служат "маскировкой" для тривиальных утверждений. Например, кто-то доказал теорему: "квазиинвариантные функторы локально-банаховых категорий удовлетворяют уравнению Пупкера - Хуцишвили". Переводим на "человеческий" язык, и оказывается, что это означает "производная постоянной функции равна нулю" :)

[psilogic.livejournal.com]

Процедура проверки равенства множеств X и Y рекурсии не требует, достаточно цикла:

1.1. найти непомеченный элемент e в X
1.2. если не найден, перейти к шагу 2.1
1.3. найти e в Y
1.4. если не найден, результат false
1.5. пометить e в Y
1.6. пометить e в X
1.7. перейти к шагу 1.1
2.1. найти непомеченный элемент e в Y
2.2. если найден, результат false
2.3. результат true

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

Лично у меня нездоровый интерес к теме усилился после того, как упомянули монады - эта хрень из функциональных языков программирования, которые (ФЯП) манят, сцуки :)

[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)), очень удобно ]

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

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

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

[migmit.livejournal.com]

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

[psilogic.livejournal.com]

графы, ага

[migmit.livejournal.com]

Немножко не понял.

[psilogic.livejournal.com]

ну графы как средство представления

[migmit.livejournal.com]

Всё равно нифига не понял.

Начнём от печки: коммент выше "графы, ага" - одобрительный по отношению к моему комменту перед ним, или осуждательный?

[psilogic.livejournal.com]

Обобрительный :))) Графы и в Вики по ссылке имеются.

[beroal.livejournal.com]

Сначала в практику надо протащить хотя бы алгебру. Если программист не знает, что конкатенация последовательностей есть моноид, нахуй ему теория категорий? Ёбаный ад — это состояние education.

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

[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. Язык математических текстов действительно неоднозначный во многих случаях, но в данном случае нужно просто знать идиому.