World Library  
Flag as Inappropriate
Email this Article

F-algebra

Article Id: WHEBN0002168700
Reproduction Date:

Title: F-algebra  
Author: World Heritage Encyclopedia
Language: English
Subject: Initial algebra, Missing science topics/ExistingMathF, Catamorphism, Functional programming, WikiProject Mathematics/List of mathematics articles (F)
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

F-algebra

The commutative diagram, which defines a property required by morphisms of the original category, so that they can be morphisms of the newly defined category of F-algebras.

In mathematics, specifically in category theory, F-algebras generalize algebraic structure. Rewriting the algebraic laws in terms of morphisms eliminates all references to quantified elements from the axioms, and these algebraic laws may then be glued together in terms of a single functor F, the signature.

F-algebras can also be used to represent data structures used in programming, such as lists and trees.

The main related concepts are initial F-algebras which may serve to encapsulate the induction principle, and the dual construction F-coalgebras.

Contents

  • Definition 1
  • Examples 2
    • Groups 2.1
    • Algebraic structures 2.2
    • Lattice 2.3
    • Recurrence 2.4
  • Initial F-algebra 3
  • Terminal F-coalgebra 4
  • See also 5
  • Notes 6
  • Further reading 7
  • External links 8

Definition

If C is a category, and F: CC is an endofunctor of C, then an F-algebra is an object A of C together with a C-morphism F(A) → A.

A homomorphism from an F-algebra (A, α) to an F-algebra (B, β) is a C-morphism f: AB such that f o α = β o F(f), according to the following diagram:

Equipped with these morphisms, F-algebras constitute a category.

The dual construction are F-coalgebras, which are objects A* together with a morphism α* : A*F(A*).

Examples

Groups

Classically, a group is a set G with a binary operation m : G × GG, or m(x,y) = xy, satisfying three axioms: the associativity, the existence of an identity element, and the existence of an inverse for each element of the group.

To treat this in a categorical framework, we first define the identity and inverse as functions (morphisms of set in a category) e and i respectively. Let C be an arbitrary category with finite products and a terminal object *. The group G is a object in C. The identity function e sends each element in * to 1, the identity element in the group G. The inverse function i sends each element x in G to its inverse x−1, satisfying m(x−1, x) = m(x, x−1) = 1. Then a group G can be defined as a 4-tuple (G, m, e, i), which describes a monoid category with only one object G. Each morphism f in this monoid category has an inverse f−1 that satisfies f−1 o f = f o f−1 = Id.[1]

It is then possible to rewrite the axioms in terms of functions (note how the existential quantifiers disappear):

  • ∀ x∈G, ∀ y∈G, ∀ z∈G, m(m(x, y), z) = m(x, m(y, z)).
  • ∀ x∈G, m(e(*), x) = m(x, e(*)) = x.
  • ∀ x∈G, m(i(x), x) = m(x, i(x)) = e(*).

Then remove references to the elements of G (which will also remove universal quantifiers):

  • m∘(m, Id) = m(Id, m).
  • m∘(e, Id) = m∘(Id, e) = Id.
  • m∘(i, Id) = m∘(Id, i) = e.

Which is the same as claiming commutativity for the following diagrams:[2]

, , .

Now use the coproduct (the disjoint union of sets) to glue the three morphisms in one: α = e + i + m according to

\begin{matrix} \alpha : {1}+G+G \times G & \to & G \\ 1 & \mapsto & 1 \\ x & \mapsto & x^{-1} \\ (x,y) & \mapsto & x \cdot y \end{matrix}

This defines a group as a F-algebra where F is the functor F(G) = 1 + G + G × G.

Note 1: The above construction is used to define group objects over an arbitrary category with finite products and a terminal object *. When the category admits finite coproducts, the group objects are F-algebra. For example, finite groups are F-algebras in the category of finite sets and Lie groups are F-algebras in the category of smooth manifolds with smooth maps.

Algebraic structures

Going one step ahead of universal algebra, most algebraic structures are F-algebras. For example abelian groups are F-algebras for the same functor F(G) = 1 + G + GxG as for groups with an additional axiom for commutativity: mt = m, where t(x,y) = (y,x) is the transpose on GxG.

Monoids, which generalize groups in that a monoid element does not need to have an inverse, are F-algebras of signature F(M) = 1 + MxM. In the same vein, semigroups are F-algebras of signature F(S) = SxS

Rings, domains and fields are also F-algebras with a signature involving two laws +,•:RxR → R, an additive identity 0:1 → R, a multiplicative identity 1:1 → R, and an additive inverse for each element -:RR. As all these functions share the same codomain R they can be glued into a single signature function 1 + 1 + R + RxR + RxRR, with axioms to express associativity, distributivity,... This makes rings F-algebras on the category of sets with signature 1 + 1 + R + RxR + RxR.

Alternatively, we can look at the functor F(R) = 1 + RxR in the category of groups. In that context, the multiplication is a homorphism, meaning m(x+y, z) = m(x,z)+m(y,z) and m(x,y+z) = m(x,y)+m(x,z), which are precisely the distributivity conditions. Therefore, rings are F-algebras of signature 1 + RxR over the category of groups which satisfies two axioms (associativity and inverse for the multiplication).

When we come to vector spaces and modules, the signature functor includes a scalar multiplication kxEE, and the signature F(E) = 1 + E + kxE is parametrized by k over the category of fields, or rings.

Algebras can be viewed as F-algebras of signature 1 + 1 + A + AxA + AxA + kxE over the category of sets, of signature 1 + AxA over the category of modules (a module with an internal multiplication), and of signature kxE over the category of rings (a ring with a scalar multiplication).

Lattice

Not all mathematical structures are F-algebras. For example, a poset P may be defined in categorical terms with a morphism s:P → Ω, on a subobject classifier (Ω = {0,1} in the category of set and s(x,y)=1 precisely when xy). The axioms restricting the morphism s to define a poset can be rewriten in terms of morphisms. However, as the codomain of s is Ω and not P, it is not an F-algebra.

However, lattices in which every two elements have a supremum and an infimum, and in particular total orders in which every two elements are comparable, are F-algebras. This is because they can equivalently be defined in terms of the algebraic operations: xy = inf(x,y) and xy = sup(x,y), subject to certain axioms (commutativity, associativity, absorption and idempotency). Thus they are F-algebras of signature PxP + PxP. It is often said that lattice theory draws on both order theory and universal algebra.

Recurrence

Consider the functor F: \mathbf{Set} \to\mathbf{Set} that sends a set X to 1+X. Here, Set denotes the category of sets, + denotes the usual coproduct given by disjoint union, and 1 is a terminal object (i.e. any singleton set). Then the set \mathbb{N} of natural numbers together with the function [\mathrm{zero},\mathrm{succ}] : 1+\mathbb{N} \to \mathbb{N}, which is the coproduct of the functions \mathrm{zero} : 1 \to \mathbb{N} (whose image is 0) and \mathrm{succ} : \mathbb{N} \to \mathbb{N} (which sends an integer n to n+1), is an F-algebra.

Initial F-algebra

If the category of F-algebras for a given endofunctor F has an initial object, it is called an initial algebra. The algebra (\mathbb{N}, [\mathrm{zero},\mathrm{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.

Types defined by using least fixed point construct with functor F can be regarded as an initial F-algebra, provided that parametricity holds for the type.[3]

See also Universal algebra.

Terminal F-coalgebra

In a dual way, similar relationship exists between notions of greatest fixed point and terminal F-coalgebra, these can be used for allowing potentially infinite objects while maintaining strong normalization property.[3] In the strongly normalizing Charity programming language (i.e. each program terminates in it), coinductive data types can be used achieving surprising results, e.g. defining lookup constructs to implement such “strong” functions like the Ackermann function.[4]

See also

Notes

  1. ^ Section I.2, III.6 in Lane, S. Mac (1988). Categories for the working mathematician (4th corr. print. ed.). New York: Springer-Verlag.  
  2. ^ The vertical arrows without labels in the third diagram must be unique since * is terminal.
  3. ^ a b Philip Wadler: Recursive types for free! University of Glasgow, June 1990. Draft.
  4. ^ Robin Cockett: Charitable Thoughts (ps and ps.gz)

Further reading

  •  

External links

  • Categorical programming with inductive and coinductive types by Varmo Vene
  • Philip Wadler: Recursive types for free! University of Glasgow, June 1990. Draft.
  • Algebra and coalgebra from CLiki
  • B. Jacobs, J.Rutten: A Tutorial on (Co) Algebras and (Co) Induction. Bulletin of the European Association for Theoretical Computer Science, vol. 62, 1997
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.