Choice function for Borel sets?

Question

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? 

Answer 1

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.

Answer 2

As Simon pointed out, you can't do this without some use of choice. However, you can "almost" do it: the trick is to work with codes for Borel sets instead of actual Borel sets (when you can).

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.

See, for example, Kechris's Classical Descriptive Set Theory (II.18) for details on the Jankov–von Neumann Uniformization Theorem, and many other useful uniformization theorems (Kuratowski–Ryll Nardzewski, Kondô–Novikov, etc) that can be used in a variety of contexts.