Exercise 9.2

Question

Find if possible a choice function for each of the following collections, without using the choice axiom:
\begin{enumerate}[label=(\alph*)]
\item The collection $\mathcal{A}$ of nonempty subsets of ${{\mathbb{Z}}_+}$.
\item The collection $\mathcal{B}$ of nonempty subsets of ${\mathbb{Z}}$.
\item The collection $\mathcal{C}$ of nonempty subsets of the rational numbers ${\mathbb{Q}}$.
\item The collection $\mathcal{D}$ of nonempty subsets of $X^{\omega}$, where $X = \left\{0,1\right\}$.
\end{enumerate}

Dan Whitman · Accepted Answer

\begin{lemma}\label{lem:choice:countable}
If $A$ is a countable set and $\mathcal{A}$ is the collection of nonempty subsets of $A$ then $\mathcal{A}$ has a choice function.
\end{lemma}
\begin{proof}
Since $A$ is countable, there is an injective function $A 	o {{\mathbb{Z}}_+}$ by Theorem~7.1.
We define a choice function $c : \mathcal{A} 	o \bigcup_{B \in \mathcal{A}} B$.
Consider any $X \in \mathcal{A}$ so that $X$ is a nonempty subset of $A$.
Then $f(X)$ is a nonempty subset of ${{\mathbb{Z}}_+}$ so that it has a unique smallest element $n$ since ${{\mathbb{Z}}_+}$ is well-ordered.
Now, since $n \in f(X)$, clearly there is an $x \in X$ such that $f(x) = n$.
Moreover, it follows from the fact that $f$ is injective that this $x$ is unique.
So set $c(X) = x$ so that clearly $x$ is a choice function on $\mathcal{A}$ since $c(X) = x \in X$.
\end{proof}

extbf{Main Problem.}

(a) Since ${{\mathbb{Z}}_+}$ is countable, a choice function can be constructed as in Lemma~ef{lem:choice:countable}.

(b) Since ${\mathbb{Z}}$ is countable (by Example~7.1), a choice function can be constructed as in Lemma~ef{lem:choice:countable}.

(c) Since ${\mathbb{Q}}$ is countable (by Exercise~7.1), a choice function can be constructed as in Lemma~ef{lem:choice:countable}.

(d) First, there is an injective function $f$ from the real interval $[0,1]$ to $X^{\omega}$.
The most straightforward such function is, for each $x \in [0,1]$ let $0.x_1 x_2 x_3 \ldots$ be a unique binary expansion of $x$ (these can be made unique by avoiding binary expansions that end in all 1's, noting though that the expansion of $1$ itself must be $0.111\ldots$).
So suppose that $c$ were a choice function on $\mathcal{D}$ (that is presumably constructed without the choice axiom).
If $X$ is a nonempty subset of $[0,1]$ then $f(X)$ is a set in $\mathcal{D}$ so that we can choose $c(f(X)) \in f(X)$.
Since $f$ is injective, there is a unique $x \in X$ where $f(x) = c(f(X))$, and so choosing $x$ results in a choice function on the collection of nonempty subsets of $[0,1]$ since $X$ was arbitrary.

This would allow one to then well-order $[0,1]$ without using the choice axiom, which evidently nobody has done.
As far as I have been able to determine, this has not yet been proven impossible, it is just that nobody has been able to do it.
So it would seem that such an explicit construction of a choice function on $\mathcal{D}$ would at least make one famous.
Or else it is impossible, which is what we assume to be the case here.

Exercise 9.2

Answers

Comments

Exercise 9.2

Answers

Comments

Add answer