2
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the above, F is defined to send object $X$ in Category set to $X\times X+X+1$ object, that is to say $F(X)=X\times X+X+1.$ How F is defined for morphisms? (i.e., what is F(g) where g is a function from X to Y?) $\endgroup$ – qartal May 23 '15 at 22:55
  • $\begingroup$ The function $F(g)$ does one of the following things: if the input is a pair $(a,b) : X\times X$, it gives result $(g(a),g(b))$, if the input is just $a:X$, it results in $g(a)$, and if the input is $\star:1$, the result is $\star$. $\endgroup$ – Dave Clarke May 24 '15 at 10:46
  • $\begingroup$ You answered another question (that is to say, what is the internal functionality of $F(X) \rightarrow X$ arrow?). My question was about definition of F functor itself: In a functor definition, we define Object mappings as well as morphism mappings. For functor F we have an object mapping definition, but we miss morphism mapping definition. In other words, for each morphism g in Set category what is F(g)? maybe this is very trivial to define. $\endgroup$ – qartal May 24 '15 at 16:03
  • $\begingroup$ Actually, I defined what you asked me to define. $\endgroup$ – Dave Clarke May 24 '15 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.