0
$\begingroup$

Let $U$ be a set of finite sequences like $\{1,1\cdot1,1\cdot2,\dots,1\cdot 2\cdot3,\dots\}$, i.e. there is no $0$ element in any sequence and all sequences start from $1$.

Can this set be defined as free monoid? (is this set a free monoid?)

I have tried the following:

Let $\mathcal{N}_{>0}$ be the set of positive integers. Let $U$ be the free monoid with identity $0$, generated by $\mathcal{N}_{>0}$ with operation $\cdot$

but after this discussion (see comments below the question) I am confused, is it properly or not?

$\endgroup$
  • $\begingroup$ is the finite sequence $2\cdot 1$ also in your list? $\endgroup$ – Harry Richman Jul 27 '17 at 22:18
  • $\begingroup$ @HarryRichman thank you, I have edited my question. No, $2\cdot 1$ is not in this list. $\endgroup$ – Andremoniy Jul 27 '17 at 22:25
  • $\begingroup$ Is the empty sequence an element of $U$? If not, then $U$ is not even a monoid, assuming the operation is supposed to be concatenation. $\endgroup$ – Eric Wofsey Jul 27 '17 at 22:32
  • $\begingroup$ @EricWofsey yes, I was thinking about that. Let us assume that it is: the empty sequence is part of $U$. $\endgroup$ – Andremoniy Jul 27 '17 at 22:34
1
$\begingroup$

Let $S$ be the set of (nonempty) sequences that start with $1$ and then all the following terms are greater than $1$. Then $U$ is freely generated by $S$ as a monoid. Indeed, every element $x\in U$ can be written as a composition of a sequence elements of $S$ in a unique way: just break $x$ up into subsequences of consecutive terms, each one starting with a $1$ and going until either you reach the next $1$ in $x$ or the end of $x$.

$\endgroup$
  • $\begingroup$ Thank you, but I am confused with this definition. Is it rigorous to define $S$ in that way as in just a verbal form "...sequence that start..."? Also, the comparison operator should be formally defined as well? And what operation is used for generation the monoid $U$? $\endgroup$ – Andremoniy Jul 27 '17 at 22:45
  • $\begingroup$ I am sorry, I am not an algebraist, but I am looking for the formally proper definition of this thing. $\endgroup$ – Andremoniy Jul 27 '17 at 22:46
1
$\begingroup$

More generally, consider an alphabet $A$ (in your case the set of positive integers). The free monoid on $A$ (usually denoted $A^*$) is the set of words on $A$, equipped with the concatenation product. For instance, if $A = \{a, b, c\}$ the product of the words $abac$ and $caba$ is the word $abaccaba$. The empty word is the neutral element of the free monoid $A^*$.

Now, let $a$ be an element of $A$ (in your case $a = 1$) and let $B = A - \{a\}$. Then the set $S = aB^*$ is a suffix code, which means that no word of $S$ is a suffix of another element of $S$. In this case, the submonoid of $A^*$ generated by $S$ is a free monoid.

$\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.