7.7 Modelo matematico de las formulas elementales

En esta seccion daremos un modelo matematico de los conceptos de termino elemental de tipo τ$\tau$ y formula elemental de tipo τ$\tau$. Esto corresponde al punto (1) del Programa de Logica Matematica.

7.7.1 Variables

Las variables usadas en las formulas elementales no estaban del todo especificadas. Para hacer bien preciso este concepto definiremos un conjunto concreto de variables. Sea Var$Var$ el siguiente conjunto de palabras del alfabeto {X,0,1,...,9,0,1,...,9}: Var={X1,X2,...,X9,X10,X11,...,X19,X20,X21,...} Es decir el elemento n-esimo de Var es la palabra de la forma Xα donde α es el resultado de reemplazar en la palabra que denota n en notacion decimal, el ultimo numeral por su correspondiente numeral bold y los otros por sus correspondientes italicos. Para dar un ultimo ejemplo, el elemento trecientos cuarenta y unesimo de Var es la siguiente palabra de longitud cuatro: X341 A los elementos de Var los llamaremos variables. La razon por la cual usamos numerales italicos y bold es que a los numerales normales los usamos habitualmente en los tipos y sera conveniente que entonces no ocurran en las variables. Ademas tomamos el ultimo simbolo de cada variable en bold para que de esta manera nunca una variable sea una subpalabra de otra variable distinta a ella, lo cual contribuye a simplificar la escritura de los resultados.

Denotaremos con xi al i-esimo elemento de Var, para cada i∈N.

7.7.2 Terminos

Dado un tipo τ, definamos recursivamente los conjuntos de palabras Tτk, con k≥0, de la siguiente manera: Tτ0=Var∪CTτk+1=Tτk∪{f(t1,...,tn):f∈Fn, n≥1 y t1,...,tn∈Tτk}. Sea Tτ=⋃k≥0Tτk Los elementos de Tτ seran llamados terminos de tipo τ. Un termino t es llamado cerrado si xi no es subpalabra de t, para cada i∈N. Definamos Tτc={t∈Tτ:t es cerrado} Algunos ejemplos:

1. (E1) Sea τ=({uno,doli},{MAS,P},{Her},a), con a dado por a(MAS)=4, a(P)=1 y a(Her)=3. Entonces

   1. Las palabras uno, doli y X156669 son terminos de tipo τ ya que pertenecen a Tτ0

   2. MAS(uno,doli,X19,X5) y P(uno) son terminos de tipo τ ya que pertenecen a Tτ1 (por que?)

   3. Las palabras P(P(uno))     MAS(P(X4),doli,X19,X5) son terminos de tipo τ ya que pertenecen a Tτ2

   4. P(MAS(P(X4),MAS(X1,X2,X3,X4),X19,X5)) es un termino ya que pertenece a Tτ3

   5. uno, doli, P(uno) y MAS(uno,doli,doli,doli) son terminos cerrados de tipo τ

   Lo que debe quedar claro es que como objetos matematicos los terminos son meras palabras, por ejemplo MAS(uno,doli,X19,X5) es una palabra (de longitud 20)

2. (E2) Sea τ=({0,1},{+,×,↑},∅,a), con a dado por a(+)=2, a(×)=3 y a(↑)=1. Entonces X1119        0        1        +(+(↑(X4),×(X2,1,0)),×(1,X2,X3)) son terminos de tipo τ. Tambien ↑(+(↑(0),×(0,1,0))) es un termino cerrado de tipo τ

3. (E3) Sea τ=(∅,{s,i},∅,{(s,2),(i,2)}) el tipo de los reticulados terna. Entonces s(X2,X3)         s(s(X4,X14),i(X2,X1119)) son terminos de tipo τ. No hay terminos cerrados de tipo τ. Cabe destacar que X2 s X3 no es un termino de tipo τ aunque esto no es trivial de la definicion de termino y requiere de una demostracion.

Observacion importante: Notar que los terminos de tipo τ son un modelo matematico de los terminos elementales puros de tipo τ, es decir aquellos en los cuales no ocurren nombres de elementos fijos. Medite...

El siguiente lema es la herramienta basica para probar propiedades de los terminos.

Proof. Por induccion en k.

CASO k=1: Es directo ya que por definicion Tτ1=Var∪C∪{f(t1,...,tn):f∈Fn, n≥1 y t1,...,tn∈Tτ0}.

CASO k⇒k+1: Sea t∈Tτk+1. Por definicion de Tτk+1 tenemos que t∈Tτk o t=f(t1,...,tn) con f∈Fn, n≥1 y t1,...,tn∈Tτk. Si se da que t∈Tτk, entonces podemos aplicar hipotesis inductiva y usar que Tτk−1⊆Tτk. Esto completa el caso.  

Algunos ejemplos de propiedades de los terminos las cuales se pueden probar facilmente usando el lema anterior son

1. - Si t∈Tτ es tal que en t ocurre el simbolo ), entonces t=f(t1,...,tn) con f∈Fn, n≥1 y t1,...,tn∈Tτ.

2. - Ningun termino comienza con un simbolo del alfabeto {0,1,...,9}

3. - Si t∈Tτ comienza con X entonces t∈Var

4. - Si t∈Tτ y [t]i=), con i<|t|, entonces [t]i+1= , o [t]i+1= )

5. - Si t∈Tτ, entonces |t|(=|t|).

Una posible forma de probar que una palabra dada no es un termino es encontrar una propiedad que posean todos los terminos la cual no cumpla dicha palabra. Por ejemplo si τ=(∅,{glp},∅,a), con a(glp)=1, la palabra α=glp((X133) no es un termino ya que |α|(≠|α|).

7.7.2.1 Unicidad de la lectura de terminos

Definamos conjuntos Balk, con k≥1 de la siguiente manera: Bal1={()}Balk+1=Balk∪{(b1...bn):b1,...,bn∈Balk,n≥1}. Sea Bal=⋃k≥1Balk Recordemos que β es un tramo inicial (propio) de α si hay una palabra γ tal que α=βγ (y β∉{ε,α}). En forma similar se define tramo final (propio).

Proof. Probaremos por induccion en k, que valen (1), (2) y (3) para cada b∈Balk. El caso k=1 es trivial. Supongamos b∈Balk+1. Si b∈Balk, se aplica directamente HI. Supongamos entonces que b=(b1...bn), con b1,...,bn∈Balk, n≥1. Por HI, b1,...,bn cumplen (1) por lo cual b cumple (1). Veamos que b cumple (2). Sea x un tramo inicial propio de b. Notese que x es de la forma x=(b1...bix1 con 0≤i≤n−1 y x1 un tramo inicial de bi+1 (en el caso i=0 interpretamos b1...bi=ε). Pero entonces ya que |x|(−|x|)=1+(i∑j=1|bj|(−|bj|))+|x1|(−|x1|) tenemos que por HI, se da que |x|(−|x|)>0. En forma analoga se puede ver que b cumple (3).  

Dado un alfabeto Σ tal que ( y ) pertenecen a Σ, definamos del:Σ∗→Σ∗, de la siguiente manera del(ε)=εdel(αa)=del(α)a, si a∈{(,)}del(αa)=del(α), si a∈Σ−{(,)}

Proof. Es dejada al lector.  

Proof. Es dejada al lector.  

Notese que en la definicion de tipo se exige que nunca un nombre de cte sea subpalabra propia de otro nombre de cte, lo cual garantiza que nunca puede ser un nombre de cte un tramo inicial o final propio de otro nombre de cte. Lo que si puede suceder es que un tramo final propio de un nombre de cte c sea un tramo inicial propio de otro nombre de cte d. Mas formalmente puede suceder que haya palabras x,y,z, las tres distintas de ε tales que c=xy y d=yz. En tal caso solemos decir que las palabras c y d se mordizquean. Por ejemplo si τ=({uno,noli},∅,∅,∅), es facil ver que τ es un tipo y que uno y noli se mordizquean. El lema siguiente nos dice que este es el unico caso de mordizqueo de terminos.

Proof. Supongamos s∈C. Ya que y≠ε tenemos que t debe comenzar con un simbolo que ocurre en un nombre de cte, lo cual dice que t no puede ser ni una variable ni de la forma g(t1,...,tm), es decir t∈C. Supongamos s∈Var. Si x≠ε tenemos que t debe comenzar con alguno de los siguientes simbolos 01...901 ...9 lo cual es absurdo. O sea que x=ε y por lo tanto t debe comenzar con X. Pero esto dice que t∈Var de lo que sigue facilmente que z=ε. Supongamos entonces que s es de la forma f(s1,...,sn). Ya que ) debe ocurrir en t, tenemos que t es de la forma g(t1,...,tm). O sea que del(s),del(t)∈Bal. Ya que ) ocurre en y, del(y)≠ε. Tenemos tambien que del(s)=del(x)del(y)del(t)=del(y)del(z) La primera igualdad, por (1) y (3) del Lema 7.3, nos dice que |del(y)|(−|del(y)|)≤0, y la segunda que |del(y)|(−|del(y)|)≥0, por lo cual |del(y)|(−|del(y)|)=0 Pero entonces (3) del Lema 7.3 nos dice que del(y) no puede ser tramo final propio de del(s), por lo cual debe suceder que del(y)=del(s), ya que del(y)≠ε. Claramente entonces obtenemos que del(x)=ε. Similarmente se puede ver que del(z)=ε. Ya que que t termina con ) tenemos que z=ε. O sea que f(s1,...,sn)=xg(t1,...,tm) con del(x)=ε, de lo que se saca que f=xg ya que ( no ocurre en x. De la definicion de tipo se desprende que x=ε.  

Proof. En virtud del Lema 7.2 solo nos falta probar la unicidad en el punto (2). Supongamos que t=f(t1,...,tn)=g(s1,...,sm) con n,m≥1,f∈Fn, g∈Fm, t1,...,tn,s1,...,sm∈Tτ. Notese que f=g. O sea que n=m=a(f). Notese que t1 es tramo inicial de s1 o s1 es tramo inicial de t1, lo cual por el lema anterior nos dice que t1=s1. Con el mismo razonamiento podemos probar que debera suceder t2=s2,...,tn=sn.  

El teorema anterior es importante ya que nos permite definir recursivamente funciones con dominio contenido en Tτ. Por ejemplo podemos definir una funcion F:Tτ→Tτ, de la siguiente manera:

1. - F(c)=c, para cada c∈C

2. - F(v)=v, para cada v∈Var

3. - F(f(t1,...,tn))=f(F(t1),...,F(tn)), si f∈Fn, con n≠2

4. - F(f(t1,t2))=f(t2,t1), si f∈F2.

Notese que si la unicidad de la lectura no fuera cierta, entonces las ecuaciones anteriores no estarian definiendo en forma correcta una funcion ya que el valor de F en termino t estaria dependiendo de cual descomposicion tomemos para t.

Ocurrencias de una palabra en otra

Dadas palabras α,β∈Σ∗, con |α|,|β|≥1, y un natural i∈{1,...,|β|}, se dice que α ocurre a partir de i en β cuando se de que existan palabras δ,γ tales que β=δαγ y |δ|=i−1. Intuitivamente hablando α ocurre a partir de i en β cuando se de que si comensamos a leer desde el lugar i-esimo de β en adelante, leeremos la palabra α completa y luego posiblemente seguiran otros simbolos.

Notese que una palabra α puede ocurrir en β, a partir de i, y tambien a partir de j, con i≠j. En virtud de esto, hablaremos de las distintas ocurrencias de α en β. Por ejemplo hay dos ocurrencias de la palabra aba en la palabra cccccccabaccccabaccccc y tambien hay dos ocurrencias de la palabra aba en la palabra cccccccababacccccccccc En el primer caso diremos que dichas ocurrencias de aba son disjuntas ya que ocupan espacios disjuntos dentro de la palabra. En cambio en el segundo caso puede apreciarse que las dos ocurrencias se superponen en una posicion. A veces diremos que una ocurrencia esta contenida o sucede dentro de otra. Por ejemplo la segunda ocurrencia de ab en babbbfabcccfabccc esta contenida en la primer ocurrencia de fabc en babbbfabcccfabccc.

No definiremos en forma matematica precisa el concepto de ocurrencia pero el lector no tendra problemas en comprenderlo y manejarlo en forma correcta.

Reemplazos de ocurrencias

Tambien haremos reemplazos de ocurrencias por palabras. Por ejemplo el resultado de reemplazar la primer ocurrencia de abb en ccabbgfgabbgg por oolala es la palabra ccoolalagfgabbgg. Cuando todas las ocurrencias de una palabra α en una palabra β sean disjuntas entre si, podemos hablar del resultado de reeplazar simultaneamente cada ocurrencia de α en β por γ. Por ejemplo si tenemos α=yetβ=ghsyetcjjjyetbcpyeteabcγ=%% entonces ghs%%cjjj%%bcp%%eabc es el resultado de reemplazar simultaneamente cada ocurrencia de α en β por γ. Es importante notar que los reemplazos se hacen simultaneamente y no secuencialmente (i.e. reemplazando la primer ocurrencia de α por γ y luego al resultado reemplazarle la primer ocurrencia de α por γ y asi sucesivamente). Obviamente el reemplazo secuencial puede dar un resultado distinto al simultaneo (que es el que usaremos en general) e incluso puede suceder que en el reemplazo secuencial el proceso se pueda iterar indefinidamente. Dejamos al lector armar ejemplos de estas cituaciones.

Tambien se pueden hacer reemplazos simultaneos de distintas palabras en una palabra dada. Supongamos tenemos palabras α1,...,αn,β tales que

1. - αi≠αj, para i≠j

2. - Para cada i, las distintas ocurrencias de αi en β son disjuntas

3. - Si αi ocurre en β y αj ocurre en β, con i≠j, entonces dichas ocurrencias son disjuntas

entonces dadas palabras cualesquiera γ1,...,γn hablaremos del resultado de reemplazar simultaneamente:

1. - cada ocurrencia de α1 en β, por γ1

2. - cada ocurrencia de α2 en β, por γ2

3.                         ⋮

4. - cada ocurrencia de αn en β, por γn

Por ejemplo si tomamos α1=ghα2=yetα3=anaβ=ghbbbyetbbgh%%ana##ana!!!anaγ1=AAγ2=BBBBγ3=CCC entonces AAbbbBBBBbbAA%%CCC##CCC!!!CCC es el resultado de reemplazar simultaneamente:

1. - cada ocurrencia de α1 en β, por γ1

2. - cada ocurrencia de α2 en β, por γ2

3. - cada ocurrencia de α3 en β, por γ3

7.7.2.2 Subterminos

Sean s,t∈Tτ. Diremos que s es subtermino (propio) de t si (no es igual a t y) s es subpalabra de t. A continuacion veremos de que manera ocurren los subterminos de un termino.

Proof. (a) Supongamos la ocurrencia de s comienza en algun tj. Entonces el Lema 7.6 nos conduce a que dicha ocurrencia debera estar contenida en tj. Veamos que la ocurrencia de s no puede ser a partir de un i∈{1,...,|f|}. Supongamos lo contrario. Tenemos entonces que s debe ser de la forma g(s1,...,sm) ya que no puede estar en Var∪C. Notese que i≠1 ya que en caso contrario s seria un tramo inicial propio de t. Pero entonces g debe ser un tramo final propio de f, lo cual es absurdo. Ya que s no puede comenzar con parentesis o coma, hemos contemplado todos los posibles casos de comienzo de la ocurrencia de s en t.

(b) y (c) pueden probarse por induccion, usando (a).  

Nota: Es importante notar que si bien no hemos definido en forma presisa el concepto de ocurrencia o de reemplazo de ocurrencias, la prueba del lema anterior es rigurosa en el sentido de que solo usa propiedades del concepto de ocurrencia y reemplazo de ocurrencias las cuales deberan ser comunes a cualquier definicion o formulacion matematica que se hiciera de aquellos conceptos. En este caso, es posible dar una defincion presisa y satisfactoria de dichos conceptos aunque para otros conceptos tales como el de prueba absoluta de consistencia, aun no se ha encontrado una formulacion matematica adecuada.

Tτ es efectivamente computable

Notemos que hay un alfabeto finito A tal que Tτ⊆A∗. Es decir que Tτ es un conjunto A-mixto y por lo tanto podriamos preguntarnos si es A-efectivamente computable. Es decir si hay un procedimiento efectivo que dada una palabra α∈A∗decida si α es un termino de tipo τ o no. Supongamos para simplificar el analisis que los conjuntos C y F son finitos. Una forma de convencerse rapidamente de que si hay tal procedimiento efectivo es la siguiente. Primero notamos que hay un procedimiento efectivo que dado un n∈ω da como salida una lista con todos los terminos de tipo τ que tienen longitud menor o igual a n. Dejamos al lector imaginar como haria este procedimiento basandose en la definicion recursiva de los conjuntos Tτk. Luego, usando este procedimiento efectivo es facil hacer uno que decida la pertenecia a Tτ. Cabe destacar que hay muchos otros procedimientos que son mas eficientes y se valen de un conocimiento mas fino de la estructura de los terminos. Mas adelante, en el contexto de la prueba del Teorema de Incompletitud (ver la prueba del Lema 7.57), se prueba que tambien Tτ es un conjunto A-p.r.. Dejamos al lector para masticar un rato el caso en el que los conjuntos C y F pueden ser infinitos. Mas concretamente dejamos como ejercicio probar que para un tipo τ cualquiera se tiene que Tτ es A-efectivamente computable sii C y F son A-efectivamente computables.

7.7.3 Formulas

Sea τ un tipo. Las palabras de alguna de las siguientes dos formas (t≡s),con t,s∈Tτr(t1,...,tn), con r∈Rn, n≥1 y t1,...,tn∈Tτ seran llamadas formulas atomicas de tipo τ. Por ejemplo si τ=({uno,doli},{MAS,P},{Her},a), con a dado por a(MAS)=4, a(P)=1 y a(Her)=3, entonces

1. - (uno≡doli)

2. - (X156669≡doli)

3. - Her(uno,X4,doli)

4. - (MAS(uno,doli,X19,X5)≡uno)

5. - Her(P(P(uno)),MAS(P(X4),doli,X19,X5),X19)

son formulas atomicas de tipo τ.

Dado un tipo τ, definamos recursivamente los conjuntos de palabras Fτk, con k≥0, de la siguiente manera: Fτ0={formulas atomicas de tipo τ}Fτk+1=Fτk∪{¬φ:φ∈Fτk}∪{(φ∨ψ):φ,ψ∈Fτk}∪               {(φ∧ψ):φ,ψ∈Fτk}∪{(φ→ψ):φ,ψ∈Fτk}∪                      {(φ↔ψ):φ,ψ∈Fτk}∪{∀vφ:φ∈Fτk y v∈Var}∪                                                                             {∃vφ:φ∈Fτk y v∈Var} Sea Fτ=⋃k≥0Fτk Los elementos de Fτ seran llamados formulas de tipo τ.

Algunos ejemplos:

1. (E1) Sea τ=({uno,doli},{MAS,P},{Her},a), con a dado por a(MAS)=4, a(P)=1 y a(Her)=3. Entonces

   1. ¬((X1≡X2)∧Her(P(doli),doli,X19))

   2. ∃X9Her(doli,doli,X9)

   3. ∃X9¬(uno≡doli)

   4. ¬∃X9∀X7(Her(X9,doli,X7)→(P(doli)≡X7))

   5. ∀X5559∀X7∃X51(MAS(uno,doli,X19,X5)≡uno)→Her(doli,doli,doli))

   son formulas de tipo τ

2. (E2) Sea τ=({0,1},{s,i},{≤},{(s,2),(i,2),(≤,2)}) el tipo de los reticulados cuaterna. Entonces

   1. ≤(1,0)

   2. ≤(X1,X2)

   3. ¬(s(X2,X1)≡X2))

   4. ∀X2∀X1≤(X2,s(X2,X1))

   5. ((i(X1,X2)≡0)∧(s(X1,X2)≡1))

   6. ∀X9∃X1((0≡X1)→∃X1¬≤(X2,s(X2,X1)))

   son formulas de tipo τ. Cabe destacar que (X1≤X2) no es una formula de tipo τ aunque, como veremos en los ejercicios esto no es trivial de la definicion de formula y requiere de una demostracion.

Observacion importante: Notar que las formulas de tipo τ son un modelo matematico de las formulas elementales puras de tipo τ , es decir aquellas en las cuales no ocurren nombres de elementos fijos. Medite...

El siguiente lema es la herramienta basica que usaremos para probar propiedades acerca de los elementos de Fτ.

Proof. Induccion en k.  

7.7.3.1 Unicidad de la lectura de formulas

Tal como para el caso de terminos veremos que las formulas tambien tienen su unicidad de lectura.

Proof. (b) Induccion en k. El caso k=0 es trivial. Supongamos (b) vale para cada φ∈Fτk y sea φ∈Fτk+1. Hay varios casos de los cuales haremos solo dos

CASO φ=(ψ1ηψ2), con ψ1,ψ2∈Fτk y η∈{∨,∧,→,↔}.

Podemos tomar x=ε y φ1=φ.

CASO φ=Qxiψ, con ψ∈Fτk, i≥1 y Q∈{∀,∃}.

Por HI hay ˉx∈({¬}∪{Qv:Q∈{∀,∃} y v∈Var})∗ y ψ1∈Fτ tales que ψ=ˉxψ1 y ψ1 es de la forma (γ1ηγ2) o atomica. Entonces es claro que x=Qxiˉx y φ1=ψ1 cumplen (b).  

Proof. Si φ es de la forma (t≡s), entonces |del(y)|(−|del(y)|)<0 para cada tramo final propio y de φ, lo cual termina el caso ya que del(ψ) es balanceada. Supongamos entonces φ=r(t1,...,tn). Notese que ψ no puede ser tramo final de t1,...,tn) ya que del(ψ) es balanceada y |del(y)|(−|del(y)|)<0 para cada tramo final y de t1,...,tn). Es decir que ψ=y(t1,...,tn), para algun tramo final y de r. Ya que en ψ no ocurren cuantificadores ni nexos ni el simbolo ≡ el Lema 7.8 nos dice ψ=˜r(s1,...,sm), con ˜r∈Rm, m≥1 y s1,...,sm∈Tτ. Ahora es facil usando un argumento paresido al usado en la prueba del Teorema 7.1 concluir que m=n, si=ti, i=1,...,n y ˜r es tramo final de r. Por (3) de la definicion de tipo tenemos que ˜r=r lo cual nos dice que φ=ψ y x=ε  

Proof. Por induccion en el k tal que φ∈Fτk. El caso k=0 es probado en el lema anterior. Asumamos que el resultado vale cuando φ∈Fτk y veamos que vale cuando φ∈Fτk+1. Basta con hacer el caso en que φ∈Fτk+1−Fτk. Primero haremos el caso en que φ=Qvφ1, con Q∈{∀,∃},v∈Var y φ1∈Fτk. Supongamos x≠ε. Ya que ψ no comienza con simbolos de v, tenemos que ψ debe ser tramo final de φ1 lo cual nos dice que hay una palabra x1 tal que x=Qvx1 y φ1=x1ψ. Por HI tenemos que x1∈({¬}∪{Qv:Q∈{∀,∃} y v∈Var})∗ con lo cual x∈({¬}∪{Qv:Q∈{∀,∃} y v∈Var})∗. El caso en el que φ=¬φ1 con φ1∈Fτk, es similar. Note que no hay mas casos posibles ya que φ no puede comenzar con ( porque en x no ocurren parentesis por hipotesis.  

Proof. Ya que φ termina con ) tenemos que del(y)≠ε. Por un lema anterior tenemos que del(φ),del(ψ)∈Bal. Ademas del(φ)=del(x)del(y)del(ψ)=del(y)del(z) La primera igualdad, por (1) y (3) del Lema 7.3, nos dice que |del(y)|(−|del(y)|)≤0, y la segunda que |del(y)|(−|del(y)|)≥0, por lo cual |del(y)|(−|del(y)|)=0 Pero entonces (3) del Lema 7.3 nos dice que del(y) no puede ser tramo final propio de del(φ), por lo cual debe suceder que del(y)=del(φ), ya que del(y)≠ε. Claramente entonces obtenemos que del(x)=ε. Similarmente se puede ver que del(z)=ε. Pero ψ termina con ) lo cual nos dice que z=ε. Es decir que φ=xψ. Por el lema anterior tenemos que x∈({¬}∪{Qv:Q∈{∀,∃} y v∈Var})∗