Section 1.7: Problem 11 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
(a) Explain why the union of two effectively enumerable sets is again effectively enumerable.
(b) Explain why the intersection of two effectively enumerable sets is again effectively enumerable.
We have two equivalent definitions for effective enumerability of , namely, by being able to list all elements of , and by being able to answer “yes” for iff . We will use whatever is more convenient in each point below. So, let and be the procedures described in the second definition corresponding to the two effectively enumerable sets.
(a) We can effectively list all members of each set “simultaneously” (and take care of duplications if we need to). What we mean by “simultaneously” is explained in Exercise 8. Alternatively, given any wff , we could run both procedures and with input “simultaneously”, and stop and answer “yes” whenever at least one of them returns “yes” (this may work infinitely long only if is a member of neither set, in which case we don’t care that it never stops).
(b) We can effectively list all members of the intersection by listing all the members of both sets and output as long as it appears in both listings (for every in the intersection it will take finite time to appear). However, this approach may require arbitrary amount of memory, to keep entries found in one list but not in the other. Moreover, if there is infinite number of elements in one set that are not in the other, the procedure will require any arbitrary amount of memory at some point. Alternatively, given any wff , we could run both procedures and with input sequentially or “simultaneously”, and stop and answer “yes” as long as both procedures returned “yes” (this may take infinitely long if is not a member of either one, but, again, we don’t care if this happens in this case).