Proving $A$ is countably infinite if there exists a function $f: A \to \mathbb{N}$ such that for every $k$, the set of solutions to $f(a)=k$ is finite 
Let $A$ be a set for which there exists a function $f:A \to \mathbb{N}$ with the property that for every $k \in \mathbb{N}$, the subset of $A$ given by the solutions to $f(a)=k$ is finite.
Show that $A$ is finite or countably infinite.

Suppose $k \in \mathbb{N}$ and let $A$ be an infinite set. Then define $X_k = \{a \in A:f(a)=k \}$ to be the subset of $A$ given by the solutions to $f(a)=k$.
I'm trying to prove that $f$ is bijective, but I am having difficulty. If we assume $f(x)=f(y)=c$, how do we show that $x=y$? Since $f(x)$ and $f(y)$ are equal, they would belong to the same finite set of solutions $X_c$. Do we use the fact that $X_c$ must be finite to show $x=y$? I'm not entirely sure how to use this.
For surjectivity, we would just have to show that the subsets $X_1,X_2,X_3,\ldots$ are nonempty, right? Then $f$ would map $A$ to all of $\mathbb{N}$ and then we could conclude that $f$ is surjective. How could we show this rigorously?
 A: As you've already done, we define the sets 
$$X_k = \{ a \in A : f(a) = k \}.$$
Then we have $A = \bigcup_{k \in \mathbb{N}} X_k$. This is a countable union of countable sets and therefore countable.
A: We cannot prove this without the Axiom of Choice or one of its weaker brethren  because it has been shown to be consistent with the axiom system ZF that there exists a countable family $F$ of Tarski-finite sets for which $G=\cup F$ is not countable. Such a $G$ could not be well-orderable, or even linearly orderable.....(1).Suppose we assume there is a linear order $<_L$ on $A.$ Define a relation $<_W$ on $A$ as follows: For $a,b\in A$ let $$a<_W b \iff (\;[f(a)<f(b)]\lor [f(a)=f(b)\land a<_L b]\;).$$ Observe that $<_W$ is also a linear order on $A.$ Now, by induction on $k\in N$, the set $\{b\in A :f(b)<k\}$ is finite for each $k\in N.$   Hence for each $a\in A$ the set $$pred_W (a)=\{b :b<_W a\}=\{b :f(b)<f(a)\}\cup \{b  :f(b)=f(a)\land b<_L a\}$$ is finite. ("pred" is for "predecessors".)..... Finally, for $a\in A,$ define $$g(a)=n\in N\cup \{0\} \iff pred_W (a) \text  { has exactly } n\text { members}.$$ Since $<_W$ is a linear order, we have $$a<_W b\implies a\in pred_W(b)\to g(a)<g(b).$$ So $g$ is injective and therefore $A$ is countable..... (2) Instead, suppose we assume that whenever $F=\{f_n:n\in N\}$ is a family of non-empty finite sets , there exists a choice-function $h:N\to \cup F.$ That is, $\forall n\in N\;(h(n)\in F_n).$ Now  regarding the function $f:A\to N,$ for each $n\in N$ let $F_n$ be the set of bijections from $\{a :f(a)=n\}$ to $\{j\in N :j\leq J_n\}$ where $J_n$ is the number of members of $f^{-1}\{n\}.$ (Note that $\{a:f(a)=n\}=\phi\implies F_n=\{\phi\}.$) Let $h:N\to\cup_{n\in N}F_n$ be a choice-function. Write $h(n)=h_n$ for ease of reading, as $h(n)$ is a function. Now for $a,b\in A$ define $$a<_W b \iff  [f(a)<f(b)]\;\lor \;[f(a)=f(b)=n\;\land \; h_n(a)<h_n(b)].$$ Then $<_W$ is a linear order on A and we may apply part (1). 
