Finding a choice function without the choice axiom

Is there a way to define a choice function on the set of subsets of $\{0,1\}\times\{0,1\}\times\ldots = \prod_{n \in \mathbb N} \{0,1\}$ in ZF? I know that $\prod_{n \in \mathbb N} \{0,1\}$ is uncountable, but I'm not quite sure how to fabricate a choice function without the choice axiom...any hint is much appreciated!

Theorem I: If $X$ is a set, then $X$ can be well-ordered if and only if there exists a choice function on $\mathcal P(X)\setminus\{\varnothing\}$.

Proof. If $X$ can be well-ordered fix a well-ordering, and a choice function returns the minimal element of every non-empty subset.

If $\mathcal P(X)\setminus\{\varnothing\}$ has a choice function $F$ we define by a transfinite argument a well-ordering of $X$:

Suppose for $\alpha$, $x_\beta$ was chosen for $\beta<\alpha$, let $x_\alpha=F(X\setminus\{x_\beta\mid\beta<\alpha\})$. This is well-defined, and obviously one-to-one from ordinals into $X$. Since $X$ is a set, the induction has to end at some ordinal $\kappa$. Therefore we have a bijection between $\kappa$ and $X$ so $X$ can be well-ordered. $\square$

Theorem II: It is consistent with ZF that the real numbers cannot be well-ordered.

I won't prove that here, since this requires a lot more machinery from advanced set theory, but this is essentially what Cohen proved in his original work about forcing.

Corollary: It is consistent with ZF that there is no choice function on $\mathcal P(\mathbb R)\setminus\{\varnothing\}$.

This is now a trivial corollary, in a model where $\mathbb R$ cannot be well-ordered -- there is no choice function on $\mathcal P(\mathbb R)\setminus\{\varnothing\}$.

So you're basically asking for a choice function on $2^{2^\mathbb{N}}$, which is essentially equivalent to finding a choice function on $2^\mathbb{R}$, since a bijection between $\mathbb{R}$ and $2^\mathbb{N}$ can be constructed. If there were a way of making such a choice without referring to the axiom of choice, then the Vitali set, which is not Lebesgue Measurable, would exist in all models of ZF. There are models of ZF in which all sets of reals are measurable.

It may be useful to complement the negative answers by indicating that, as long as the sets are reasonably definable, then there are choice functions, and it is only when we look for choice functions on arbitrary sets of reals that we find obstacles.

The area of set theory that studies these positive results is descriptive set theory. Some of the positive results are absolute (that is, they just hold under the basic axiomatization of set theory, $\mathsf{ZFC}$). Others require stronger assumptions, typically expressed by saying that appropriate large cardinals exist.

At one end of the spectrum we have that (provably in $\mathsf{ZF}$, that is, without any use of choice) we have a choice function on the family of non-empty open, closed, or $G_\delta$ sets. A nice modern argument showing this can be found in section 2 of

Arnold W. Miller. A Dedekind finite Borel set. Arch. Math. Logic 50 (2011), no. 1-2, 1–17. MR2765632 (2012f:03101).

Then there are the classical uniformization results. The idea here is that if we have a family $(A_r\mid r\in I)$ of non-empty "nice" sets of reals, with $I$ itself being "nice", then we have a choice function for this family, which again is "nice". This is formalized as a "uniformization" result for a class of sets $\Gamma$: If $A\subseteq\mathbb R^2$, a uniformization of $A$ is a function $f$ with domain ${\rm dom}(A)=\{x\in\mathbb R\mid \exists y (x,y)\in A\}$ and such that for all $x\in{\rm dom}(f)$, we have $(x,f(x))\in A$. We say that a class $\Gamma$ of sets has the uniformization property iff any $A\subseteq\mathbb R^2$ in $\Gamma$ admits a uniformization whose graph (as a subset of $\mathbb R^2$) is again in $\Gamma$.

The Novikov-Kondo-Addison uniformization Theorem states that $\mathbf{\Pi}^1_1$ and $\mathbf{\Sigma}^1_2$ have the uniformization property. Here, a set $B\subseteq\mathbb R^n$ is $\mathbf{\Pi}^1_1$ iff its complement is the continuous image of a Borel subset of $\mathbb R$, and it is $\mathbf{\Sigma}^1_2$ iff it is the continuous image of a $\mathbf{\Pi}^1_1$ set of reals. This is as far as we can prove in $\mathsf{ZF}$, and it suffices for most practical purposes; it is an "empirical fact" that any family of sets of reals that one tends to encounter (unless one is explicitly working in set theory) can be described as a $\mathbf{\Sigma}^1_2$ relation, or even something simpler.

Assuming large cardinals, this can be extended through the projective hierarchy, and we can show that the classes $\mathbf{\Pi}^1_3,\mathbf{\Sigma}^1_4,\mathbf{\Pi}^1_5,\dots$ all have the uniformization property. (Here, sets in $\mathbf{\Pi}^1_n$ are complements of sets in $\mathbf{\Sigma}^1_n$, and sets in $\mathbf{\Sigma}^1_{n+1}$ are continuous images of sets in $\mathbf{\Pi}^1_n$.) How far one can go ties up with the extent of determinacy, and it is the object of much current work.

Another collection of positive results comes from assuming we have "simple" sets ("nice" Borel sets of low complexity), and trying to show that we have "simple" choice functions for them. This is the topic of the book

John E. Jayne, and C. Ambrose Rogers. Selectors, Princeton University Press, Princeton, NJ, 2002. MR1915965 (2003j:54018).

As with the unifomization property, the general question is, given a set-valued map $F:X\to\mathcal P(Y)$ (where $X,Y$ are topological spaces, and $F(x)\ne\emptyset$ for all $x\in X$), when can one find a function $f:X\to Y$ with $f(x)\in F(x)$ for all $x\in X$, and moreover ensure that $f$ is a function of some given Borel (or Baire) class? The book presents the positive results most used in analysis, centering on arguments that are not set-theoretic in nature.