1
$\begingroup$

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$. Then I 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.

$\endgroup$
1
$\begingroup$

What you need to show is that given an algorithm that enumerates a (possibly finite) sequence $a_1,a_2,a_3,\ldots$, and another algorithm that enumerates a (possibly finite) sequence $b_1,b_2,b_3,\ldots$, then you can come up with another algorithm which enumerates all words of the form $a_i b_j$.

The simplest approach is to use the same idea that Cantor used to prove that the rationals are equinumerous with the integers, namely to come up with an algorithm that enumerates $a_i b_j$ in the following order: $$ a_1 b_1, a_1 b_2, a_2 b_1, a_1 b_3, a_2 b_2, a_3 b_1, \ldots $$ I'll let you to fill in the details.

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