1

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

Asaf Karagila
  • 393,674
ratkke
  • 111
  • Depends on what $A, B$ and $\cdot$ are. – Git Gud Dec 15 '13 at 14:36
  • A and B are sets, this multiplication means, that if we have, for example, A={1, 2} and B={3,4,5} the answer will be {13, 14, 15, 23, 24, 25} – ratkke Dec 15 '13 at 14:40
  • The tag cardinals implies that you are only interested in countability, whereas computability implies that you are interested in recursiveness (i.e. the existence of an algorithm). Incidentally, this takes the question out of the context of the elementary set theory tag as well. – Asaf Karagila Dec 15 '13 at 15:14
  • Where did you come across this question? I might consider using it next semester as an example or a homework question. – Asaf Karagila Dec 15 '13 at 15:55

2 Answers2

4

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.

mjqxxxx
  • 41,358
  • @mhqxxxx Thank you for your help, i misunderstand just 1 crucial thing. What does $S^{c}$ means? – ratkke Dec 15 '13 at 16:46
-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.

Jeremy Daniel
  • 3,190
  • I am sorry, i misunderstande your proof. Why is there non-zero element in B, since B is not enumarable? I think, that by defenition that set is enumerable if and only if there is an algorithm that will enumerate this set. Can you explain me it, please? – ratkke Dec 15 '13 at 14:47
  • Maybe you should precise your definition of enumerable. What I wrote is for a naive definition, where enumerable is equivalent with countable. – Jeremy Daniel Dec 15 '13 at 14:50
  • If you meant "recursively enumerable", then I cannot answer your question. – Jeremy Daniel Dec 15 '13 at 14:51
  • 1
    No, in my defenition enumerable is not the same as countable. My defenition is from Math logic, 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. – ratkke Dec 15 '13 at 14:56
  • 1
    You should precise this in your question, I think. – Jeremy Daniel Dec 15 '13 at 15:02
  • 2
    @rattke In mathematical logic, the concept you apparently have in mind is called either "recursively enumerable" or "computably enumerable", not just "enumerable". – Andreas Blass Dec 15 '13 at 15:56