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:
- $x ∗ (y ∗ z) = (x ∗ y) ∗ z$ (Associativity)
- $e ∗ x = x = x ∗ e$ (Identity element)
- $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:Setto 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)=Xtimes X+X+1.$$ Think of this as representing the three different operators. The first component of the sum, $Xtimes X$, captures the arguments of $*:Xtimes Xto X$. The second component, $X$, captures the arguments of $∼:Xto X$. The third component, $1$, captures the constant $e:1to 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 $(Ato 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):(Xtimes X to X)times (Xto X) times (1to X).$$ Using the isomorphism, we can find an equivalent function $$f’:(Xtimes 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
