![[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) собака->кот
- Закон тождества. Пусть есть заклинание превращения в самого себя (как "лОпус-задрОпОс"). Тогда неважно, когда его применять - до другого превращения или после:
человек->волк
все равно, что:
человек->человек, человек->волк
или:
волк->человек
все равно, что:
волк->человек, человек->человек
Всякие-разные морфизмы
Еще один студент с факультета полиморфизма обнаружил в Книге Заклинаний формулу превращения в дракона. Пробормотал: "драгонаутус-фойер-гросс-райзер!" - и превратился в огромное жЫвотное. Попробовал изрыгнуть пламя - вах! Получается! "Ладно", - подумал он, - "а теперь обратно". Обернулся к подставке, на которой лежала книга, а там - только пепел. Упс! Кажется, перестарался огнеметчик.
Вот когда для заданного превращения все-таки есть возможность превратиться обратно - тогда это превращение называется "изоморфизм".
Студент стал искать выход из своего затруднительного положения. Оказалось, что подходящего заклинания - чтобы превратиться из дракона прямиком в человека - никак не обнаруживается. Но нашлось нечто другое: куча заклинаний превращения из дракона в разных животных. Студент решил посмотреть, нельзя ли скомбинировать все эти заклинания так, чтобы найти путь к человеческому облику. Обнаружилось, что есть заклинание лемур->человек и длинная, сложная цепочка заклинаний, ведущих от дракона к лемуру. Причем, единственная цепочка.
Вот такая ситуёвина, когда для первой части превращения есть только один подходящий метод, называется "мономорфизмом".
А "эпиморфизм" – это когда есть только один подходящий вариант для заданной второй части. Скажем, обнаружилось, что из дракона можно превратиться в виверну, тогда студент стал искать путь превращения из виверны в человека, и нашел только один вариант.
"Биморфизм" – когда и для первой, и для второй части есть по одному подходящему варианту.
"Эндоморфизм" – когда одно превращение или серия превращений возвращает к исходной точке, например человек->волк->человек.
"Автоморфизм" – изоморфизм И эндоморфизм.
Тонкость, которую я НЕ понял: чем отличаются тождественный морфизм, эндоморфизм и автоморфизм? На первый взгляд – это одно и то же, в смысле определения эквивалентны. Может ли быть эндоморфизм, который НЕ является единичным? Может ли быть эндоморфизм, который НЕ является изоморфизмом?
Крокодила так просто не возьмешь :)
Пример двух разных равенств для одних и тех же объектов: сравнение строк. Оно может быть "с учетом регистра" или "без учета регистра".
[ При этом становится возможной ПРОЦЕДУРА проверки на то, находятся ли заданные элементы в рассматриваемом отношении. ]
Причем, становится возможной всегда. И также верно и обратное - когда есть процедура, можно построить отношение. Получается наличие отношения необходимо и достаточно для наличия операции.
Вы говорите, что мы можем задать бинарную операцию * как множество упорядоченных пар вида:
((x,y),z)
где x,y,z из M
Ну так с равенством то же самое, это множество упорядоченных пар вида:
((x,y),z)
где x,y,z из M
где M получается объединением {0,1} с множеством N, где x и y всегда оказываются из N, z всегда оказываются из {0,1}
оцифровка слонов
У Вас постоянно делается акцент на идее "взаимозаменяемости", и я не могу отрицать того факта, что вместо рассмотрения какой-то операции можно ввести подходящее отношение. Например, в логике предикатов часто происходит отказ от функциональных символов (призванных обозначать операции) в пользу предикатных символов (которые интерпретируются как отношения). Это вполне стандартный приём, когда вместо f(x,y)=z начинают писать P(x,y,z). Возможны и другие эффекты "взаимозаменяемости", но это не даёт возможности отождествлять одно с другим.
Часто бывает можно ввести некое "кодирование", и вместо одних объектов говорить о других. Мы можем занумеровать слонов, и говорить о свойствах чисел, но это не делает ни слонов числами, ни чисел слонами :)
Поэтому я ещё раз обращаю Ваше внимание на то, что оборот "операция равенства" звучит некорректно -- примерно так же плохо, как оборот "отношение сложения". При этом допустимо говорить "операция сравнения" -- пусть даже не в смысле того, что в математике называется "бинарной операцией".
Re: оцифровка слонов
Ну вот видите. Вот функцию можно задать несколькими способами - таблицей, формулой, словесным описанием. Вас не напрягает, что все эти способы взаимозаменяемы, а функция по-прежнему называется функцией? Вот и меня не напрягает, что операцию равенства можно задать несколькими взаимозаменяемыми способами, а равенство всякий раз называеся операцией. При этом на работе я постоянно использую слово "операция" или "оператор" по отношению равенству - потому, что такая терминология принята у программистов. Так что, как бы оно там ни было корректно у математиков, мне это неудобно, и я все равно буду "сбиваться". Точно как у Вас с "совестью" ;)
мини-расследование
Прежде всего, мне в какой-то программистской литературе встретился термин "операция равенства" -- в качестве частного случая термина "операция отношения". Поскольку литература -- переводная, а качество переводов у нас сами знаете какое, то я решил посмотреть, что же изначально было в оригинале. Оказалось, что "relational operator". Такое словоупотребление у меня вряд ли вызвало бы возражение. По сути дела, это означает особый тип операторов, которые можно было бы назвать "реляционными", то есть связанными с отношениями типа равенства или "больше"/"меньше". Но их в силу тех или иных причин предпочли перевести по-другому. Здесь сыграли роль ещё какие-то явления типа того, что "операторами" по-русски принято было называть то, что по-английски называется "statement". Короче говоря, возникла некая "катавасия", и явно не от хорошей жизни. Так что следовать этой терминологии внутри "программистской кухни" ещё более или менее допустимо (в каждой профессиональной области есть свой жаргон, в конце концов), но вот за её пределами я бы этого делать уже не стал.
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
Что касается Ымманентности, то так можно о чем угодно сказать: какое-то утверждение может быть дано заранее (как аксиома, гипотеза или условие задачки) или может как-то процеДурно устанавливаться).
Лично у меня нездоровый интерес к теме усилился после того, как упомянули монады - эта хрень из функциональных языков программирования, которые (ФЯП) манят, сцуки :)