Fdtxjr

Starting with an arbitrary class of sets $Gamma$, can you generate a free semigroup $Gamma^*$ over $Gamma$ with the group operation of concatenation ($frown$)?

The goal here is to codify a formal language in terms of set theory.

The difficulty is in coming up with a set-theoretic operation that corresponds to concatenation such that it makes every new element resulting from concatenation unique, and is associative.

Given $a,b in Gamma$, the first thought would be to represent $a frown bfrown c$ as a 3-tuple $<a,b,c>$. I know I can define tuples set-theoretically via $<a,b>:=a,a,b$ but this will violate associativity in concatenation:

$$a frown(b frown c)=<a,<b,c>> ne <<a,b>,c>=(a frown b)frown c$$

I have tried other variants but I haven't been able to come up with a set-theoretic description of concatenation that respects associativity, any ideas?

EDIT: This is a related question: https://mathoverflow.net/questions/12190/set-theoretic-foundations-for-formal-language-theory

unfortunately none of the answers provide an explicit definition of concatenation in set-theoretic terms.

There are a couple ways to address this. Equivalence classes give the most algebraically natural treatment:

• Taking the naive definition of concatenation-as-ordered-pair, we get the free magma $hatGamma$ on $Gamma$.



• 
  

  Now the free semigroup will just be the free magma modulo the "associativity relation" - basically, we just need to whip up the binary relation $sim$ describing when two elements of $hatGamma$ "should be" equal. It's a bit messy to describe $sim$ "explicitly" - this winds up being an inductive construction - but we can also define it as the smallest equivalence relation on $hatGamma$ such that (or, the intersection of all equivalence relations on $hatGamma$ such that) for all $a,b,c,dinhatGamma$ we have:

  
  
  

  • $asim b$ and $csim d$ implies $langle a,cranglesimlangle b,drangle$, and

  
  

  • $langle a,langle b,crangleranglesim langlelangle a,brangle, crangle$.

  
  

It's now easy to define the semigroup operation $cdot$ as $$[a]_simcdot[b]_sim=[langle a,brangle_sim$$ (after, of course, checking that this is in fact well-defined). Or if you want to be really pedantic about it, given $sim$-classes $E,F$, their product $Ecdot F$ is the unique $sim$-class $G$ such that there are elements $ain E$ and $bin F$ such that $langle a,branglein G$.

Another approach, less algebraically natural but perhaps more concrete, is via tuples as functions.

Specifically:

• An element of $Gamma^*$ will be a function $f$ such that $(1)$ the domain of $f$ is some natural number $n$, and $(2)$ the range of $f$ is $subseteqGamma$. A function with domain $n$ is "morally" an $n$-tuple.



• 
  

  We can now define a fully associative version of concatenation using arithmetic. Specifically, suppose $f,gin Gamma^*$ with domains $m,n$ respectively. We let $f^smallfrown g$ be the function $h$ given by: $dom(h)=m+n$, for $k<m$ we have $h(k)=f(k)$, and for $mle k<n$ we have $h(k)=g(k-m)$.

  
  
  
  • So for example if $dom(f)=2, dom(g)=1$, $f$ sends $0$ to $0$ and $1$ to $1$, and $g$ sends $0$ to $3$, then $f^smallfrown g$ has domain $3$, sends $0$ to $0$, sends $1$ to $1$, and sends $2$ to $3$.
  
  

(Remember that in set theory a natural number is just a finite ordinal, and in particular is just the set of smaller natural number; so e.g. "$dom(f)=5$" makes perfect sense.)

The only thing this relies on is arithmetic of finite ordinals, which is straightforward to develop.