Введение

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

Алгебраические структуры

На шаг впереди универсальной алгебры, большинство алгебраических структур являются F-алгебрами. Например, абелевы группы являются F-алгебрами для того же функтора F(G) = 1 + G + G×G, что и для групп, с дополнительной аксиомой коммутативности: m∘t = m, где t(x,y) = (y,x) – транспозиция на G×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 над категорией модулей (модуль с внутренним умножением) и с сигнатурой k×A над категорией колец (кольцо со скалярным умножением), когда они ассоциативны и унитарны.

Решетка

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

Повторность

Рассмотрим функтор, который отображает множество X в множество X × {*}. Здесь Set обозначает категорию множеств, ⊕ обозначает обычный сопродукт, заданный дизъюнктным объединением, а {*} — терминальный объект (то есть любое множество, состоящее из одного элемента). Тогда множество натуральных чисел вместе с функцией f, которое является сопродуктом функций succ и id, является F-алгеброй.

Начальная F-алгебра

Если категория F-алгебр для данного эндофунктора F имеет начальный объект, она называется начальной алгеброй. Алгебра в приведенном выше примере является начальной алгеброй. Различные конечные структуры данных, используемые в программировании, такие как списки и деревья, могут быть получены как начальные алгебры конкретных эндофункторов. Типы, определенные с использованием конструкции наименьшей неподвижной точки с функтором F, могут рассматриваться как начальная F-алгебра, при условии, что для данного типа выполняется условие параметричности. См. также Универсальную алгебру.

Терминальная F-алгебра

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