Universal Algebra & Free Algebra

110 Views Asked by At

Q: Let $f$ be the embedding (injective homomorphism) of $A$ into $Str(A): a \in A$ is sent to the corresponding string of length $1$.

Prove that $(f; \langle Str(A), \hat{}, ()\rangle )$ is the free monoid where $\hat{} $ is an associative binary operation with identity $()$ on $A$.

Notes:

i) Question is in the setting of Universal Algebra.

ii) $\hat{}$ is concatenation of string, i.e. attach two strings together.

iii) I have already shown $\langle Str(A), \hat{}, () \rangle$ is a monoid, only need to show $(f; \langle Str(A), \hat{}, ()\rangle )$ is a free algebra.

1

There are 1 best solutions below

2
On

You state you have shown it is a monoid,

So you have shown $\hat{}$ is associative and that the structure has identity which you denote as $()$, seemingly the empty string

This is related to Kleene star

Appears all that is left is to show that the elements of $A$ under $f$ are free generators for $(A \text{ under } f)^*$ (the Kleene star of $A$ under $f$ and since $f$ embeds $A$ into $Str(A)$, we have $f(a) = a$ which is the string of length 1 as you say, we can take $A = \{a_1,...a_n\} =\{f(a_1), \ldots, f(a_n)\} $ as your free-generators.

Perhaps $A$ is not finite by assumption which is fine, I just use a finite set to be illustrative in my explanation.