# Enumerable disjoint subsets whose union is equal to the union of the sets

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?

• 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. – Yuval Filmus Sep 27 '17 at 16:21
• Once you understand what the question is actually asking, I doubt that you will have trouble solving it. – Yuval Filmus Sep 27 '17 at 16:22
• You don't define $A,B$. You are given $A,B$. The sets you have to come up with are $C,D$. – Yuval Filmus Sep 27 '17 at 16:35
• 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. – Yuval Filmus Sep 27 '17 at 17:39
• This isn't for us; it belongs in math.SE. – Rick Decker Sep 27 '17 at 18:21

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.

• 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$). – Raphael Sep 28 '17 at 6:51
• It doesn't really matter as long as you do it in exactly the same way for both $C$ and $D$. – Yuval Filmus Sep 28 '17 at 6:53
• 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$. – Raphael Sep 28 '17 at 6:58

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

• Assuming the OP means recursively enumerable, this is wrong. – Raphael Sep 27 '17 at 18:38
• @Raphael. I made no such assumption. – Rick Decker Sep 27 '17 at 23:54
• 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. – Yuval Filmus Sep 28 '17 at 6:29
• "a subset of [a recursively] enumerable set is [recursively] enumerable" -- this is a wrong statement, as I'm sure we can agree. – Raphael Sep 28 '17 at 6:48
• It seems at least as reasonable to interpret "enumerable" as "countable". The OP's responses support that. – Rick Decker Sep 28 '17 at 11:24