Transfinite Induction and the Axiom of Choice

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.

1) Why does standard induction alone not suffice to show the axiom of choice for systems of countable sets? Doesn't induction show the truth of the statement for all natural numbers, and therefore for any system of sets that can be indexed by the natural numbers (countable sets)? I know this to be false, but I do not know why.

As Jason DeVito points out in the comments to his answer, just because something holds for all natural numbers $n$ doesn't mean that it holds for the set $\mathbb{N}$ of natural numbers itself: For a trivial example, every natural number $n$ is finite, yet $\mathbb{N}$ itself is infinite.

2) Why can't the above "proof" that induction implies the AoC for countable sets not be repaired by using transfinite induction? Isn't this the purpose of transfinite induction, to allow one to induct on sets of infinite size? Shouldn't transfinite induction suffice to prove the axiom of choice for any system of sets indexed by a well-ordered set?

A proof by ordinary induction has two parts: a base case and a successor step. A proof by transfinite induction has three parts: a base case, a successor step, and a limit step. The limit step says that for an infinite stage (technically, an ordinal number) $\lambda$, if the property $P$ holds at every stage $\alpha < \lambda$, then it holds at stage $\lambda$. For many properties $P$, the base case and successor step hold but the limit step fails. To revisit the trivial example from above, let's try to prove that every set is finite. Let $P(\alpha)$ be the statement "every set of size $\alpha$ is finite," and let us try to prove that $P(\alpha)$ holds for all $\alpha$ by transfinite induction. In this example the base case and successor step hold trivially, but the induction will fail at the very first limit step.

For the less trivial example of the axiom of choice, let $P(\alpha)$ be the statement "every sequence of sets of length $\alpha$ has a choice function." As suggested in the question, the base case and induction step are trivial. But the limit step fails again: Let $(A_i : i \in \mathbb{N})$ be an infinite sequence of sets and suppose by the induction hypothesis that for every finite $n$, the proper initial segment $(A_i : i < n)$ of the sequence has a choice function. The natural attempt to define a choice function $f$ for $(A_i : i \in \mathbb{N})$ would be to take choice functions $f_n$ for $(A_i : i < n)$ and combine them in some way. But first we would have to choose a choice function $f_n$ for each finite $n$, which is just as hard as the original problem! So transfinite induction doesn't help us at all.