0
$\begingroup$

In the free monoid over a set the unique sequence of zero elements, often called the empty string is the identity element.

Is the empty string an element of the underlying set of the free monoid?

In the free monoid the elements of the underlying set are finite sequences of letters from an alphabet: $ \{ab,aab,a,b...\} $ I'm just wondering how exactly is the empty sequence represented in this underlying set?

Take a look at Wikipedia Kleene star:

If V is a set of symbols or characters, then $V*$ is the set of all strings over symbols in $V$, including the empty string $\epsilon$.

$\endgroup$
2
$\begingroup$

A monoid is a tuple $(M,m,e)$ where $M$ is a set, $m:M\times M \to M$ is an associative law and $e\in M$ is a neutral element for $m$.

By definition, the underlying set of $(M,m,e)$ is $M$: therefore $e\in M$ means that $e$ is an element of the underlying set.

In the free monoid generated by $A$, the neutral element is the empty string, so the empty string does belong to the underlying set of the free monoid, but there's nothing special about the free monoid here.

$\endgroup$
3
  • $\begingroup$ In the free monoid the elements of the underlying set are finite sequences of letters from an alphabet: ${ab, aab, a, b}$ I'm just wondering how exactly is the empty sequence represented in this underlying set. $\endgroup$ – Roland Nov 20 '18 at 11:08
  • 2
    $\begingroup$ @Roland As the empty string. You can name it whatever you like. $\endgroup$ – Tobias Kildetoft Nov 20 '18 at 11:17
  • 3
    $\begingroup$ @Roland Said another way, "finite" includes length 0! $\endgroup$ – Kevin Arlin Nov 20 '18 at 17:21
3
$\begingroup$

Yes, it is.

If $M$ is the monoid free over set $S$ then you can identify the elements of $M$ with functions $n\to S$ where $n$ is a nonnegative integer with $n:=\{0,\dots,n-1\}$.

Then $0$ is the empty set and the empty string is the empty function $0=\varnothing\to S$.

The empty function is also the empty set, so the empty string corresponds with $\varnothing$.

If e.g. we are dealing with function $2\to S$ of the form $\{(0,a),(1,b)\}$ then this function corresponds with string "ab".

$\endgroup$

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.