# Choice function for Borel sets?

Let's say we want to define a choice function for certain particular subsets $S \subset2^{\mathbb{R}}$, i.e. we want a function $c:S \rightarrow \mathbb{R}$ such that $c(X)\in X$ for every $X\in S$. We don't want to invoke the axiom of choice. Clearly we require $\emptyset\notin S$.

For example, if $S$ is the set of non-empty open sets for the usual topology, then we can fix an enumeration of the rationals and for every open $A$ pick the first rational (in this particular enumeration) lying in $A$.

If $S$ is the set of non-empty closed sets, then for any $A\in S$ we can consider the least $n$ such that $$-n,n$\cap A$ is non empty and then pick the infimum of this non empty compact set.

The question is the following: can you define a choice function for, say, $S=F_{\sigma}\setminus \{\emptyset\}$ or $G_{\delta}\setminus\{\emptyset\}$ or maybe for the higher levels of the Borel hierarchy? Is it possible to prove that such choice function exists for such $S$ without using the axiom of choice?

• How do I make appear parenthesis around the simbol for the empty set? – Gian Maria Dall'Ara Mar 19 '10 at 14:02
• Some backticks around the entire formula fixed it. – Harald Hanche-Olsen Mar 19 '10 at 14:14

It is impossible without using the Axiom of Choice to prove the existence of such a choice function for $F_{\sigma}$ sets, which include the countable sets. To see this, it is easier to work with the space $2^{\mathbb{N}}$ of infinite binary sequences instead of $\mathbb{R}$. Let $E$ be the eventual equality equivalence relation on $2^{\mathbb{N}}$. Then there is no measurable function which selects an element from each $E$-class.
Let $S \subseteq \mathbb{R}\times\mathbb{R}$ be a universal analytic set, i.e. $S$ is analytic and for every analytic set $A \subseteq \mathbb{R}$ there is a $x$ such that $A = S_x = \{ y \in \mathbb{R} : (x,y) \in S \}$. By the Jankov–von Neumann Uniformization Theorem (which is provable in ZF), the set $S$ has a uniformizing (partial) function $f:\mathbb{R}\to\mathbb{R}$, i.e. $\mathrm{dom}(f) = \{ x \in \mathbb{R} : S_x \neq \varnothing \}$ and $\{(x,f(x)) : x \in \mathbb{R}\} \subseteq S$. Since every Borel set is analytic, this $f$ gives you what you want provided you know codes $x$ such that the $S_x$ are Borel sets you're interested in. Picking a unique code for each Borel set is a difficult task which requires some choice. However, you can invoke the Axiom of Choice once to get such a function that gives unique codes and keep working with that function until the end of time, thereby avoiding repeated uses of choice.