Intereting Posts

Intuition for complex eigenvalues
Integral $\int_0^\infty\frac{1}{\sqrt{x}}\left(1+\log\frac{1+e^{x-1}}{1+e^x}\right)dx$
“Binary-Like” Function?; In Consecutive Products as Multi-Factorials…
Do you need real analysis to understand complex analysis?
birthday problem – which solution for expected value of collisions is correct?
Why is the Jordan Curve Theorem not “obvious”?
Infinite recurrence relation which depends on subsequent sequence values
Simplifying a certain polylogarithmic sum in two variables
Existence of square root
Some questions about $S^n$
Degree of maps and coverings
Every open cover of the real numbers has a countable subcover (Lindelöf's lemma)
Finding the Transformation to a Canonical form for a Quadric Surface
Proof of identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ for Fibonacci numbers
How do I find the basis of this eigen space?

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!

- The Intersection of Ordered Pairs
- Visualizing $\cap_{i = 1}^\infty A_i = (\cup_{i = 1}^\infty A_i^c)^c$
- Is the set $\{\{1\},\emptyset\}$ a subset of $\{\{1\}\}$?
- Let $A, B$ be sets. Show that $\mathcal P(A ∩ B) = \mathcal P(A) ∩ \mathcal P(B)$.
- Is there a notation for being “a finite subset of”?
- Question about set notation: what does $]a,b[$ mean?

- Cantor's theorem via non-injectivity.
- Proof that the symmetric difference is associative
- Uniqueness proof for $\forall A\in\mathcal{P}(U)\ \exists!B\in\mathcal{P}(U)\ \forall C\in\mathcal{P}(U)\ (C\setminus A=C\cap B)$
- Elementary set theory - prove or disprove question
- Examples of bijective map from $\mathbb{R}^3\rightarrow \mathbb{R}$
- Equinumerousity of operations on cardinal numbers
- Prove: If $(g \circ f)$ is bijective, is $f$ bijective?
- Can a collection of subsets of $\mathbb{N}$ such that no one set contains another be uncountable?

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.

- Learning Complex Geometry – Textbook Recommendation Request
- A problem For the boundary value problem, $y''+\lambda y=0$, $y(-π)=y(π)$ , $y’(-π)=y’(π)$
- How do you integrate $\int \frac{1}{a + \cos x} dx$?
- A proof that the “set of all sets” does not exist in ZFC using Cantor's Theorem?
- Semidirect Products with GAP
- Need help proving this integration
- Optimization of relative entropy
- What are well-defined functions?
- Integration of Rational Functions – Problem with proof relating to complex solutions
- Covering space is a fiber bundle
- Min. number of vertices in graph as function of $\kappa(G)$ and $\operatorname{diam}(G)$
- Quadratic polynomial over $K$
- MDS and low distortion embeddings
- Why are vector spaces not isomorphic to their duals?
- A prime ideal with the algebraic set reducible