Which operator $\oplus$ turns a function $f$ into a monoid homomorphism from $(L,*,[])$ to $(\mathbb{R},\oplus,\epsilon)$

abstract-algebramonoidsemigroups

This question is inspired by this question. I do not have a strong background in abstract algebra, so this might be trivial or pointless.

Let $L$ be the set of all lists of finite length and denote $*$ as the list concatenation. Denote $[]\in L$ as the empty list (length $0$). Then $(L,*,[])$ is a monoid under $*$ and with identity $[]$ (because $x*y=y*x$ and $x*[]=[]*x$, $\forall x,y \in L$).

Let us define the operator $[l,i]$ with $l \in L$ and $i\in \{1,\cdots, |l|\}$ which returns the $i$th element from $l$. We simply write $[i]$ if no confusion arises and $l$ is clear from the given context.

Let $(\mathbb{R}, \oplus, \epsilon)$ be a monoid with set $\mathbb{R}$ under some binary operation $\oplus$ and identity element $\epsilon$. By definition:

  • $\forall a,b,c \in \mathbb{R}: (a\oplus b) \oplus c= a \oplus (b\oplus c)$
  • $\forall a \in \mathbb{R}: \epsilon \oplus a = a \oplus \epsilon=a$

We define

$$f:L \to \mathbb{R}:[x_1,\cdots,x_n] \mapsto
\left\{\begin{array}{ll} [1]-\sum_{i=2}^n [i], & n \geq 2 \\
[1], & \text{if } n=1 \\
0 , & \text{otherwise} \end{array} \right. $$

Question 1: Which operator $\oplus$ turns $f$ into a monoid homomorphism from $(L,*,[])$ to $(\mathbb{R},\oplus,\epsilon)$? I have a strong feeling that this is wrong, but how would we disprove it? Moreover, are there any general ways to define monoids in order for a given function to be a homomorphism between them?

The following must hold

  • $\forall x,y \in L: f(x * y)=f(x) \oplus f(y)$
  • $f([]) \mapsto \epsilon$

The map $f$ already yields to $f([])=0$, hence $\epsilon=0$. Now, we are limited for the choice of $\oplus$, e.g. $(\mathbb{R}, \cdot)$ is not possible anymore. $(\mathbb{R},+,0)$ forms a monoid, however $f(x * y)=f(x)+f(y)$ is obviously wrong.

Question 2: If we omit the possibility of lists of length zero, and thus removing the identity element from $L$, then $(L,*)$ would form a semigroup. Could we define $\oplus$ such that $(\mathbb{R},\oplus)$ form a semigroup and $f$ (omitting the $n=0$ case of course) is a homomorphism between two semigroups?

Best Answer

This may be a misunderstanding of the notation, but it seems there is no structure on $\mathbb{R}$ making $f$ a monoid homomorphism.

Since $f([a, b]) = a-b$, the only viable $\oplus$ would be the usual subtraction on $\mathbb{R}$, but this is not associative.

Related Question