Когерентность алгебраических операций. Часть 2. Ассоциаторы и полугруппоидальные категории.
Для обсуждения вопросов, связанных с ассоциативностью категорных операций, нам потребуется понятие полугруппоидальной категории.
Определение 1. Пусть C -- магматическая категория. Ассоциатор на C -- это естественный изоморфизм α:⊗C○(⊗C⨉IC)→⊗C○(IC⨉⊗C). Ассоциатор α называется когерентным, если коммутативна следующая диаграмма (тождество пятиугольника):
Определение 2. Полугруппоидальная категория -- это пара (C,α), где C -- магматическая категория и α -- когерентный ассоциатор (полугруппоидальная от слова полугруппа).
Наша следующая задача -- построение дискретной полугруппоидальной категории на множестве A. После тренировки с магматическими категориями это не так уж и сложно, однако, это несколько более тонкая задача. Легко допустить ошибку, если подумать, что достаточно просто добавить к дискретной категории на множестве A стрелки ассоциативности и породить получившимся графом свободную категорию. Или если подумать, что достаточно взять свободную магматическую категорию от получившейся свободной категории. Дело в том, что необходимо совместить взятие свободной категории и свободной магматической категории, причём сделать это индуктивно.
Построим дискретную полугруппоидальную категорию на множестве A следующим образом. В качестве магмы объектов, очевидно, необходимо взять свободную магму F[A]. Обозначим через X наименьшее подмножество в ({(,),,,⊗}⊔A⊔F[A]⨉3⊔F[A]⨉3)*, такое, что A⊔F[A]⨉3⊔F[A]⨉3⊂X, и для любых t,s∈F[A] выполняется (⊗,(,t,,,s,))∈X и ((,t,,,s,))∈X. Суть данного построения элементарна: элементы множества A отождествляются с тождественными морфизмами, элементы первой компоненты F[A]⨉3⊔F[A]⨉3 -- с морфизмами ассоциатора, второй -- с обратными к ним, (⊗,(,t,,,s,)) -- с тензорным произведением t и s, ((,t,,,s,)) -- с композицией t и s. Тем не менее, построение ещё не завершено. Определим отображения domX:X→F[A] и codX:X→F[A] индуктивно очевидным образом. Обозначим через Y наименьшее подмножество в X, такое, что A⊔F[A]⨉3⊔F[A]⨉3⊂Y, для любых t,s∈F[A] выполняется (⊗,(,t,,,s,))∈Y, и для любых t,s∈F[A], таких, что domX(s)=codX(t), выполняется ((,t,,,s,))∈Y. Обозначим domY=domX|Y, codY=codX|Y. Определим отображение idY:F[A]→Y индуктивно очевидным образом. Обозначим через R наименьшее отношение эквивалетности на Y, такое, что выполняются следующие соотношения (не буду писать формулами): ассоциативность композиции, унитальность тождественных морфизмов, естественность и обратимость ассоциатора, тождество пятиугольника, бифункториальность тензорного произведения, конгруэнтность тензорного произведения и композиции. Нетрудно проверить, что множество объектов F[A], множество морфизмов Y/R, профакторизованные отображения dom,cod,id,comp, и очевидным образом определённые функтор тензорного произведения и ассоциатор образуют полугруппоидальную категорию (обозначим её DA). Кроме того, для каждой полугруппоидальной категории С с множеством объектов A существует функтор DA→С, тождественный на A и переводящий диаграммы DA в формальные диаграммы C.
Определение 3. Категория называется эквикатегорией, если она одновременно является группоидом и предпорядком (по аналогии с понятием эквимножества -- пары (X,~), где X -- множество и ~ -- отношение эквивалентности на X (см. определение 10 в постинге [1])).
Теорема 1. (о когерентности в полугруппоидальных категориях) Пусть A -- множество. Тогда DA -- эквикатегория.
Доказательство теоремы 1. То, что DA является группоидом -- очевидно. Необходимо доказать, что DA является предпорядком. Построим отображение γ:F[A]→Y/R, такое, что γ(t):ν(t)→t индуктивно по длине объекта t следующим образом: γ(a)=id(a); для t,s∈F[A], где ω(s)=(s1,...,sn), построим морфизм γ(t⊗s) при помощи композиции:
Обозначим через B0 наименьшее подмножество Y, такое, что для любого t∈F[A] выполняется idX(t)∈B0, для любых t,s,r выполняется α(t,s,r)∈B0, для любых t∈F[A] и b∈B0 выполняется t⊗b∈B0 и b⊗t∈B0. Обозначим через B проекцию B0 на Y/R. Нетрудно доказать по индукции, что для каждого t∈F[A] морфизм γ(t) представляется в виде композиции морфизмов из В.
Пусть f1,...,fn,g1,...,gm∈B, t∈F[A], fn○...○f1:ν(t)→t, gm○...○g1:ν(t)→t. Докажем, что fn○...○f1=gm○...○g1 (утверждение (*)). Доказательство проведём индуктивно по рангу t. Для δ(t)=0 утверждение очевидно (для этого заметим, что всякий морфизм из B либо увеличивает ранг, либо является тождественным). Докажем шаг индукции. Без ограничения общности предположим, что все морфизмы f1,...,fn,g1,...,gm не являются тождественными (следовательно, повышают ранг). Обозначим dom(fn)=t' и dom(gm)=t''. Нетрудно видеть, что для доказательства шага индукции достаточно доказать, что существует такой объект t''' и такие морфизмы h1,...,hp,k1,...,kq∈B, что hp○...○h1:t'''→t', kq○...○k1:t'''→t'' и fn○hp○...○h1=gm○kq○...○k1. Докажем это утверждение индукцией по длине t. База (ψ(t)=3) очевидна, докажем шаг. Требуется перебор вариантов:
1). Пусть t'=t'' и fn=gm. Тогда положим t'''=t', p=q=1, h1=k1=id(t');
2). Пусть fn≠gm. Тогда t=s⊗r для некоторых s,r∈F[A] и возможны следующие варианты:
2.1). Пусть fn=s⊗f, gm=s⊗g. Тогда воспользуемся доказанным утверждением для меньших длин и применим его к морфизмам f и g;
2.2). Пусть fn=f⊗r, gm=g⊗r. Аналогично пункту 2.1;
2.3). Пусть t'=s⊗r', t''=s'⊗r, fn=s⊗f, gm=g⊗r. Тогда положим t'''=s'⊗r', p=q=1, h1=g⊗r', k1=s'⊗f;
2.4). Пусть t'=s'⊗r, t''=s⊗r', fn=f⊗r, gm=s⊗g. Аналогично случаю 2.3;
2.5). Пусть r=d⊗e, t'=(s⊗d)⊗e, t''=s'⊗(d⊗e), fn=α(s,d,e), gm=f⊗(d⊗e). Тогда положим t'''=(s'⊗d)⊗e, p=q=1, h1=(f⊗d)⊗e, k1=α(s',d,e);
2.6). Пусть r=d⊗e, t'=(s⊗d)⊗e, t''=s⊗(d'⊗e), fn=α(s,d,e), gm=s⊗(f⊗e). Аналогично случаю 2.5;
2.7). Пусть r=d⊗e, t'=(s⊗d)⊗e, t''=s⊗(d⊗e'), fn=α(s,d,e), gm=s⊗(d⊗f). Аналогично случаю 2.5;
2.8). Пусть r=d⊗(e⊗j), t'=(s⊗d)⊗(e⊗j), t''=s⊗((d⊗e)⊗j), fn=α(s,d,e⊗j), gm=s⊗α(d,e,j). Тогда положим t'''=((s⊗d)⊗e)⊗j, p=1, q=2, h1=α(s⊗d,e,j), k1=α(s,d,e)⊗j, k2=α(s,d⊗e,j) [именно здесь вылезает диаграмма пятиугольника];
2.9-2.12 -- симметричные 2.5-2.8. Таким образом, утверждение (*) доказано.
Заметим, далее, что всякий морфизм в категории DA представляется в виде композиции морфизмов из B и обратных к ним. Таким образом, с любыми двумя морфизмами f,g:t→s можно связать диаграмму следующего вида:
где все морфизмы fi и gj принадлежат B. Из утверждения (*) следует, что каждый малый треугольник на диаграмме коммутативен. Из леммы о расширении диаграммы следует, что вся данная диаграмма коммутативна. Из ответа [2] следует, что коммутативность диаграммы не разрушится от добавления обратных морфизмов; таким образом, теорема 1 доказана.
Замечание 1. В отличие от термина "магматическая категория" (ср. замечание 2 в постинге [3]), термин "полугруппоидальная категория" иногда используется в книгах и статьях по теории категорий (в основном, у австралийской школы). В частности, Stephen Lack в статье Homotopy-theoretic aspects of 2-monads строит магматические и полугруппоидальные категории как алгебры над 2-монадами.
Продолжение следует.
Определение 1. Пусть C -- магматическая категория. Ассоциатор на C -- это естественный изоморфизм α:⊗C○(⊗C⨉IC)→⊗C○(IC⨉⊗C). Ассоциатор α называется когерентным, если коммутативна следующая диаграмма (тождество пятиугольника):
Определение 2. Полугруппоидальная категория -- это пара (C,α), где C -- магматическая категория и α -- когерентный ассоциатор (полугруппоидальная от слова полугруппа).
Наша следующая задача -- построение дискретной полугруппоидальной категории на множестве A. После тренировки с магматическими категориями это не так уж и сложно, однако, это несколько более тонкая задача. Легко допустить ошибку, если подумать, что достаточно просто добавить к дискретной категории на множестве A стрелки ассоциативности и породить получившимся графом свободную категорию. Или если подумать, что достаточно взять свободную магматическую категорию от получившейся свободной категории. Дело в том, что необходимо совместить взятие свободной категории и свободной магматической категории, причём сделать это индуктивно.
Построим дискретную полугруппоидальную категорию на множестве A следующим образом. В качестве магмы объектов, очевидно, необходимо взять свободную магму F[A]. Обозначим через X наименьшее подмножество в ({(,),,,⊗}⊔A⊔F[A]⨉3⊔F[A]⨉3)*, такое, что A⊔F[A]⨉3⊔F[A]⨉3⊂X, и для любых t,s∈F[A] выполняется (⊗,(,t,,,s,))∈X и ((,t,,,s,))∈X. Суть данного построения элементарна: элементы множества A отождествляются с тождественными морфизмами, элементы первой компоненты F[A]⨉3⊔F[A]⨉3 -- с морфизмами ассоциатора, второй -- с обратными к ним, (⊗,(,t,,,s,)) -- с тензорным произведением t и s, ((,t,,,s,)) -- с композицией t и s. Тем не менее, построение ещё не завершено. Определим отображения domX:X→F[A] и codX:X→F[A] индуктивно очевидным образом. Обозначим через Y наименьшее подмножество в X, такое, что A⊔F[A]⨉3⊔F[A]⨉3⊂Y, для любых t,s∈F[A] выполняется (⊗,(,t,,,s,))∈Y, и для любых t,s∈F[A], таких, что domX(s)=codX(t), выполняется ((,t,,,s,))∈Y. Обозначим domY=domX|Y, codY=codX|Y. Определим отображение idY:F[A]→Y индуктивно очевидным образом. Обозначим через R наименьшее отношение эквивалетности на Y, такое, что выполняются следующие соотношения (не буду писать формулами): ассоциативность композиции, унитальность тождественных морфизмов, естественность и обратимость ассоциатора, тождество пятиугольника, бифункториальность тензорного произведения, конгруэнтность тензорного произведения и композиции. Нетрудно проверить, что множество объектов F[A], множество морфизмов Y/R, профакторизованные отображения dom,cod,id,comp, и очевидным образом определённые функтор тензорного произведения и ассоциатор образуют полугруппоидальную категорию (обозначим её DA). Кроме того, для каждой полугруппоидальной категории С с множеством объектов A существует функтор DA→С, тождественный на A и переводящий диаграммы DA в формальные диаграммы C.
Определение 3. Категория называется эквикатегорией, если она одновременно является группоидом и предпорядком (по аналогии с понятием эквимножества -- пары (X,~), где X -- множество и ~ -- отношение эквивалентности на X (см. определение 10 в постинге [1])).
Теорема 1. (о когерентности в полугруппоидальных категориях) Пусть A -- множество. Тогда DA -- эквикатегория.
Доказательство теоремы 1. То, что DA является группоидом -- очевидно. Необходимо доказать, что DA является предпорядком. Построим отображение γ:F[A]→Y/R, такое, что γ(t):ν(t)→t индуктивно по длине объекта t следующим образом: γ(a)=id(a); для t,s∈F[A], где ω(s)=(s1,...,sn), построим морфизм γ(t⊗s) при помощи композиции:
Обозначим через B0 наименьшее подмножество Y, такое, что для любого t∈F[A] выполняется idX(t)∈B0, для любых t,s,r выполняется α(t,s,r)∈B0, для любых t∈F[A] и b∈B0 выполняется t⊗b∈B0 и b⊗t∈B0. Обозначим через B проекцию B0 на Y/R. Нетрудно доказать по индукции, что для каждого t∈F[A] морфизм γ(t) представляется в виде композиции морфизмов из В.
Пусть f1,...,fn,g1,...,gm∈B, t∈F[A], fn○...○f1:ν(t)→t, gm○...○g1:ν(t)→t. Докажем, что fn○...○f1=gm○...○g1 (утверждение (*)). Доказательство проведём индуктивно по рангу t. Для δ(t)=0 утверждение очевидно (для этого заметим, что всякий морфизм из B либо увеличивает ранг, либо является тождественным). Докажем шаг индукции. Без ограничения общности предположим, что все морфизмы f1,...,fn,g1,...,gm не являются тождественными (следовательно, повышают ранг). Обозначим dom(fn)=t' и dom(gm)=t''. Нетрудно видеть, что для доказательства шага индукции достаточно доказать, что существует такой объект t''' и такие морфизмы h1,...,hp,k1,...,kq∈B, что hp○...○h1:t'''→t', kq○...○k1:t'''→t'' и fn○hp○...○h1=gm○kq○...○k1. Докажем это утверждение индукцией по длине t. База (ψ(t)=3) очевидна, докажем шаг. Требуется перебор вариантов:
1). Пусть t'=t'' и fn=gm. Тогда положим t'''=t', p=q=1, h1=k1=id(t');
2). Пусть fn≠gm. Тогда t=s⊗r для некоторых s,r∈F[A] и возможны следующие варианты:
2.1). Пусть fn=s⊗f, gm=s⊗g. Тогда воспользуемся доказанным утверждением для меньших длин и применим его к морфизмам f и g;
2.2). Пусть fn=f⊗r, gm=g⊗r. Аналогично пункту 2.1;
2.3). Пусть t'=s⊗r', t''=s'⊗r, fn=s⊗f, gm=g⊗r. Тогда положим t'''=s'⊗r', p=q=1, h1=g⊗r', k1=s'⊗f;
2.4). Пусть t'=s'⊗r, t''=s⊗r', fn=f⊗r, gm=s⊗g. Аналогично случаю 2.3;
2.5). Пусть r=d⊗e, t'=(s⊗d)⊗e, t''=s'⊗(d⊗e), fn=α(s,d,e), gm=f⊗(d⊗e). Тогда положим t'''=(s'⊗d)⊗e, p=q=1, h1=(f⊗d)⊗e, k1=α(s',d,e);
2.6). Пусть r=d⊗e, t'=(s⊗d)⊗e, t''=s⊗(d'⊗e), fn=α(s,d,e), gm=s⊗(f⊗e). Аналогично случаю 2.5;
2.7). Пусть r=d⊗e, t'=(s⊗d)⊗e, t''=s⊗(d⊗e'), fn=α(s,d,e), gm=s⊗(d⊗f). Аналогично случаю 2.5;
2.8). Пусть r=d⊗(e⊗j), t'=(s⊗d)⊗(e⊗j), t''=s⊗((d⊗e)⊗j), fn=α(s,d,e⊗j), gm=s⊗α(d,e,j). Тогда положим t'''=((s⊗d)⊗e)⊗j, p=1, q=2, h1=α(s⊗d,e,j), k1=α(s,d,e)⊗j, k2=α(s,d⊗e,j) [именно здесь вылезает диаграмма пятиугольника];
2.9-2.12 -- симметричные 2.5-2.8. Таким образом, утверждение (*) доказано.
Заметим, далее, что всякий морфизм в категории DA представляется в виде композиции морфизмов из B и обратных к ним. Таким образом, с любыми двумя морфизмами f,g:t→s можно связать диаграмму следующего вида:
где все морфизмы fi и gj принадлежат B. Из утверждения (*) следует, что каждый малый треугольник на диаграмме коммутативен. Из леммы о расширении диаграммы следует, что вся данная диаграмма коммутативна. Из ответа [2] следует, что коммутативность диаграммы не разрушится от добавления обратных морфизмов; таким образом, теорема 1 доказана.
Замечание 1. В отличие от термина "магматическая категория" (ср. замечание 2 в постинге [3]), термин "полугруппоидальная категория" иногда используется в книгах и статьях по теории категорий (в основном, у австралийской школы). В частности, Stephen Lack в статье Homotopy-theoretic aspects of 2-monads строит магматические и полугруппоидальные категории как алгебры над 2-монадами.
Продолжение следует.