F-алгебра

В математике и особенно в теории категорий F F -алгеброй для эндофунктора:

F : C C F : \mathbf{C} \longrightarrow \mathbf{C}

называется объект A A из C \mathbf{C} совместно с C \mathbf{C} -морфизмом:

α : F A A \alpha : FA \longrightarrow A .

В этом смысле F-алгебры являются дуальными к F-коалгебрам.

Гомоморфизм из F F -алгебры ( A , α ) (A, \alpha) в F F -алгебру ( B , β ) (B, \beta) является морфизмом:

f : A B f:A\longrightarrow B

в C \mathbf{C} таким, что:

f α = β F f f \circ \alpha = \beta \circ Ff .

Таким образом сами по себе F F -алгебры представляют собой категорию.

ПримерПравить

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

Начальная алгебраПравить

  Основная статья: Начальная алгебра

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

См. такжеПравить