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

En esta seccion daremos biyecciones naturales entre \(\Sigma^{\ast}\) y \(\omega\), para cada alfabeto no vacio \(\Sigma\). Dichas biyecciones dependen de tener asociado a \(\Sigma\) un orden total, el cual nos permite de manera “lexicografica” 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 interes extra ya que esta emparentado con nuestra notacion decimal clasica de los numeros de \(\omega\).

2.1.1 Notacion decimal sin \(0\)

Llamaremos numerales a los siguientes simbolos \[0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\] Usaremos \(Num\) para denotar el conjunto de numerales. Notese que \(Num\cap\omega=\emptyset\). Es decir, no debemos confundir los simbolos que usualmente denotan los primeros diez numeros enteros con los numeros que ellos denotan. De hecho en china o japon los primeros diez numeros enteros se denotan con otros simbolos. Similarmente las palabras pertenecientes a \(Num^{\ast}\) denotan (notacion decimal) a los numeros 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 matematico (es decir las guias, el apunte, lo que escriben los profesores en el pizarron, etc) representamos dos objetos diferentes de la misma forma. Por ejemplo \(45\) puede estar denotando al numero entero cuarenta y cinco o tambien \(45\) puede estar denotando la palabra de longitud \(2\) cuyo primer simbolo es el numeral \(4\) y cuyo segundo simbolo es el numeral \(5\), es decir ella misma. Por dar otro ejemplo, el simbolo \(1\) en nuestro discurso algunas veces se denotara a si mismo y otras veces denotara al numero uno.

Es bien conocido que, en notacion decimal, las siguientes palabras del alfabeto \(Num\), denotan, de menor a mayor, a los numeros 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 notacion 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\)-esima palabra representa o denota al numero \(n-1\) o, dicho de otra forma, el numero \(n\in\omega\) es representado por la \((n+1)\)-esima palabra de la lista.

Un detalle de la representacion decimal de numeros de \(\omega\) mediante palabras de \(Num^{\ast}\) es que la misma no nos da una biyeccion entre \(Num^{\ast}\) y \(\omega\) ya que por ejemplo las palabras \(00016\) y \(16\) representan el mismo numero. Dicho de otra forma en la lista anterior no figuran todas las palabras de \(Num^{\ast}\), a saber estan omitidas todas las palabras que comienzan con el simbolo \(0\) y tienen longitud mayor que uno. A continuacion daremos una representacion de los numeros de \(\omega\) mediante palabras, la cual no tendra este problema. El alfabeto que usaremos tendra todos los numerales menos el \(0\) y ademas tendra un simbolo para denotar al numero diez, a saber el simbolo \(d\). Es decir \[\widetilde{Num}=\{1,2,3,4,5,6,7,8,9,d\}\] Representaremos a los numeros 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 habra dado cuenta de que el siguiente a una palabra \(\alpha\) de la lista anterior se obtiene aplicando las siguientes clausulas

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

2. adhocprefix-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. buscar de derecha a izquierda el primer simbolo no igual a \(d\)

   2. reemplazar dicho simbolo por su siguiente en la lista \(1,2,3,4,5,6,7,8,9,d\)

   3. reemplazar por el simbolo \(1\) a todos los simbolos iguales a \(d\) que ocurrian a la derecha del simbolo 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})=d^{n+1}\), para cada \(n\geq0\)

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

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

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

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

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

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

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

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

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

Notese que la definicion 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 numero \(0\) es representado en la lista anterior con la palabra \(\varepsilon\)

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

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

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

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

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

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

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

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

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

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

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

Como puede notarse en estos primeros veinte y pico numeros solo dos (el \(0\) y el \(20\)) se representan en forma distinta a la reprentacion decimal clasica. Es natural que \(\varepsilon\) denote al numero \(0\) y ademas notese 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\) deberiamos leerla como "ventidiez" y si nos fijamos en la lista ella representa al numero treinta lo cual nuevamente es muy natural. Otro ejemplo: a \(6d\) deberiamos leerla como "sesentidiez" y es natural ya que en la lista representa al setenta. Tambien, la palabra \(9d\) puede leerse noventidiez ya que representa en la lista al numero \(100\).

La lista anterior va representando los numeros de \(\omega\) en forma muy natural pero aunque nuestra intuicion nos diga que no, en principio podria pasar que una misma palabra del alfabeto \(\widetilde{Num}\) ocurra dos veces en la lista y esto nos diria que una misma palabra estaria representando a dos numeros distintos. Tambien, en principio podria 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

Notese que la propiedad (S) nos dice que la funcion \[\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 funcion es inyectiva, por lo cual entre las dos nos garantizan que dicha representacion establece una biyeccion 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\). Notese que dada una palabra \(\alpha\in\widetilde{Num}^{\ast}\), el numero \(\#(\alpha)\) es justamente el numero representado por la palabra \(\alpha\), o dicho de otra forma \(\#(\alpha)\) es la posicion que ocupa \(\alpha\) en la lista, contando desde el \(0\) (es decir \(\alpha\) es la \((\#(\alpha)+1)\)-esima 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}\] Aqui hay que tener cuidado como leemos las igualdades anteriores. Por ejemplo en la igualdad \[\#(1)=1\] la primera ocurrencia del simbolo \(1\) se refiere al numeral uno, es decir denota una palabra y la segunda ocurrencia se esta refiriendo al numero uno, es decir denota un numero.

Dejamos al lector el ejercicio de ganar intuicion con ejemplos hasta que se convensa de que tal como en el caso de la notacion decimal, el numero \(\#(\alpha)\) se expresa como una suma de potencias de \(10\), con los coeficientes dados en funcion de los simbolos 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 aqui una prueba de este hecho ya que lo probaremos abajo para el caso general. Para ganar intuicion 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 funcion \(\#\) 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 numeros como suma de potencias de diez, en forma analoga a la notacion decimal clasica, podemos refozar aun mas la analogia poniendo nombres adecuados que, tal como en el caso clasico, nos permitan leer las palabras de \(\widetilde{Num}\) describiendo su suma de potencias asociada. Por ejemplo podriamos llamar "decenta" al numero \(100\), por analogia a "treinta", "cuarenta",...,"noventa". O sea una decenta es diez veces diez. De esta forma la palabra \(d1\) se leera "decenta y uno" y esto es natural ya que en la lista representa al \(101\). La palabra \(dd\) se leera "decenta y diez" y esto describe a la perfeccion el numero 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 aqui como en los otros casos vistos en los cuales no hay ocurrencias del simbolo \(d\) la palabra representa al mismo numero que representa en la notacion decimal clasica. Por dar otro ejemplo, la palabra \(59d3\) se leera "cinco mil novecientos decenta y tres" y representara al numero \(6003\).

Para seguir debemos ponerle nombre a "diez veces cien", es decir, "decientos" (por analogia con "novecientos = nueve veces cien") denotara al numero \(1000=10.100\). De esta forma la palabra \(d51\) se leera "decientos cincuenta y uno" y esto es natural ya que pensando un rato se puede ver que ella representa al \(1051\). Tambien, la palabra \(ddd\) se leera "decientos decenta y diez" y representara al numero \(1110\).

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 definicion, 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\)

Notese que hasta el momento nada nos asegura que no suceda que para algun \(n\) se de que \(B_{n}\) sea una lista infinita, lo cual ademas nos diria que los bloques \(B_{n+1},B_{n+2},...\) son todos vacios. Es decir podria pasar que la lista se estanque en una longitud \(n\) y nunca aparezca una palabra de longitud mayor que \(n\). Esto por supuesto obligaria 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 intuicion nos dice que en el bloque \(B_{n}\) estan listadas sin repeticion todas las palabras de \(\widetilde{Num}^{\ast}\) de longitud \(n\), pero debemos justificar esto con argumentos solidos. Algunas propiedades basicas que se pueden probar facilmente 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 ultima posicion

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 util el siguiente resultado obvio

Dejamos como ejercicio al lector hacer la prueba de (3) usando el lema anterior y las propiedades (1) y (2). Ahora es facil usando (3) probar inductivamente que

1. adhocprefix(4)adhocsufix \(B_{n}\) es una lista sin repeticiones de todas las palabras de longitud \(n\)

Pero claramente de (4) se desprenden en forma obvia las propiedades (S) y (I).

2.1.2 El caso general

Sea \(\Sigma\) un alfabeto no vacio 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 biyeccion 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\)

Notese que la definicion 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 definicion 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))\)

Notese 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)\)-esimo elemento de la lista, o lo que es lo mismo, el \(i\)-esimo elemento de la lista contando desde el \(0\). O sea que las propiedades (S) y (I) nos garantizan que la funcion \(\ast^{\leq}\) es biyectiva. A continuacion 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 numeros \(i_{k},...,i_{0}\) van dando el numero de orden de cada simbolo de \(\alpha\) yendo de izquierda a derecha. Por ejemplo si \(\Sigma=\{\%,!,@\}\) y \(\leq\) es el orden total sobre \(\Sigma\) dado por \(\%<!<@\) (es decir que aqui \(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 envargo si hubieramos tomado el orden dado por \(@<\%<!\), para la misma palabra hubieramos tenido \(i_{4}=3\), \(i_{3}=2\), \(i_{2}=1\), \(i_{1}=2\) y \(i_{0}=1\).

Ahora podemos definir la funcion \(\#^{\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. Primero probaremos por induccion en \(x\) que

1. adhocprefix(a)adhocsufix Para cada \(x\in\omega\), se tiene que \(\#^{\leq}(\ast^{\leq}(x))=x\)

El caso \(x=0\) es trivial. Supongamos que \(\#^{\leq}(\ast^{\leq}(x))=x\), veremos entonces que \(\#^{\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 algun \(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 (a).

Por definicion la inversa de \(\ast^{\leq}\) es la funcion con dominio \(\Sigma^{\ast}\) que a una palabra \(\alpha\) le asocia el unico \(x\in\omega\) tal que \(\ast^{\leq}(x)=\alpha\). Es decir debemos probar que

1. adhocprefix(b)adhocsufix \(\#^{\leq}(\alpha)=\) unico \(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 \(x\in\omega\) tal que \(\ast^{\leq}(x)=\alpha\). Pero (a) nos dice que \(\#^{\leq}(\ast^{\leq}(x))=x\) por lo cual \(\#^{\leq}(\alpha)=x\).  

Cabe destacar que dada una palabra \(\alpha\), el numero \(\#^{\leq}(\alpha)\) nos dice en que posicion se hubica \(\alpha\) en la lista, es decir \(\alpha\) es la (\(\#^{\leq}(\alpha)+1\))-esima 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 "identificacion" entre numeros de \(\omega\) y palabras del alfabeto \(\Sigma\). Es decir, en algun sentido identificamos palabras y numeros ya que se corresponden biunivocamente. Supongamos que \(\alpha\) es una palabra de \(\Sigma^{\ast}-\{\varepsilon\}\) y queremos "verla como un numero". Entonces en ves de ver sus simbolos vemos los ordenes de aparicion en \(\Sigma\) de los mismos y miramos la suma de potencias asociada.

Supongamos ahora que \(x\) es un numero de \(\omega-\{0\}\) y ademas supongamos que somos super inteligentes y que cuando vemos a \(x\) vemos la secuencia unica de numeros \(i_{k},i_{k-1},...,i_{0}\) que nos permite expresarlo como suma de potencias segun 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 simbolo \(i_{j}\)-esimo de \(\Sigma\).

2.1.2.1 Caracter 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}\] Notese que esto nos permite calcular recursivamente el valor de \(s^{\leq}\) ya que las ecuaciones anteriores nos muestran como obtener rapidamente \(s^{\leq}(\alpha a)\) en terminos de \(s^{\leq}(\alpha)\) y \(a\), donde \(a\) es un elemento cualquiera de \(\Sigma\). Por supuesto, en algun momento deberemos usar el dato inicial \(s^{\leq}(\varepsilon)=a_{1}\). En un lenguaje de programacion funcional, las tres ecuaciones anteriores son directamente un programa para computar \(s^{\leq}\) o si se quiere una definicion de dicha funcion. 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 funcion \(\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 funcion \(\#^{\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 Extension del orden total de \(\Sigma\) a \(\Sigma^{\ast}\)

Podemos extender \(\leq\) a \(\Sigma^{\ast}\) usando el orden de aparicion 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 notacion decimal clasica (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 facil de escribir daremos a continuacion la caracterizacion lexicografica del orden \(<\) asociado al orden total de \(\Sigma^{\ast}\) inducido por \(\leq\). Antes un lema tecnico.

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 tambien suponer que tomamos un caso en el que \(N\) es minimo. 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 diria que \(N\) no es minimo. Veamos ahora el caso \(i=n\). Notese que \(\rho\notin\{a_{n}\}^{*}\) ya que si asi fuera tendriamos: \[\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 diria que \(N\) no es minimo. 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 minimo.  

Proof. (1). Como ya lo vimos para el caso \(\Sigma=\widetilde{Num}\), ya que la funcion \(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 definicion, la parte de la lista en la cual las palabras tienen longitud exactamente \(n\). Ademas 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 definicion) \(\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\). Ademas ya que \(\alpha<\beta\) tenemos por definicion 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 condicion del item (2) del lema anterior es de tipo descriptiva, tiene un caracter algotitmico bien marcado ya que cuando tenemos dos palabras no iguales a \(\varepsilon\), de la misma longitud, podemos ver el primer par de dijitos en los que difieren y la relacion de orden que tienen dichos simbolos es la que tienen dichas palabras.

Tambien 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 funcion \(s^{\leq}\):

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

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

Proof. Es un corolario directo del Lema 2.6.  

Deberia ser intuitivamente claro que el orden recien definido sobre \(\Sigma^{\ast}\) posee las mismas propiedades matematicas que el orden usual de \(\omega\). Esto se entendera 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 tambien vale en \(\Sigma^{\ast}\) con el orden inducido por un orden total sobre \(\Sigma\):

Proof. Es un corolario directo del Lema 2.6.