F-algebra

Encyclopedia : F : FA : FAL : F-algebra

---

In mathematics, specifically in category theory, an [F]-algebra for an endofunctor

[F : \mathbf\longrightarrow \mathbf]

is an object [A] of [\mathbf] together with a [\mathbf]-morphism

[\alpha : FA \longrightarrow A].

In this sense F-algebras are dual to F-coalgebras.

A homomorphism from [F]-algebra [(A, \alpha)] to [F]-algebra [(B, \beta)] is a morphism

[f:A\longrightarrow B]

in [\mathbf] such that

[ f\circ \alpha = \beta \circ Ff].

Thus the [F]-algebras constitute a category.

Example

Consider the functor [F: \mathbf \longrightarrow \mathbf] that sends [X] to [1+X]. Then the set [N] together with the function [[zero,succ] : 1+N \longrightarrow N], where [N] is the set of natural numbers with [zero : 1 \longrightarrow N] and [succ : N \longrightarrow N], is an [F]-algebra.

Initial algebra

If the category of [F]-algebras for a given endofunctor F has an initial object, it is called an initial algebra. The algebra [(N, [zero,succ])] in the above example is an initial algebra. Various finite data structures used in programming, such as lists and trees, can be obtained as initial algebras of specific endofunctors.

See also Universal algebra.

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?