Álgebra inicial

En matemáticas , un álgebra inicial es un objeto inicial en la categoría de $F$ - álgebras para un endofunctor $F$ dado . Esta inicialidad proporciona un marco general para la inducción y la recursión .

Considere el endofunctor $F : Conjunto \to Conjunto$ que envía $X$ a $1 + X$ , donde $1 es el$ conjunto de un punto ( singleton ) , el objeto terminal en la categoría. Un álgebra para este endofunctor es un conjunto $X$ (llamado portador del álgebra) junto con una función $f$ $: (1 +$ $X$ $) \to$ $X$ . Definir tal función equivale a definir un punto y una función $X$ $\to$ $X.$ Definir ${\ estilo de visualización x \ en X}$

Entonces el conjunto $N$ de números naturales junto con la función $[cero,succ]: 1 + N \to N$ $es un F$ -álgebra inicial . La inicialidad (la propiedad universal para este caso) no es difícil de establecer; el homomorfismo único a un $F$ - álgebra arbitraria $(A, [e, f])$ , para $e : 1 \to A$ un elemento de $A$ y $f : A \to A$ una función en $A$ , es la función que envía el número natural $n$ a $f n (e)$ , es decir, $f (f (\dots(f (e))\dots))$ , la aplicación de $n veces de$ $f$ a $e$ .

El conjunto de los números naturales es el portador de un álgebra inicial para este functor: el punto es cero y la función es la función sucesora .

Para un segundo ejemplo, considere el endofunctor $1 + N \times (-)$ en la categoría de conjuntos, donde $N$ es el conjunto de números naturales. Un álgebra para este endofuntor es un conjunto $X$ junto con una función 1 $+ N \times X \to X.$ Para definir tal función, necesitamos un punto y una función $N$ $\times$ $X$ $\to$ $X.$ El conjunto de listas finitas de números naturales es un álgebra inicial para este funtor. El punto es la lista vacía, y la función es contras . ${\ estilo de visualización x \ en X}$ , tomando un número y una lista finita, y devolviendo una nueva lista finita con el número al principio.

En categorías con coproductos binarios , las definiciones que se acaban de dar son equivalentes a las definiciones habituales de un objeto de número natural y un objeto de lista , respectivamente.