F-алгебра

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

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

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

$\alpha : FA \longrightarrow A$.

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

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

$f:A\longrightarrow B$

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

$f \circ \alpha = \beta \circ Ff$.

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

Пример

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

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

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

См. также

• Универсальная алгебра