Problema: Demostrar que el conjunto de todas las funciones biyectivas sobre los números naturales es incontable.
Ya he visto muchas respuestas a este problema y parece que siempre hay una parte en la que los números naturales se dividen en dos subconjuntos infinitos contables de $\mathbb{N}$ . ¿Me estoy perdiendo algo? He llegado a la siguiente prueba y sospecho que puede haber un error en alguna parte.
Utilizo el hecho de que existe una biyección entre el conjunto de todas las funciones biyectivas sobre $\mathbb{N}$ y el conjunto de todas las permutaciones de $\mathbb{N}$ . Esa parte no debería ser el problema por lo que tengo entendido.
Utilizo el argumento de la diagonalización de Cantor de la siguiente manera: Sea $\pi_{i}$ sea la permutación i-ésima en una lista de todas las permutaciones en $\mathbb{N}$ . La capacidad de enumerar todas las permutaciones nos daría una enumeración que haría el conjunto contable, por lo tanto asumimos que tal lista existe y hacemos una prueba por contradicción:
Sea la lista de todas las permutaciones $(\pi_{1},\pi_{2},\pi_{3},\pi_{4},...)$ definimos ahora una permutación $\pi$ de la siguiente manera:
$\pi(0) \in $ $\mathbb{N} \backslash \{\pi_{1}(0)\} $
$\pi(1) \in $ $\mathbb{N} \backslash \{\pi(0), \pi_{2}(1)\} $
$\pi(2) \in $ $\mathbb{N} \backslash \{\pi(0), \pi(1), \pi_{3}(2)\} $
.
.
.
$\pi(k) \in $ $\mathbb{N} \backslash \{\pi(0), \pi(1), ...,\pi(k - 1), \pi_{k+1}(k)\} $
Entonces concluiría la prueba afirmando que la permutación anterior no está en la lista, lo cual es una contradicción con nuestra suposición y, por tanto, el conjunto de todas las permutaciones no puede ser contable, siendo por tanto incontable. ¿Es esto correcto? Agradezco la ayuda.
