4.3: Método Zig-Zag de Cantor

Template:MathJaxZach

Ya hemos considerado algunas enumeraciones “fáciles”. Ahora vamos a considerar algo un poco más difícil. Considere el conjunto de pares de números naturales, que definimos en la sección 1.5 así:\[\Nat \times \Nat = \Setabs{\tuple{n,m}}{n,m \in \Nat}\nonumber\] Podemos organizar estos pares ordenados en una matriz, así:\[\begin{array}{ c | c | c | c | c | c} & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \dots \\ \hline \mathbf 0 & \tuple{0,0} & \tuple{0,1} & \tuple{0,2} & \tuple{0,3} & \dots \\ \hline \mathbf 1 & \tuple{1,0} & \tuple{1,1} & \tuple{1,2} & \tuple{1,3} & \dots \\ \hline \mathbf 2 & \tuple{2,0} & \tuple{2,1} & \tuple{2,2} & \tuple{2,3} & \dots \\ \hline \mathbf 3 & \tuple{3,0} & \tuple{3,1} & \tuple{3,2} & \tuple{3,3} & \dots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array}\nonumber\] Claramente, cada par ordenado en\(\Nat \times \Nat\) aparecerá exactamente una vez en la matriz. En particular,\(\tuple{n,m}\) aparecerá en la fila\(n\) th y\(m\) th columna. Pero, ¿cómo organizamos los elementos de tal matriz en una lista “unidimensional”? El patrón en la matriz a continuación demuestra una manera de hacer esto (aunque por supuesto hay muchas otras opciones):\[\begin{array}{ c | c | c | c | c | c | c} & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 &\dots \\ \hline \mathbf 0 & 0 & 1& 3 & 6& 10 &\ldots \\ \hline \mathbf 1 &2 & 4& 7 & 11 & \dots &\ldots \\ \hline \mathbf 2 & 5 & 8 & 12 & \ldots & \dots&\ldots \\ \hline \mathbf 3 & 9 & 13 & \ldots & \ldots & \dots & \ldots \\ \hline \mathbf 4 & 14 & \ldots & \ldots & \ldots & \dots & \ldots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots&\ldots & \ddots\\ \end{array}\nonumber\] Este patrón se llama método zig-zag de Cantor. Enumera de la\(\Nat \times \Nat\) siguiente manera:\[\tuple{0,0}, \tuple{0,1}, \tuple{1,0}, \tuple{0,2}, \tuple{1,1}, \tuple{2,0}, \tuple{0,3}, \tuple{1,2}, \tuple{2,1}, \tuple{3,0}, \dots\nonumber\] Y esto establece lo siguiente:

Proposición\(\PageIndex{1}\)

\(\Nat \times \Nat\)es contable.

Comprobante. Vamos a\(f \colon \Nat \to \Nat\times\Nat\) llevar cada uno\(k \in \Nat\) a la tupla\(\tuple{n,m} \in \Nat \times \Nat\) tal que\(k\) sea el valor de la fila\(n\) th y\(m\) th columna en la matriz zig-zag de Cantor. ◻

Esta técnica también generaliza bastante bien. Por ejemplo, podemos usarlo para enumerar el conjunto de triples ordenados de números naturales, es decir:\[\Nat \times \Nat \times \Nat = \Setabs{\tuple{n,m,k}}{n,m,k \in \Nat}\nonumber\] Pensamos en\(\Nat \times \Nat \times \Nat\) como el producto cartesiano de\(\Nat \times \Nat\) con\(\Nat\), es decir,\[\Nat^3 = (\Nat \times \Nat) \times \Nat = \Setabs{\tuple{\tuple{n,m},k}}{n, m, k \in \Nat }\nonumber\] y así podemos enumerar \(\Nat^3\)con una matriz etiquetando un eje con la enumeración de\(\Nat\), y el otro eje con la enumeración de\(\Nat^2\):\[\begin{array}{ c | c | c | c | c | c} & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \dots \\ \hline \mathbf{\tuple{0,0}} & \tuple{0,0,0} & \tuple{0,0,1} & \tuple{0,0,2} & \tuple{0,0,3} & \dots \\ \hline \mathbf{\tuple{0,1}} & \tuple{0,1,0} & \tuple{0,1,1} & \tuple{0,1,2} & \tuple{0,1,3} & \dots \\ \hline \mathbf{\tuple{1,0}} & \tuple{1,0,0} & \tuple{1,0,1} & \tuple{1,0,2} & \tuple{1,0,3} & \dots \\ \hline \mathbf{\tuple{0,2}} & \tuple{0,2,0} & \tuple{0,2,1} & \tuple{0,2,2} & \tuple{0,2,3} & \dots\\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}\nonumber\] Así, al usar un método como el método zig-zag de Cantor, podemos obtener de manera similar una enumeración de \(\Nat^3\). Y podemos seguir adelante, obteniendo enumeraciones de\(\Nat^n\) para cualquier número natural\(n\). Entonces, tenemos:

Proposición\(\PageIndex{2}\)

\(\Nat^n\)es contable, para cada\(n \in \Nat\).