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!
Elementary Set Theory – Finding Choice Function without Axiom of Choice
axiom-of-choiceelementary-set-theory
Related Solutions
A Dedekind finite set is one all of whose subsets have strictly smaller cardinality. If $X$ is infinite Dedekind finite (iDf), then $X$ and ${\mathbb N}$ are incomparable in size. This means that no subset of $X$ is countable unless it is finite. Certain Dedekind finite sets may be amorphous, this means that any subset is finite or cofinite.
It is consistent that there are iDf sets, but no amorphous sets. It is also consistent that there are infinite amorphous sets, so the answer to your question is no, in general. However, if every Dedekind finite set is amorphous, then there are no iDf sets. Hence, if there is an iDf set at all, there is one that can be split into two infinite sets, and neither is countable.
(Of course, under choice, there are no iDf sets and every uncountable set admits an uncountable subset with uncountable complement.)
You are working only with finite products, and this hold in general. In the Choice Function $\Rightarrow$ AoC direction you don't know if $D$ is nonempty, that is what you are trying to pare working only with finite products, and this hold in general. In the AoC $\Rightarrow$ Choce Function direction you need a choice function on $\mathcal{A},$ not in $D.$ Moreover, I think we need to clarify some definitions.
First one definition
Definition: Let $\mathcal{A}$ be a nonempty collection os sets. A surjective function $f$ from some set $J$ to $\mathcal{A}$ is called an indexing function for $\mathcal{A}.$ $J$ is called the index set. The collection $\mathcal{A},$ together with $f,$ is called an indexed family of sets.
I'll use your definition of axiom of choice.
Axiom of choice: For any indexed family $\{ A_\alpha \}_{\alpha \in J}$ of nonempty sets, with $J \neq 0,$ the cartesian product $$ \prod_{\alpha \in J} A_\alpha$$ is not empty. Recall that the cartesian product is the set of all functions $$ \mathbf{x}:J \to \bigcup_{\alpha \in J}A_\alpha$$ such that $\mathbf{x}(\alpha) \in A_\alpha$ for all $\alpha \in J.$
Now,
Existence of a choice function: Given a collection $\mathcal{A}$ of nonempty sets, there exists a function $$ c: \mathcal{A} \to \bigcup_{A \in \mathcal{A}}A$$ such that $c(A)$ is an element of $A: c(A)\in A$ for each $A \in \mathcal{A}.$
Axiom of choice $\Rightarrow$ Existence of choice function.
We are assuming that for any indexed family $\{ A_\alpha \}_{\alpha \in J}$ of nonempty sets, with $J \neq 0,$ the cartesian product $ \prod_{\alpha \in J} A_\alpha$ is not empty. Let $\mathcal{A}$ be a collection of nonempty sets. We have to prove that there exists a function $ c: \mathcal{A} \to \bigcup_{A \in \mathcal{A}}A$ such that $c(A) \in A$ for each $A \in \mathcal{A}.$ We first index $\mathcal{A}$: let $J=\mathcal{A}$ and $f:\mathcal{A} \to \mathcal{A}$ given by $f(A)=A.$ Then $\{A\}_{A \in \mathcal{A}}$ is an indexed family of sets, so we can consider its cartesian product $\prod_{A \in \mathcal{A}}A.$ By hypothesis, this product is nonempty, so there exists a function $$ \mathbf{x}: \mathcal{A} \to \bigcup_{A \in \mathcal{A}}A$$ such that $\mathbf{x}(A) \in A$ for each $A \in \mathcal{A}.$ Then $c=\mathbf{x}$ is the function we were looking for.
Existence of choice function $\Rightarrow$ Axiom of choice
Now we are assuming that the existence of choice function, and let $\{A_\alpha \}_{\alpha \in J}$ be an indexed family of nonempty sets, with $J \neq 0.$ This means that there is a nonempty collection of sets $\mathcal{A}$ and there is an indexing (i.e. surjective) function $f:J \to \mathcal{A}$ such that $f(\alpha)=A_\alpha \in \mathcal{A}$ for each $\alpha \in J.$ By the existence of choice function, there is a function $c:\mathcal{A} \to \bigcup_{A \in \mathcal{A}}A$ such that $c(A) \in A$ for each $A \in \mathcal{A}.$ Thus the function $$ \mathbf{x}:= c \circ f : J \to \mathcal{A} = \bigcup_{\alpha \in J}A_\alpha$$ satisfies $\mathbf{x}(\alpha)=c(f(\alpha))=c(A_\alpha) \in A_\alpha$ for each $\alpha \in J,$ so the product $\prod_{\alpha \in J}A_\alpha$ is nonempty.
Best Answer
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$
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.
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\}$.