91Ó°ÊÓ

Show that if \(A\) and \(B\) are enumerable, so is \(A \cup B\). To do this, suppose there are surjective functions \(f: \mathbb{Z}^{+} \rightarrow A\) and \(g: \mathbb{Z}^{+} \rightarrow B,\) and define a surjective function \(h: \mathbb{Z}^{+} \rightarrow A \cup B\) and prove that it is surjective. Also consider the cases where \(A\) or \(B=\varnothing\).

Show that \(Q\) is enumerable. Recall that any rational number can be written as a fraction \(z / m\) with \(z \in \mathbb{Z}, m \in \mathbb{N}^{+}\).

A subset of \(\mathbb{N}\) is said to be cofinite iff it is the complement of a finite set \(\mathbb{N} ;\) that is, \(A \subseteq \mathbb{N}\) is cofinite iff \(\mathbb{N} \backslash A\) is finite. Let \(I\) be the set whose elements are exactly the finite and cofinite subsets of \(\mathbb{N}\). Show that \(I\) is enumerable.

Show that the enumerable union of enumerable sets is enumerable. That is, whenever \(A_{1}, A_{2}, \ldots\) are sets, and each \(A_{i}\) is enumerable, then the union \(\bigcup_{i=1}^{\infty} A_{i}\) of all of them is also enumerable. [NB: this is hard!]

Let \(S\) be the set of all surjective functions from the set of positive integers to the set \(\\{0,1\\},\) i.e., \(S\) consists of all surjective \(f: \mathbb{Z}^{+} \rightarrow \mathbb{B} .\) Show that \(S\) is non-enumerable.

Define an enumeration of the square numbers \(1,4,9,16, \ldots\)