Proof of the axiom of choice for finite sets in ZF [closed]

Question

Let the set $A$ be finite and $\emptyset \notin A$. How can I, without using the axiom of choice, prove by mathematical induction that there exists a function $f : A \rightarrow \bigcup A$ satisfying $f(a) \in a$ for all $a \in A$?

Answer 1

It holds vacuously for $A = \emptyset$: then $\bigcup A = \emptyset$ and the empty function $\emptyset: \emptyset \to \emptyset$ trivially fulfills $f(a) \in A$ for all $a\in A$ -- because it is impossible to find a counterexample in an empty set.

Let $n_0 \in\mathbb{N}$ be the smallest number such that there is $A$ of cardinality $n_0$ with $\emptyset \notin A$, but no choice function $f:A \to \bigcup A$ with $f(a)\in a$ for all $a\in A$. We just saw that $n_0$ cannot be $0$.

So we have $n_0 > 0$. Let $a_0\in A$. Because $n_0$ is the smallest integer such that there is no choice function, there is a choice function $f:\big(A\setminus \{a_0\}\big)\to \bigcup\big(A\setminus\{a_0\}\big)$. Pick $x_0\in a_0$ (which is possible since $a_0\neq \emptyset$). Now set $$f' = f \cup \big\{(a_0, x_0)\big\}.$$ It is easy to verify that this is a choice function for $A$, contradicting the assumption that $A$ does not have a choice function.