A concrete example of a choice function

Question

I'm trying to understand a bit what lies behind the Axiom of Choice, and I was wondering,

are there concrete examples of a choice function on the Borel set?

The Borel set seems nice enough for a constructive example, but I can't find an example. Is it possible to find one?

Edit: by "Borel set", I mean the the smallest σ-algebra on R which contains all the intervals.

Answer 1

I interpret the revised question to be asking for a choice function for the Borel algebra of all Borel sets of reals, that is, a function that assigns to each Borel set of reals an element of that set.

This question is answered in the negative in this MO thread. The argument is essentially that if you could define such a choice function, you could use it to construct a Vitali set, since the elements of $\mathbb R/\mathbb Q$ are Borel sets. But a Vitali set can be proved to be non-measurable without using the axiom of choice, and the existence of non-measurable sets can't be proved without the axiom of choice.

Answer 2

The point of the axiom of choice is to guarantee the existence of functions which cannot be constructed otherwise.

Things we can "visualize" and grasp are usually nice enough to define a choice function on them.

For example:

1. From a family of non-empty intervals $\bigg\lbrace(a_i,b_i)\mid a_i<b_i, i\in I\bigg\rbrace$ we can always set $f(i)=\dfrac{a_i+b_i}{2}$.

2. If $\bigg\lbrace A_i\mid i\in I\bigg\rbrace$ is a family of non-empty sets, and there exists some $\varphi(i,x,y)$ which is a formula which defines a well-ordering of $A_i$, that is: for $x,y\in A_i$ we have $x<y\iff\varphi(i,x,y)$ is a well ordering of $A_i$ for all $i\in I$. In such case we can choose the minimal element of such order.
   To show you how that is possible, we can take $A_i=\{n\in\mathbb N\mid 2^i<n\}$, then every such $A_i$ is well ordered by the usual ordering of $\mathbb N$ (which is definable from the $\in$ relation). Then we can take the least element of $A_i$.

On the other hand, this requirement of uniformity is quite important. The following example can show us how much:

If there is a Dedekind-finite set of reals, then there is a countable family of real numbers which has no choice function.

A set is Dedekind-finite if it has no countably infinite subset. Under the axiom of choice a set is Dedekind-finite if and only if it is finite, however Paul Cohen proved the independence of the axiom of choice by constructing an infinite Dedekind-finite subset of the real numbers.

Let us denote such set with $D$. Without loss of generality $D$ is unbounded from below and from above. If it happens that $D$ is bounded, take the homeomorphism of $\mathbb R$ with $(\inf D,\sup D)$ and the image of $D$ is unbounded and Dededkind-finite.

Now take $\mathscr D=\{D\cap(r,s)=D_{rs}\mid r,s\in\mathbb Q\}$ as the family of sets. Suppose by contradiction that there was a choice function on $\mathscr D$ then by this choice function we can define a function $f$ from $Q$ which was the countable set of interval with rational endpoints into $D$.

Suppose $f$ was not injective, we can enumerate $Q=\{A_i\mid i\in\mathbb N\}$, and define for every $x\in\operatorname{Rng}(f)$ let $A_x$ be $A_i$ such that $i=\min\{n\in\mathbb N\mid f(A_n)=x\}$. Now we can show that the restriction of $f$ to $\{A_x\mid x\in\operatorname{Rng}(f)\}$ is injective, and into $D$. This contradicts the fact that $D$ has no countably infinite subset.