Permutations

S(IN) l'ensemble des permutations de IN est-il dénombrable ?

Non. S(IN) est equipotent a S(X) pour tout X infinie denombrable. Pour un sous-ensemble J de X (assez grand) il existe une permutation sigma_J de IN dont l'ensemble des points fixes est exactement IN\J car:
1- Si J est finie, on le permute cycliquement, et on laisse tout ce qui est en dehors de J fixe.
2- Si J est infinie, encore on fixe tout ce qui est en dehors de J. De plus, J est equipotent a Z-{0} ou on a une permutation (x-> -x) sans points fixes, qu'on peut transporter a J.

Par définition, J = l'ensemble des points fixe de sigma_J. S(N) contient alors un partie équipotent a P(N) qui est déjà non-denombrable. D'ou le résultat.

C'est ca l'idée, bien vu.

Soit f: P(IN)\ {vide} --->S(IN) définie par : pour AcIN (non vide) , f(A) est la permutation dont les éléments de A y sont les seuls points fixes.
il est clair que f est injective et comme P(IN) est non dénombrable alors S(IN) aussi