Cardinality of the set of all involutions from $\mathbb N$ to itself

Question

The following is a section in my homework, I couldnt solve it so I'm asking for some help.

I have the following set : $\{f:\mathbb N \to \mathbb N | f(f(a)) = a \text{ for all } a\in \mathbb N\}$.

I need to find if this set is a finite set, countably infinite set ($\aleph_0$) or infinite and uncountable.

Thanks in advance for your help

Answer 1

Hint. There is an injection from the set of binary strings that have infinitely many of both $1$s and $0$s, to the set of functions $f = f^{-1}$. Note that the latter is equivalent to the set of partitions of $\mathbb N$ into sets of disjoint pairs.

Answer 2

HINT: Prove that there exists one such $f$ for which $f(x)\neq x$, for all $x$. Then use this fact to show that for every infinite $A\subseteq\Bbb N$, there exists a function $f_A$ such that $f_A(a)\neq a\iff a\in A$; and $f_A(f_A(a))=a$ for every $a\in\Bbb N$.

Answer 3

One step beyond: This set is, at least, infinite countable (Alef-sub0). For every pair (n,m) of natural numbers (and they are Alef-sub0) we define f(n)=m and f(m)=n, out of this the function is the identify, i.e. f(x)=x. I guess we can go furher and prove the cardinal of this set is c, but I need to go to beed now. Hope it helps.