Jump to content

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

(Перенаправлено с Т-алгебры )

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

Введение и определение [ править ]

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

Формальное определение [ править ]

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

  • (как естественные преобразования ); здесь и образованы « горизонтальной композицией ».
  • (как естественные преобразования ; здесь обозначает тождественное преобразование из к ).

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

            

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

            

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

Монада набора мощности [ править ]

Монада набора мощности — это монада по категории : За комплект позволять быть силовым набором и для функции позволять — функция между наборами степеней, индуцированная получением прямых изображений под . Для каждого набора , у нас есть карта , который присваивает каждому синглтон . Функция

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

Замечания [ править ]

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

Композиция монад вообще не является монадой. Например, функтор двойной мощности не допускает никакой монадной структуры. [2]

Комонады [ править ]

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

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

Терминологическая история [ править ]

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

Примеры [ править ]

Личность [ править ]

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

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

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

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

Этот эндофунктор быстро становится монадой, где карта единиц происходит из карты единиц. присоединения, а карта умножения строится с использованием карты единиц присоединения:

Фактически, любую монаду можно найти как явное присоединение функторов, используя категорию Эйленберга–Мура. (категория -алгебры). [6]

Двойная дуализация [ править ]

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

где оба функтора задаются путем отправки векторного пространства V в его двойственное векторное пространство . Соответствующая монада отправляет векторное пространство V в его двойной двойник. . Эта монада обсуждается в гораздо большей степени Коком (1970) .

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

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

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

Например, пусть функтор забывчивости из категории Grp групп в категорию Set пусть множеств, и свободный групповой функтор из категории множеств в категорию групп. Затем является левым сопряженным к . В этом случае ассоциированная монада берет набор и возвращает базовый набор свободной группы .Единичная карта этой монады задается картами

включая любой набор в набор естественным образом, как строки длины 1. Далее, умножением этой монады является отображение

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

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

Монады кодовой плотности [ править ]

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

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

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

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

Возможно монада [ править ]

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

Единица задается включением набора в :

Умножение отображает элементы между собой, и две непересекающиеся точки в тому, кто в .

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

Государственная монада [ править ]

Учитывая набор , эндофунктор монады состояния отображает каждый набор к набору функций . Компонент агрегата на отображает каждый элемент к функции

Умножение отображает функцию к функции

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

Монада окружения [ править ]

Учитывая набор , эндофунктор читателя или монады среды отображает каждый набор к набору функций . Таким образом, эндофунктор этой монады — это в точности функтор hom . Компонент агрегата на отображает каждый элемент к постоянной функции .

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

Список и набор монад [ править ]

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

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

Алгебры для монады [ править ]

Дана монада по категории , естественно считать -алгебры , т. е. объекты на что действовал способом, совместимым с единицей и умножением монады. Более формально, А. -алгебра это объект из вместе со стрелой из называется структурной картой алгебры такой, что диаграммы

и

добираться.

Морфизм из -алгебра – это стрелка из такая, что диаграмма

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

Примеры [ править ]

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

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

Алгебры над монадой распределения [ править ]

Другой пример — монада распределения по категории наборов. Это определяется отправкой набора к набору функций с конечным носителем и такие, что их сумма равна . В обозначениях построителя множеств это набор

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

Алгебры над симметричной монадой [ править ]

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

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

алгебры в спектрах колец 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-категории . Описанные выше монады являются монадами для .

См. также [ править ]

Ссылки [ править ]

  1. ^ Барр, Майкл; Уэллс, Чарльз (1985), «Топосы, тройки и теории» (PDF) , Fundamentals of the Mathematical Sciences , vol. 278, Springer-Verlag, стр. 82 и 120, ISBN.  0-387-96115-1 .
  2. ^ Клин; Саламанка (2018), «Итерированный ковариантный набор полномочий не является монадой», Электронные заметки по теоретической информатике , 341 : 261–276, doi : 10.1016/j.entcs.2018.11.013
  3. ^ Маклейн 1978 , с. 138.
  4. ^ Бенабу, Жан (1967). «Введение в бикатегории» . В Бенабу, Дж.; Дэвис, Р.; Долд, А.; Исбелл, Дж.; Маклейн, С.; Оберст, У.; Роос, Ж.-Э. (ред.). Отчеты семинара по категории Среднего Запада . Конспект лекций по математике. Том. 47. Берлин, Гейдельберг: Шпрингер. стр. 1–77. дои : 10.1007/BFb0074299 . ISBN  978-3-540-35545-8 .
  5. ^ «RE: Монады» . Гмане . 04 апреля 2009 г. Архивировано из оригинала 26 марта 2015 г.
  6. ^ Рил, Эмили . «Теория категорий в контексте» (PDF) . п. 162. Архивировано (PDF) из оригинала 5 апреля 2021 г.
  7. ^ Риль 2017 , с. 155.
  8. ^ Свирщ, Т. (1974), «Монадические функторы и выпуклость», Bull. акад. Полон. наук. Сер. наук. Математика. Астрон. Физ. , 22 : 39–42, МР   0390019 , Джейкобс, Барт (2010), «Выпуклость, двойственность и эффекты», Теоретическая информатика , ИФИП «Достижения в области информационных и коммуникационных технологий», том. 323, стр. 1–19, номер документа : 10.1007/978-3-642-15240-5_1 , ISBN.  978-3-642-15239-9
  9. ^ Бастерра, М. (15 декабря 1999 г.). «Когомологии Андре – Квиллена коммутативных S-алгебр» . Журнал чистой и прикладной алгебры . 144 (2): 111–143. дои : 10.1016/S0022-4049(98)00051-6 . ISSN   0022-4049 .
  10. ^ Маклейн (1978) использует более строгое определение, в котором эти две категории скорее изоморфны, чем эквивалентны.
  11. ^ Маклейн (1978 , §§VI.3, VI.9)
  12. ^ Уодлер, Филип (1993). «Монады для функционального программирования» . В Брое, Манфред (ред.). Расчеты по проектированию программ . Серия НАТО ASI. Том. 118. Берлин, Гейдельберг: Шпрингер. стр. 233–264. дои : 10.1007/978-3-662-02880-3_8 . ISBN  978-3-662-02880-3 . «Концепция монады, возникшая из теории категорий, была применена Моджи для структурирования денотационной семантики языков программирования».
  13. ^ Малри, Филип С. (1 января 1998 г.). «Монады в семантике» . Электронные заметки по теоретической информатике . Совместные американо-бразильские семинары по формальным основам программных систем. 14 : 275–286. дои : 10.1016/S1571-0661(05)80241-5 . ISSN   1571-0661 .

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 41839d9d31e493345a4f4f28b2bdaa22__1710601980
URL1:https://arc.ask3.ru/arc/aa/41/22/41839d9d31e493345a4f4f28b2bdaa22.html
Заголовок, (Title) документа по адресу, URL1:
Monad (category theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)