Монада (теория категорий)

Не путать с Монадой (гомологической алгеброй) .

Информацию об использовании монад в компьютерном программном обеспечении см. в разделе « Монады в функциональном программировании» .

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

Монады, кажется, беспокоят многих людей. На YouTube даже есть видео под названием «Монады повредили мою голову»! ... Вскоре после этого говорящая женщина восклицает:

Какого черта?! Как вообще объяснить, что такое монада?

Джон Баэз,

В теории категорий , разделе математики , монада — это тройка. $(T,\eta ,\mu )$ состоящий из функтора T из категории в себя и двух естественных преобразований $\eta ,\mu$ которые удовлетворяют таким условиям, как ассоциативность. Например, если $F,G$ функторы сопряжены друг с другом, то $T=G\circ F$ вместе с $\eta ,\mu$ определяемое присоединенным отношением, является монадой.

Вкратце, монада — это некоторой фиксированной категории ( моноид в категории эндофункторов эндофунктор — это функтор, отображающий категорию в себя). По мнению Джона Баэза, монаду можно рассматривать как минимум двумя способами:

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

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

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

Введение и определение

Монада — это определенный тип эндофунктора . Например, если $F$ и $G$ представляют собой пару сопряженных функторов , причем $F$ слева примыкать к $G$, то композиция $G\circ F$ это монада. Если $F$ и $G$ являются обратными функторами, соответствующая монада является тождественным функтором . В общем, присоединения не являются эквивалентами — они связывают категории разной природы. Теория монад важна как часть усилий по выявлению того, что «сохраняют» присоединения. Другая половина теории, того, что можно узнать аналогичным образом из рассмотрения $F\circ G$, обсуждается в рамках двойственной теории комонад .

Формальное определение

На протяжении всей этой статьи $C$ обозначает категорию . Монада ​ на $C$ состоит из эндофунктора $T\colon C\to C$ вместе с двумя естественными преобразованиями : $\eta \colon 1_{C}\to T$ (где $1_{C}$ обозначает тождественный функтор на $C$) и $\mu \colon T^{2}\to T$ (где $T^{2}$ это функтор $T\circ T$ от $C$ к $C$). Они необходимы для выполнения следующих условий (иногда называемых условиями когерентности ):

• $\mu \circ T\mu =\mu \circ \mu T$ (как естественные преобразования $T^{3}\to T$); здесь $T\mu$ и $\mu T$ образованы « горизонтальной композицией ».
• $\mu \circ T\eta =\mu \circ \eta T=1_{T}$ (как естественные преобразования $T\to T$; здесь $1_{T}$ обозначает тождественное преобразование из $T$ к $T$).

Мы можем переписать эти условия, используя следующие коммутативные диаграммы :

в статье о естественных преобразованиях . Объяснение обозначений см. $T\mu$ и $\mu T$или см. ниже коммутативные диаграммы, не использующие эти понятия:

Первая аксиома сродни ассоциативности в моноидах , если мы подумаем о $\mu$ как бинарная операция моноида, а вторая аксиома сродни существованию единичного элемента (который мы считаем заданным формулой $\eta$). Действительно, монада на $C$ альтернативно может быть определен как моноид в категории $\mathbf {End} _{C}$ чьи объекты являются эндофункторами $C$ и чьи морфизмы являются естественными преобразованиями между ними с моноидальной структурой , индуцированной композицией эндофункторов.

Монада набора мощности

Монада набора мощности — это монада ${\mathcal {P}}$ по категории $\mathbf {Set}$: За комплект $A$ позволять $T(A)$ быть силовым набором $A$ и для функции $f\colon A\to B$ позволять $T(f)$ — функция между наборами степеней, индуцированная получением прямых изображений под $f$. Для каждого набора $A$, у нас есть карта $\eta _{A}\colon A\to T(A)$, который присваивает каждому $a\in A$ синглтон ​ $\{a\}$. Функция

$\mu _{A}\colon T(T(A))\to T(A)$

принимает набор множеств в его объединение . Эти данные описывают монаду.

Примечания

Аксиомы монады формально аналогичны аксиомам моноида . Фактически монады являются частными случаями моноидов, а именно моноидами среди эндофункторов. $\operatorname {End} (C)$, который оснащен умножением, заданным композицией эндофункторов.

Композиция монад вообще не является монадой. Например, функтор двойной мощности ${\mathcal {P}}\circ {\mathcal {P}}$ не допускает никакой монадной структуры.

Комонады

Категориальное двойственное определение — это формальное определение комонады ( или котройки ); это можно быстро сказать в терминах, что комонада для категории $C$ это монада противоположной категории $C^{\mathrm {op} }$. Следовательно, это функтор $U$ от $C$ самому себе, с набором аксиом для счётчика и коумножения , которые возникают в результате перестановки стрелок повсюду в только что данном определении.

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

Терминологическая история

Понятие монады было изобретено Роджером Годементом в 1958 году под названием «стандартная конструкция». Монаду называли «двойной стандартной конструкцией», «тройкой», «моноидом» и «триадой». Термин «монада» использован не позднее 1967 года Жаном Бенабу .

Примеры

Личность

Тождественный функтор категории $C$ это монада. Его умножение и единица являются тождественной функцией на объектах $C$.

Монады, возникающие из присоединений

Любое дополнение

$F:C\rightleftarrows D:G$

порождает монаду C. на Эта весьма распространенная конструкция работает следующим образом: эндофунктор представляет собой составную

$T=G\circ F.$

Этот эндофунктор быстро становится монадой, где карта единиц происходит из карты единиц. $\operatorname {id} _{C}\to G\circ F$ присоединения, а карта умножения строится с использованием карты единиц присоединения:

$T^{2}=G\circ F\circ G\circ F\xrightarrow {G\circ {\text{counit}}\circ F} G\circ F=T.$

Фактически, любую монаду можно найти как явное присоединение функторов, используя категорию Эйленберга–Мура. $C^{T}$ (категория $T$-алгебры).

Двойная дуализация

Монада двойной дуализации для фиксированного поля k возникает из присоединения

$(-)^{*}:\mathbf {Vect} _{k}\rightleftarrows \mathbf {Vect} _{k}^{op}:(-)^{*}$

где оба функтора задаются путем отправки векторного пространства V в его двойственное векторное пространство $V^{*}:=\operatorname {Hom} (V,k)$. Соответствующая монада отправляет векторное пространство V в его двойной двойник. $V^{**}$. Эта монада обсуждается в гораздо большей степени Коком (1970) .

Операторы замыкания на частично упорядоченных множествах

Для категорий, возникающих из частично упорядоченных наборов $(P,\leq )$ (с единственным морфизмом из $x$ к $y$ тогда и только тогда, когда $x\leq y$), то формализм становится значительно проще: присоединенные пары — это связи Галуа , а монады — операторы замыкания .

Свободно-забывчивые придатки

Например, пусть $G$ — функтор забывчивости из категории Grp групп в категорию Set пусть множеств, и $F$ — свободный групповой функтор из категории множеств в категорию групп. Затем $F$ является левым сопряженным к $G$. В этом случае ассоциированная монада $T=G\circ F$ берет набор $X$ и возвращает базовый набор свободной группы $\mathrm {Free} (X)$. Единичная карта этой монады задается картами

$X\to T(X)$

включая любой набор $X$ в набор $\mathrm {Free} (X)$ естественным образом, как строки длины 1. Далее, умножением этой монады является отображение

$T(T(X))\to T(X)$

созданный путем естественной конкатенации или «сглаживания» «строк строк». Это составляет два естественных преобразования . Предыдущий пример о свободных группах можно обобщить на любой тип алгебры в смысле множества алгебр универсальной алгебры . Таким образом, каждый такой тип алгебры порождает монаду в категории множеств. Важно отметить, что тип алгебры можно восстановить по монаде (как категории алгебр Эйленберга–Мура), поэтому монады также можно рассматривать как обобщающие многообразия универсальных алгебр.

Другая монада, возникающая из присоединения, - это когда $T$ - это эндофунктор категории векторных пространств, который отображает векторное пространство $V$ к его тензорной алгебре $T(V)$и который отображает линейные карты в их тензорное произведение. Тогда мы имеем естественное преобразование, соответствующее вложению $V$ в свою тензорную алгебру и естественное преобразование, соответствующее отображению из $T(T(V))$ к $T(V)$ получается простым разложением всех тензорных произведений.

Монады кодовой плотности

В мягких условиях функторы, не допускающие левого сопряженного, также порождают монаду, так называемую коденситную монаду . Например, включение

$\mathbf {FinSet} \subset \mathbf {Set}$

не допускает левого сопряженного. Его монада кодовой плотности — это монада на множествах, отправляющая любой набор X в набор ультрафильтров на X . Этот и подобные примеры обсуждаются в Leinster (2013) .

Монады, используемые в денотационной семантике

См. также: Монада (функциональное программирование).

Следующие монады над категорией множеств используются в денотационной семантике императивных языков программирования , а аналогичные конструкции используются в функциональном программировании.

Возможно, монада

Эндофунктор монады « может быть» или «партициальность» добавляет точку непересекающегося:

$(-)_{*}:\mathbf {Set} \to \mathbf {Set}$

$X\mapsto X\cup \{*\}$

Единица задается включением набора $X$ в $X_{*}$:

$\eta _{X}:X\to X_{*}$

$x\mapsto x$

Умножение отображает элементы $X$ между собой, и две непересекающиеся точки в $(X_{*})_{*}$ тому, кто в $X_{*}$.

И в функциональном программировании, и в денотационной семантике монада may моделирует частичные вычисления , то есть вычисления, которые могут потерпеть неудачу.

Государственная монада

Учитывая набор $S$, эндофунктор монады состояния отображает каждый набор $X$ к набору функций $S\to S\times X$. Компонент агрегата на $X$ отображает каждый элемент $x\in X$ к функции

$\eta _{X}(x):S\to S\times X$

$s\mapsto (s,x)$

Умножение отображает функцию $f:S\to S\times (S\to S\times X),s\mapsto (s',f')$ к функции

$\mu _{X}(f):S\to S\times X$

$s\mapsto f'(s')$

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

Монада окружающей среды

Учитывая набор $E$, эндофунктор читателя или монады среды отображает каждый набор $X$ к набору функций $E\to X$. Таким образом, эндофунктор этой монады — это в точности функтор hom $\mathrm {Hom} (E,-)$. Компонент агрегата на $X$ отображает каждый элемент $x\in X$ к постоянной функции $e\mapsto x$.

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

Список и набор монад

Монада списка ( или недетерминизма отображает множество X в множество конечных последовательностей е. списков ) с элементами из X. т . Модуль отображает элемент x в X в одноэлементный список [x]. Умножение объединяет список списков в один список.

В функциональном программировании монада списка используется для моделирования недетерминированных вычислений . Ковариантная монада powerset также известна как монада множества и также используется для моделирования недетерминированных вычислений.

Алгебры для монады

Смотрите также: F-алгебра и псевдоалгебра.

Дана монада $(T,\eta ,\mu )$ по категории $C$, естественно считать $T$-алгебры , т. е. объекты $C$ на что действовал $T$ способом, совместимым с единицей и умножением монады. Более формально, А. $T$-алгебра $(x,h)$ это объект $x$ из $C$ вместе со стрелой $h\colon Tx\to x$ из $C$ называется структурной картой алгебры такой, что диаграммы

и

добираться.

Морфизм $f\colon (x,h)\to (x',h')$ из $T$-алгебра – это стрелка $f\colon x\to x'$ из $C$ такая, что диаграмма

ездит на работу. $T$-алгебры образуют категорию, называемую категорией Эйленберга–Мура и обозначаемую $C^{T}$.

Примеры

Алгебры над свободной групповой монадой

Например, для рассмотренной выше монады свободной группы $T$-алгебра – это множество $X$ вместе с картой из группы free, сгенерированной $X$ к $X$ при соблюдении условий ассоциативности и единства. Такая структура эквивалентна утверждению, что $X$ это сама группа.

Алгебры над монадой распределения

Другой пример — монада распределения ${\mathcal {D}}$ по категории наборов. Это определяется отправкой набора $X$ к набору функций $f:X\to [0,1]$ с конечным носителем и такие, что их сумма равна $1$. В обозначениях построителя множеств это набор $${\mathcal {D}}(X)=\left\{f:X\to [0,1]:{\begin{matrix}\#{\text{supp}}(f)<+\infty \\\sum _{x\in X}f(x)=1\end{matrix}}\right\}$$Изучив определения, можно показать, что алгебры над монадой распределения эквивалентны выпуклым множествам , т. е. множествам, снабженным операциями $x+_{r}y$ для $r\in [0,1]$ подчиняется аксиомам, напоминающим поведение выпуклых линейных комбинаций $rx+(1-r)y$ в евклидовом пространстве.

Алгебры над симметричной монадой

Другим полезным примером монады является функтор симметричной алгебры в категории $R$-модули для коммутативного кольца $R$. $${\text{Sym}}^{\bullet }(-):{\text{Mod}}(R)\to {\text{Mod}}(R)$$отправка $R$-модуль $M$ к прямой сумме симметричных тензорных степеней $${\text{Sym}}^{\bullet }(M)=\bigoplus _{k=0}^{\infty }{\text{Sym}}^{k}(M)$$где ${\text{Sym}}^{0}(M)=R$. Например, ${\text{Sym}}^{\bullet }(R^{\oplus n})\cong R[x_{1},\ldots ,x_{n}]$ где $R$-алгебра справа рассматривается как модуль. Тогда алгебры над этой монадой коммутативны. $R$-алгебры. Существуют также алгебры над монадами для знакопеременных тензоров. ${\text{Alt}}^{\bullet }(-)$ и полные тензорные функторы $T^{\bullet }(-)$ дающий антисимметричный $R$-алгебры и бесплатно $R$-алгебры, поэтому $${\begin{aligned}{\text{Alt}}^{\bullet }(R^{\oplus n})&=R(x_{1},\ldots ,x_{n})\\{\text{T}}^{\bullet }(R^{\oplus n})&=R\langle x_{1},\ldots ,x_{n}\rangle \end{aligned}}$$где первое кольцо — это свободная антисимметричная алгебра над $R$ в $n$-генераторы, а второе кольцо — свободная алгебра над $R$ в $n$-генераторы.

Коммутативные алгебры в кольцевых спектрах E-бесконечности

Аналогичная конструкция существует для коммутативного $\mathbb {S}$-алгебры ^{стр. 113} что дает коммутативный $A$-алгебры для коммутатива $\mathbb {S}$-алгебра $A$. Если ${\mathcal {M}}_{A}$ это категория $A$-модули, то функтор $\mathbb {P} :{\mathcal {M}}_{A}\to {\mathcal {M}}_{A}$ это монада, заданная $$\mathbb {P} (M)=\bigvee _{j\geq 0}M^{j}/\Sigma _{j}$$где $$M^{j}=M\wedge _{A}\cdots \wedge _{A}M$$ $j$-раз. Затем существует связанная категория ${\mathcal {C}}_{A}$ коммутативного $A$-алгебры из категории алгебр над этой монадой.

Монады и дополнения

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

$T(-):C\rightleftarrows C^{T}:{\text{forget}}$

левый сопряженный которого отправляет объект X в свободную T -алгебру T ( X ). Однако обычно существует несколько различных присоединений, порождающих монаду: пусть $\mathbf {Adj} (C,T)$ быть категорией, объектами которой являются дополнения $(F,G,e,\varepsilon )$ такой, что $(GF,e,G\varepsilon F)=(T,\eta ,\mu )$ и чьи стрелки являются морфизмами присоединений, тождественными на $C$. Тогда упомянутое выше свободно-забывчивое присоединение, включающее категорию Эйленберга–Мура $C^{T}$ является терминальным объектом в $\mathbf {Adj} (C,T)$. Исходным объектом является категория Клейсли , которая по определению является полной подкатегорией $C^{T}$ состоящая только из свободных Т -алгебр, т. е. Т -алгебр вида $T(x)$ для некоторого объекта x из C .

Монадические присоединения

Учитывая любое дополнение $(F:C\to D,G:D\to C,\eta ,\varepsilon )$ со связанной монадой T функтор G можно факторизовать как

$D{\stackrel {\tilde {G}}{\to }}C^{T}{\stackrel {\text{forget}}{\to }}C,$

т. е. G ( Y ) может быть естественным образом наделена структурой T -алгебры для любого Y из D . Соединение называется монадическим, если первый функтор ${\tilde {G}}$ дает эквивалентность категорий между D и категорией Эйленберга – Мура. $C^{T}$. В более широком смысле функтор $G\colon D\to C$ называется монадическим, если он имеет левое сопряженное $F$ образуя монадическое присоединение. Например, свободно-забывчивое присоединение между группами и множествами является монадическим, поскольку, как говорилось выше, алгебры над ассоциированной монадой являются группами. В общем, зная, что присоединение является монадическим, можно реконструировать объекты в D из объектов в C и T -действия.

Теорема Бека о монадичности

Теорема Бека о монадичности дает необходимое и достаточное условие монадичности присоединения. Упрощенная версия этой теоремы утверждает, что G является монадической, если она консервативна (или G отражает изоморфизмы, т. е. морфизм в D является изоморфизмом тогда и только тогда, когда его образ под G является изоморфизмом в C ), а C имеет и G сохраняет коэквалайзеры .

Например, функтор забвения из категории бикомпактов на множествах является монадическим. Однако функтор забывания всех топологических пространств в множества не является консервативным, поскольку существуют непрерывные биективные отображения (между некомпактными или нехаусдорфовыми пространствами), которые не могут быть гомеоморфизмами . Таким образом, этот функтор забывания не является монадическим. Двойственная версия теоремы Бека, характеризующая комонадические присоединения, актуальна в различных областях, таких как теория топоса и разделы алгебраической геометрии, связанные со спуском . Первым примером комонического присоединения является присоединение

$-\otimes _{A}B:\mathbf {Mod} _{A}\rightleftarrows \mathbf {Mod} _{B}:\operatorname {forget}$

для кольцевого гомоморфизма $A\to B$ между коммутативными кольцами. По теореме Бека это присоединение является комонадическим тогда и только тогда, когда B как точно плоский A -модуль . Таким образом, это позволяет спускать B -модули, оснащенные нисходящим данным (т. е. действием комонады, заданным присоединением), к A -модулям. Полученная в результате теория точно плоского спуска широко применяется в алгебраической геометрии.

Использование

Монады используются в функциональном программировании для выражения типов последовательных вычислений (иногда с побочными эффектами). См. монады в функциональном программировании и более математически ориентированный модуль Викибука b:Haskell/Category Theory .

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

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

Обобщение

Можно определить монады в 2-категории $C$. Описанные выше монады являются монадами для $C=\mathbf {Cat}$.

См. также

• Закон распределения между монадами
• Теория Ловера
• Монада (функциональное программирование)
• Полиада
• Сильная монада
• Жири монада
• Моноидальная монада

Дальнейшее чтение

• Барр, Майкл ; Уэллс, Чарльз (1999), Теория категорий для информатики (PDF)
• Годемент, Роджер (1958), Алгебраическая топология и теория балок. , Научные новости. Инди., Опубл. Математика. унив. Страсбург, том. 1252, Париж: Герман, стр. viii+283 стр.
• Кок, Андерс (1970), «О монадах двойной дуализации», Mathematica Scandinavica , 27 : 151, doi : 10.7146/math.scand.a-10995
• Ленстер, Том (2013), «Кодовая плотность и монада ультрафильтра» (PDF) , Теория и применение категорий , 28 : 332–370, arXiv : 1209.3606 , Bibcode : 2012arXiv1209.3606L
• Маклейн, Сондерс (1978), Категории для работающего математика , Тексты для выпускников по математике, том. 5, номер домена : 10.1007/978-1-4757-4721-8 , ISBN  978-1-4419-3123-8
• Педиккио, Мария Кристина; Толен, Уолтер, ред. (2004). Категориальные основания. Специальные темы по порядку, топологии, алгебре и теории пучков . Энциклопедия математики и ее приложений. Том. 97. Кембридж: Издательство Кембриджского университета . ISBN  0-521-83414-7 . Збл   1034.18001 .
• Перроне, Паоло (2024), «Глава 5. Монады и комонады» , Теория стартовых категорий , World Scientific, doi : 10.1142/9789811286018_0005 , ISBN  978-981-12-8600-1
• Рил, Эмили (2017), Теория категорий в контексте , Courier Dover Publications, ISBN  9780486820804
• Тури, Даниэле (1996–2001), конспекты лекций по теории категорий (PDF)

Внешние ссылки

• Монады , YouTube-видео из пяти коротких лекций (с одним приложением).
• В книге Джона Баэза «Находки по математической физике на этой неделе» (неделя 89) монады делятся на две категории.
• Монады и комонады , видеоурок.
• https://medium.com/@felix.kuehl/a-monad-is-just-a-monoid-in-the-category-of-endofunctors-lets-actually-unravel-this-f5d4b7dbe5d6