Enumerable and not enumerable sets

Question

I am i bit stuck on this problem. Is it possible that sets A and B are not enumerable, but set $$A \cdot B =\{x \cdot y \mid x \in A, y \in B\}$$ is enumerable? Defenition of emumerable set so, set is enumerable if there is an algorithm, that may enumerate it. Or, set is enumerable if there is exist semi-characteristic function which equals 1 if x in A, or not define if x not in A. Thanks in advance

Answer 1

If $A$ and $B$ are subsets of the real numbers and $.$ means the product, the answer is no. Indeed, since $B$ is not enumerable, it contains a non-zero number $y_0$. Then $A.B$ contains the set $A.y_0 := \{x.y_0 | x \in A\}$ which is in bijection with $A$ since $y_0$ is invertible.

Answer 2

Yes, this is certainly possible. Note that for any $S\subset\mathbb{N}$, if we take $A=\{1\}\cup S$ and $B=\{1\}\cup S^{c}$, then $A\cdot B=\mathbb{N}$, which is enumerable. So we just need a non-enumerable set $S$ whose complement is also non-enumerable. For instance, let $S$ be the set of (encodings of) Turing machines that accept finitely many inputs. Then $S^{c}$ is the set of (encodings of) Turing machines that accept infinitely many inputs, plus those numbers that do not encode a Turing machine. Neither $S$ not $S^{c}$ is enumerable, because the corresponding decision problem (does a particular Turing machine accept finitely many inputs?) is undecidable.