The natural numbers are well-ordered without the axiom of choice. In fact they still serve as the definition for countability without the axiom of choice assumed. Therefore the basic things we know about the natural numbers hold regardless to the axiom of choice. In particular $\mathbb{N\times N}$ is still countable, and $\{A\subseteq\mathbb N\mid A\text{ is finite}\}$ is also countable.
However when the axiom of choice is negated some other weird things could happen in the power set of the natural numbers, and in other infinite sets:
- There could be a set which is infinite, but has no countably infinite subset.
- It could be that there are no free ultrafilters on the natural numbers.
- It could be that the power set of the natural numbers cannot be well-ordered (it can still be linearly ordered, though).
- Countable unions of general countable sets need not be countable.
- It is possible that there is no linear basis for $\mathbb R$ over $\mathbb Q$.
Let us focus on the first one for a moment, such sets are known as infinite Dedekind-finite sets. Their existence contradicts the axiom of countable choice, so if we assume that we can prove that every infinite set has a countably infinite subset. The fourth one has the same properties, it negates the axiom of countable choice.
Both the second, third and fifth points, however, are compatible with countable choice.
As for why we accept the axiom of choice, historically we did not accept it. People found its consequence strange (regardless to the fact they have used it intuitively). After it was proved that assuming the axiom of choice does not add inconsistencies to ZF, people began using the axiom of choice more and see its wonderful applications. It simply made things easier.
For more reading:
- Advantage of accepting the axiom of choice
- Motivating implications of the axiom of choice?
- Advantage of accepting non-measurable sets
- Why is the axiom of choice separated from the other axioms?
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
The problem is that you also do a "meta" induction when proving choice for a finite number of sets and this "meta" induction fails in the transfinite or countable case.
To be more clear, the proof of choice for a number of sets sets usually goes something like this (I'm assuming choice is "the product of nonempty sets is nonempty").
Base case is vacuously true (you're given one nonempty set and want to prove it's nonempty).
Next, assume inductively that for any nonempty sets $X_1,...,X_n$, the product $X_1\times...\times X_n$ is nonempty. Now, given $n+1$ sets, $X_1,...,X_{n+1}$, you want to show their product is nonempty. By the induction hypothesis, there is an element $y\in X_1\times....\times X_n$. Also, there is an element $x_{n+1}\in X_{n+1}$ by assumption. Then $\{\{y,x_{n+1}\}, x_{n+1}\} = (y, x_{n+1})$ is an element of the product.
On the meta level, what you're saying by unraveling the induction is "I have $n+1$ sets $X_1,...,X_{n+1}$, and I know there is an element (which is itself a set because we're doing set theory!) in each $X_i$ which I'll call $x_i$. By using the axiom of pairing once, I can form the set $\{x_1,x_2\}$. By using it again, I can form the set $\{\{x_1,x_2\}, x_1\}$, which is the definition of $(x_1,x_2)$. Using the axiom of pairing two more times, I can form $(x_1, x_2, x_3)$. In general (i.e., by induction), by using the axiom of pairing $2(n+1)$ times, I can form the set $(x_1,x_2,...,x_{n+1})$. This set (element) is a member of $X_1\times...\times X_{n+1}$, and hence this product is nonempty!"
What goes wrong as soon as you try to adapt this to the countable or larger setting is on the meta level. Essentially, you'd have to apply the pairing axiom countably (or more) times to create the set $(x_1,...)$ which "should" be in $X_1\times...\times $. But naive set theory has taught us that just because we think something "should" be a set, doesn't mean it should (see, for example, Russel's Paradox). Thus, we at least cannot trust this proof to work in countable or larger settings. Of course, the failure of this approach doesn't mean there is NO way of proving choice from $ZF$, but it's known from other methods that you cannot prove choice from $ZF$ alone.