F- алгебра

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

F -алгебры также могут использоваться для представления структур данных , используемых в программировании , таких как списки и деревья .

Основными связанными понятиями являются исходные F -алгебры, которые могут служить для инкапсуляции принципа индукции, и двойственные конструкции F -коалгебры .

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

Если $C$ это категория , и $F:C\rightarrow C$ является эндофунктором $C$ , затем $F$ - алгебра - это кортеж $(A,\alpha )$ , где $A$ является объектом $C$ и $\alpha$ это $C$ - морфизм $F(A)\rightarrow A$ . Объект $A$ называется носителем алгебры. Когда это допустимо из контекста, алгебры часто упоминаются только по их носителю, а не по кортежу.

Гомоморфизм из $F$ -алгебра $(A,\alpha )$ к $F$ -алгебра $(B,\beta )$ это $C$ -морфизм $f:A\rightarrow B$ такой, что $f\circ \alpha =\beta \circ F(f)$ , согласно следующей коммутативной диаграмме :

Оснащенный этими морфизмами, $F$ -алгебры составляют категорию.

Двойная конструкция представляет собой $F$ -коалгебры – объекты $A^{*}$ вместе с морфизмом $\alpha ^{*}:A^{*}\rightarrow F(A^{*})$ .

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

Группы [ править ]

Классически группа представляет собой набор $G$ с групповым законом $m:G\times G\rightarrow G$ , с $m(x,y)=x\cdot y$ , удовлетворяющий трем аксиомам: существование единичного элемента, существование обратного для каждого элемента группы и ассоциативность.

Чтобы представить это в категориальной структуре, сначала определите тождество и обратное как функции (морфизмы множества $G$ ) к $e:1\rightarrow G$ с $e(*)=1$ , и $i:G\rightarrow G$ с $i(x)=x^{-1}$ . Здесь $1$ обозначает множество с одним элементом $1=\left\{*\right\}$ , что позволяет идентифицировать элементы $x\in G$ с морфизмами $1\rightarrow G$ .

Тогда можно записать аксиомы группы в терминах функций (обратите внимание, что квантор существования отсутствует):

$\forall x\in G,\forall y\in G,\forall z\in G,m(m(x,y),z)=m(x,m(y,z))$ ,
$\forall x\in G,m(e(*),x)=m(x,e(*))=x$ ,
$\forall x\in G,m(i(x),x)=m(x,i(x))=e(*)$ .

Тогда это можно выразить с помощью коммутативных диаграмм: ^[1]^[2]

Теперь используйте копроизведение ( несвязное объединение множеств), чтобы склеить три морфизма в один: $\alpha =e+i+m$ в соответствии с

{\begin{matrix}\alpha :{1}+G+G\times G&\to &G,\\*&\mapsto &1,\\x&\mapsto &x^{-1},\\(x,y)&\mapsto &x\cdot y.\end{matrix}}

Таким образом, группа – это $F$ -алгебра где $F$ это функтор $F(G)=1+G+G\times G$ . Однако обратное не обязательно верно. Некоторый $F$ -алгебра где $F$ это функтор $F(G)=1+G+G\times G$ не являются группами.

Приведенная выше конструкция используется для определения групповых объектов в произвольной категории с конечными произведениями и терминальным объектом. $1$ . Когда категория допускает конечные копродукции , групповые объекты $F$ -алгебры. Например, конечные группы – это $F$ -алгебры в категории конечных множеств и Ли групп $F$ -алгебры в категории гладких многообразий с гладкими отображениями .

Алгебраические структуры [ править ]

Заходя на шаг впереди универсальной алгебры , большинство алгебраических структур являются F -алгебрами. Например, абелевы группы являются F -алгебрами для того же функтора F ( G ) = 1 + G + G × G , что и для групп, с дополнительной аксиомой коммутативности: m ∘ t = m , где t ( x , y ) = ( y , x ) — транспонирование G x G .

Моноиды — это F -алгебры сигнатуры F ( M = 1 + M × M. ) Точно так же полугруппы — это F -алгебры сигнатуры F ( S ) = S × S.

Кольца , области и поля также являются F -алгебрами с сигнатурой, включающей два закона +,•: R × R → R, аддитивное тождество 0: 1 → R , мультипликативное тождество 1: 1 → R и аддитивное обратное для каждого -: R → R. элемент Поскольку все эти функции имеют одну и ту же кодовую область R, их можно склеить в одну сигнатурную функцию 1 + 1 + R + R × R + R × R → R с аксиомами для выражения ассоциативности, дистрибутивности и т. д. Это делает кольца F -алгебрами в категории множеств с сигнатурой 1 + 1 + R + R × R + R × R .

Альтернативно мы можем посмотреть на функтор F ( R ) = 1 + R × R в категории абелевых групп . В этом контексте умножение является гомоморфизмом, что означает m ( x + y , z ) = m ( x , z ) + m ( y , z ) и m ( x , y + z ) = m ( x , y ) + m ( x , z ), которые и являются условиями дистрибутивности. Следовательно, кольцо — это F -алгебра сигнатуры 1 + R × R над категорией абелевых групп, удовлетворяющая двум аксиомам (ассоциативности и тождественности умножения).

Когда мы переходим к векторным пространствам и модулям , функтор сигнатуры включает скалярное умножение k × E → E , а сигнатура F ( E ) = 1 + E + k × E параметризуется k над категорией полей или колец.

Алгебры над полем можно рассматривать как F -алгебры сигнатуры 1 + 1 + A + A × A + A × A + k × A над категорией множеств, сигнатуры 1 + A × A над категорией модулей (a модуля с внутренним умножением) и сигнатуры k × A над категорией колец (кольцо со скалярным умножением), когда они ассоциативны и унитарны.

Решетка [ править ]

Не все математические структуры являются F -алгебрами. Например, частично упорядоченное множество P может быть определено в категориальных терминах с морфизмом s : P × P → Ω на классификаторе подобъектов ( Ω = {0,1} в категории множеств и s ( x , y )=1 точно когда x ≤ y ). Аксиомы, ограничивающие морфизм s для определения чу-множества, можно переписать в терминах морфизмов. Однако, поскольку кодоменой s является Ω, а не P , это не F -алгебра.

Однако решетки , которые представляют собой частичные порядки, в которых каждые два элемента имеют верхнюю и нижнюю грани, и, в частности, полные порядки , являются F -алгебрами. Это связано с тем, что их можно эквивалентно определить в терминах алгебраических операций: x ∨ y = inf( x , y ) и x ∧ y = sup( x , y ), при условии соблюдения определенных аксиом (коммутативности, ассоциативности, поглощения и идемпотентности). . Таким образом, они являются F -алгебрами сигнатуры P x P + P x P . Часто говорят, что теория решеток опирается как на теорию порядка, так и на универсальную алгебру.

Повторение [ править ]

Рассмотрим функтор $F:\mathrm {\bf {Set}} \to \mathrm {\bf {Set}}$ который отправляет набор $X$ к $1+X$ . Здесь, $\mathrm {\bf {Set}}$ обозначает категорию множеств, $+$ обозначает обычное копроизведение, заданное непересекающимся объединением , и $1$ является терминальным объектом (т.е. любым одноэлементным набором). Тогда набор $\mathbb {N}$ натуральных чисел вместе с функцией $[\mathrm {zero} ,\mathrm {succ} ]:1+\mathbb {N} \to \mathbb {N}$ – которое является копроизведением функций $\mathrm {zero} :1\mapsto 0$ и $\mathrm {succ} :n\mapsto n+1$ — является F -алгеброй.

Исходная F -алгебра [ править ]

Если категория F -алгебр для данного эндофунктора F имеет начальный объект , то она называется начальной алгеброй . Алгебра $(\mathbb {N} ,[\mathrm {zero} ,\mathrm {succ} ])$ в приведенном выше примере — исходная алгебра. Различные конечные структуры данных , используемые в программировании , такие как списки и деревья , могут быть получены как исходные алгебры конкретных эндофункторов.

Типы, определенные с использованием конструкции наименьшей неподвижной точки с функтором F, можно рассматривать как исходную F -алгебру при условии, что параметричность . для типа сохраняется ^[3]

См. также Универсальная алгебра .

Терминал F -коалгебра [ править ]

образом Двойственным аналогичная связь существует между понятиями наибольшей неподвижной точки и терминальной F -коалгебры. Их можно использовать для разрешения потенциально бесконечных объектов, сохраняя при этом строгое свойство нормализации . ^[3] В сильно нормализующем языке программирования Charity (т.е. на нем завершается каждая программа) коиндуктивные типы данных могут использоваться для достижения удивительных результатов, позволяя определять конструкции поиска для реализации таких «сильных» функций, как функция Аккермана . ^[4]

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

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

^ Вертикальные стрелки без меток на второй диаграмме должны быть уникальными, поскольку * является конечным.
^ Строго говоря, (i,id) и (id,i) помечены несовместимо с другими диаграммами, поскольку эти морфизмы сначала «диагонализируются».
^ Jump up to: Перейти обратно: ^а ^б Филип Вадлер: Рекурсивные типы бесплатно! Архивировано 16 октября 2007 г. в Университете Wayback Machine в Глазго, июнь 1990 г. Черновик.
^ Робин Кокетт : Благотворительные мысли ( ps. Архивировано 29 декабря 2020 г. на Wayback Machine и ps.gz. Архивировано 29 декабря 2020 г. на Wayback Machine )

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

Пирс, Бенджамин К. (1991). « F -Алгебры». Базовая теория категорий для специалистов по информатике . ISBN 0-262-66071-7 .
Барр, Майкл; Уэллс, Чарльз (1990). Теория категорий для информатики . Нью-Йорк: Прентис Холл. п. 355. ИСБН 0131204866 . OCLC 19126000 .

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

Категориальное программирование с индуктивными и коиндуктивными типами ( Архивировано 30 ноября 2020 г. в Wayback Machine ), Вармо Вене.
Филип Вадлер: Рекурсивные типы бесплатно! ( Архивировано 30 ноября 2020 г. в Wayback Machine ) Университет Глазго, июнь 1990 г. Черновик.
Алгебра и коалгебра ( Архивировано 27 апреля 2019 г. в Wayback Machine ) из CLiki
Б. Джейкобс, Дж. Руттен: Учебное пособие по (Co) алгебре и (Co) индукции. Бюллетень Европейской ассоциации теоретической информатики , том. 62, 1997 г., архивировано 12 февраля 2021 г. в Wayback Machine.
Понимание F-алгебр ( Архивировано 4 августа 2020 г. в Wayback Machine ), Бартош Милевски

[1] Вертикальные стрелки без меток на второй диаграмме должны быть уникальными, поскольку * является конечным.

[2] Строго говоря, (i,id) и (id,i) помечены несовместимо с другими диаграммами, поскольку эти морфизмы сначала «диагонализируются».

[free-rectypes-3] Jump up to: Перейти обратно: ^а ^б Филип Вадлер: Рекурсивные типы бесплатно! Архивировано 16 октября 2007 г. в Университете Wayback Machine в Глазго, июнь 1990 г. Черновик.

[4] Робин Кокетт : Благотворительные мысли ( ps. Архивировано 29 декабря 2020 г. на Wayback Machine и ps.gz. Архивировано 29 декабря 2020 г. на Wayback Machine )

[1]

[2]

[3]

[4]