Function composition giving the same value

Question

Let $A = \{f: \mathbb N \rightarrow \mathbb N$ | $\forall n\in \mathbb N \ \ \exists p \ge 1 \ \ f^p(n)=n$}

What is $\overline{\overline{A}}$?

Answer 1

This is the set of functions in $S_{\mathbb{N}}$ whose cycle decomposition consists of finite cycles only (an infinite cycle is just some shift on an infinite set). The cardinality is clearly that of the continuum.

Answer 2

Hint: $\overline{\overline{B}}\le\overline{\overline{A}}\le2^{\aleph_0}$ where $B=\{f:\mathbb N\to\mathbb N$ | $\forall n\in\mathbb N\ \ f(f(n))=n\}$.

For each set $X\subseteq\mathbb N$ there is an involution $f_X\in B$ which swaps $2n$ with $2n-1$ for each $n\in X$ while leaving everything else fixed.

Answer 3

For every real number $x$ between 0 and 1 whose decimal expansion does not have a zero, it is easy to describe an element $f_x$ of A in a one-one way, and consequently $A$ will be uncountable.

An example is less messier to write than a formula for general $x$.

Let $x= 0.317$.

Corresponding $f_x$ sends the first 3 natural numbers in a 3-cycle, the next number is fixed, the next 7 numbers are sent in a 7-cycle. In this case, $x$ has terminating-decimal expansion and we can agree to keep all the numbers exceeding the 'digital sum' to be fixed points. Otherwise we will get a function $f_x$ with $f_x(n)\neq n$ for infinitely many $n$.