Dedekind finite union of Dedekind finite sets is Dedekind finite

I could use some help proving the following:

Let $A$ be a Dedekind Finite set of pairwise disjoint Dedekind finite sets $\left(\mbox{i.e each}\, a\in A\,\mbox{is a Dedekind Finite set}\right)$ show that $\bigcup A$ is Dedekind Finite.

-

HINT: Let $S=\bigcup A$, and suppose that there is an injection $\omega\to S$. For $a\in A$ let $$N_a=\{k\in\omega:f(k)\in a\}\;.$$ Show that $N_a$ is finite for each $a\in A$ and use that result to construct an injection from $\omega$ to $A$, contradicting the Dedekind-finiteness of $A$.

-
I got the first part but I'm not sure how to construct the injection. I assume this is where I use the fact the sets in $A$ are pairwise disjoint. I don't want to use the Axiom of Choice since under AC I already know that Dedekind Finite is equivalent to finite and then the whole idea of the proof is moot. – Serpahimz Dec 23 '12 at 14:59
@Serpahimz: Let $A_0=\{a\in A:N_a\ne\varnothing\}$, and for $a\in A_0$ let $n(a)=\min N_a$. Let $N=\{n(a):a\in A_0\}$. There’s a bijection from $\omega$ to $N$, which you can compose with ... what? – Brian M. Scott Dec 23 '12 at 15:04
I think to finish I compose it with $g:N\to A$ defined by $g\left(n\left(a\right)\right)=a$ and I show that it is well defined by using the fact the sets are pairwise disjoint and thus for all $a\neq b$ I know that $n\left(a\right)\neq n\left(b\right)$ Hope I won't make a fool of myself – Serpahimz Dec 23 '12 at 15:14
One small thing I'm not sure about is why there is a bijection between $\omega$ and N. Isn't it possible that N is finite? – Serpahimz Dec 23 '12 at 15:17
@Serpahimz: If $N$ were finite, $A_0$ would be finite, and some $N_a$ would be infinite, which is impossible. – Brian M. Scott Dec 23 '12 at 15:22

If $B\subseteq\bigcup A$ is a countably infinite set, then $B_a=B\cap a$ is a Dedekind-finite set for every $a\in A$.

Show that every partition of a countably infinite set into Dedekind-finite sets is finite, and one of the parts has to be countably infinite.

Deduce that there is some $a\in A$ such that $B_a$ is countably infinite which is a contradiction to Dedekind-finiteness of $a$.

To prove the fact in the middle note that we may assume that the infinite set is $\mathbb N$ and that a partition is merely a surjection. Show, if so, that every surjection from $\mathbb N$ onto a Dedekind-finite set implies that the range is finite. (Hint: If $f\colon\mathbb N\to X$ is a surjection then there is an injection $g\colon X\to\mathbb N$.)

-
I used the previously suggested proof for my exercise (simply because it was first and I already started typing it) but this is also an elegant solution. Thanks a lot for replying! – Serpahimz Dec 23 '12 at 15:23
Note that both proofs are actually the same. It just might be slightly easier to use one over the other depending on how you defined a Dedekind-finite set. – Asaf Karagila Dec 23 '12 at 15:34