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

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

Тут пошла такая пьянка:

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

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

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

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

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

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

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

Объект

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Категория

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Flat | Top-Level Comments Only

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

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

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

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

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

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

Тогда там неправильное опЕрделение?

"Морфизмы объекта A в себя называются эндоморфизмами"

- в Вашем примере получается h из A={1,2,3} в A'={1,2}

Что касается употребления: в программировании используют понятные термины: "отношение один к одному", "один ко многим" и т.п. imho тут удобно, т.к. запоминать ничего не надо

А что Вам кажется не соответствующим определению? Там вообще-то всё правильно.

> в Вашем примере получается h из A={1,2,3} в A'={1,2}

Нет, это не так. Я рассматриваю отображение из A в A, в соответствии с понятием отображения. На это я имею право несмотря на то, что значение 3 оно не принимает. Напомню, что отображением f из A в B называется правило, которое каждому элементу из A сопоставляет некоторый элемент из B. При этом нигде не говорится, что все элементы из B должны быть "поюзаны". Это дополнительное требование, которое может быть наложено, но тогда получается понятие "сюръективного" отображения, которое также называют отображением A на B.

Вы правы только в том, что отображение из {1,2,3} в {1,2} тоже можно рассмотреть, но это будет уже другой морфизм, и он эндоморфизмом не будет.

Если нужен более "чистый" пример, то можно рассмотреть его на примере бесконечных множеств. Скажем, взять морфизм из N в N, заданный по правилам h(1)=h(2)=1, h(3)=2, h(4)=3 и так далее. Это будет эндоморфизм, но он не является автоморфизмом.

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

Кстати, вся терминология касательно соответствий, отношений и операций -- это намного полезнее теоретико-категорных понятий.

[ А что Вам кажется не соответствующим определению? ]

То, что в определении говорится A про "морфизм в себя", и Вы это трактуете как "в подмножество себя". Но там нигде не прописано, что A есть множество, а значит нет никаких оснований подразумевать подмножество, а под морфизмом - отображение множества на множество, это может быть только частным случаем. Следовательно, "в себя" может значить разве что эквивалентность объектов (A=A). Я непраф?

[ можно рассмотреть его на примере бесконечных множеств ]

Ага, вот это я понимаю.

[ говорить следует о соответствиях, а не об отношениях ]

Тут, к сожалению, чисто терминологическая нестыковка: в программировании "отношение" - это слово, специально "зарезервированное" под это дело:
вот это

Ваша ошибка заключается в том, что предлог "в" Вы пытаетесь трактовать "содержательно". Представьте себе, что есть единый оборот типа "отображение-из-A-в-B". Так просто принято говорить. В этой "мать-и-мачехе" не надо пытаться найти союз "и" :)

Морфизм в категории, конечно, может не быть отображением. Например, может быть дан граф, у которого "объектами" будут вершины, а "морфизмами" -- направленные рёбра. Что угодно может быть. Всякий морфизм, согласно определению, это морфизм некоторого объекта A в некоторый объект B. Это означает, что у каждого морфизма есть свой "порт приписки" (A) и "порт назначения" (B).

Если имеет место частный случай, состоящий в том, что A=B, то такой морфизм называется "эндоморфизмом" (объекта A). В словесной форме это принято выражать оборотом "из A в себя", что по смыслу совершенно то же, что "из A в A".

Выше Вы верно заметили, что морфизмов одного объекта в другой может быть много. Это же касается и морфизмов из A в A. Среди них обязательно есть один тождественный, но могут быть и другие.

Что касается отношений, то тут особой нестыковки нет. То понятие, на которое Вы ссылаетесь, можно назвать "отношением", но это уже отход от "стандарта". То есть в таких случаях желательно делать оговорку. А вообще-то "n-арное отношение" обычно рассматривают на неком множестве D, что соответствует частному случаю D₁=...=D_n=D.

При n=2, когда множества разные, я предпочитаю называть подмножество декартова произведения AxB термином "бинарное соответствие между A и B".

"Соответствие между" - мне нравиццо, т.к. это выглядит интуитивно понятно и для нематематика.

[ В словесной форме это принято выражать оборотом "из A в себя", что по смыслу совершенно то же, что "из A в A". ]

На самом деле я так и понял, причиной непонимания было другое. Когда Вы говорили "А вот если взять что-то вроде h из A в A такого, что h(1)=1, h(2)=1, h(3)=2, то это уже не будет автоморфизм, но эндоморфизмом он является" - я это так понял, что раз нет никакого h(j)=3, то в правом объекте морфизма h:A->B не будет элемента 3. Но, если разрешить появление 3 "из ничего" (а почему бы и нет), то все нормально.

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

Я часто сталкивался с этим явлением, когда многие люди считают, что все отображения должны быть сюръективными. Типа, если число 3 "не используется", то как бы зачем оно вообще?

Дело в том, что когда мы определяем отображение, сопоставляя одному числу другое, то зачастую бывает не известно, что будет использовано, а что нет. Представьте себе какой-нибудь многочлен 6-й степени типа x⁶+x²+x. Множество значений, которое он принимает, очень трудно описать сколь-нибудь "разумно". Ясно, что это будет замкнутый луч от какого-то значения c до бесконечности, но вот чему равно c -- это можно сказать только "приближённо".

Часто бывает так, что рассматривается целое семейство функций, и тогда за ними становится труднее следить, если не фиксировать одну и ту же область значений, которые им в принципе разрешено принимать. Вам наверняка будет хорошо понятен такой пример: булевой функцией от одной переменной называется отображение из {0,1} в {0,1}. Ясно, что "тожественная истина" или "тождественная ложь" -- это тоже будет частный случай б.ф., хотя одно из значений она принимать не будет. Смысл здесь в том, что второе множество указывает на то, что за его пределы выходить нельзя, то есть когда функция приняла значение 2 или "пи", то она уже не называется "булевой".

> операция равенства морфизмов

Такой операции вообще-то нет, и "равенство" -- это "отношение", а не "операция"!

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

[ Такой операции вообще-то нет, и "равенство" -- это "отношение", а не "операция"! ]

У-хи-хи-хи! :) Когда Вы так делаете, я сразу вспоминаю, насколько небрежно Вы относитесь к терминологии в любой другой области, кроме математики :)) Но меня, в общем, устраивает, что хотя бы в математике оно так :)

Равенство можно отнести и туда, и туда - разве нет? Скажу по-секрету, у меня есть железная отмазка: в программистской терминологии равенство называют операцией (или оператором), у которой два параметра X, Y (обычно из одного и того же множества), а на выходе - результат true или false.

[ Кроме того, равенство в математике всегда "имманентно", то есть любые два математических объекта либо равны "от Бога", либо не равны. ]

Замысловато сказали - чуть мозг в кучку не завял :) У нас, у программЁров, равенства разные могут быть, по всякому можно определить, что означает, когда говорится, что два объекта заданного типа равны - так что не совсем понятно, что Вы имели в виду...

*в программистской терминологии равенство называют операцией (или оператором), у которой два параметра X, Y (обычно из одного и того же множества), а на выходе - результат true или false.*

Интересно, а по жизни программеры тоже скряги, как они экономят слова? Не хотят говорить
"операция сравнения значений", а говорят просто "равенство"...

Мне присуще впечатление, что языки программирования специально изуродованы под китайскую грамоту. Если используемые в них понятия привести к литературной норме, то пользование ими и составление программ оказалось бы изумительно легким... ;-)

[ Не хотят говорить "операция сравнения значений", а говорят просто "равенство"... ]

Это другое. К операция сравнения значений относятся еще и "больше", "меньше" и т.п.

[ Мне присуще впечатление, что языки программирования специально изуродованы под китайскую грамоту. ]

Наоборот там все оптимизировано - программисты не фелософы, геморрой себе не создают :)

Понятия можно "почистить" - "операция выделения равных значений".

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

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

Хотя программирование - это уже индустрия...

[ Понятия можно "почистить" - "операция выделения равных значений". ]

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

фЯлософы... :))

Все зависит от потребности различения - разнятся же красный и красный выгоревший :)

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

дык, с чего ты взял, что избыточно урезанной?

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

Тогда цикл замыкается в знаменитую "железную отмазку": нечто называется так не потому, что оно таким образом недвусмысленно в широком понимании, а потому, что кто-то когда-то так вякнул. Это не есть хорошо ;-)

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

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

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

По поводу равенства: давайте на "примитивном" уровне ощутим разницу между понятием "операции" (бинарной) и "отношения" (тоже бинарного). Имеется некоторое множество M. Говорят, что на нём задана операция *, если каждой упорядоченной паре (x,y) элементов из M она сопоставляет некоторый элемент из M. То есть это не что иное как отображение из MxM в M, или всюду определённая (на M) функция от двух переменных со значениями в M. Например, сложение, умножение -- это примеры операций, которые могут быть заданы на Z, на R или на чём-то ещё.

Теперь как определяется отношение на M? Концепция тут принята такая. Вот есть отношение равенства, или отношение параллельности (на множестве прямых), или отношение "больше" на множестве чисел. Допустим, я знаю "содержательно", когда элементы находятся в этом отношении, а когда нет. Точнее, когда произвольно заданный элемент x находится в отношении с каким-то элементом y. Мне показывают две прямые, а я для себя определяю, параллельны они или нет. Я при этом могу ответить как бы на "все" вопросы и составить "шпаргалку", то есть полный список таких упорядоченных пар видв (x,y), где x находится в рассматриваемом отношении с y. Ясно, что такой список несёт как бы полную информации о самом отношении, про которое пока непонятно, что это такое? Я знаю, что 5 больше 3, и потому пара (5,3) входит в мой список для отношения "больше", а пара (2,7) иил (4,4) в него уже не входит.

Но что такое "больше" само по себе, без "атрибутов" в виде x и y? Принимается такое "мужественное" решение: считать чисто "директивно", что "больше" -- это и есть составленный список пар. Что ведёт к такому формальному определению: отношением на M называется произвольное подмножество в MxM.

ПРОДОЛЖЕНИЕ СЛЕДУЕТ; ПРОСЬБА ПИСАТЬ НИЖЕ!

При этом становится возможной ПРОЦЕДУРА проверки на то, находятся ли заданные элементы в рассматриваемом отношении. А именно, берём пару (x,y), "сканируем" весь список, и говорим TRUE, если пара в нём нашлась, и FALSE, если не нашлась. Что приводит к оторбражению из того же MxM, но уже не в M, а в {0,1}. Такое отображение, с точки зрения содержащейся в нём информации, практически равноценно "отношению" как множеству пар. Но формально это уже другой объект, и его можно называть уже "бинарным предикатом" на множестве M.

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

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

Равенство в этом смысле как бы "абсолютно", то есть числа x и y -- если их кто-то зафиксировал -- либо равны, либо нет. То, что могут существовать какие-то другие процедуры, никак этому не противоречит, потому что там речь идёт о неких отношениях эквивалентности, ПОХОЖИХ чем-то на равенство, понимаемое как "абсолютное тождество", где x равен только x и ничему другому. Это соотвтетсвует "диагональному" отношению, где список состоит из всех пар вида (x,x), и больше туда ничего не входит.

Я могу рассматривать какие-то выражения типа x+7 и (4+x)+3. Их можно считать "равными", и мы даже так делаем, когда ставим между ними знак равенства. Но надо понимать, что под этим понимается совсем другое. Как выражения, они не равны, но при любом x у них будут одинаковые значения. Это задаёт отношение эквивалентности (одно из возможных), и с ним далее идёт работа.

Что касается категорий, от которых мы "отошли", то там всё просто, если говорить о равенстве. Оно везде полагается "абсолютным", то есть имеется в виду "абсолютное тождество". Можно, например, считать, что у категории есть "хозяин", который провёл полную "инвентаризацию", занумеровав все объекты и все морфизмы. Каждая "единица хранения" имеет у него при этом свой уникальный "инвентарный номер", и по нему можно производить "идентификацию". Скажем, "хозяин" знает, что под номером 177 у него идёт тождественный морфизм объекта номер 56. А композицией морфизмов 13 и 19 будет морфизм номер 7. И так далее. То есть я к тому, что о равенстве можно не говорить здесь в том плане, что оно "уже есть". И ещё надо отличать равенство как таковое от процедуры проверки на факт равенства чего-то чему-то. Разница была описана мной выше.

В программировании равенство это такая же операция, как сложение и вычитание. Оно может быть и 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}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Процедура проверки равенства множеств 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

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

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

Flat | Top-Level Comments Only

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

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

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

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

соответствия

Re: соответствия

соответствия и отношения

no subject

иманентность равенства

с Тиграми по понятиям :)

Re: с Тиграми по понятиям :)

Re: с Тиграми по понятиям :)

Re: с Тиграми по понятиям :)

Re: с Тиграми по понятиям :)

Re: с Тиграми по понятиям :)

Re: с Тиграми по понятиям :)

Re: с Тиграми по понятиям :)

процедуры (1)

процедуры (2)

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

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

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

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

no subject

рекурсия

no subject