En realidad, ahora que lo pienso, también se puede hacer por un argumento similar al de la diagonal de Cantor. Lo único que hay construir la matriz adecuadamente. Me pongo a ello, ya que me acabo de dar cuenta.
Por contradicción supongamos que el conjunto \( A=\{\sigma:\mathbb{N}\rightarrow\mathbb{N} : \sigma\text{ es una permutación}\} \) es numerable, entonces numerémoslo como
\( A=\{\sigma_1,\ldots,\sigma_k,\ldots\}. \)
Construimos la siguiente matriz
\( \begin{pmatrix} \sigma_1(1) & \sigma_2(1) & \cdots\\ \sigma_1(2) & \sigma_2(2) & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix}, \)
y cada entrada la modificamos poniendo el valor \( 0 \) si es par y el valor \( 1 \) si es impar, esto es queda la matriz
\( M = \begin{pmatrix} \phi(\sigma_1(1)) & \phi(\sigma_2(1)) & \cdots\\ \phi(\sigma_1(2)) & \phi(\sigma_2(2)) & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix}, \)
donde \( \phi(n) = \left\{\begin{array}{ll} 0 & \text{ si } n \text{ es par,}\\ 1 & \text{ si } n \text{ es impar.}\\\end{array}\right. \)
Si aplicamos el argumento de diagonal de Cantor a la matriz \( M \), esto es quedarnos con la diagonal \( (\phi(\sigma_1(1)),\phi(\sigma_2(2)),\ldots) \) y cambiarle el valor, si es cero lo transformamos en 1 y si es 1 se transforma en 0, esto es consideramos el elemento \( v=(\overline{\phi(\sigma_1(1))},\overline{\phi(\sigma_2(2))},\ldots) \), donde \( \overline{0} = 1 \) y \( \overline{1}=0 \). Se verifica que \( v \) no puede ser ninguna columna de la matriz \( M \), pero esto contradice que no esté dicha combinación (¿esto se podría demostrar? Creo que no es inmediato...).
Perdón, pensé que funcionaría la idea, pero ahora que lo escribo me es difícil argumentar de que el elemento \( v \) deba ser una combinación válida (¿quién quita que no sea todo cero y por tanto no debería de estar en \( M \)?). El problema es que son biyecciones, con funciones en general el argumento sí es válido, pero al ser biyecciones no es inmediato (y de hecho no estoy seguro de que funciones) el argumento.
Pido disculpas por no completarlo, pensaba borrar este mensaje, pero por si acaso a alguien se le ocurre alguna forma de arreglarlo pues aquí lo dejo.