# What is an example of set $A$, that is decidable if $AA$, but which is not decidable if it is $A$ alone

I encountered a question to give an example of a set $A$ that is not decidable as $A$, but which becomes decidable if it is concatenated with itself, i.e. $AA$.

In case a set $A$ is decidable, then it is easy to see that $AA$ is also decidable, since a $TM$ that decides $A$ can be modified to also recognize $AA$... But I am having a hard time to look for examples given its converse.

You can pick your favourite undecidable language $L$ and build $A$ in this way:

$A = \{ 1 \} \cup \{ 2n \} \cup \{ 2n + 1 \mid n \in L \}$

$A$ contains $1$ and all even numbers, but it also contains ... (I let you try to complete the proof)

Note that I assume that $AA = \{ xy \mid x, y \in A\}$; because if you define $AA=\{ xx\mid x \in A\}$ then it doesn't exist an undecidable language $A$ such that $AA$ is decidable (again I let you try to prove it :-).

• Thanks, but in case $x={1}$ and $y=2n+1|n \in L$, wouldn't $xy$ be undecidable because of $y$ being an odd number 'inside' the undecidable part of $A$? Commented Oct 2, 2017 at 8:52
• @LinkL: no because in $AA$ you find: the number 2: $x=1 \in A; y=1 \in A$; all odd numbers greater than 1: $x=1 \in A; y=2n \in A$ and all even numbers greater than 2: $x=2\cdot 1 \in A, y = 2n \in A$ ... so $AA = \{ n > 1 \}$ which is clearly decidable.
– Vor
Commented Oct 2, 2017 at 10:24
• Oh right I get it now Commented Oct 2, 2017 at 10:25
• Accidentally the same construction was used answering "Proving that non-regular languages are closed under concatenation", although the question was much more restrictive. Commented Oct 2, 2017 at 10:28