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\)-алгеброй.

Начальная алгебра[править]

Icons-mini-icon 2main.png Основная статья: Начальная алгебра

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

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