[Solved]: Intuition behind F-algebra

Problem Detail: 

I looked at here for getting an intuition about F-algebra, but I am still left with some questions.

Suppose I have a group signature as $\Sigma= (* : X \times X \rightarrow X, \thicksim: X \rightarrow X , e : \rightarrow X)$, with the following axioms in a unuiversal algebraic way:

1. $x ∗ (y ∗ z) = (x ∗ y) ∗ z$ (Associativity)
2. $e ∗ x = x = x ∗ e$ (Identity element)
3. $x ∗ (\thicksim x) = e = (\thicksim x) ∗ x$ (Inverse element)

A model of the above signature is an assignment of two functions to its function symbols, and a constant to its constant symbol, such that the above three laws hold.

My Question:

How the above structure with three axioms, can be encoded (represented) in an F-algebraic notion:

1) What is my endo-Functor F and why is that?

2) How these three laws are represented in F-algebra?

p.s.: I would appreciate if anybody refer to a textbook, or a document that I can read more examples to further understand the F-algebra concept.

Asked By : qartal

Answered By : Dave Clarke

Given a functor $F:Set\to Set$, an $F$-algebra is just a function $f:F(X)\to X$, where $X$ is some set known as the carrier set.

In your example, $X$ is the set of elements of some group.

The endo functor $F$ in this case is $$F(X)=X\times X+X+1.$$ Think of this as representing the three different operators. The first component of the sum, $X\times X$, captures the arguments of $*:X\times X\to X$. The second component, $X$, captures the arguments of $∼:X\to X$. The third component, $1$, captures the constant $e:1\to X$ – the $1$ represents a set with one element, thus the function $e$ picks out a single element of $X$.

To understand why these components are summed together, recall that there is an isomorphism $(A\to X) \times (B \to X) \equiv (A+B)\to X$ (where $+$ is disjoint union of sets).

The three functions above can be seen as an element of the set given by the product of their signatures: $$f=(*,∼,e):(X\times X \to X)\times (X\to X) \times (1\to X).$$ Using the isomorphism, we can find an equivalent function $$f':(X\times X + X + 1)\to X,$$ which is $F(X)\to X$. Thus, an $F$-algebra.

To capture the notion of a group needs additional equations (the expected ones), which falls outside of the basic definition of an $F$-algebra, but are added in a trivial way.

Googling "Universal Algebra" will find you some online textbooks/notes. I'm not sure which ones are good.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42905

3.2K people like this

 Download Related Notes/Documents