I want to show that the image of the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ is countably infinite.
Notice that $\varphi = i \circ b \circ p$ where $p$ is a surjective map, $b$ is a bijective map and $i$ is an injective map. More specifically, let $\sim$ be the relation on the set $\mathbb{N} \times \mathbb{N}$ such that $$x \sim y \iff \varphi(x) = \varphi(y)$$ This is trivially an equivalence relation.
Denote the equivalence class of $a$ as $[a]_{\sim}$ and the quotient set as $\mathbb{N}/{\sim}$.
Take the map $p: \mathbb{N} \to \mathbb{N}/{\sim}$ such that $p(n) = [n]_{\sim}$. This is surjective. Now, take $b: \mathbb{N}/{\sim} \to \text{Im}(\varphi)$ as $b([n]_{\sim}) = \varphi(n)$. One can prove that this map is bijective. Finally, $i: \text{Im}(\varphi) \to \text{Im}(\varphi)$ is just the inclusion map, i.e., $i(\varphi(n)) = \varphi(n)$.
With this, one can write $\varphi = b \circ p$ because adding $i$ will not change anything. Since $b$ is bijective, $|\mathbb{N}/{\sim}| = |\text{Im}(\varphi)|$. My goal is also to prove $|\text{Im}(\varphi)| = |\mathbb{N}|$, and hence, countably infinite.
I tried using the map $\beta: \mathbb{N}/{\sim} \to \mathbb{N}$ such that $$\beta ([n]_{\sim}) = m \iff \varphi(n) = \varphi(m)$$ for some fixed $m \in [n]_{\sim}$.
I proved that this is well-defined and that this is injective, but I am having trouble checking that this map is surjective. I tried the following:
Surjectivity
Take $n \in \mathbb{N}$. Trivially, $n \in [n]_{\sim}$. So, fixing $n$, gives: $$\beta([n]_{\sim}) = n$$
Is this true?
To be honest, I think that it is a lot easier than you think. By definition do you have $$\mbox{Im}(\varphi)=\{\varphi(n):n\in\mathbb{N}\}$$ and thus $|\mbox{Im}(\varphi)|\leq |\mathbb{N}|,$ thus it is at maximum countably infinite. And thus you only have to show that it cannot be finite and that follows from $\phi$ on the set of primes, since $\varphi$ is injective on the set of primes.