recursively enumerable sets closed under concatenation

190 Views Asked by At

I'm trying to show the set of all recursively enumerable sets is closed under concatenation. I'm trying to use the definition of recursively enumerable sets to construct the argument. I believe that I must consider the Cartesian product $S_1\times S_2$ of two recursively enumerable sets $S_1$ and $S_2$. I then construct the function $f:S_1\times S_2\rightarrow \lbrace 1\rbrace\cup\lbrace\perp \rbrace$ (where $\perp$ is undefined) such that: $$f(x,y)=\begin{cases} 1 &\text{ if } x\in S_1 \text{ and } y\in S_2\\ \perp&\text{ otherwise} \end{cases}$$ Does the mere existence of this function $f$ show that $S_1S_2$ is recursively enumerable? I'm still new to these proofs, so any help would be appreciated.