F-алгебра

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

F-алгеброй эндофунктора

F : \mathcal{C}\longrightarrow \mathcal{C}

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

\alpha : FA \longrightarrow A.

Таким образом, F-алгебра — это пара (A, \alpha).

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

f : A \longrightarrow B,

для которого верно

f \circ \alpha = \beta \circ Ff:

Commutative diagram defining F-algebra.png

Для любого заданного эндофунктора F можно рассмотреть категорию, объектами которой являются F-алгебры, а морфизмами — гомоморфизмы между F-алгебрами.

Примеры[править | править вики-текст]

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

Литература[править | править вики-текст]