1
$\begingroup$

I'm given that two sets, $A$ and $B$ are enumerable. I have to show that there exist subsets $A \supset C$ and $B \supset D$ ($C$ and $D$ also enumerable) such that $C$ and $D$ are disjoint and $A\cup B = C \cup D$. I was thinking to take $A=B=\{0,1\}$ and define $C=\{n : f(n)=1\}$, $D=\{n: f(n)=0\}$. Do you think this is right?

$\endgroup$
  • 3
    $\begingroup$ You need to show that for every $A,B$ there exist sets $C,D$. I don't see where $f$ is coming from - it doesn't appear in your statement of the problem. $\endgroup$ – Yuval Filmus Sep 27 '17 at 16:21
  • 1
    $\begingroup$ Once you understand what the question is actually asking, I doubt that you will have trouble solving it. $\endgroup$ – Yuval Filmus Sep 27 '17 at 16:22
  • 3
    $\begingroup$ You don't define $A,B$. You are given $A,B$. The sets you have to come up with are $C,D$. $\endgroup$ – Yuval Filmus Sep 27 '17 at 16:35
  • 1
    $\begingroup$ I suggest contacting a TA. It seems you are missing some basic definitions, and it is hard to diagnose this any further on this platform. $\endgroup$ – Yuval Filmus Sep 27 '17 at 17:39
  • 1
    $\begingroup$ This isn't for us; it belongs in math.SE. $\endgroup$ – Rick Decker Sep 27 '17 at 18:21
3
$\begingroup$

This answer assumes that enumerable means recursively enumerable.

Here is an enumerator for $C$:

  • Run enumerators for $A,B$ in parallel.
  • Whenever the enumerator for $A$ outputs a word, check whether the word has already been enumerated by the enumerator for $B$; if it hasn't, output it and continue.

The enumerator for $D$ is defined symmetrically.

$\endgroup$
  • $\begingroup$ So the idea is to assign the element from the intersection to the side whose enumerator gets there first. If this construction is to define unique $C$, $D$, the specific implementation of "run in parallel" matters (alongside the choice of the enumerators for $A$, $B$). $\endgroup$ – Raphael Sep 28 '17 at 6:51
  • 1
    $\begingroup$ It doesn't really matter as long as you do it in exactly the same way for both $C$ and $D$. $\endgroup$ – Yuval Filmus Sep 28 '17 at 6:53
  • $\begingroup$ Right. Just saying, $C$ and $D$ will differ if you change the details of the construction, but all have the required properties. If $A \cap B$ is infinite, it seems plausible that there are infinitely many such $C$ and $D$. $\endgroup$ – Raphael Sep 28 '17 at 6:58
2
$\begingroup$

Can you use the fact that a subset of an enumerable set is enumerable? If you can, then you could choose $C=A$ and $D=B\setminus A$ (set difference). Then $C$ and $D$ are enumerable and it's easy to show that $A\cup B=C\cup D$.

$\endgroup$
  • 2
    $\begingroup$ Assuming the OP means recursively enumerable, this is wrong. $\endgroup$ – Raphael Sep 27 '17 at 18:38
  • 1
    $\begingroup$ @Raphael. I made no such assumption. $\endgroup$ – Rick Decker Sep 27 '17 at 23:54
  • 2
    $\begingroup$ This answer is extremely doubtful. It seems reasonable (if not certain) to assume that enumerable means recursively enumerable in this context, since this site is for computer science. $\endgroup$ – Yuval Filmus Sep 28 '17 at 6:29
  • $\begingroup$ "a subset of [a recursively] enumerable set is [recursively] enumerable" -- this is a wrong statement, as I'm sure we can agree. $\endgroup$ – Raphael Sep 28 '17 at 6:48
  • $\begingroup$ It seems at least as reasonable to interpret "enumerable" as "countable". The OP's responses support that. $\endgroup$ – Rick Decker Sep 28 '17 at 11:24

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.