So I wanna show that if $Y$ is an infinite countable set (i.e. there exists a surjection $\phi: \mathbb{N} \to A$), then there exists a bijection $\psi: \mathbb{N} \to A$. Here's what I came up with.
Define a sequence of maps $f_{i} : \mathbb{N} \to A, i \in \mathbb{N}$ as follows: Set $f_0 = \phi$, and construct $f_{i}$ by setting $f_{i} = f_{i - 1}$ if $f_{i - 1}$ is an injection, and if not let $ f_{i}(x) = \begin{cases} f_{i - 1}(x) & x < \min \{ x \in \mathbb{N} : (\exists x' < x)(f_{i - 1}(x') = f_{i - 1}(x) \\ f_{i - 1}(x + 1) & \textrm{otherwise} \end{cases}$. That is, since we're trying to make an injective map, the next map in the sequence is made by taking the first instance of "repetition" in $f_{i - 1}$, taking it out and sliding it along. So if $f_{i - 1} = (1, 2, 3, 4, 5, 1, 6, 7, 8, 9, 10, 9, 15, 19, 23, \ldots)$, then $f_{i} = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 15, 19, 23, \ldots)$. I then want to take a sort of "limit" of these $f_{i}$ to come up with a new map that has no repetition. So construct the map $g_{i} : A \to \mathbb{N}$ by $g_{i}(a) = \min \{ x \in \mathbb{N} : f_{i}(x) = a \}$. Then since $(g_{i}(a))_{i \in \mathbb{N}}$ is a bounded monotonic sequence in $\mathbb{N}$, there exists $\lim_{i \to \infty} g_{i}(a) = \min \{ g_{i}(a) : i \in \mathbb{N} \} = : g_{\infty}(a)$.
I want to show $g_{\infty} : A \to \mathbb{N}$ is a bijection, and then set $\psi = g_{\infty}^{- 1}$.
First we show $g_{\infty}$ is injective. Suppose to the contrary that there exists $x_{0} \in \mathbb{N}$ for which there exist distinct $a, a' \in A$ such that $g_{\infty}(a) = g_{\infty}(a') = x_{0}$. Recall that $(g_{i}(a))_{i \in \mathbb{N}}$ is a downward monotonic sequence in $\mathbb{N}$, so there exist $i, i' \in \mathbb{N}$ for which $g_{i}(a) = g_{i'}(a') = x_{0}$. Suppose without loss of generality that $i \geq i'$. Then $f_{i}(x_{0}) = a$ and $f_{i}(x_{0}) = a'$, where $a \neq a'$, a contradiction. Thus $g$ is injective.
Second we show it is surjective, which we again do by suppose to the contrary that $g_{\infty}$ is not surjective. If $y \in \mathbb{N} \setminus g_{\infty}(A)$, then there does not exist $i_{y} \in \mathbb{N}$ such that $f_{i}(y) = f_{i_{y}}(y)$ for all $i \geq i_{y}$. Let $y_{0} = \min (\mathbb{N} \setminus g_{\infty}(A))$. Then for each $x \in \{ 1, \ldots, y_{0} - 1 \}$ exists $a_{x}$ such that $g_{\infty}(a_{x}) = x$. In fact, there exists $i_{0}$ such that for all $i \geq i_{0}$ we have $g_{i}(a_{x}) = x$, and thus $f_{i}(x) = a_{x}$ for $x < y_{0}$. Let $x_{0} = \min \{ x \geq y_{0} : (\nexists x' < x)(f_{i_{0}}(x) = f_{i_{0}}(x')) \}$, i.e. the first element of $\mathbb{N}$ to map to a "new" element in $f_{i_{0}}$.
We claim $g_{\infty}(f_{i_{0}}(x_{0})) = y_{0}$. Let $\ell = x_{0} - y_{0}$. We claim that $f_{i_{0} + \ell}(y_{0}) = f_{i_{0}}(x_{0})$.* But this means that in fact $y_{0} \neq \min (\mathbb{N} \setminus g_{\infty}(A))$, so we have a contradiction. This concludes the proof.
Is the above correct?
*I just realized I'm not entirely sure how to demonstrate this.
