Монада (теория категорий)
В теории категорий — разделе математики , монада (также тройка , триада , стандартная конструкция и фундаментальная конструкция ). [1] является моноидом в категории эндофункторов . некоторой фиксированной категории Эндофунктор — это функтор, отображающий категорию в себя, а монада — это эндофунктор вместе с двумя естественными преобразованиями, необходимыми для выполнения определенных условий когерентности . Монады используются в теории пар сопряженных функторов и обобщают операторы замыкания на частично упорядоченных множеств произвольные категории. Монады также полезны в теории типов данных , денотационной семантике императивных языков программирования и в языках функционального программирования , позволяя языкам без изменяемого состояния выполнять такие вещи, как симуляция циклов for; см. Монада (функциональное программирование) .
Введение и определение [ править ]
Монада — это определенный тип эндофункторов . Например, если и представляют собой пару сопряженных функторов , причем слева примыкать к , то композиция это монада. Если и являются обратными функторами, соответствующая монада является тождественным функтором . В общем, присоединения не являются эквивалентами — они связывают категории разной природы. Теория монад важна как часть усилий по выявлению того, что «сохраняют» присоединения. Другая половина теории, то, что можно узнать аналогичным образом из рассмотрения , обсуждается в рамках двойственной теории комонад .
Формальное определение [ править ]
На протяжении всей этой статьи обозначает категорию . Монада на состоит из эндофунктора вместе с двумя естественными преобразованиями : (где обозначает тождественный функтор на ) и (где это функтор от к ). Они необходимы для выполнения следующих условий (иногда называемых условиями когерентности ):
- (как естественные преобразования ); здесь и образованы « горизонтальной композицией ».
- (как естественные преобразования ; здесь обозначает тождественное преобразование из к ).
Мы можем переписать эти условия, используя следующие коммутативные диаграммы :
в статье о естественных преобразованиях . Объяснение обозначений см. и или см. ниже коммутативные диаграммы, не использующие эти понятия:
Первая аксиома сродни ассоциативности в моноидах , если мы подумаем о как бинарная операция моноида, а вторая аксиома сродни существованию единичного элемента (который мы считаем заданным формулой ). Действительно, монада на альтернативно может быть определен как моноид в категории чьи объекты являются эндофункторами и чьи морфизмы являются естественными преобразованиями между ними с моноидальной структурой , индуцированной композицией эндофункторов.
Монада набора мощности [ править ]
Монада набора мощности — это монада по категории : За комплект позволять быть силовым набором и для функции позволять — функция между наборами степеней, индуцированная получением прямых изображений под . Для каждого набора , у нас есть карта , который присваивает каждому синглтон . Функция
принимает набор множеств в его объединение . Эти данные описывают монаду.
Замечания [ править ]
Аксиомы монады формально аналогичны аксиомам моноида . По сути, монады являются частным случаем моноидов, а именно моноидами среди эндофункторов. , который снабжен умножением, заданным композицией эндофункторов.
Композиция монад вообще не является монадой. Например, функтор двойной мощности не допускает никакой монадной структуры. [2]
Комонады [ править ]
Категориальное двойственное определение — это формальное определение комонады ( или котройки ); это можно быстро сказать в терминах, что комонада для категории это монада противоположной категории . Следовательно, это функтор от самому себе, с набором аксиом для счетного и коумножения , которые возникают в результате перестановки стрелок повсюду в только что данном определении.
Монады относятся к моноидам так же, как комонады относятся к комоноидам . Каждое множество является комоноидом уникальным образом, поэтому комоноиды менее известны в абстрактной алгебре , чем моноиды; однако комоноиды в категории векторных пространств с обычным тензорным произведением важны и широко изучаются под названием коалгебр .
Терминологическая история [ править ]
Понятие монады было изобретено Роджером Годементом в 1958 году под названием «стандартная конструкция». Монаду называли «двойной стандартной конструкцией», «тройкой», «моноидом» и «триадой». [3] Термин «монада» использован не позднее 1967 года Жаном Бенабу . [4] [5]
Примеры [ править ]
Личность [ править ]
Тождественный функтор категории это монада. Его умножение и единица являются тождественной функцией на объектах .
Монады, возникающие из присоединений [ править ]
Любое дополнение
порождает монаду C. на Эта весьма распространенная конструкция работает следующим образом: эндофунктор представляет собой составную
Этот эндофунктор быстро становится монадой, где карта единиц происходит из карты единиц. присоединения, а карта умножения строится с использованием карты единиц присоединения:
Фактически, любую монаду можно найти как явное присоединение функторов, используя категорию Эйленберга–Мура. (категория -алгебры). [6]
Двойная дуализация [ править ]
Монада двойной дуализации для фиксированного поля k возникает из присоединения
где оба функтора задаются путем отправки векторного пространства V в его двойственное векторное пространство . Соответствующая монада отправляет векторное пространство V в его двойной двойник. . Эта монада обсуждается в гораздо большей степени Коком (1970) .
Операторы замыкания частично упорядоченных множеств [ править ]
Для категорий, возникающих из частично упорядоченных наборов (с единственным морфизмом из к тогда и только тогда, когда ), то формализм становится значительно проще: присоединенные пары — это связи Галуа , а монады — операторы замыкания .
Свободно-забывчивые придатки [ править ]
Например, пусть — функтор забывчивости из категории Grp групп в категорию Set пусть множеств, и — свободный групповой функтор из категории множеств в категорию групп. Затем является левым сопряженным к . В этом случае ассоциированная монада берет набор и возвращает базовый набор свободной группы .Единичная карта этой монады задается картами
включая любой набор в набор естественным образом, как строки длины 1. Далее, умножением этой монады является отображение
созданный путем естественной конкатенации или «сглаживания» «строк строк». Это составляет два естественных преобразования .Предыдущий пример о свободных группах можно обобщить на любой тип алгебры в смысле множества алгебр универсальной алгебры . Таким образом, каждый такой тип алгебры порождает монаду в категории множеств. Важно отметить, что тип алгебры можно восстановить по монаде (как категории алгебр Эйленберга–Мура), поэтому монады также можно рассматривать как обобщающие многообразия универсальных алгебр.
Другая монада, возникающая из присоединения, - это когда - это эндофунктор категории векторных пространств, который отображает векторное пространство к его тензорной алгебре и который отображает линейные карты в их тензорное произведение. Тогда мы имеем естественное преобразование, соответствующее вложению в свою тензорную алгебру и естественное преобразование, соответствующее отображению из к получается простым разложением всех тензорных произведений.
Монады кодовой плотности [ править ]
В мягких условиях функторы, не допускающие левого сопряженного, также порождают монаду, так называемую коденситную монаду . Например, включение
не допускает левого сопряженного. Его монада кодовой плотности — это монада на множествах, отправляющая любой набор X в набор ультрафильтров на X . Этот и подобные примеры обсуждаются в Leinster (2013) .
используемые в денотационной Монады , семантике
Следующие монады над категорией множеств используются в денотационной семантике императивных языков программирования , а аналогичные конструкции используются в функциональном программировании.
Возможно монада [ править ]
Эндофунктор монады « может быть» или «частность» добавляет точку непересекающегося: [7]
Единица задается включением набора в :
Умножение отображает элементы между собой, и две непересекающиеся точки в тому, кто в .
И в функциональном программировании, и в денотационной семантике монада may моделирует частичные вычисления , то есть вычисления, которые могут потерпеть неудачу.
Государственная монада [ править ]
Этот раздел нуждается в дополнении: опишите умножение. Вы можете помочь, добавив к нему . ( февраль 2023 г. ) |
Учитывая набор , эндофунктор монады состояния отображает каждый набор к набору функций . Компонент агрегата на отображает каждый элемент к функции
Умножение отображает функцию к функции
В функциональном программировании и денотационной семантике монада состояний моделирует вычисления с сохранением состояния .
Монада окружения [ править ]
Этот раздел нуждается в дополнении: опишите умножение. Вы можете помочь, добавив к нему . ( февраль 2023 г. ) |
Учитывая набор , эндофунктор читателя или монады среды отображает каждый набор к набору функций . Таким образом, эндофунктор этой монады — это в точности функтор hom . Компонент агрегата на отображает каждый элемент к постоянной функции .
В функциональном программировании и денотационной семантике монада среды моделирует вычисления с доступом к некоторым данным, доступным только для чтения.
Список и набор монад [ править ]
Этот раздел нуждается в дополнении: опишите умножение. Вы можете помочь, добавив к нему . ( февраль 2023 г. ) |
Монада списка ( или недетерминизма отображает множество X в множество конечных последовательностей е. списков ) с элементами из X. т . Модуль отображает элемент x в X в одноэлементный список [x]. Умножение объединяет список списков в один список.
В функциональном программировании монада списка используется для моделирования недетерминированных вычислений . Ковариантная монада powerset также известна как монада множества и также используется для моделирования недетерминированных вычислений.
Алгебры для монады [ править ]
Дана монада по категории , естественно считать -алгебры , т. е. объекты на что действовал способом, совместимым с единицей и умножением монады. Более формально, А. -алгебра это объект из вместе со стрелой из называется структурной картой алгебры такой, что диаграммы
и |
добираться.
Морфизм из -алгебра – это стрелка из такая, что диаграмма
ездит на работу. -алгебры образуют категорию, называемую категорией Эйленберга–Мура и обозначаемую .
Примеры [ править ]
над свободной Алгебры групповой монадой
Например, для рассмотренной выше монады свободной группы -алгебра – это множество вместе с картой из группы free, сгенерированной к при соблюдении условий ассоциативности и единства. Такая структура эквивалентна утверждению, что это сама группа.
Алгебры над монадой распределения [ править ]
Другой пример — монада распределения по категории наборов. Это определяется отправкой набора к набору функций с конечным носителем и такие, что их сумма равна . В обозначениях построителя множеств это набор
Алгебры над симметричной монадой [ править ]
Другим полезным примером монады является функтор симметричной алгебры в категории -модули для коммутативного кольца .
алгебры в спектрах колец E Коммутативные бесконечности -
Аналогичная конструкция существует для коммутативного -алгебры [9] стр. 113 что дает коммутативный -алгебры для коммутатива -алгебра . Если это категория -модули, то функтор это монада, заданная
Монады и дополнения [ править ]
Как уже говорилось выше, любое присоединение порождает монаду. И наоборот, каждая монада возникает из некоторого присоединения, а именно присоединения свободно-забывчивого.
левый сопряженный которого отправляет объект X в свободную T -алгебру T ( X ). Однако обычно существует несколько различных присоединений, порождающих монаду: пусть быть категорией, объектами которой являются дополнения такой, что и чьи стрелки являются морфизмами присоединений, тождественными на . Тогда упомянутое выше свободно-забывчивое присоединение, включающее категорию Эйленберга–Мура является терминальным объектом в . Исходным объектом является категория Клейсли , которая по определению является полной подкатегорией состоящая только из свободных Т -алгебр, т. е. Т -алгебр вида для некоторого объекта x из C .
Монадические присоединения [ править ]
Учитывая любое дополнение со связанной монадой T функтор G можно факторизовать как
т. е. G ( Y ) может быть естественным образом наделена структурой T -алгебры для любого Y из D . Соединение называется монадическим, если первый функтор дает эквивалентность категорий между D и категорией Эйленберга – Мура. . [10] В более широком смысле функтор называется монадическим, если он имеет левое сопряженное образуя монадическое присоединение. Например, свободно-забывчивое присоединение между группами и множествами является монадическим, поскольку, как говорилось выше, алгебры над ассоциированной монадой являются группами. В общем, зная, что присоединение является монадическим, можно реконструировать объекты в D из объектов в C и T -действия.
Бека монадичности о Теорема
Теорема Бека о монадичности дает необходимое и достаточное условие монадичности присоединения. Упрощенная версия этой теоремы утверждает, что G является монадической, если она консервативна (или G отражает изоморфизмы, т. е. морфизм в D является изоморфизмом тогда и только тогда, когда его образ под G является изоморфизмом в C ), а C имеет и G сохраняет коэквалайзеры .
Например, функтор забывания из категории бикомпактов на множествах является монадическим. Однако функтор забывания всех топологических пространств в множества не является консервативным, поскольку существуют непрерывные биективные отображения (между некомпактными или нехаусдорфовыми пространствами), которые не могут быть гомеоморфизмами . Таким образом, этот функтор забывания не является монадическим. [11] Двойственная версия теоремы Бека, характеризующая комонадические присоединения, актуальна в различных областях, таких как теория топоса и разделы алгебраической геометрии, связанные со спуском . Первым примером комонического присоединения является присоединение
для кольцевого гомоморфизма между коммутативными кольцами. По теореме Бека это присоединение является комонадическим тогда и только тогда, когда B как точно плоский A -модуль . Таким образом, это позволяет спускать B -модули, оснащенные нисходящим данным (т. е. действием комонады, заданным присоединением), к A -модулям. Полученная в результате теория точно плоского спуска широко применяется в алгебраической геометрии.
Использует [ править ]
Монады используются в функциональном программировании для выражения типов последовательных вычислений (иногда с побочными эффектами). См. монады в функциональном программировании и более математически ориентированный модуль Wikibook b:Haskell/Category Theory .
Монады используются в денотационной семантике нечистых функциональных и императивных языков программирования . [12] [13]
В категориальной логике была проведена аналогия между теорией монад-комонад и модальной логикой через операторы замыкания , внутренние алгебры и их связь с S4 и моделями интуиционистскими логиками .
Обобщение [ править ]
Можно определить монады в 2-категории . Описанные выше монады являются монадами для .
См. также [ править ]
- Закон распределения между монадами
- Теория Ловера
- Монада (функциональное программирование)
- Полиада
- Сильная монада
Ссылки [ править ]
- ^ Барр, Майкл; Уэллс, Чарльз (1985), «Топосы, тройки и теории» (PDF) , Fundamentals of the Mathematical Sciences , vol. 278, Springer-Verlag, стр. 82 и 120, ISBN. 0-387-96115-1 .
- ^ Клин; Саламанка (2018), «Итерированный ковариантный набор полномочий не является монадой», Электронные заметки по теоретической информатике , 341 : 261–276, doi : 10.1016/j.entcs.2018.11.013
- ^ Маклейн 1978 , с. 138.
- ^ Бенабу, Жан (1967). «Введение в бикатегории» . В Бенабу, Дж.; Дэвис, Р.; Долд, А.; Исбелл, Дж.; Маклейн, С.; Оберст, У.; Роос, Ж.-Э. (ред.). Отчеты семинара по категории Среднего Запада . Конспект лекций по математике. Том. 47. Берлин, Гейдельберг: Шпрингер. стр. 1–77. дои : 10.1007/BFb0074299 . ISBN 978-3-540-35545-8 .
- ^ «RE: Монады» . Гмане . 04 апреля 2009 г. Архивировано из оригинала 26 марта 2015 г.
- ^ Рил, Эмили . «Теория категорий в контексте» (PDF) . п. 162. Архивировано (PDF) из оригинала 5 апреля 2021 г.
- ^ Риль 2017 , с. 155.
- ^ Свирщ, Т. (1974), «Монадические функторы и выпуклость», Bull. акад. Полон. наук. Сер. наук. Математика. Астрон. Физ. , 22 : 39–42, МР 0390019 , Джейкобс, Барт (2010), «Выпуклость, двойственность и эффекты», Теоретическая информатика , ИФИП «Достижения в области информационных и коммуникационных технологий», том. 323, стр. 1–19, номер документа : 10.1007/978-3-642-15240-5_1 , ISBN. 978-3-642-15239-9
- ^ Бастерра, М. (15 декабря 1999 г.). «Когомологии Андре – Квиллена коммутативных S-алгебр» . Журнал чистой и прикладной алгебры . 144 (2): 111–143. дои : 10.1016/S0022-4049(98)00051-6 . ISSN 0022-4049 .
- ^ Маклейн (1978) использует более строгое определение, в котором эти две категории скорее изоморфны, чем эквивалентны.
- ^ Маклейн (1978 , §§VI.3, VI.9)
- ^ Уодлер, Филип (1993). «Монады для функционального программирования» . В Брое, Манфред (ред.). Расчеты по проектированию программ . Серия НАТО ASI. Том. 118. Берлин, Гейдельберг: Шпрингер. стр. 233–264. дои : 10.1007/978-3-662-02880-3_8 . ISBN 978-3-662-02880-3 . «Концепция монады, возникшая из теории категорий, была применена Моджи для структурирования денотационной семантики языков программирования».
- ^ Малри, Филип С. (1 января 1998 г.). «Монады в семантике» . Электронные заметки по теоретической информатике . Совместные американо-бразильские семинары по формальным основам программных систем. 14 : 275–286. дои : 10.1016/S1571-0661(05)80241-5 . ISSN 1571-0661 .
Дальнейшее чтение [ править ]
- Барр, Майкл ; Уэллс, Чарльз (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 .
- Рил, Эмили (2017), Теория категорий в контексте , Courier Dover Publications, ISBN 9780486820804
- Тури, Даниэле (1996–2001), конспекты лекций по теории категорий (PDF)
Внешние ссылки [ править ]
- Монады , пять кратких лекций (с одним приложением).
- В книге Джона Баэза «Находки по математической физике на этой неделе» (неделя 89) монады делятся на две категории.
- Монады и комонады , видеоурок.