Prove that if $A$ and $B$ are Dedekind finite then so is their union, without using natural numbers or Axiom of Choice Note admins: THIS IS NOT A DUPLICATE to other posts (see the last sentence).

Prove that if $A$ and $B$ are Dedekind finite then so is their union, without using the concept of natural numbers or Axiom of Choice.

Of course, the result is trivial with the natural numbers, but the book from which this question is derived said this can be proven without the aid of natural numbers and Axiom of Choice (I am using Moschovakis' Notes on Set Theory, 1st edition, chapter 4, x4.25)
We are allowed to use $ZF$ Axioms.
Suppose on the contrary thay there are Dedekind finite sets $A,B$ such that $A \cup B$ is Dedekind infinite. If either $f(A) \subset A$ or $f(B) \subset B$ then we can easily create a proper injection from one set to itself (just take restriction of $f$), so assume that that is not the case.
I am not sure what to do here. A hint would be more appreciated then a full answer.
I realize that there already are many questions and answers regarding how a union of two Dedekind finite sets are still Dedekind finite, but my question is different: the difficulty here is that (1) since I am not allowed to use natural numbers, we cannot talk about a set being finite or infinte, much less list some elements or sets, and (2) we cannot use Axiom of Choice.
 A: Here's a hint.
Suppose f is an injection from $A \cup 
B$ to a proper subset.
Define $D(x) = \bigcap \{S \subset A \cup B : x \in S, f(S) \subseteq S\}$.
Choose $c \in (A \cup B) \setminus f(A \cup B)$. Let $C = D(c)$.
Show that $x \prec y$ iff $D(y) \subsetneq D(x)$ is a well-ordering of C and attempt to construct injections on $A \cap C$ and $B \cap C$ taking members of each to the next member under the well-ordering. Show that at least one of these must exist. It is onto a proper subset and so one of A and B is Dedekind-infinite.
(You might get away without fully proving the well-ordering. Showing that if $X \subset C$ is non-empty then $\exists! x \in X, X \subseteq D(x)$ may be enough.)
ETA more details.
Let's call a set $S$ f-closed if $f(S) \subseteq S \subseteq A \cup B$
Note that for any such $S$,  $x \in S$ implies $D(x) \subseteq S$.
In particular, $D(x)$, $f(D(x))$, $D(f(x))$, $D(f(x)) \cup \{ x \}$ and $f(D(x)) \cup \{ x \}$ are all f-closed, for any x, which can be used to show $D(f(x)) = f(D(x))$ and $D(x) = D(f(x)) \cup \{ x \} = f(D(x)) \cup \{ x \}$. And also, for any $y \in D(x)$, $D(y) \subseteq D(x)$.
Next we need to prove: If  $S$ is f-closed, non-empty and $S \subseteq D(x)$ for some x, then there exists $y \in D(x)$ such that $S=D(y)$
Suppose this fails for a particular $S$. Let $T = \{y \in D(x) : S \subsetneq D(y) \}$. If $y \in T$ then $S \subseteq D(f(y))$ (as $y \notin S$) but we can't have $S = D(f(y))$ so we must have $S \subsetneq D(f(y))$ and so $f(y) \in T$. Thus $T$ is f-closed. But $x \in T$ and so  $T = D(x)$, which implies S is empty - a contradiction. 
A similar argument shows that if $D(x) \neq D(f(x))$ then for any $y$,$z \in D(x)$, $D(y) = D(z)$ iff $y = z$. In particular this applies in C.
So now if $X \subseteq C$ is non-empty, let $W = \bigcup \{D(x) : x \in X \}$. This f-closed so there is a unique $m \in C$ such that $W = D(m)$. Clearly $m \in X$. Define $min(X) = m$. (This can be used to construct the full well-ordering, but it is all we need to complete the proof.)
Now try to define a function on $A \cap C$ by $g(x) = min(D(f(x) \cap A)$. If this is possible  $g$ is an injection from $A \cap C$ to a proper subset. If it is not possible then for some $y \in C$, $(D(y) \cap A = \emptyset$. Then $D(y) \subseteq B \cap C$ and f restricted to $D(y)$ is an injection onto a proper subset. At least one of $A \cap C$ and $B \cap C$ must be Dedekind-infinite.
