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.