Понял сегодня вечером, что не понимаю даже того

[posic]

что такое конический слабый предел категорий. Как получить категорию Эйленберга-Мура в виде предела диаграммы, составленной из категории с монадой? Не могу врубиться в то, что утверждается по этому поводу в литературе. На самый первый поверхностный взгляд, вроде оно не бессмысленно, а в деталях картинка не складывается у меня. Надо, видимо, вчитаться в работу Росса Стрита 1976 года.

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

Comments

[chaource]

Про категорiю Эйленберга-Мура въ связи съ монадами я что-то слышалъ. Это что-то вроде initial object для категорiи adjunctions данной монады. Когда-то я интересовался этимъ, потому что была надѣжда получить такъ называемые "трансформеры монадъ" автоматически. Надѣжда не оправдалась. Оказалось, что есть тамъ и terminal object in the category of adjunctions. Иногда трансформеръ получается изъ terminal object, иногда изъ initial object, а иногда ни изъ того, ни изъ другого. И поскольку ничего путнаго придумать не удалось, я бросилъ это изучать.

То, что программисты называютъ "трансформеромъ" данной монады T - это какой-либо эндофункторъ F въ категорiи монадъ, для котораго выполняются два условiя:

1) F(Id) = T , гдѣ Id - это тождественная монада (т.е. тождественный эндофункторъ, который всегда одновременно является монадой).

2) Существуетъ естественное преобразованiе ID -> F, гдѣ ID - это тождественный эндофункторъ уже въ категорiи монадъ.

Трансформеры полезны, потому что имѣя монаду T съ трансформеромъ, мы можемъ для любой другой монады U взять образъ F(U) и получить новую монаду, которая объединяетъ въ себѣ полезныя для программированiя свойства обѣихъ монадъ (T и U). Въ программированiи это означаетъ, что мы автоматически можемъ построить новую структуру данныхъ, имѣя структуры T, F, U.

Можно составить нѣкiй списокъ полезныхъ для программированiя монадъ въ категорiи Set, и для каждой есть рецептъ построенiя трансформера. Есть примѣрно 6 разныхъ типовъ рецептовъ, и никакой особо внятной системы тамъ не видно.

Первая въ спискѣ монада - это эндофункторъ категорiи Set, называемый Maybe. Этотъ эндофункторъ беретъ множество и дѣлаетъ изъ него новое множество съ добавленнымъ дизъюнктивно однимъ элементомъ, который гарантированно не является элементомъ стараго множества. Обозначимъ этотъ элементъ *. Тогда функторъ дѣлаетъ такъ:

Maybe {a, b, c} = {a, b, c, *}


Я не знаю, какъ это лучше обозначить, чтобы математикамъ было ясно. Программисты пишутъ Maybe S = 1 + S

[posic]

Ты очень понятно объяснил, что такое Maybe.

Я написал ряд работ про примеры того, что я называю "аддитивными монадами на категории Set". Они возникают в теории контрамодулей. Но вряд ли это интересно для программирования, хотя бы уже потому, что эти мои монады обычно переводят конечные множества в бесконечные. Аддитивные монады на категории множеств, переводящие конечные множества в конечные, соответствуют, я думаю, просто конечным кольцам (ассоциативным с единицей).

[chaource]

А что такое "аддитивная монада"? Но вообще я бы посмотрѣлъ на примѣры, интересно. Даже если множество безконечно, это не обязательно плохо для программированiя, потому что, скажемъ, множество натуральныхъ чиселъ тоже безконечно, а программисты обычно допускаютъ такiя множества и во многихъ языкахъ есть типъ "цѣлое число неограниченнаго размѣра".

[posic]

Аддитивная монада на категории множеств -- это такая монада M, что в множестве "M(пустого множества)" есть элемент 0, в множестве M(одноэлементного множества {x}) есть элемент -x, и в множестве M(двухэлементного множества {x,y}) есть элемент x+y, такие что на любом множестве A с действием монады M получается структура абелевой группы с этими операциями.

Например, пусть R -- кольцо. Тогда монада M_R сопоставляет каждому множеству X множество всех формальных линейных комбинаций элементов X с коэффициентами из R. То есть берется прямая сумма X копий абелевой группы R, и рассматривается просто как множество -- это множество M_R(X). Единица и умножение в кольце R индуцируют структуру монады на функторе M_R.

Другие примеры в том же русле, только там есть операции бесконечной арности. Например, рассмотрим кольцо k[[t]] формальных степенных рядов от одной переменной t над полем k. Тогда соответствующая монада M сопоставляет каждому множеству X множество всех бесконечных формальных линейных комбинаций элементов X с коэффициентами из k[[t]], с условием, что семейство коэффициентов в бесконечной формальной линейной комбинации должно сходиться к нулю в t-адической топологии кольца k[[t]]. Вместо k[[t]] можно p-адические числа и разные другие топологические кольца рассматривать (или даже не топологические кольца, а "кольца с понятием сходимости").

[chaource]

Например, пусть R -- кольцо. Тогда монада M_R сопоставляет каждому множеству X множество всех формальных линейных комбинаций элементов X с коэффициентами из R. То есть берется прямая сумма X копий абелевой группы R, и рассматривается просто как множество -- это множество M_R(X). Единица и умножение в кольце R индуцируют структуру монады на функторе M_R.

Если я правильно понялъ, то M_R(X) это просто декартово произведенiе R × X. Монада получается изъ-за того, что R является моноидомъ съ единицей и произведенiемъ.

M_R(M_R(X)) → M_R(X) опредѣляется какъ R × R × X → R × X, гдѣ функцiя R × R → R это умноженiе въ кольцѣ.

Такая монада въ программированiи извѣстна и называется "the Writer monad". Используется вмѣсто кольца просто моноидъ.

[posic]

Нет, конечно, ты неправильно понял. M_R(X) -- это не R × X ни разу. M_R(X) -- это подмножество в R^X, состоящее из всех функций X → R, принимающих значение 0 на всех, кроме конечного числа, элементах множества X.

[posic]

Например, допустим, R -- это поле вычетов по модулю 3, т.е. R = {0,1,2} (остатки по модулю 3). И, допустим, Х -- это множество из двух элементов, X = {x,y}. Тогда M_R(X) = R^X -- это множество из девяти элементов. Элементами множества M_R(X) являются следующие формальные выражения ("формальные линейные комбинации"):

0 x + 0 y
0 x + 1 y
0 x + 2 y
1 x + 0 y
1 x + 1 y
1 x + 2 y
2 x + 0 y
2 x + 1 y
2 x + 2 y

Итого девять штук.

[chaource]

Ага, я ошибся. Однако тогда всё становится гораздо болѣе другое...

Тогда M_R(M_R(X)) = (X → R) → R и для программированiя это совершенно непонятно что такое. Въ программированiи нельзя построить функцiю изъ (X → R) → R въ X → R, потому что (X → R) → R коварiантно по X, a X → R контраварiантно. Но это только потому, что функцiи въ программированiи интерпретируются какъ элементы Hom-set какой-то категорiи. А здѣсь совершенно другое.

[chaource]

Скажемъ, M_R(M_R(X)) для этого примѣра выглядитъ такъ: это множество формальныхъ линейныхъ комбинацiй вида:

1 (0 x + 0 y) + 0 (0 x + 1 y) + 2(0 x + 2 y) + ...

Потомъ мы раскрываемъ скобки и получаемъ опять элементъ множества M_R(X).

Я не вижу, какъ это выглядѣло бы въ примѣненiи къ программированiю. Тамъ всё по-другому работаетъ.

Я раньше думалъ, что программированiе используетъ категорiю множествъ и тамъ пишетъ эндофункторы. Однако, категорiя множествъ, видимо, гораздо богаче, чѣмъ то, что необходимо для программированiя. Потому что напримѣръ въ категорiи множествъ есть два вида функтора Powerset, одинъ коварiантный, другой контраварiантный, а въ программированiи есть только контраварiантный аналогъ.

[posic]

Да, именно так. И важно, что R -- кольцо (при раскрытии скобок надо перемножать элементы R, а при приведении подобных членов -- складывать).

[chaource]

Это очень сложная структура по мѣркамъ программированiя. Моноидомъ не обойдешься, нужно кольцо (а такого обычно нѣтъ для стандартныхъ структуръ данныхъ).

Чтобы вычислить раскрытiе скобокъ, нужно перечислить всѣ комбинацiи. Въ терминахъ программированiя это выглядитъ такъ. Дается элементъ mmx ∈ M_R(M_R(X)) = (X → R) → R и мы должны вычислить соотвѣтствующiй ему элементъ mx ∈ M_R(X) = X → R. Чтобы вычислить функцiю типа X → R, мы должны по любому данному элементу x ∈ X вычислить соотвѣтствующее значенiе r ∈ R. Чтобы это сдѣлать, мы должны сначала перечислить всѣ возможныя функцiи f ∈ X → R. Каждую такую функцiю f надо подставить въ mmx и получить соотвѣтствующее значенiе mmx(f) ∈ R, это значенiе помножить на f(x) и всѣ результаты просуммировать. Получится mx(x).

mx(x) = \sum _ {f ∈ X → R} mmx(f) * f(x)

Теперь видно, что результатъ контраварiантенъ по x.

Но ни въ одномъ языкѣ программированiя нѣтъ такой конструкцiи - итерацiя по всѣмъ функцiямъ типа A → B. Не говоря уже объ итерацiи только по такимъ функцiямъ, которыя принимаютъ ненулевое значенiе лишь въ конечномъ числѣ точекъ.

[posic]

Что касается функтора Powerset, то дело обстоит так. Для любого множества A, функтор, переводящий множество X в множество A^X, контравариантен по X. Но если A -- множество с отмеченным элементом "ноль", то можно рассмотреть подмножество в A^X, состоящее из всех функций X → A, переводящих почти все (все, кроме конечного числа) элементы множества X в элемент "ноль". Обозначим это подмножество через A^(X) ⊂ A^X.

Отображение, переводящее произвольное множество X в множество A^(X), вообще не является функтором (от аргумента X) на категории множеств. Ситуация меняется, когда A -- абелева группа. Для любой абелевой группы A, отображение, переводящее множество X в множество A^(X) -- ковариантный функтор (от аргумента X) на категории множеств.

Например, если в примере выше взять множество из двух элементов Z = {z,t} и отображение f: X → Z, заданное правилами f(x)=z, f(y)=z (т.е., оба элемента x и y переходят в z, а в t ничего не переходит), то определено отображение M_R(f): M_R(X) → M_R(Z). Например, элемент

1 x + 1 y

переходит при отображении M_R(f) в элемент

1 z + 1 z = 2 z + 0 t.

[chaource]

https://math.stackexchange.com/questions/1487902/covariant-power-set-functor

А тутъ есть обсужденiе, гдѣ не требуется отмѣченная точка и абелева группа. Это какой-то другой powerset функторъ?

[posic]

Это почти частный случай. Надо заменить мою абелеву группу A на коммутативный моноид (вычитание в A не используется в моей конструкции, я просто привык думать про группы в этом контексте), а потом подставить на место коммутативного моноида A конкретный моноид из двух элементов {0,1} с нейтральным элементом 0 и сложением, заданным по правилу 1 + 1 = 1 (как бы "логическое или").

[posic]

Вернее сказать, я не совсем прав. Это все-таки другой powerset функтор, который имеет смысл потому, что в моноиде A = {0,1} с операцией "логическое или" можно сложить бесконечно много элементов. Для любого, сколь угодно бесконечного семейства элементов из A, если хотя бы один из этих элементов -- единица, то "сумма" (логическая дизъюнкция их всех) равна 1, а если все эти элементы нули, то 0.

То, что я написал комментом выше -- это функтор, сопоставляющий множеству X множество всех его конечных подмножеств, а отображению f: X → Z -- образ подмножества. А по твоей ссылке не сказано, что подмножества должны быть конечными. Бесконечные подмножества тоже можно рассматривать, потому что бесконечная дизъюнция имеет смысл. Если множество X предполагается конечным, то разницы нет.

[chaource]

Въ общемъ, имѣя элементъ px ∈ X → 2 и функцiю f: X → Z, мы строимъ элементъ pz ∈ Z → 2. Для даннаго z ∈ Z мы вычисляемъ:

pz(z) = LogicalOr_{x ∈ X} (px(x) LogicalAnd f(x) == z).

Для вычисленiя этого нужна итерацiя по всѣмъ элементамъ множества X, для которыхъ px(x) = true.

Это будетъ работать въ языкѣ программированiя, гдѣ предусмотрены типы данныхъ вида "функцiя, значенiя которой не равны нулю лишь для конечнаго числа точекъ, вмѣстѣ со спискомъ этихъ точекъ". Это еще можно какъ-то запрограммировать - такая функцiя эквивалентна просто списку значенiй x.

А вотъ списокъ всѣхъ такихъ функцiй уже далеко не просто составлять.