2.1 Ordenes naturales sobre \(\Sigma^{\ast}\)

En esta sección daremos biyecciones naturales entre \(\Sigma^{\ast}\) y \(\omega\), para cada alfabeto no vacío \(\Sigma\). Dichas biyecciones dependen de tener asociado a \(\Sigma\) un orden total, el cual nos permite de manera “lexicográfica” listar con el tipo de orden de \(\omega\) a todos los elementos de \(\Sigma^{\ast}\). El tratamiento de este tema fue sacado del libro de Davis y Weyuker.

Primero haremos un caso particular pero que tiene un interés extra ya que esta emparentado con nuestra notación decimal clásica de los números de \(\omega\).

2.1.1 Notación decimal sin \(0\)

Llamaremos numerales a los siguientes símbolos \[0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\] Usaremos \(Num\) para denotar el conjunto de numerales. Nótese que \(Num\cap\omega=\emptyset\). Es decir, no debemos confundir los símbolos que usualmente denotan los primeros diez números enteros con los números que ellos denotan. De hecho en china o japón los primeros diez números enteros se denotan con otros símbolos. Similarmente las palabras pertenecientes a \(Num^{\ast}\) denotan (notación decimal) a los números de \(\omega\) pero debemos tener en cuenta que \(Num^{\ast}\cap\omega=\emptyset\). Cuando tratamos con palabras de \(Num^{\ast}\), debemos ser cuidadosos ya que muchas veces en nuestro discurso matemático (es decir las guías, el apunte, lo que escriben los profesores en el pizarrón, etc) representamos dos objetos diferentes de la misma forma. Por ejemplo \(45\) puede estar denotando al número entero cuarenta y cinco o también \(45\) puede estar denotando la palabra de longitud \(2\) cuyo primer símbolo es el numeral \(4\) y cuyo segundo símbolo es el numeral \(5\), es decir ella misma. Por dar otro ejemplo, el símbolo \(1\) en nuestro discurso algunas veces se denotará a si mismo y otras veces denotará al número uno.

Es bien conocido que, en notación decimal, las siguientes palabras del alfabeto \(Num\), denotan, de menor a mayor, a los números de \(\omega\) \[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...\] Por supuesto esta lista de palabras es infinita pero asumimos que el lector sabe como obtener la palabra siguiente a cada miembro de la lista (i.e. sumar 1 en notación decimal), lo cual determina por completo la lista conociendo que la misma comienza con la palabra \(0\).

Cabe destacar que debido a la presencia del numeral \(0\) en la lista, la \(n\)-ésima palabra representa (o denota) al número \(n-1\). Dicho de otra forma, el número \(n\in\omega\) es representado por la \((n+1)\)-ésima palabra de la lista.

Un detalle de la representación decimal de números de \(\omega\) mediante palabras de \(Num^{\ast}\) es que la misma no nos da una biyección entre \(Num^{\ast}\) y \(\omega\) ya que por ejemplo las palabras \(00016\) y \(16\) representan el mismo número. Dicho de otra forma en la lista anterior no figuran todas las palabras de \(Num^{\ast}\), a saber están omitidas todas las palabras que comienzan con el símbolo \(0\) y tienen longitud mayor que uno. A continuación daremos una representación de los números de \(\omega\) mediante palabras, la cual no tendrá este problema. El alfabeto que usaremos tendrá todos los numerales menos el \(0\) y además tendrá un símbolo para denotar al número diez, a saber el símbolo \(d\). Es decir \[\widetilde{Num}=\{1,2,3,4,5,6,7,8,9,d\}\] Representaremos a los números de \(\omega\) con la siguiente lista infinita de palabras de \(\widetilde{Num}\)

\(\varepsilon,1,2,3,4,5,6,7,8,9,d,\)

\(11,12,...,1d,21,22,...,2d,...,91,92,...,9d,d1,d2,...,dd,\)

\(111,112,...,11d,121,122,...,12d,...\)

El lector ya se habrá dado cuenta de que el siguiente a una palabra \(\alpha\) de la lista anterior se obtiene aplicando las siguientes clausulas

1. adhocprefix(1)adhocsufix Si \(\alpha=d^{n}\), con \(n\geq0\) entonces el siguiente de \(\alpha\) es \(1^{n+1}\)

2. adhocprefix(2)adhocsufix Si \(\alpha\) no es de la forma \(d^{n}\), con \(n\geq0\), entonces el siguiente de \(\alpha\) se obtiene de la siguiente manera:

   1. adhocprefix-adhocsufix buscar de derecha a izquierda el primer símbolo no igual a \(d\)

   2. adhocprefix-adhocsufix reemplazar dicho símbolo por su siguiente en la lista \(1,2,3,4,5,6,7,8,9,d\)

   3. adhocprefix-adhocsufix reemplazar por el símbolo \(1\) a todos los símbolos iguales a \(d\) que ocurrían a la derecha del símbolo reemplazado

Para hacer las cosas mas formalmente, definamos \(s:\widetilde{Num}^{\ast}\rightarrow\widetilde{Num}^{\ast}\) de la siguiente manera

1. adhocprefix-adhocsufix \(s(d^{n})=1^{n+1}\), para cada \(n\geq0\)

2. adhocprefix-adhocsufix \(s(\alpha1d^{n})=\alpha21^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

3. adhocprefix-adhocsufix \(s(\alpha2d^{n})=\alpha31^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

4. adhocprefix-adhocsufix \(s(\alpha3d^{n})=\alpha41^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

5. adhocprefix-adhocsufix \(s(\alpha4d^{n})=\alpha51^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

6. adhocprefix-adhocsufix \(s(\alpha5d^{n})=\alpha61^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

7. adhocprefix-adhocsufix \(s(\alpha6d^{n})=\alpha71^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

8. adhocprefix-adhocsufix \(s(\alpha7d^{n})=\alpha81^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

9. adhocprefix-adhocsufix \(s(\alpha8d^{n})=\alpha91^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

10. adhocprefix-adhocsufix \(s(\alpha9d^{n})=\alpha d1^{n}\) , cada vez que \(\alpha\in\widetilde{Num}^{\ast}\) y \(n\geq0\)

Nótese que la definición de \(s\) es correcta ya que una palabra de \(\widetilde{Num}^{\ast}\) ya sea es de la forma \(d^{n}\), con \(n\geq0\), o es de la forma \(\alpha\delta d^{n}\), con \(\alpha\in\widetilde{Num}^{\ast}\), \(\delta\in\widetilde{Num}-\{d\}\) y \(n\geq0\); y estos casos posibles son mutuamente excluyentes.

Claramente se tiene entonces que la lista anterior puede ser escrita de la siguiente manera \[\varepsilon,s(\varepsilon),s(s(\varepsilon)),s(s(s(\varepsilon))),s(s(s(s(\varepsilon)))),...\]

Y como ya dijimos, pensamos que las palabras de la lista van representando en forma creciente los elementos de \(\omega\):

1. adhocprefix-adhocsufix El número \(0\) es representado en la lista anterior con la palabra \(\varepsilon\)

2. adhocprefix-adhocsufix El número \(1\) es representado en la lista anterior con la palabra \(1\)

   \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\)

3. adhocprefix-adhocsufix El número \(9\) es representado en la lista anterior con la palabra \(9\)

4. adhocprefix-adhocsufix El número \(10\) es representado en la lista anterior con la palabra \(d\)

5. adhocprefix-adhocsufix El número \(11\) es representado en la lista anterior con la palabra \(11\)

   \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\)

6. adhocprefix-adhocsufix El número \(19\) es representado en la lista anterior con la palabra \(19\)

7. adhocprefix-adhocsufix El número \(20\) es representado en la lista anterior con la palabra \(1d\)

8. adhocprefix-adhocsufix El número \(21\) es representado en la lista anterior con la palabra \(21\)

9. adhocprefix-adhocsufix El número \(22\) es representado en la lista anterior con la palabra \(22\)

   \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\)

Como puede notarse en estos primeros veinte y pico números solo dos (el \(0\) y el \(20\)) se representan en forma distinta a la representación decimal clásica. Es natural que \(\varepsilon\) denote al número \(0\) y además nótese que la palabra \(1d\) (que en la lista representa el \(20\)) puede leerse como "diecidiez" (es decir la palabra que sigue a "diecinueve") que justamente es \(20\). Por supuesto con esta manera de pensar la palabra \(2d\) deberíamos leerla como "ventidiez" y si nos fijamos en la lista ella representa al número treinta lo cual nuevamente es muy natural. Otro ejemplo: a \(6d\) deberíamos leerla como "sesentidiez" y es natural ya que en la lista representa al setenta. También, la palabra \(9d\) puede leerse noventidiez ya que representa en la lista al número \(100\).

La lista anterior va representando los números de \(\omega\) en forma muy natural pero aunque nuestra intuición nos diga que no, en principio podría pasar que una misma palabra del alfabeto \(\widetilde{Num}\) ocurra dos veces en la lista y esto nos diría que una misma palabra estaría representando a dos números distintos. También, en principio podría suceder que haya una palabra del alfabeto \(\widetilde{Num}\) la cual nunca figure en la lista. Mas abajo probaremos que estas dos posibilidades no suceden, es decir mostraremos que

1. adhocprefix(S)adhocsufix Toda palabra de \(\widetilde{Num}^{\ast}\) aparece en la lista

2. adhocprefix(I)adhocsufix Ninguna palabra de \(\widetilde{Num}^{\ast}\) aparece mas de una ves

Nótese que la propiedad (S) nos dice que la función \[\begin{array}[t]{rll} \ast:\omega & \rightarrow & \widetilde{Num}^{\ast}\\ n & \rightarrow & (n+1)\text{-esimo elemento de la lista }\text{=\ensuremath{\overset{n\text{ veces}}{\overbrace{s(...s(s(}}\varepsilon}))...)} \end{array}\] es suryectiva y la propiedad (I) nos garantiza que dicha función es inyectiva, por lo cual entre las dos nos garantizan que dicha representación establece una biyección entre \(\omega\) y \(\widetilde{Num}^{\ast}\).

Por supuesto, la pregunta que inmediatamente surge es como calcular la inversa de \(\ast\). Llamemos \(\#\) a la inversa de \(\ast\). Nótese que dada una palabra \(\alpha\in\widetilde{Num}^{\ast}\), el número \(\#(\alpha)\) es justamente el número representado por la palabra \(\alpha\), o dicho de otra forma \(\#(\alpha)\) es la posición que ocupa \(\alpha\) en la lista, contando desde el \(0\) (es decir \(\alpha\) es la \((\#(\alpha)+1)\)-ésima palabra de la lista). Por ejemplo: \[\begin{gathered} \#(\varepsilon)=0\\ \#(1)=1\\ \vdots\\ \#(9)=9\\ \#(d)=10\\ \#(11)=11\\ \#(12)=12\\ \vdots\\ \#(19)=19\\ \#(1d)=20 \end{gathered}\] Aquí hay que tener cuidado como leemos las igualdades anteriores. Por ejemplo en la igualdad \[\#(1)=1\] la primera ocurrencia del símbolo \(1\) se refiere al numeral uno, es decir denota una palabra y la segunda ocurrencia se esta refiriendo al número uno, es decir denota un número.

Dejamos al lector el ejercicio de ganar intuición con ejemplos hasta que se convenza de que tal como en el caso de la notación decimal, el número \(\#(\alpha)\) se expresa como una suma de potencias de \(10\), con los coeficientes dados en función de los símbolos de \(\alpha\). Mas concretamente si \(\alpha=s_{1}s_{2}...s_{k}\) con \(k\geq1\) y \(s_{1},s_{2},...,s_{k}\in\widetilde{Num}\), entonces \[\#(\alpha)=\#(s_{1}).10^{k-1}+\#(s_{2}).10^{k-2}+...+\#(s_{k}).10^{0}\] No daremos aquí una prueba de este hecho ya que lo probaremos abajo para el caso general. Para ganar intuición sobre el mismo el lector puede ver mas abajo la prueba de las propiedades (S) e (I), desde donde se ve con mas claridad como va aumentando la función \(\#\) a medida que recorremos la lista de izquierda a derecha. Algunos ejemplos \[\begin{aligned} \#(1d) & =1.10^{1}+10.10^{0}=10+10=20\\ \#(dd) & =10.10^{1}+10.10^{0}=100+10=110\\ \#(111) & =1.10^{2}+1.10^{1}+1.10^{0}=100+10+1=111\\ \#(1d3d) & =1.10^{3}+10.10^{2}+3.10^{1}+10.10^{0} \end{aligned}\]

Ahora que sabemos que las palabras de \(\widetilde{Num}\) representan los números como suma de potencias de diez, en forma análoga a la notación decimal clásica, podemos reforzar aun mas la analogía poniendo nombres adecuados que, tal como en el caso clásico, nos permitan leer las palabras de \(\widetilde{Num}\) describiendo su suma de potencias asociada. Por ejemplo podríamos llamar "decenta" al número \(100\), por analogía a "treinta", "cuarenta",...,"noventa". O sea una decenta es diez veces diez. De esta forma la palabra \(d1\) se leerá "decenta y uno" y esto es natural ya que en la lista representa al \(101\). La palabra \(dd\) se leerá "decenta y diez" y esto describe a la perfección el número que representa, i.e. el \(10.10+10=110\). La palabra que sigue en la lista a \(dd\) es \(111\) la cual representa al \(111\), es decir aquí como en los otros casos vistos en los cuales no hay ocurrencias del símbolo \(d\) la palabra representa al mismo número que representa en la notación decimal clásica. Por dar otro ejemplo, la palabra \(59d3\) se leerá "cinco mil novecientos decenta y tres" y representara al número \(6003\).

Para seguir debemos ponerle nombre a "diez veces cien", es decir, "decientos" (por analogía con "novecientos = nueve veces cien") denotará al número \(1000=10.100\). De esta forma la palabra \(d51\) se leerá "decientos cincuenta y uno" y esto es natural ya que pensando un rato se puede ver que ella representa al \(1051\). También, la palabra \(ddd\) se leerá "decientos decenta y diez" y representara al número \(1110\). En la página granlogico.com hay un programa hecho por Guido Ivetta el cual hace lo siguiente:

1. adhocprefix-adhocsufix Dado un número \(n\) expresado en notación clásica decimal da explícitamente la palabra \(*(n)\) y la forma de pronunciarla o leerla a dicha palabra

2.1.1.1 Prueba de las propiedades (S) e (I)

Dado que el siguiente a un elemento \(\alpha\) de la lista es de la misma longitud que \(\alpha\) o tiene longitud igual a \(\left\vert \alpha\right\vert +1\), podemos representar la lista anterior de la siguiente manera: \[B_{0};B_{1};B_{2};B_{3};B_{4};...\] donde cada \(B_{n}\) es, por definición, la parte de la lista en la cual las palabras tienen longitud exactamente \(n\). Por ejemplo:

1. adhocprefix-adhocsufix \(B_{0}\) es \(\varepsilon\)

2. adhocprefix-adhocsufix \(B_{1}\) es \(1,2,3,4,5,6,7,8,9,d\)

3. adhocprefix-adhocsufix \(B_{2}\) es \(11,12,...,1d,21,22,...,2d,...,91,92,...,9d,d1,d2,...,dd\)

Nótese que hasta el momento nada nos asegura que no suceda que para algún \(n\) se dé que \(B_{n}\) sea una lista infinita, lo cual además nos diría que los bloques \(B_{n+1},B_{n+2},...\) son todos vacíos. Es decir podría pasar que la lista se estanque en una longitud \(n\) y nunca aparezca una palabra de longitud mayor que \(n\). Esto por supuesto obligaría a que se repitan muchas veces palabras de dicha longitud \(n\) ya que hay una cantidad finita de las mismas (\(10^{n}\)).

Por supuesto nuestra intuición nos dice que en el bloque \(B_{n}\) están listadas sin repetición todas las palabras de \(\widetilde{Num}^{\ast}\) de longitud \(n\), pero debemos justificar esto con argumentos sólidos. Algunas propiedades básicas que se pueden probar fácilmente son:

1. adhocprefix(1)adhocsufix Si \(B_{n}=\alpha_{1},...,\alpha_{k}\), entonces \(\alpha_{1}=1^{n}\) y \(\alpha_{k}=d^{n}\)

2. adhocprefix(2)adhocsufix \(d^{n}\) ocurre en \(B_{n}\) solo en la última posición

estas propiedades son consecuencias inmediatas de como se calcula el elemento siguiente a uno dado en la lista y son dejadas como ejercicio. Otra propiedad importante es la siguiente

1. adhocprefix(3)adhocsufix Si \(B_{n}=\alpha_{1},...,\alpha_{k}\), entonces \(B_{n+1}=1\alpha_{1},...,1\alpha_{k},2\alpha_{1},...,2\alpha_{k},...,d\alpha_{1},...,d\alpha_{k}\)

Para probar (3) es muy útil el siguiente resultado obvio

Dejamos como ejercicio al lector hacer la prueba de (3) usando el lema anterior y las propiedades (1) y (2). Usaremos a continuación (3) para probar:

1. adhocprefix(4)adhocsufix Para cada \(n\in\omega\) se tiene que \(B_{n}\) es una lista sin repeticiones de todas las palabras de longitud \(n\)

Probaremos (4) usando la Regla de Inducción a partir de \(0\). Para cada \(n\in\omega\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:

• \(\mathrm{Enu}_{n}\): \(B_{n}\) es una lista sin repeticiones de todas las palabras de longitud \(n\).

Es claro que \(\mathrm{Enu}_{0}\) es verdadero. Además es claro que (3) nos garantiza que si \(\mathrm{Enu}_{n}\) es verdadero, entonces \(\mathrm{Enu}_{n+1}\) lo es. O sea que la Regla de Inducción a partir de \(0\) nos dice que todos los enunciados son verdaderos por lo cual (4) lo es.

Finalmente nótese que de (4) se desprenden en forma obvia las propiedades (S) y (I).

2.1.2 El caso general

Sea \(\Sigma\) un alfabeto no vacío y supongamos \(\leq\) es un orden total sobre \(\Sigma\). Supongamos que \(\Sigma=\{a_{1},...,a_{n}\}\), con \(a_{1}<a_{2}<...<a_{n}\). Inspirados en la lista dada anteriormente de las palabras de \(\widetilde{Num}^{\ast}\), podemos dar la siguiente lista de palabras de \(\Sigma^{\ast}\)

\({\small \varepsilon,a}_{1}{\small ,a}_{2}{\small ,...,a}_{n}{\small ,}\)

\({\small a}_{1}{\small a}_{1}{\small ,a}_{1}{\small a}_{2}{\small ,...,a}_{1}{\small a}_{n}{\small ,a}_{2}{\small a}_{1}{\small ,a}_{2}{\small a}_{2}{\small ,...,a}_{2}{\small a}_{n}{\small ,...,a}_{n}{\small a}_{1}{\small ,a}_{n}{\small a}_{2}{\small ,...,a}_{n}{\small a}_{n}{\small ,}\)

\({\small a}_{1}{\small a}_{1}{\small a}_{1}{\small ,a}_{1}{\small a}_{1}{\small a}_{2}{\small ,...,a}_{1}{\small a}_{1}{\small a}_{n}{\small ,a}_{1}{\small a}_{2}{\small a}_{1}{\small ,a}_{1}{\small a}_{2}{\small a}_{2}{\small ,...,a}_{1}{\small a}_{2}{\small a}_{n}{\small ,...,a}_{1}{\small a}_{n}{\small a}_{1}{\small ,a}_{1}{\small a}_{n}{\small a}_{2}{\small ,a}_{1}{\small a}_{n}{\small a}_{n}{\small ,}\)

\({\small a}_{2}{\small a}_{1}{\small a}_{1}{\small ,a}_{2}{\small a}_{1}{\small a}_{2}{\small ,...,a}_{2}{\small a}_{1}{\small a}_{n}{\small ,a}_{2}{\small a}_{2}{\small a}_{1}{\small ,a}_{2}{\small a}_{2}{\small a}_{2}{\small ,...,a}_{2}{\small a}_{2}{\small a}_{n}{\small ,...,a}_{2}{\small a}_{n}{\small a}_{1}{\small ,a}_{2}{\small a}_{n}{\small a}_{2}{\small ,a}_{2}{\small a}_{n}{\small a}_{n}{\small ,}\)

\({\small \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\vdots\)

\({\small a}_{n}{\small a}_{1}{\small a}_{1}{\small ,a}_{n}{\small a}_{1}{\small a}_{2}{\small ,...,a}_{n}{\small a}_{1}{\small a}_{n}{\small ,a}_{n}{\small a}_{2}{\small a}_{1}{\small ,a}_{n}{\small a}_{2}{\small a}_{2}{\small ,...,a}_{n}{\small a}_{2}{\small a}_{n}{\small ,...,a}_{n}{\small a}_{n}{\small a}_{1}{\small ,a}_{n}{\small a}_{n}{\small a}_{2}{\small ,a}_{n}{\small a}_{n}{\small a}_{n}{\small ,}\)

\({\small a}_{1}{\small a}_{1}{\small a}_{1}{\small a}_{1}{\small ,a}_{1}{\small a}_{1}{\small a}_{1}{\small a}_{2}{\small ,...}\)

El objetivo es probar que la lista anterior enumera sin repeticiones todas las palabras de \(\Sigma^{\ast}\), i.e. produce naturalmente una biyección entre \(\omega\) y \(\Sigma^{\ast}\). Pero antes debemos definir mas formalmente la lista. Para esto definamos \(s^{\leq}:\Sigma^{\ast}\rightarrow\Sigma^{\ast}\) de la siguiente manera

1. adhocprefix-adhocsufix \(s^{\leq}((a_{n})^{m})=(a_{1})^{m+1}\), para cada \(m\geq0\)

2. adhocprefix-adhocsufix \(s^{\leq}(\alpha a_{i}(a_{n})^{m})=\alpha a_{i+1}(a_{1})^{m}\), cada vez que \(\alpha\in\Sigma^{\ast}\), \(1\leq i<n\) y \(m\geq0\)

Nótese que la definición de \(s^{\leq}\) es correcta ya que una palabra de \(\Sigma^{\ast}\) ya sea es de la forma \((a_{n})^{m}\), con \(m\geq0\), o es de la forma \(\alpha a_{i}(a_{n})^{m}\), con \(\alpha\in\Sigma^{\ast}\), \(1\leq i<n\) y \(m\geq0\); y estos dos casos posibles son mutuamente excluyentes.

Claramente se tiene entonces que la lista anterior puede ser escrita de la siguiente manera \[\varepsilon,s^{\leq}(\varepsilon),s^{\leq}(s^{\leq}(\varepsilon)),s^{\leq}(s^{\leq}(s^{\leq}(\varepsilon))),s^{\leq}(s^{\leq}(s^{\leq}(s^{\leq}(\varepsilon)))),...\] Con esta definición formal de la lista, podemos probar de la misma forma en la que lo hicimos arriba para el caso \(\Sigma=\widetilde{Num}\) que:

1. adhocprefix(S)adhocsufix Toda palabra de \(\Sigma^{\ast}\) aparece en la lista

2. adhocprefix(I)adhocsufix Ninguna palabra de \(\Sigma^{\ast}\) aparece mas de una ves en la lista

(dejamos al lector los detalles por tratarse de un argumento completamente similar).

Definamos \(\ast^{\leq}:\omega\rightarrow\Sigma^{\ast}\) recursivamente de la siguiente manera:

1. adhocprefix-adhocsufix \(\ast^{\leq}(0)=\varepsilon\)

2. adhocprefix-adhocsufix \(\ast^{\leq}(i+1)=s^{\leq}(\ast^{\leq}(i))\)

Nótese que dado \(i\in\omega\), tenemos que: \[\ast^{\leq}(i)=\overset{i\text{ veces}}{\overbrace{s^{\leq}(...s^{\leq}(s^{\leq}(}}\varepsilon))...)\] Es claro que entonces \(\ast^{\leq}(i)\) nos da el \((i+1)\)-ésimo elemento de la lista, o lo que es lo mismo, el \(i\)-ésimo elemento de la lista contando desde el \(0\). O sea que las propiedades (S) y (I) nos garantizan que la función \(\ast^{\leq}\) es biyectiva. A continuación describiremos su inversa. Primero un lema obvio pero muy importante.

Notar que el \(k\) del lema anterior es \(\left\vert \alpha\right\vert -1\) y los números \(i_{k},...,i_{0}\) van dando el número de orden de cada símbolo de \(\alpha\) yendo de izquierda a derecha. Por ejemplo si \(\Sigma=\{\%,!,@\}\) y \(\leq\) es el orden total sobre \(\Sigma\) dado por \(\%<!<@\) (es decir que aquí \(a_{1}=\%\), \(a_{2}=!\) y \(a_{3}=@\)) entonces para la palabra \(!\%@\%@\) tenemos \(k=4\) y \(i_{4}=2\), \(i_{3}=1\), \(i_{2}=3\), \(i_{1}=1\) y \(i_{0}=3\). Sin embargo si hubiéramos tomado el orden dado por \(@<\%<!\), para la misma palabra hubiéramos tenido \(i_{4}=3\), \(i_{3}=2\), \(i_{2}=1\), \(i_{1}=2\) y \(i_{0}=1\).

Ahora podemos definir la función \(\#^{\leq}\) de la siguiente manera \[\begin{array}[t]{rll} \#^{\leq}:\Sigma^{\ast} & \rightarrow & \omega\\ \varepsilon & \rightarrow & 0\\ a_{i_{k}}...a_{i_{0}} & \rightarrow & i_{k}n^{k}+...+i_{0}n^{0} \end{array}\]

Proof. Para cada \(x\in\omega\) sea \(\mathrm{Enu}_{x}\) el siguiente enunciado:

1. adhocprefixadhocsufix \(\mathrm{Enu}_{x}\): \(\#^{\leq}(\ast^{\leq}(x))=x\)

Usaremos la Regla de Inducción a partir de \(0\) para probar que todos los enunciados son verdaderos. Que \(\mathrm{Enu}_{0}\) es verdadero es trivial. Supongamos entonces que \(\mathrm{Enu}_{x}\) es verdadero (i.e. \(\#^{\leq}(\ast^{\leq}(x))=x\)) y probemos que entonces\(\mathrm{Enu}_{x+1}\) lo es (i.e. \(\#^{\leq}(\ast^{\leq}(x+1))=x+1\)). Sean \(k\geq0\) y \(i_{k},...,i_{0}\) tales que \(\ast^{\leq}(x)=a_{i_{k}}...a_{i_{0}}\). Ya que \(\#^{\leq}(\ast^{\leq}(x))=x\) tenemos que \(x=i_{k}n^{k}+...+i_{0}n^{0}\). Hay varios casos.

Caso \(i_{0}<n\). Entonces \(\ast^{\leq}(x+1)=s^{\leq}(\ast^{\leq}(x))=a_{i_{k}}...a_{i_{0}+1}\) por lo cual \[\begin{array}{ll} \#^{\leq}(\ast^{\leq}(x+1)) & =i_{k}n^{k}+i_{k-1}n^{k-1}+...+(i_{0}+1)n^{0}\\ & =\left(i_{k}n^{k}+i_{k-1}n^{k-1}+...+i_{0}n^{0}\right)+1\\ & =x+1 \end{array}\] Caso \(i_{k}=i_{k-1}=...=i_{0}=n\). Entonces \(\ast^{\leq}(x+1)=s^{\leq}(\ast^{\leq}(x))=(a_{1})^{k+2}\) por lo cual \[\begin{array}{ll} \#^{\leq}(\ast^{\leq}(x+1)) & =1n^{k+1}+1n^{k}+...+1n^{1}+1n^{0}\\ & =\left(nn^{k}+nn^{k-1}+...+nn^{0}\right)+1\\ & =x+1 \end{array}\] Caso \(i_{0}=i_{1}=...=i_{h}=n\), \(\;i_{h+1}\not=n\), para algún \(0\leq h<k\). Entonces \(\ast^{\leq}(x+1)=s^{\leq}(\ast^{\leq}(x))=a_{i_{k}}...a_{i_{h+2}}a_{i_{h+1}+1}(a_{1})^{h}\) por lo cual \[\begin{array}{ll} \#^{\leq}(\ast^{\leq}(x+1)) & =i_{k}n^{k}+...+i_{h+2}n^{h+2}+(i_{h+1}+1)n^{h+1}+1n^{h}+...+1n^{1}+1n^{0}\\ & =\left(i_{k}n^{k}+...+i_{h+2}n^{h+2}+i_{h+1}n^{h+1}+n^{h+1}+n^{h}+...+n^{1}\right)+1\\ & =\left(i_{k}n^{k}+...+i_{h+2}n^{h+2}+i_{h+1}n^{h+1}+nn^{h}+...+nn^{0}\right)+1\\ & =x+1 \end{array}\] De esta forma hemos probado que \(\mathrm{Enu}_{x+1}\) es verdadero. O sea que por la Regla de Inducción a partir de \(0\) tenemos que todos los enunciados \(\mathrm{Enu}_{x}\) son verdaderos.

Por definición la inversa de \(\ast^{\leq}\) es la función con dominio \(\Sigma^{\ast}\) que a una palabra \(\alpha\) le asocia el único \(x\in\omega\) tal que \(\ast^{\leq}(x)=\alpha\). Es decir debemos probar que

1. adhocprefixadhocsufix \(\#^{\leq}(\alpha)=\) único \(x\in\omega\) tal que \(\ast^{\leq}(x)=\alpha\), para cada \(\alpha\in\Sigma^{\ast}\)

Sea entonces \(\alpha\in\Sigma^{\ast}\). Ya que \(\ast^{\leq}\) es biyectiva (por las propiedades (S) e (I)) hay un único \(x\in\omega\) tal que \(\ast^{\leq}(x)=\alpha\). Pero \(\mathrm{Enu}_{x}\) nos dice que \(\#^{\leq}(\ast^{\leq}(x))=x\) por lo cual \(\#^{\leq}(\alpha)=x\).  

Cabe destacar que dada una palabra \(\alpha\), el número \(\#^{\leq}(\alpha)\) nos dice en que posición se ubica \(\alpha\) en la lista, es decir \(\alpha\) es la (\(\#^{\leq}(\alpha)+1\))-ésima palabra de la lista. O sea que: \[\alpha=\overset{\#^{\leq}(\alpha)\text{ veces}}{\overbrace{s^{\leq}(...s^{\leq}(s^{\leq}(}}\varepsilon))...)\]

De los desarrollos hechos se desprende el siguiente interesante resultado. Dejamos al lector la prueba como ejercicio.

Como hemos visto las biyecciones dadas producen una "identificación" entre números de \(\omega\) y palabras del alfabeto \(\Sigma\). Es decir, en algún sentido identificamos palabras y números ya que se corresponden biunivocamente. Supongamos que \(\alpha\) es una palabra de \(\Sigma^{\ast}-\{\varepsilon\}\) y queremos "verla como un número". Entonces en ves de ver sus símbolos vemos los ordenes de aparición en \(\Sigma\) de los mismos y miramos la suma de potencias asociada.

Supongamos ahora que \(x\) es un número de \(\omega-\{0\}\) y además supongamos que somos súper inteligentes y que cuando vemos a \(x\) vemos la secuencia única de números \(i_{k},i_{k-1},...,i_{0}\) que nos permite expresarlo como suma de potencias según el lema anterior. Entonces si queremos ver a \(x\) como una palabra simplemente miramos la secuencia \(i_{k},i_{k-1},...,i_{0}\) como palabra, reemplazando cada \(i_{j}\) por el símbolo \(i_{j}\)-ésimo de \(\Sigma\).

2.1.2.1 Carácter recursivo de las funciones \(s^{\protect\leq}\), \(\ast^{\protect\leq}\) y \(\#^{\protect\leq}\)

Es un ejercicio (dejado al lector) probar que cualquiera sea \(\alpha\in\Sigma^{\ast}\), se tiene que \[\begin{aligned} s^{\leq}(\varepsilon) & =a_{1}\\ s^{\leq}(\alpha a_{i}) & =\alpha a_{i+1}\text{, }i<n\\ s^{\leq}(\alpha a_{n}) & =s^{\leq}(\alpha)a_{1} \end{aligned}\] Nótese que esto nos permite calcular recursivamente el valor de \(s^{\leq}\) ya que las ecuaciones anteriores nos muestran como obtener rápidamente \(s^{\leq}(\alpha a)\) en términos de \(s^{\leq}(\alpha)\) y \(a\), donde \(a\) es un elemento cualquiera de \(\Sigma\). Por supuesto, en algún momento deberemos usar el dato inicial \(s^{\leq}(\varepsilon)=a_{1}\). En un lenguaje de programación funcional, las tres ecuaciones anteriores son directamente un programa para computar \(s^{\leq}\) o si se quiere una definición de dicha función. Dejamos al lector que intente usar las ecuaciones anteriores para dar un programa imperativo que compute \(s^{\leq}\) (esto esta hecho mas adelante en la primera lista de funciones \(\Sigma\)-efectivamente computables).

Lo mismo sucede con la función \(\ast^{\leq}\) la cual fue directamente definida en forma recursiva por las ecuaciones \[\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(i+1) & =s^{\leq}(\ast^{\leq}(i)) \end{aligned}\] Dejamos al lector corroborar que la función \(\#^{\leq}\) verifica las siguientes ecuaciones, las cuales obviamente pueden ser usadas para calcular recursivamente sus valores \[\begin{aligned} \#^{\leq}(\varepsilon) & =0\\ \#^{\leq}(\alpha a_{i}) & =\#^{\leq}(\alpha).n+i \end{aligned}\]

2.1.2.2 Extensión del orden total de \(\Sigma\) a \(\Sigma^{\ast}\)

Podemos extender \(\leq\) a \(\Sigma^{\ast}\) usando el orden de aparición en la lista, es decir

1. adhocprefix-adhocsufix \(\alpha\leq\beta\) sii \(\#^{\leq}(\alpha)\leq\#^{\leq}(\beta)\)

Es decir \(\alpha\leq\beta\) sii \(\alpha=\beta\) o \(\alpha\) ocurre antes que \(\beta\) en la lista. Obviamente este orden es un es un orden total sobre \(\Sigma^{\ast}\). Llamaremos a este orden el orden total de \(\Sigma^{\ast}\) inducido por \(\leq\). Tal como en el caso de la notación decimal clásica (con \(0\)) el orden total de \(\Sigma^{\ast}\) inducido por \(\leq\) puede ser caracterizado “lexicograficamente” en forma similar al orden de los diccionarios. Ya que se vuelve mas fácil de escribir daremos a continuación la caracterización lexicográfica del orden \(<\) asociado al orden total de \(\Sigma^{\ast}\) inducido por \(\leq\). Antes un lema técnico.

Proof. Lo probaremos por el absurdo. O sea supongamos hay \(\alpha,\beta,\rho,\gamma_{1},\gamma_{2}\in\Sigma^{\ast}\) tales que \[\alpha=\rho a_{i}\gamma_{1}\text{ y }\beta=\rho a_{j}\gamma_{2},\text{ con }i>j\text{ y }\left|\gamma_{1}\right|=\left|\gamma_{2}\right|\] y ademas \[\beta=\overset{N\text{ veces}}{\overbrace{s^{\leq}(...s^{\leq}(s^{\leq}(}}\alpha))...)\] con \(N\geq1\). Podemos también suponer que tomamos un caso en el que \(N\) es mínimo. Supongamos \(\gamma_{1}\in\{a_{n}\}^{*}\). Veamos primero el caso \(i<n\). Entonces \(s^{\leq}(\alpha)=\rho a_{i+1}(a_{1})^{\left|\gamma_{1}\right|}\) lo cual produce un absurdo porque nos diría que \(N\) no es mínimo. Veamos ahora el caso \(i=n\). Nótese que \(\rho\notin\{a_{n}\}^{*}\) ya que si así fuera tendríamos: \[\beta=\overset{N\text{ veces}}{\overbrace{s^{\leq}(...s^{\leq}(s^{\leq}(}}\alpha))...)\geq\left|s^{\leq}(\alpha)\right|>\left|\alpha\right|=\left|\beta\right|\] O sea que \(\rho=\rho'a_{u}(a_{n})^{v}\), con \(\rho'\in\Sigma^{\ast}\), \(u\neq n\) y \(v\geq0\). Pero entonces \[\alpha=\rho a_{n}(a_{n})^{\left|\gamma_{1}\right|}=\rho'a_{u}(a_{n})^{v}a_{n}(a_{n})^{\left|\gamma_{1}\right|}=\rho'a_{u}(a_{n})^{v+\left|\gamma_{1}\right|+1}\] lo cual nos dice que \[s^{\leq}(\alpha)=\rho'a_{u+1}(a_{n})^{v+\left|\gamma_{1}\right|+1}\] Ya que \[\beta=\rho a_{j}\gamma_{2}=\rho'a_{u}(a_{n})^{v}a_{j}\gamma_{2}\] volvemos a encontrar un caso que nos diría que \(N\) no es mínimo. Ahora supongamos \(\gamma_{1}\notin\{a_{n}\}^{*}\). Entonces \[s^{\leq}(\alpha)=\rho a_{i}s^{\leq}(\gamma_{1})\] y claramente entonces volvemos a obtener un caso que nos dice que \(N\) no es mínimo.  

Proof. (1). Como ya lo vimos para el caso \(\Sigma=\widetilde{Num}\), ya que la función \(s^{\leq}\) siempre agranda en 1 la longitud de la palabra o la deja igual, la lista de palabras es de la forma \[B_{0};B_{1};B_{2};B_{3};B_{4};...\] donde cada \(B_{n}\) es, por definición, la parte de la lista en la cual las palabras tienen longitud exactamente \(n\). Además las propiedades (S) e (I) nos garantizan que para cada \(n\in\omega\): \[B_{n}=\{\alpha\in\Sigma^{*}:\left|\alpha\right|=n\}\] Note que si \(\left|\alpha\right|\neq\left|\beta\right|\) entonces \(\alpha\text{ y }\beta\) ocurren en distintos bloques por lo cual tenemos que que \(\alpha<\beta\) si y solo si (por definición) \(\alpha\) ocurre antes que \(\beta\) en la lista si y solo si \(\left|\alpha\right|<\left|\beta\right|\)

(2). Supongamos que \(\left|\alpha\right|=\left|\beta\right|\) Es claro que la equivalencia se cumple cuando \(\alpha=\beta=\varepsilon\) ya que en tal caso ambas condiciones no se cumplen. O sea que podemos suponer que \(\alpha\neq\varepsilon\) y \(\beta\neq\varepsilon\). Entonces \(\alpha=\rho a_{i}\gamma_{1}\) y \(\beta=\rho a_{j}\gamma_{2}\) con \(\rho,\gamma_{1},\gamma_{2}\in\Sigma^{\ast}\), \(i,j\in\omega\) y \(\left|\gamma_{1}\right|=\left|\gamma_{2}\right|\). Supongamos que \(\alpha<\beta\), es decir \(\alpha\leq\beta\) y \(\alpha\neq\beta\). Ya que \(\alpha\neq\beta\), tenemos que \(i\neq j\). Además ya que \(\alpha<\beta\) tenemos por definición del orden total de \(\Sigma^{\ast}\) inducido por \(\leq\) que \(\alpha\) ocurre antes que \(\beta\) en la lista, es decir \[\beta=\overset{N\text{ veces}}{\overbrace{s^{\leq}(...s^{\leq}(s^{\leq}(}}\alpha))...),\text{ con \ensuremath{N\geq1}}\] El Lema 2.5 nos dice que no puede ser \(i\) mayor que \(j\) por lo cual tenemos que \(i<j\). Claramente entonces existen \(\rho,\gamma_{1},\gamma_{2}\in\Sigma^{\ast}\) y \(i,j\in\omega\) tales que \[\alpha=\rho a_{i}\gamma_{1}\text{ y }\beta=\rho a_{j}\gamma_{2}\text{ y }i<j\]

Supongamos ahora que existen \(\rho,\gamma_{1},\gamma_{2}\in\Sigma^{\ast}\) y \(i,j\in\omega\) tales que \[\alpha=\rho a_{i}\gamma_{1}\text{ y }\beta=\rho a_{j}\gamma_{2}\text{ y }i<j\] Note que \(\alpha\neq\beta\). Ya que \(\left|\gamma_{1}\right|=\left|\gamma_{2}\right|\) (puesto que \(\left|\alpha\right|=\left|\beta\right|\)) tenemos que el Lema 2.5 (aplicado a \(\beta\text{ y }\alpha\)) nos dice que \[\alpha\notin\{s^{\leq}(\beta),s^{\leq}(s^{\leq}(\beta)),s^{\leq}(s^{\leq}(s^{\leq}(\beta))),s^{\leq}(s^{\leq}(s^{\leq}(s^{\leq}(\beta)))),...\}\] Esto nos dice que \(\alpha\) no esta a la derecha de \(\beta\) en la lista por lo cual \(\alpha\) esta a la izquierda de \(\beta\) en la lista o lo que es lo mismo \(\alpha<\beta\).  

Cabe destacar que si bien la condición del ítem (2) del lema anterior es de tipo descriptiva, tiene un carácter algorítmico bien marcado ya que cuando tenemos dos palabras no iguales a \(\varepsilon\), de la misma longitud, podemos ver el primer par de dígitos en los que difieren y la relación de orden que tienen dichos símbolos es la que tienen dichas palabras.

También es interesante tener caracterizado el orden sin dividir por casos:

Proof. Es un corolario directo del lema anterior.  

Una consecuencia inmediata del Lema 2.6 es la siguiente propiedad de la función \(s^{\leq}\):

1. adhocprefix-adhocsufix \(s^{\leq}(\alpha)=\text{menor elemento de }\{\beta\in\Sigma^{\ast}:\alpha<\beta\}\), cualesquiera sea \(\alpha\in\Sigma^{\ast}\)

Dejamos esto como ejercicio. También se puede caracterizar la relación \(<\) asociada al orden total de \(\Sigma^{\ast}\) inducido por \(\leq\) de manera recursiva:

Proof. Es un corolario directo del Lema 2.6.  

Debería ser intuitivamente claro que el orden recién definido sobre \(\Sigma^{\ast}\) posee las mismas propiedades matemáticas que el orden usual de \(\omega\). Esto se entenderá en forma mas profunda cuando veamos el concepto de isomorfismo de posets mas adelante. Veamos un ejemplo de una propiedad del orden usual de \(\omega\) que también vale en \(\Sigma^{\ast}\) con el orden inducido por un orden total sobre \(\Sigma\):

Proof. Es un corolario directo del Lema 2.6.