![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Про теорию категорий в стиле фэнтези
Тут пошла такая пьянка: ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
a_shen помянул теорию категорий, avva помянул теорию категорий... причем, помянули в таком смысле, что это нечто жутко абстрактное, непонятно, как объяснить простым смертным.
Захотелось мне посмотреть, что за страшная такая теория категорий. То есть, попробовать объяснить хотя бы самому себе. :)
Начинать я люблю с определений: раз и два.
Ну что тут скажешь: видим образчики того, как составить определение так, "чтобы никто не догадался". Как нарочно, чтобы было непонятно. Значков много, разложены значки кривовато. Например, определение в вики содержит такое:
"задано множество морфизмов (или стрелок) HomC(A,B)..."
- ну и к чему относится "Hom" - к понятию "морфизм" или к понятию "множество морфизмов"? Я сначала подумал первое, потом стал читать дальше, оказалось - второе. Вот и получается: вроде как математика, формулы, а все-равно - двусмысленности.
Дальше пошли примеры, и, когда сопоставил примеры с определениями, стало более-менее ясно. Не так страшен черт, как его малюют. И объяснить, вроде бы, не так уж и сложно - по крайней мере себе. Можно даже в стиле фэнтези.
Объект
Во-первых, представьте себе некий "объект". Тут есть первая психологическая ловушка - для примера может прийти в голову что-то простое типа "число 5" или "точка A". Так вот, не берите простое, берите сразу сложное - и тогда (как ни парадоксально) понять будет проще.
В качестве объекта возьмем... робота-трансформера или... мага-полиморфа. Маг-полиморф - это который умеет превращаться в разных животных. Все-таки предпочту второе - когда-то для одной игрушки программировал магов-полиморфов, ностальгия, знаете ли. :)
Вот что такое объект. А в категории таких объектов много. То есть, клан магов-полиморфов например. Замечу: это вовсе НЕ аналогия и не художественная метафора, это - вполне корректный пример, частный случай, поскольку теория категорий почти не ограничивает, что именно считать объектами.
Морфизм = превращение
Во-вторых, понятие "морфизм" или "стрелка". Маг-полиморф говорит: "лупус-задрупус-мордус-впередус-жопус-в-хвостус" и превращается, скажем, в волка. Вот морфизм - это и есть превращение. Опять же, для понятности лучше представлять себе превращение сложного объекта в другой сложный объект. Дальше я буду часто говорить "превращение" - мне кажется, это "качественный" и интуитивно понятный перевод термина "морфизм" на русский язык.
Кстати, еще одна психологическая ловушка, мешающая пониманию: слово морфизм - существительное. Но существительные по-умолчанию ассоциируются с предметами. А морфизм удобнее представлять себе как действие с началом и завершением.
Композиция = последовательное превращение
Есть один тонкий момент: может быть много заклинаний превращения мага в волка. Например, заклинание "лупус-задрупус..." заставляет хвост постепенно вырастать из задницы, а заклинание "хомо-дисперсус-конденсус-канис" запускает сложный процесс: сначала превращает мага в облако протоплазмы (первая часть - "хомо-дисперсус"), а потом из облака формируется матерый волчара (вторая часть - "конденсус-канис").
Последний пример называется "композиция". Композиция - это два превращения, идущих друг за другом: маг -> облако протоплазмы -> волк.
Еще одно извращение, мешающее пониманию: вместо того, чтобы писать превращения в порядке применения, их пишут наоборот:
("конденсус-канис" o "хомо-дисперсус")
- значок "o" - обозначает операцию композиции. Почему пишут наоборот - не знаю, может, изобретатель теории категорий был евреем, и ему так привычнее :)
Тождественный морфизм = превращение в себя
А теперь представим себе студента школы магии. Перепутал он "у" и "о" в астральных формулах. Начал балаболить: "лОпус-задрОпОс..." - и дело не пошло. Хвост начал отрастать, но отвалился и испарился. И вроде бы все на месте - лишних деталей не осталось. То есть, была некая попытка превращения, но объект вернулся в прежнее состояние. Вот вам тождественный морфизм.
Категория
Категория - это когда есть совокупность объектов (пример: клан магов-полиморфов), совокупность морфизмов (пример: заклинания превращения, которые используют те маги) и выполняется еще парочка условий.
Что за условия? Да ничего особенного - пара аксиом: ассоциативность и закон тождества.
- Ассоциативность. Пусть маг-полиморф может принимать 4 формы: человек, волк, собака, кот. И пусть есть 4 заклинания:
1. человек->волк
2. волк->собака->кот
3. человек->волк->собака
4. собака->кот
Так вот, закон ассоциативности утверждает, что в кота можно превратиться обоими возможными путями:
(заклинание 1) человек->волк, (заклинание 2) волк->собака->кот
все равно, что:
(заклинание 3) человек->волк->собака, (заклинание 4) собака->кот
- Закон тождества. Пусть есть заклинание превращения в самого себя (как "лОпус-задрОпОс"). Тогда неважно, когда его применять - до другого превращения или после:
человек->волк
все равно, что:
человек->человек, человек->волк
или:
волк->человек
все равно, что:
волк->человек, человек->человек
Всякие-разные морфизмы
Еще один студент с факультета полиморфизма обнаружил в Книге Заклинаний формулу превращения в дракона. Пробормотал: "драгонаутус-фойер-гросс-райзер!" - и превратился в огромное жЫвотное. Попробовал изрыгнуть пламя - вах! Получается! "Ладно", - подумал он, - "а теперь обратно". Обернулся к подставке, на которой лежала книга, а там - только пепел. Упс! Кажется, перестарался огнеметчик.
Вот когда для заданного превращения все-таки есть возможность превратиться обратно - тогда это превращение называется "изоморфизм".
Студент стал искать выход из своего затруднительного положения. Оказалось, что подходящего заклинания - чтобы превратиться из дракона прямиком в человека - никак не обнаруживается. Но нашлось нечто другое: куча заклинаний превращения из дракона в разных животных. Студент решил посмотреть, нельзя ли скомбинировать все эти заклинания так, чтобы найти путь к человеческому облику. Обнаружилось, что есть заклинание лемур->человек и длинная, сложная цепочка заклинаний, ведущих от дракона к лемуру. Причем, единственная цепочка.
Вот такая ситуёвина, когда для первой части превращения есть только один подходящий метод, называется "мономорфизмом".
А "эпиморфизм" – это когда есть только один подходящий вариант для заданной второй части. Скажем, обнаружилось, что из дракона можно превратиться в виверну, тогда студент стал искать путь превращения из виверны в человека, и нашел только один вариант.
"Биморфизм" – когда и для первой, и для второй части есть по одному подходящему варианту.
"Эндоморфизм" – когда одно превращение или серия превращений возвращает к исходной точке, например человек->волк->человек.
"Автоморфизм" – изоморфизм И эндоморфизм.
Тонкость, которую я НЕ понял: чем отличаются тождественный морфизм, эндоморфизм и автоморфизм? На первый взгляд – это одно и то же, в смысле определения эквивалентны. Может ли быть эндоморфизм, который НЕ является единичным? Может ли быть эндоморфизм, который НЕ является изоморфизмом?
a_shen помянул теорию категорий, avva помянул теорию категорий... причем, помянули в таком смысле, что это нечто жутко абстрактное, непонятно, как объяснить простым смертным.Захотелось мне посмотреть, что за страшная такая теория категорий. То есть, попробовать объяснить хотя бы самому себе. :)
Начинать я люблю с определений: раз и два.
Ну что тут скажешь: видим образчики того, как составить определение так, "чтобы никто не догадался". Как нарочно, чтобы было непонятно. Значков много, разложены значки кривовато. Например, определение в вики содержит такое:
"задано множество морфизмов (или стрелок) HomC(A,B)..."
- ну и к чему относится "Hom" - к понятию "морфизм" или к понятию "множество морфизмов"? Я сначала подумал первое, потом стал читать дальше, оказалось - второе. Вот и получается: вроде как математика, формулы, а все-равно - двусмысленности.
Дальше пошли примеры, и, когда сопоставил примеры с определениями, стало более-менее ясно. Не так страшен черт, как его малюют. И объяснить, вроде бы, не так уж и сложно - по крайней мере себе. Можно даже в стиле фэнтези.
Объект
Во-первых, представьте себе некий "объект". Тут есть первая психологическая ловушка - для примера может прийти в голову что-то простое типа "число 5" или "точка A". Так вот, не берите простое, берите сразу сложное - и тогда (как ни парадоксально) понять будет проще.
В качестве объекта возьмем... робота-трансформера или... мага-полиморфа. Маг-полиморф - это который умеет превращаться в разных животных. Все-таки предпочту второе - когда-то для одной игрушки программировал магов-полиморфов, ностальгия, знаете ли. :)
Вот что такое объект. А в категории таких объектов много. То есть, клан магов-полиморфов например. Замечу: это вовсе НЕ аналогия и не художественная метафора, это - вполне корректный пример, частный случай, поскольку теория категорий почти не ограничивает, что именно считать объектами.
Морфизм = превращение
Во-вторых, понятие "морфизм" или "стрелка". Маг-полиморф говорит: "лупус-задрупус-мордус-впередус-жопус-в-хвостус" и превращается, скажем, в волка. Вот морфизм - это и есть превращение. Опять же, для понятности лучше представлять себе превращение сложного объекта в другой сложный объект. Дальше я буду часто говорить "превращение" - мне кажется, это "качественный" и интуитивно понятный перевод термина "морфизм" на русский язык.
Кстати, еще одна психологическая ловушка, мешающая пониманию: слово морфизм - существительное. Но существительные по-умолчанию ассоциируются с предметами. А морфизм удобнее представлять себе как действие с началом и завершением.
Композиция = последовательное превращение
Есть один тонкий момент: может быть много заклинаний превращения мага в волка. Например, заклинание "лупус-задрупус..." заставляет хвост постепенно вырастать из задницы, а заклинание "хомо-дисперсус-конденсус-канис" запускает сложный процесс: сначала превращает мага в облако протоплазмы (первая часть - "хомо-дисперсус"), а потом из облака формируется матерый волчара (вторая часть - "конденсус-канис").
Последний пример называется "композиция". Композиция - это два превращения, идущих друг за другом: маг -> облако протоплазмы -> волк.
Еще одно извращение, мешающее пониманию: вместо того, чтобы писать превращения в порядке применения, их пишут наоборот:
("конденсус-канис" o "хомо-дисперсус")
- значок "o" - обозначает операцию композиции. Почему пишут наоборот - не знаю, может, изобретатель теории категорий был евреем, и ему так привычнее :)
Тождественный морфизм = превращение в себя
А теперь представим себе студента школы магии. Перепутал он "у" и "о" в астральных формулах. Начал балаболить: "лОпус-задрОпОс..." - и дело не пошло. Хвост начал отрастать, но отвалился и испарился. И вроде бы все на месте - лишних деталей не осталось. То есть, была некая попытка превращения, но объект вернулся в прежнее состояние. Вот вам тождественный морфизм.
Категория
Категория - это когда есть совокупность объектов (пример: клан магов-полиморфов), совокупность морфизмов (пример: заклинания превращения, которые используют те маги) и выполняется еще парочка условий.
Что за условия? Да ничего особенного - пара аксиом: ассоциативность и закон тождества.
- Ассоциативность. Пусть маг-полиморф может принимать 4 формы: человек, волк, собака, кот. И пусть есть 4 заклинания:
1. человек->волк
2. волк->собака->кот
3. человек->волк->собака
4. собака->кот
Так вот, закон ассоциативности утверждает, что в кота можно превратиться обоими возможными путями:
(заклинание 1) человек->волк, (заклинание 2) волк->собака->кот
все равно, что:
(заклинание 3) человек->волк->собака, (заклинание 4) собака->кот
- Закон тождества. Пусть есть заклинание превращения в самого себя (как "лОпус-задрОпОс"). Тогда неважно, когда его применять - до другого превращения или после:
человек->волк
все равно, что:
человек->человек, человек->волк
или:
волк->человек
все равно, что:
волк->человек, человек->человек
Всякие-разные морфизмы
Еще один студент с факультета полиморфизма обнаружил в Книге Заклинаний формулу превращения в дракона. Пробормотал: "драгонаутус-фойер-гросс-райзер!" - и превратился в огромное жЫвотное. Попробовал изрыгнуть пламя - вах! Получается! "Ладно", - подумал он, - "а теперь обратно". Обернулся к подставке, на которой лежала книга, а там - только пепел. Упс! Кажется, перестарался огнеметчик.
Вот когда для заданного превращения все-таки есть возможность превратиться обратно - тогда это превращение называется "изоморфизм".
Студент стал искать выход из своего затруднительного положения. Оказалось, что подходящего заклинания - чтобы превратиться из дракона прямиком в человека - никак не обнаруживается. Но нашлось нечто другое: куча заклинаний превращения из дракона в разных животных. Студент решил посмотреть, нельзя ли скомбинировать все эти заклинания так, чтобы найти путь к человеческому облику. Обнаружилось, что есть заклинание лемур->человек и длинная, сложная цепочка заклинаний, ведущих от дракона к лемуру. Причем, единственная цепочка.
Вот такая ситуёвина, когда для первой части превращения есть только один подходящий метод, называется "мономорфизмом".
А "эпиморфизм" – это когда есть только один подходящий вариант для заданной второй части. Скажем, обнаружилось, что из дракона можно превратиться в виверну, тогда студент стал искать путь превращения из виверны в человека, и нашел только один вариант.
"Биморфизм" – когда и для первой, и для второй части есть по одному подходящему варианту.
"Эндоморфизм" – когда одно превращение или серия превращений возвращает к исходной точке, например человек->волк->человек.
"Автоморфизм" – изоморфизм И эндоморфизм.
Тонкость, которую я НЕ понял: чем отличаются тождественный морфизм, эндоморфизм и автоморфизм? На первый взгляд – это одно и то же, в смысле определения эквивалентны. Может ли быть эндоморфизм, который НЕ является единичным? Может ли быть эндоморфизм, который НЕ является изоморфизмом?
no subject
Возвращаясь к категориям, обратите внимание, что отношение равенства между множествами имеет "процедурный" смысл: для установления равенства множеств надо убедиться, что каждый элемент, принадлежащий первому множеству, принадлежит также и второму, и наоборот. Это, в общем, процедура. А для того, чтобы "процедурно" установить отношение равенства морфизмов f:A->B и g:C->D, недостаточно процедурно установить, отношения A=C и B=D.
рекурсия
По поводу равенства множеств всё не так просто. Дело в том, что когда я при помощи описанной Вами процедуры попытаюсь установить, равны ли два множества, то мне придётся каждый элемент каждого из множеств проверить на факт принадлежности другому множеству. В этом случае я извлекаю из одной "авоськи" какой-то элемент, после чего возникает задача проверки, имеется ли во второй "авоське" точно такой же элемент. А тогда мне взятый элемент придётся опять-таки сравнивать с другими элементами, то есть "рекурсивно" вызывать ту же самую процедуру. При этом совершенно не ясно из "априорных" соображений, выдаст ли такая процедура конечный результат.
Из этого следует, что вообще-то равенство множеств полагается чем-то "первичным" или "имманентным". То есть "хозяин" всей этой ситуации заранее должен знать, какие элементы равны, а какие -- нет. Скажем, могло быть так, что он сам "изготовлял" всё своё "хозяйство". И в каких-то случаях речь идёт о "точных копиях", где равенство как бы "гарантировано".
Последний факт насчёт морфизмов не вызывает сомнения, но это просто означает, что разных морфизмов из A в B может быть много. Это совершенно обычная ситуация: так же точно бывает с рёбрами графа. Кстати, я бы вообще при описании категорий привлёк бы понятие графа, если бы надо было донести эти сведения для тех, кто интересуется сутью понятия. Правда, сам этот интерес мне непонятен, так как человек ровным счётом ничего не теряет, если он об этом не имеет никакого представления. Такое понятие в математике могло вообще не возникнуть: оно мне кажется чисто "техническим" и "аппаратным". А ведь есть огромное количество вещей и важных, и интересных по содержанию. А категории часто служат "маскировкой" для тривиальных утверждений. Например, кто-то доказал теорему: "квазиинвариантные функторы локально-банаховых категорий удовлетворяют уравнению Пупкера - Хуцишвили". Переводим на "человеческий" язык, и оказывается, что это означает "производная постоянной функции равна нулю" :)
no subject
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
Что касается Ымманентности, то так можно о чем угодно сказать: какое-то утверждение может быть дано заранее (как аксиома, гипотеза или условие задачки) или может как-то процеДурно устанавливаться).
Лично у меня нездоровый интерес к теме усилился после того, как упомянули монады - эта хрень из функциональных языков программирования, которые (ФЯП) манят, сцуки :)