Esistenza di una funzione $NN \to NN$ - surely known

[Gabriel6]

Sia $F$ l'insieme delle funzioni $NN \to NN$, dove $NN = \{1, 2, \ldots\}$. Per ogni $f \in F$ ed ogni $k \in NN \cup \{0\}$, poniamo $f^{(k+1)} = f \circ f^{(k)}$, con $f^{(0)} = 1_NN$ (l'identità). Se $k$ è un intero $\ge 2$, esiste $f \in F$ \ $\{1_NN\}$ tale che $f^{(k)}(n) = n$, per ogni $n \in NN$?

[vict85]

"Gabriel":Sia $F$ l'insieme delle funzioni $NN \to NN$, dove $NN = \{1, 2, \ldots\}$. Per ogni $f \in F$ ed ogni $k \in NN \cup \{0\}$, poniamo $f^{(k+1)} = f \circ f^{(k)}$, con $f^{(0)} = 1_NN$ (l'identità). Se $k$ è un intero $\ge 2$, esiste $f \in F$ \ $\{1_NN\}$ tale che $f^{(k)}(n) = n$, per ogni $n \in NN$?

Prendiamo l'insieme delle permutazioni di un insieme numerabile di elementi (come è $NN$). Possiamo vedere ogni elemento di questo insieme come composizione di cicli (non necessariamente finiti) disgiunti. Dato un insieme di cicli disgiunti possiamo determinare il periodo della loro composizione semplicemente facendo il minimo comun multiplo dell'ordine di ogni ciclo.
Ogni permutazione è una biiezione e quindi $S_oo \subset F$ . L'ugualianza $f^{k}=1_NN$ è equivalente a dire che l'ordine di $f$ in $F$ è $k$. Questo avviene se il mcm dell'ordine dei cicli che lo compongono è $k$. Un esempio può essere la funzione che è formata da soli $k$-cicli. Un esempio con $k=2$ può essere la funzione che scambia un numero dispari con il pari che lo segue.

[Gabriel6]

Ok.

[vict85]

Ovviamente $1_NN$ è l'unica funzione per cui $AA k \ge 2,n in NN, f^k(n) = n$

La dimostrazione è semplice.

Nel senso che $f^2(n) = n$ allora $f(f(n))=n$ quindi f è fatto di scambi o è uguale a $1_NN$.
Ma abbiamo anche che $f^3(n)=n$ ma $f^2(n) = n$ e quindi $f(n)=n$ cioé $f=1_NN$


La dimostrazione che ho fatto sopra usava le permutazioni ma le stesse cose possono essere ricavate osservando semplicemente $f^k=I_NN$ nel senso che essendo $f^(k)(n)=f^0(n)$ si ha che $f^s(n)=f^r(n)$ dove $r$ è il resto delle divisione di $s$ per $k$ quindi il "periodo" di $n$ deve essere un divisore di $k$.

[Gabriel6]

Non v'è dubbio alcuno.