алгебры для одной специфической монады

[juan_gandhi]

Вот возьмём-ка монадку X2, из моего поста.

"Какая ж тут у нас монада? Монада берёт множество X и сопоставляет ему X×X. Монадная единица - диагональ (η(x) = (x,x)), а монадное умножение, X×X×X×X → X×X строится, согласно картинкам из начала этой части, из ε: (Y1×Y2, Y1×Y2) →(Y1,Y2) - проектированием по первой и последней координатам. μ(x1,x2,x3,x4) = (x1,x4)."

Так вот, а какие ж бывают алгебры над такой монадой? Нам надо, чтобы был f: A×A → A, соблюдающий условия:

f(a,a) == a

f(f(a1,a2),f(a3,a4)) == f(a1,a4)

Мне вот что-то сдаётся, что в условиях булевости и точечности (ну, скажем, в множествах) только проекция удовлетворяет такому условию. p1(a1,a2) = a1; p2(a1,a2) = a2.

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

Comments

[kcmamu.livejournal.com]

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

[ivan-gandhi.livejournal.com]

О блин, вот это да. Можно детали?

У меня что-то получается, что любая пара {a,b} переходит в {f(a,b), f(b,a)} и обратно.

[kcmamu.livejournal.com]

Вот пускай число элементов есть p*q (p и q не обязательно простые).

Закодируем элементы наборами {x, y}, где x принимает p значений, а y -- q значений. Существенно, что кодировок много ((pq)!).

Новые функции такие: f({x, y}, {z, t}) = {x, t} (т. е. одну координату проектируем влево, а вторую -- вправо). Или {z, y}. При этом одна и та же функция вылезет несколько раз в разных кодировках, но все равно разных останется много. Для множеств из 4 элементов их 6, для 6 элементов -- 120. (Плюс тем две p1 и p2, что у тебя.)

[ivan-gandhi.livejournal.com]

О. Убедил.

Классно!

[migmit.livejournal.com]

p1 и p2 тоже укладываются в эту схему, достаточно положить p=1 или q=1.

[migmit.livejournal.com]

О. Это практически моя олимпиадная задачка.

Вспоминаем теорему из нулевой главы Джонстона: пусть есть пара сопряжённых функторов F:C->A, U:A->C, F-|U, и H — монада, индуцированная этим сопряжением. Предположим, что в A имеются коуравнители рефлексивных пар, U сохраняет их и отражает изоморфизмы. Тогда U — монадический функтор, т.е., категория A эквивалентна категории алгебр над H в C, а U при этой эквивалентности переходит в стирающий функтор.

Ну вот, отсюда и получается, что любое непустое множество с такой бинарной операцией изоморфно произведению множеств XxY, на котором операция задана как f((x1,y1),(x2,y2)) = (x1,y2).

[ivan-gandhi.livejournal.com]

Вот! Я долго пытался вспомнить, откуда это, с каких олимпиад. Спасибо.