Cardinality of a quotient set $\mathbb{N}^\mathbb{N}/\sim$

Question

I'm having trouble with the following task:

On the set of all functions $\mathbb{N}^\mathbb{N}$ an equivalence relation $\sim$ is defined in the following way:

$f \sim g \iff \forall n \in \mathbb{N}. f(f(n)) = g(g(n))$.

Prove that the quotient set $\mathbb{N}^\mathbb{N}/\sim$ is uncountable.

I've tried to find an injective function from $\mathbb{N}^\mathbb{N}$ to $\mathbb{N}^\mathbb{N}/\sim$ and I've tried proving that every equivalence class has only one element, but I haven't succeeded in either of the attempts. I can't even figure out what would be the main idea needed for the proof.

Answer 1

For each $A\subseteq\Bbb N\setminus\{0,1\}$ let

$$f_A:\Bbb N\to\Bbb N:n\mapsto\begin{cases} 0,&\text{if }n\in A\cup\{0\}\\ 1,&\text{otherwise;} \end{cases}$$

then $f_A\circ f_A=f_A$, so the function

$$\varphi:\wp(\Bbb N\setminus\{0,1\})\to{^{\Bbb N}\Bbb N}/\!\sim\;:A\mapsto[f_A]_\sim$$

is an injection.