Let $X=\left \{ f:\mathbb{N} \to \mathbb{N} \;\;\text{sucht that } f(f(x))=x \;\;\;\forall x \in \mathbb{N} \right \}$

Question

Let $X=\left \{ f:\mathbb{N} \to \mathbb{N} \;\;\text{sucht that } f(f(x))=x \;\;\;\forall x \in \mathbb{N} \right \}$ Then

$1).$ $X$ is finite

$2).$ $X$ is similar ro $\mathbb{N}$

$3).$$X$ is similar to $\mathbb{R}$

$4).$ $X$ is similar to $P(\mathbb{R})$ (power set of R)

I tried to solve this question but question giving no clue ,i only know one function that is $f(x)=x$ which can satisfies this but only considering this one i can't say option on is right.Also it looks like permutations group $S_{\infty}$ and elements i want to find is of order $2$ . Further i am not getting how to solve ,please give me a hint

Thankyou.

Answer 1

Finding an injective function $\Phi:\mathcal P(\Bbb N)\hookrightarrow X$ (and therefore extablishing that $\lvert X\rvert=\lvert\mathcal P(\Bbb N)\rvert=\lvert\Bbb R\rvert$) is quite easy.

Call $\Phi(A):\Bbb N\to\Bbb N$ the function such that $\Phi(A)(2n)=2n+1$ and $\Phi(2n+1)=2n$ for all $n\in A$, and such that $\Phi(A)(2k)=2k$ and $\Phi(A)(2k+1)=2k+1$ for all $k\notin A$. You can check that:

• $\Phi(A)\circ \Phi(A)=id_{\Bbb N}$ for all $A$;
• the map $G:X\to \mathcal P(\Bbb N)$, $G(f)=\left\{\frac x2\,:\, x\text{ is even }\land f(x)\ne x\right\}$ satisfies $G\circ \Phi=id_{\mathcal P(\Bbb N)}$.

The discussion is, of course, with the convention $0\in\Bbb N$.

Answer 2

You should be able to rule out (1) and (4) immediately. Now, to narrow it down further... consider a related problem of asking how many subsets of $\Bbb N$ have their complement either be infinite or have their complement be an even finite number.

Why is this related? Well, consider the special subset of your functions made in the following way: First, choose the fixed points. Then, for all non-fixed points, pair off consecutively appearing numbers and have these map to eachother. For instance, if our fixed points were $\{1,3,5,7,9,\dots\}$ then we could have $f(1)=1, f(2)=4, f(3)=3, f(4)=2, f(5)=5, f(6)=8, f(7)=7, f(8)=6,\dots$

You should be able to reason that there are at least $\mathfrak{c}$ many such subsets.

Overall number of subsets is $\mathfrak{c}$, and we are excluding only a subset of the co-finite subsets of which there are countably many.

It follows there are at least $\mathfrak{c}$ many such functions.