В математике , в частности , в теории категорий , F - алгебры обобщают понятие алгебраической структуры . Переписывание алгебраических законов в терминах морфизмов исключает все ссылки на квантованные элементы из аксиом, и эти алгебраические законы затем могут быть склеены в терминах единственного функтора F - сигнатуры .
F -алгебры также могут использоваться для представления структур данных, используемых в программировании , таких как списки и деревья .
Основными связанными понятиями являются исходные F -алгебры, которые могут служить для инкапсуляции принципа индукции, и F -коалгебры двойственной конструкции .
Определение
Если С является категория и F : C → C является endofunctor из С , тогда Р - алгебра является кортежем ( , α), где является объектом из C и α представляет собой С - морфизм Р ( ) → . Объект A называется носителем алгебры. Когда это допустимо из контекста, алгебры часто упоминаются только их носителем, а не кортежем.
Гомоморфизм из F - алгебры ( A , & alpha ; ) к F - алгебры ( B , & beta ; ) является С -морфизмом е : → B такое , что F ∘ α = β ∘ F ( F ), в соответствии со следующей коммутативных диаграмма :
Обладая этими морфизмами, F -алгебры образуют категорию.
Двойственная конструкция - это F -коалгебры, которые являются объектами A * вместе с морфизмом α * : A * → F ( A * ).
Примеры
Группы
Классически группа в множестве G с группой законов m : G x G → G , где m ( x , y ) = x • y , удовлетворяющая трем аксиомам: существование единичного элемента, существование обратного для каждого элемент группы и ассоциативность.
Чтобы поместить это в категориальную структуру, сначала определите тождество и обратное как функции (морфизмы множества G ) по формуле e : 1 → G с e (*) = 1 и i : G → G с i ( x ) = x −1 . Здесь 1 обозначает набор с одним элементом 1 = {*}, что позволяет определить элементы x∈ G с морфизмами 1 → G .
Тогда можно записать аксиомы группы в терминах функций (обратите внимание, что квантор существования отсутствует):
- X∈ G , ∀ y∈ G , ∀ z∈ G , m ( m ( x , y ), z ) = m ( x , m ( y , z )),
- ∀ x∈ G , m ( e (*), x ) = m ( x , e (*)) = x ,
- ∀ x∈ G , m ( i (x), x ) = m ( x , i (x)) = e (*).
Затем удалите ссылки на элементы G (что также удалит универсальные кванторы):
- m ∘ ( m , Id ) = m ∘ ( Id , m ),
- m ∘ ( e , Id ) = m ∘ ( Id , e ) = Id ,
- m ∘ ( i , Id ) = m ∘ ( Id , i ) = e .
Это то же самое, что утверждать коммутативность следующих диаграмм: [1]
Теперь используйте копроизведение ( несвязное объединение множеств), чтобы склеить три морфизма в один: α = e + i + m согласно
Это определяет группу как F - алгебры , где Р является функтор F ( G ) = 1 + G + G × G .
Вышеупомянутая конструкция используется для определения групповых объектов по произвольной категории с конечными продуктами и конечным объектом *. Когда категория допускает конечные копроизведения , объекты группы являются F -алгебрами. Например, конечные группы являются F -алгебрами в категории конечных множеств, а группы Ли - это F -алгебры в категории гладких многообразий с гладкими отображениями .
Алгебраические структуры
На шаг впереди универсальной алгебры , большинство алгебраических структур являются F -алгебрами. Например, абелевы группы являются F -алгебрами для того же функтора F ( G ) = 1 + G + G × G, что и для групп, с дополнительной аксиомой коммутативности: m ∘ t = m , где t ( x , y ) = ( у , х ) транспонированная на G х G .
Моноиды являются F -алгебр сигнатуры F ( M ) = 1 + М × М . Точно так же полугруппы - это 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 -алгебрами сигнатуры Р х Р + Р х Р . Часто говорят, что теория решеток опирается как на теорию порядка, так и на универсальную алгебру.
Повторение
Рассмотрим функтор который отправляет набор к . Здесь, обозначает категорию множеств, обозначает обычное копроизведение, заданное дизъюнктным объединением , аявляется конечным объектом (т. е. любым одиночным набором). Тогда набориз натуральных чисел вместе с функцией- который является копродуктом функций а также - F -алгебра.
Начальная F -алгебра
Если категория F -алгебр для данного эндофунктора F имеет начальный объект , она называется начальной алгеброй . Алгебрав приведенном выше примере - это начальная алгебра. Различные конечные структуры данных, используемые в программировании , такие как списки и деревья , могут быть получены как начальные алгебры конкретных эндофункторов.
Типы, определенные с помощью конструкции с наименьшей фиксированной точкой с функтором F, можно рассматривать как исходную F -алгебру при условии, что для типа сохраняется параметричность . [2]
См. Также Универсальная алгебра .
Терминал F -коалгебра
В двойном образом, аналогичное соотношение существует между понятиями наибольшей неподвижной точкой и терминалом F -коалгебры. Их можно использовать для разрешения потенциально бесконечных объектов при сохранении строгого свойства нормализации . [2] В строго нормализующем языке программирования Charity (т.е. каждая программа на нем завершается) могут использоваться коиндуктивные типы данных для достижения удивительных результатов, позволяя определять конструкции поиска для реализации таких «сильных» функций, как функция Аккермана . [3]
Смотрите также
- Алгебры для монады
- Алгебраический тип данных
- Катаморфизм
- Dialgebra
Заметки
- ^ Вертикальные стрелки без меток на третьей диаграмме должны быть уникальными, поскольку * является терминальным.
- ^ a b Филип Вадлер: Рекурсивные типы бесплатно! Архивировано 2007-10-16 в Wayback Machine университета Глазго, июнь 1990 г. Проект.
- ^ Робин Кокетт: Благотворительные мысли ( ps, заархивировано 2020-12-29 в Wayback Machine и ps.gz, заархивировано 2020-12-29 в Wayback Machine )
Рекомендации
- Пирс, Бенджамин С. (1991). « Ф- Алгебры». Основная теория категорий для компьютерных ученых . ISBN 0-262-66071-7.
- Барр, Майкл; Уэллс, Чарльз (1990). Теория категорий для информатики . Нью-Йорк: Прентис-Холл. п. 355. ISBN 0131204866. OCLC 19126000 .
Внешние ссылки
- Категориальное программирование с индуктивным и коиндуктивным типами ( Архивировано 30 ноября 2020 г. в Wayback Machine ) Вармо Вен
- Филип Вадлер: Рекурсивные типы бесплатно! ( Архивировано 30 ноября 2020 г. в Wayback Machine ) Университет Глазго, июнь 1990 г. Черновик.
- Алгебра и коалгебра ( Архивировано 27 апреля 2019 г. в Wayback Machine ) от CLiki
- Б. Джейкобс, Дж. Руттен: Учебное пособие по (Ко) алгебрам и (Ко) индукции. Бюллетень Европейской ассоциации теоретической информатики , т. 62, 1997, Архивировано 12 февраля 2021 года в Wayback Machine.
- Понимание F-алгебр ( Архивировано 4 августа 2020 г. в Wayback Machine ) Бартош Милевски