Intereting Posts

Subgroups of Abelian Groups
Is there a proof that $\pi \times e$ is irrational?
Finite group with unique subgroup of each order.
Find the principal value of $\int_{-\infty}^{\infty}\frac{1-\cos x}{x^2}\,\mathrm dx$
How can I visualize a four-dimensional point inside a Schlegel diagram of a tesseract?
About $\lim \left(1+\frac {x}{n}\right)^n$
Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$
Finding maximal chain of cardinality $\aleph$
Why the $\nabla f(x)$ in the direction orthogonal to $f(x)$?
What does $dx$ mean?
Find the order of a subgroup of $S_5$ generated by two elements
Forcing Classes Into Sets
Sketch Saddle Point of a function of two variables $ f(x, y) = 4 + x^3 + y^3 – 3xy$
Color an $n\times n$ square with $n$ colors
Multidimensional complex integral of a holomorphic function with no poles

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!

- Existence of uncountable set of uncountable disjoint subsets of uncountable set
- Ordered Pair Formal Definition
- n-tuple Notation
- Uncountably many ordering of natural numbers
- Sufficient / necessary conditions for $f \circ g$ being injective, surjective or bijective
- Foundation for analysis without axiom of choice?
- Proving : Every infinite subset of countable set is countable
- It's in my hands to have a surjective function
- How many subsets of $\mathbb{N}$ have the same cardinality as $\mathbb{N}$?
- Question about set notation: what does $]a,b[$ mean?

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.

- countable group, uncountably many distinct subgroup?
- Tensors constructed out of metric other than the Riemann curvature tensor
- Does the set of differences of a Lebesgue measurable set contains elements of at most a certain length?
- Conditions for intersection of parabolas?
- Question on problem: Equivalence of two metrics $\iff$ same convergent sequences
- Solving an integral coming from Perron's formula
- Can every curve be subdivided equichordally?
- Closed-form of $\sum_{n=0}^\infty\;(-1)^n \frac{\left(2-\sqrt{3}\right)^{2n+1}}{(2n+1)^2\quad}$
- convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$
- How find this sum $\sum\limits_{n=0}^{\infty}\frac{1}{(3n+1)(3n+2)(3n+3)}$
- In written mathematics, is $f(x)$a function or a number?
- Analyticity of $\overline {f(\bar z)}$ given $f(z)$ is analytic
- Picture behind $SO(3)/SO(2)\simeq S^2$
- Definition of Conditional expectation of Y given X.
- $E|X-m|$ is minimised at $m$=median