Exercise 8.1.14

Proof. Suppose that $S$ is a countable system of sets and let $T=\left\{X\in S\mid X\ne \varnothing \right\}$. Then it suffices to show that there is a choice function $h$ for $T$. To see this suppose that there is such a choice function $h$ and define a function $g$ on $S$ by

for any $X\in S$, noting that clearly $X\in T$ if $X\ne \varnothing$ so that $X$ is in the domain of $h$. Then, for any nonempty $X\in S$, we have that $g(X)=h(X)\in X$ since $h$ is a choice function. Hence $g$ is a choice function on $S$.

Now we construct a choice function $h$ for $T$. First note that clearly either $T$ is finite or countable since $T\subseteq S$ and $S$ is countable. If $T$ is finite then it has a choice function $h$ by Theorem 8.1.2, so we shall assume that $T$ is also countable. It then follows that $T$ can be written as a sequence of sets $⟨X_n\mid n\in \omega ⟩$.

Now define the the binary relation $R$ on $\bigcup <!--\; FUNCTION\; APPLICATION\; -->T$ by

First, since $X_0\in T$, it is nonempty so that there is an $x\in X_0$. Then clearly $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->T$ so that $\bigcup <!--\; FUNCTION\; APPLICATION\; -->T$ is nonempty. Now consider any $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->T$ so that there is an $n\in \omega$ such that $x\in X_n$. We then have that $X_{n+1}\ne \varnothing$ since $X_{n+1}\in T$ so that there is a $y\in X_{n+1}$, noting that clearly also $y\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->T$. It then follows from the definition of $R$ that $\mathit{𝑥𝑅𝑦}$. Since $x$ was arbitrary this shows that the relation $R$ on $\bigcup <!--\; FUNCTION\; APPLICATION\; -->T$ meets the conditions of the Principle of Dependent Choices. Thus we can conclude that there is a sequence $⟨x_n\mid n\in \omega ⟩$ of elements of $\bigcup <!--\; FUNCTION\; APPLICATION\; -->T$ where $x_{n}R{x}_{n+1}$ holds for any $n\in \omega$.

Now, since we have that $x_0\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->T$, there is an $m\in \omega$ such that $x_0\in X_m$. We claim that $x_n\in X_{m+n}$ for all $n\in \omega$, which we show by induction on $n$. First, for $n=0$, we already know that $x_n=x_0\in X_m=X_{m+0}=X_{m+n}$. Now suppose that $x_n\in X_{m+n}$. By the property of the sequence ${⟨x_k⟩}_{k\in \omega }$ we know that $x_{n}R{x}_{n+1}$ so that, by the definition of $R$, we have that $x_{n+1}\in X_{(m+n)+1}=X_{m+(n+1)}$ since clearly $m+n\in \omega$ and $x_n\in X_{m+n}$. This completes the induction.

Now consider the set $T^{\prime }=\left\{X_n\mid n\in m\right\}$, which is clearly a finite system of nonempty sets. Hence by Theorem 8.1.2 it has a choice function $h^{\prime }$. Now we define a function $h:T\to \bigcup <!--\; FUNCTION\; APPLICATION\; -->T$. For any $X\in T$ we know that there is an $n\in \omega$ such that $X=X_n$. So we set

We claim that $h$ is a choice function on $T$. So consider any $X\in T$ (which automatically means that $X\ne \varnothing$) so that again $X=X_n$ for some $n\in \omega$. If $n<m$ then we have that $h(X)=h^{\prime }(X_n)\in X_n=X$ since $h^{\prime }$ is a choice function. On the other hand, if $n\ge m$, then we note that $n-m\in \omega$ and we have $h(X)=x_{n-m}\in X_{m+(n-m)}=X_n=X$ by what was shown above. Since $X$ was arbitrary this shows that $h$ is a choice function on $T$. Hence, as shown above this means that there is a choice function $g$ on $S$ as desired. □