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. 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\).
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
adhocprefixC\(_{1}\)adhocsufix si \(\alpha=d^{n}\), con \(n\geq0\) entonces el siguiente de \(\alpha\) es \(1^{n+1}\)
adhocprefixC\(_{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:
buscar de derecha a izquierda el primer simbolo no igual a \(d\)
reemplazar dicho simbolo por su siguiente en la lista \(1,2,3,4,5,6,7,8,9,d\)
reemplazar por el simbolo \(1\) a todos los simbolos iguales a \(d\) que ocurrian a la derecha del simbolo reemplazado
Notese que
adhocprefix-adhocsufix El numero \(0\) es representado en la lista anterior con la palabra \(\varepsilon\)
adhocprefix-adhocsufix El numero \(1\) es representado en la lista anterior con la palabra \(1\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\)
adhocprefix-adhocsufix El numero \(9\) es representado en la lista anterior con la palabra \(9\)
adhocprefix-adhocsufix El numero \(10\) es representado en la lista anterior con la palabra \(d\)
adhocprefix-adhocsufix El numero \(11\) es representado en la lista anterior con la palabra \(11\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\)
adhocprefix-adhocsufix El numero \(19\) es representado en la lista anterior con la palabra \(19\)
adhocprefix-adhocsufix El numero \(20\) es representado en la lista anterior con la palabra \(1d\)
adhocprefix-adhocsufix El numero \(21\) es representado en la lista anterior con la palabra \(21\)
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 muestran que
adhocprefix(S)adhocsufix Toda palabra de \(\widetilde{Num}^{\ast}\) aparece en la lista
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} \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\).
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:
adhocprefix-adhocsufix \(B_{0}\) es \(\varepsilon\)
adhocprefix-adhocsufix \(B_{1}\) es \(1,2,3,4,5,6,7,8,9,d\)
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:
adhocprefix(1)adhocsufix Si \(B_{n}=\alpha_{1},...,\alpha_{k}\), entonces \(\alpha_{1}=1^{n}\) y \(\alpha_{k}=d^{n}\)
adhocprefix(2)adhocsufix Si \(d^{n}\) ocurre en \(B_{n}\) lo hace 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
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
2.1. Sea \(\sigma\in\widetilde{Num}\) y supongamos \(\alpha\in\widetilde{Num}^{\ast}\) no es de la forma \(d^{n}\). Entonces el siguiente a \(\sigma\alpha\) es \(\sigma\beta\) donde \(\beta\) es el siguiente a \(\alpha\)
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
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).
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
adhocprefix-adhocsufix \(s^{\leq}((a_{n})^{m})=(a_{1})^{m+1}\), para cada \(m\geq0\)
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:
adhocprefix(S)adhocsufix Toda palabra de \(\Sigma^{\ast}\) aparece en la lista
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:
adhocprefix-adhocsufix \(\ast^{\leq}(0)=\varepsilon\)
adhocprefix-adhocsufix \(\ast^{\leq}(i+1)=s^{\leq}(\ast^{\leq}(i))\)
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 facil pero muy importante.
2.2. 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}\). Entonces para cada \(\alpha\in\Sigma^{\ast}-\{\varepsilon\}\) hay unicos \(k\in\omega\) y \(i_{0},i_{1},...,i_{k}\in\{1,...,n\}\) tales que \[\alpha=a_{i_{k}}...a_{i_{0}}\]
Notar que \(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}\]
2.3. La funcion \(\#^{\leq}\) es la inversa de \(\ast^{\leq}\)
Proof. Primero probaremos por induccion en \(x\) que
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
adhocprefix(b)adhocsufix \(\#^{\leq}(\alpha)=\) unico \(x\in\omega\) tal que \(\ast^{\leq}(x)=\alpha\), para cada \(\alpha\in\Sigma^{\ast}\)
Pero (b) es una concecuencia inmediata de (a).
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.
De los desarrollos hechos se desprende el interesante resultado. Dejamos al lector la prueba como ejercicio.
2.4. Sea \(n\geq1\) fijo. Entonces cada \(x\geq1\) se escribe en forma unica de la siguiente manera: \[x=i_{k}n^{k}+i_{k-1}n^{k-1}+...+i_{0}n^{0},\] con \(k\geq0\) y \(1\leq i_{k},i_{k-1},...,i_{0}\leq n\).
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\).
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}\]
Podemos extender el orden de \(\Sigma\) a \(\Sigma^{\ast}\) de la siguiente manera
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. Dejamos como ejercicio para el lector probar que \(\leq\) es un orden total sobre \(\Sigma^{\ast}\).
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 en los capitulos de logica. Veamos un ejemplo:
2.5. Si \(S\subseteq\Sigma^{\ast}\) es no vacio, entonces existe \(\alpha\in S\) tal que \(\alpha\leq\beta\), para cada \(\beta\in S\).