2.1 Ordenes naturales sobre Σ∗

En esta seccion daremos biyecciones naturales entre Σ∗ y ω, para cada alfabeto no vacio Σ. Dichas biyecciones dependen de tener asociado a Σ un orden total, el cual luego con las biyecciones obtenidas se extiende a todo Σ∗. Primero haremos un caso particular pero que tiene un interes extra ya que esta emparentado con nuestra notacion decimal clasica de los numeros de ω.

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∩ω=∅. 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∗ denotan (notacion decimal) a los numeros de ω pero debemos tener en cuenta que Num∗∩ω=∅. Cuando tratamos con palabras de Num∗, 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 ω 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∈ω es representado por la (n+1)-esima palabra de la lista.

Un detalle de la representacion decimal de numeros de ω mediante palabras de Num∗ es que la misma no nos da una biyeccion entre Num∗ y ω 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∗, 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 ω 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 ~Num={1,2,3,4,5,6,7,8,9,d} Representaremos a los numeros de ω con la siguiente lista infinita de palabras de ~Num

ε,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 α de la lista anterior se obtiene aplicando las siguientes clausulas

1. C1 si α=dn, con n≥0 entonces el siguiente de α es 1n+1

2. C2 si α no es de la forma dn, con n≥0, entonces el siguiente de α 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

Notese que

1. - El numero 0 es representado en la lista anterior con la palabra ε

2. - El numero 1 es representado en la lista anterior con la palabra 1

                            ⋮

3. - El numero 9 es representado en la lista anterior con la palabra 9

4. - El numero 10 es representado en la lista anterior con la palabra d

5. - El numero 11 es representado en la lista anterior con la palabra 11

                              ⋮

6. - El numero 19 es representado en la lista anterior con la palabra 19

7. - El numero 20 es representado en la lista anterior con la palabra 1d

8. - El numero 21 es representado en la lista anterior con la palabra 21

9. - El numero 22 es representado en la lista anterior con la palabra 22

                              ⋮

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 ε 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 ω en forma muy natural pero aunque nuestra intuicion nos diga que no, en principio podria pasar que una misma palabra del alfabeto ~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 ~Num la cual nunca figure en la lista. Mas abajo probaremos que estas dos posibilidades no suceden, es decir muestran que

1. (S) Toda palabra de ~Num∗ aparece en la lista

2. (I) Ninguna palabra de ~Num∗ aparece mas de una ves

Notese que la propiedad (S) nos dice que la funcion ∗:ω→~Num∗n→(n+1)-esimo elemento de la lista 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 ω y ~Num∗.

Por supuesto, la pregunta que inmediatamente surge es como calcular la inversa de ∗. Llamemos # a la inversa de ∗. Notese que dada una palabra α∈~Num∗, el numero #(α) es justamente el numero representado por la palabra α, o dicho de otra forma #(α) es la posicion que ocupa α en la lista, contando desde el 0 (es decir α es la (#(α)+1)-esima palabra de la lista). Por ejemplo: #(ε)=0#(1)=1⋮#(9)=9#(d)=10#(11)=11#(12)=12⋮#(19)=19#(1d)=20 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 #(α) se expresa como una suma de potencias de 10, con los coeficientes dados en funcion de los simbolos de α. Mas concretamente si α=s1s2...sk con k≥1 y s1,s2,...,sk∈~Num, entonces #(α)=#(s1).10k−1+#(s2).10k−2+...+#(sk).100 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 #(1d)=1.101+10.100=10+10=20#(dd)=10.101+10.100=100+10=110#(111)=1.102+1.101+1.100=100+10+1=111#(1d3d)=1.103+10.102+3.101+10.100

Ahora que sabemos que las palabras de ~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 ~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 α de la lista es de la misma longitud que α o tiene longitud igual a |α|+1, podemos representar la lista anterior de la siguiente manera: B0;B1;B2;B3;B4;... donde cada Bn es, por definicion, la parte de la lista en la cual las palabras tienen longitud exactamente n. Por ejemplo:

1. - B0 es ε

2. - B1 es 1,2,3,4,5,6,7,8,9,d

3. - B2 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 Bn sea una lista infinita, lo cual ademas nos diria que los bloques Bn+1,Bn+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 (10n).

Por supuesto nuestra intuicion nos dice que en el bloque Bn estan listadas sin repeticion todas las palabras de ~Num∗ de longitud n, pero debemos justificar esto con argumentos solidos. Algunas propiedades basicas que se pueden probar facilmente son:

1. (1) Si Bn=α1,...,αk, entonces α1=1n y αk=dn

2. (2) Si dn ocurre en Bn 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

1. (3) Si Bn=α1,...,αk, entonces Bn+1=1α1,...,1αk,2α1,...,2αk,...,dα1,...,dα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. (4) Bn 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 Σ un alfabeto no vacio y supongamos ≤ es un orden total sobre Σ. Supongamos que Σ={a1,...,an}, con a1<a2<...<an. Inspirados en la lista dada anteriormente de las palabras de ~Num∗, podemos dar la siguiente lista de palabras de Σ∗

ε,a1,a2,...,an,

a1a1,a1a2,...,a1an,a2a1,a2a2,...,a2an,...,ana1,ana2,...,anan,

a1a1a1,a1a1a2,...,a1a1an,a1a2a1,a1a2a2,...,a1a2an,...,a1ana1,a1ana2,a1anan,

a2a1a1,a2a1a2,...,a2a1an,a2a2a1,a2a2a2,...,a2a2an,...,a2ana1,a2ana2,a2anan,

                                                         ⋮

ana1a1,ana1a2,...,ana1an,ana2a1,ana2a2,...,ana2an,...,anana1,anana2,ananan,

a1a1a1a1,a1a1a1a2,...

El objetivo es probar que la lista anterior enumera sin repeticiones todas las palabras de Σ∗, i.e. produce naturalmente una biyeccion entre ω y Σ∗. Pero antes debemos definir mas formalmente la lista. Para esto definamos s≤:Σ∗→Σ∗ de la siguiente manera

1. - s≤((an)m)=(a1)m+1, para cada m≥0

2. - s≤(αai(an)m)=αai+1(a1)m, cada vez que α∈Σ∗, 1≤i<n y m≥0

Notese que la definicion de s≤ es correcta ya que una palabra de Σ∗ ya sea es de la forma (an)m, con m≥0, o es de la forma αai(an)m, con α∈Σ∗, 1≤i<n y m≥0; y estos dos casos posibles son mutuamente excluyentes.

Claramente se tiene entonces que la lista anterior puede ser escrita de la siguiente manera ε,s≤(ε),s≤(s≤(ε)),s≤(s≤(s≤(ε))),s≤(s≤(s≤(s≤(ε)))),... Con esta definicion formal de la lista, podemos probar de la misma forma en la que lo hicimos arriba para el caso Σ=~Num que:

1. (S) Toda palabra de Σ∗ aparece en la lista

2. (I) Ninguna palabra de Σ∗ aparece mas de una ves en la lista

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

Definamos ∗≤:ω→Σ∗ recursivamente de la siguiente manera:

1. - ∗≤(0)=ε

2. - ∗≤(i+1)=s≤(∗≤(i))

Es claro que entonces ∗≤(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 ∗≤ es biyectiva. A continuacion describiremos su inversa. Primero un lema facil pero muy importante.

Notar que k del lema anterior es |α|−1 y los numeros ik,...,i0 van dando el numero de orden de cada simbolo de α yendo de izquierda a derecha. Por ejemplo si Σ={%,!,@} y ≤ es el orden total sobre Σ dado por %<!<@ (es decir que aqui a1=%, a2=! y a3=@) entonces para la palabra !%@%@ tenemos k=4 y i4=2, i3=1, i2=3, i1=1 y i0=3. Sin envargo si hubieramos tomado el orden dado por @<%<!, para la misma palabra hubieramos tenido i4=3, i3=2, i2=1, i1=2 y i0=1.

Ahora podemos definir la funcion #≤ de la siguiente manera #≤:Σ∗→ωε→0aik...ai0→iknk+...+i0n0

Proof. Primero probaremos por induccion en x que

1. (a) Para cada x∈ω, se tiene que #≤(∗≤(x))=x

El caso x=0 es trivial. Supongamos que #≤(∗≤(x))=x, veremos entonces que #≤(∗≤(x+1))=x+1. Sean k≥0 y ik,...,i0 tales que ∗≤(x)=aik...ai0. Ya que #≤(∗≤(x))=x tenemos que x=iknk+...+i0n0. Hay varios casos.

Caso i0<n. Entonces ∗≤(x+1)=s≤(∗≤(x))=aik...ai0+1 por lo cual #≤(∗≤(x+1))=iknk+ik−1nk−1+...+(i0+1)n0=(iknk+ik−1nk−1+...+i0n0)+1=x+1 Caso ik=ik−1=...=i0=n. Entonces ∗≤(x+1)=s≤(∗≤(x))=(a1)k+2 por lo cual #≤(∗≤(x+1))=1nk+1+1nk+...+1n1+1n0=(nnk+nnk−1+...+nn0)+1=x+1 Caso i0=i1=...=ih=n, ih+1≠n,  para algun 0≤h<k. Entonces ∗≤(x+1)=s≤(∗≤(x))=aik...aih+2aih+1+1(a1)h por lo cual #≤(∗≤(x+1))=iknk+...+ih+2nh+2+(ih+1+1)nh+1+1nh+...+1n1+1n0=(iknk+...+ih+2nh+2+ih+1nh+1+nh+1+nh+...+n1)+1=(iknk+...+ih+2nh+2+ih+1nh+1+nnh+...+nn0)+1=x+1 De esta forma hemos probado (a).

Por definicion la inversa de ∗≤ es la funcion con dominio Σ∗ que a una palabra α le asocia el unico x∈ω tal que ∗≤(x)=α. Es decir debemos probar que

1. (b) #≤(α)= unico x∈ω tal que ∗≤(x)=α, para cada α∈Σ∗

Pero (b) es una concecuencia inmediata de (a).  

Cabe destacar que dada una palabra α, el numero #≤(α) nos dice en que posicion se hubica α en la lista, es decir α es la (#≤(α)+1)-esima palabra de la lista.

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 ω y palabras del alfabeto Σ. Es decir, en algun sentido identificamos palabras y numeros ya que se corresponden biunivocamente. Supongamos que α es una palabra de Σ∗−{ε} y queremos "verla como un numero". Entonces en ves de ver sus simbolos vemos los ordenes de aparicion en Σ de los mismos y miramos la suma de potencias asociada.

Supongamos ahora que x es un numero de ω−{0} y ademas supongamos que somos super inteligentes y que cuando vemos a x vemos la secuencia unica de numeros ik,ik−1,...,i0 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 ik,ik−1,...,i0 como palabra, reemplazando cada ij por el simbolo ij-esimo de Σ.

2.1.2.1 Caracter recursivo de las funciones s\protect≤, ∗\protect≤ y #\protect≤

Es un ejercicio (dejado al lector) probar que cualquiera sea α∈Σ∗, se tiene que s≤(ε)=a1s≤(αai)=αai+1, i<ns≤(αan)=s≤(α)a1 Notese que esto nos permite calcular recursivamente el valor de s≤ ya que las ecuaciones anteriores nos muestran como obtener rapidamente s≤(αa) en terminos de s≤(α) y a, donde a es un elemento cualquiera de Σ. Por supuesto, en algun momento deberemos usar el dato inicial s≤(ε)=a1. En un lenguaje de programacion funcional, las tres ecuaciones anteriores son directamente un programa para computar s≤ 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≤ (esto esta hecho mas adelante en la primera lista de funciones Σ-efectivamente computables).

Lo mismo sucede con la funcion ∗≤ la cual fue directamente definida en forma recursiva por las ecuaciones ∗≤(0)=ε∗≤(i+1)=s≤(∗≤(i)) Dejamos al lector corroborar que la funcion #≤ verifica las siguientes ecuaciones, las cuales obviamente pueden ser usadas para calcular recursivamente sus valores #≤(ε)=0#≤(αai)=#≤(α).n+i

2.1.2.2 Extension del orden total de Σ a Σ∗

Dado un orden total ≤ sobre Σ, podemos extender ≤ a Σ∗ de la siguiente manera

1. - α≤β sii #≤(α)≤#≤(β)

Es decir α≤β sii α=β o α ocurre antes que β en la lista. Dejamos como ejercicio para el lector probar que ≤ es un orden total sobre Σ∗. Llamaremos a este orden el orden total de Σ∗ inducido por ≤. Tal como en el caso de la notacion decimal clasica (con 0) el orden total de Σ∗ inducido por ≤ puede ser caracterizado “lexicograficamente” en forma similar al orden de los diccionarios. El siguiente lema muestra esto.

Proof. hhhhh  

Tambien se puede caracterizar la relacion “menor” relativa al orden total de Σ∗ inducido por ≤ de manera recursiva:

Deberia ser intuitivamente claro que el orden recien definido sobre Σ∗ posee las mismas propiedades matematicas que el orden usual de ω. 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 ω que tambien vale en Σ∗ con el orden inducido por un orden total sobre Σ: