Find if possible a choice function for each of the following collections, without using the choice axiom:
The collection \(\mathcal{A}\) of nonempty subsets of \(\mathbb{Z}_{+}\) .
The collection B of nonempty subsets of Z.
The collection C of nonempty subsets of the rational numbers Q.
The collection \(\mathcal{D}\) of nonempty subsets of \(X^{\omega}\), where \(X = \{0,1\}\) .
Solution
1. (a) Yes: \(c(A)=\min A\) (least element) is a choice function for nonempty subsets of \(\ZZ_+\).
\(\ZZ_+\) well-ordered.
2. (b) Yes: well-order \(\ZZ\) as \(0,1,-1,2,-2,\dots\) and take least in that order.
explicit well-ordering.
3. (c) Yes: \(\QQ\) countable, fix enumeration \(q_1,q_2,\dots\) and take \(c(A)=q_{\min\{n:q_n\in A\}}\).
countable well-ordering.
4. (d) No: \(\mathcal D\) is all nonempty subsets of Cantor set \(2^\omega\); no definable choice without AC (requires AC).
\(2^\omega\) uncountable with no definable well-order in ZF.
5. Q.E.D.
1 and 4.