Consider a finite set $X$ and let's denote by $F$ the set of all maps defined on $X$ with values in $\mathbb{N}$.
- How to prove that $F$ is countable.
Let $\pi_1, \pi_2 \in F$. We define the binary relation $\mathcal{R}$ as follows $\pi_1 \mathcal{R} \pi_2$ if $\forall i,j \in X, \pi_1(i) \leq \pi_1(j) \Leftrightarrow \pi_2(i) \leq \pi_2(j)$.
In other words, both functions are "ordering" the elements of $X$ in the same way. Obviously it's an equivalence relation.
2.How to compute the cardinal of the quotient set $F/ \mathcal{R}$
HINT: If you’ve already seen that $\Bbb N^n$ is countable for each positive integer $n$, for (1) you could list $X=\{x_1,x_2,\ldots,x_n\}$ and find a bijection between $F$ and $\Bbb N^n$. For (2), observe that each $f\in F$ defines a preorder (or quasiorder) on $X$. There’s a connection between these preorders and the relation $\mathcal{R}$.