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}$\{X,0,1,...,9,0,1,...,9\}$: Var={X1,X2,...,X9,X10,X11,...,X19,X20,X21,...}$$Var=\{X1,X2,...,X9,X10,X11,...,X19,X20,X21,...\}$$ Es decir el elemento n$n$-esimo de Var$Var$ es la palabra de la forma Xα$X\alpha$ donde α$\alpha$ es el resultado de reemplazar en la palabra que denota n$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$Var$ es la siguiente palabra de longitud cuatro: X341$$X341$$ A los elementos de Var$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$x_i$ al i$i$-esimo elemento de Var$Var$, para cada i∈N$i\in N$.

7.7.2 Terminos

Dado un tipo τ$\tau$, definamos recursivamente los conjuntos de palabras Tτk$T_k^{\tau }$, con k≥0$k\ge 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}.$$\begin{array}{cc}{T}_0^{\tau }& =Var\cup C\\ T_{k+1}^{\tau }& =T_k^{\tau }\cup \left\{f\right(t_1,...,t_n):f\in F_n\text{,}n\ge 1\text{y}{t}_1,...,t_n\in T_k^{\tau }\}.\end{array}$$ Sea Tτ=⋃k≥0Tτk$$T^{\tau }=\bigcup _{k\ge 0}{T}_k^{\tau }$$ Los elementos de Tτ$T^{\tau }$ seran llamados terminos de tipo τ$\tau$. Un termino t$t$ es llamado cerrado si xi$x_i$ no es subpalabra de t$t$, para cada i∈N$i\in N$. Definamos Tτc={t∈Tτ:t es cerrado}$$T_c^{\tau }=\{t\in T^{\tau }:t\text{es cerrado}\}$$ Algunos ejemplos:

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

   1. Las palabras uno$uno$, doli$doli$ y X156669$X156669$ son terminos de tipo τ$\tau$ ya que pertenecen a Tτ0$T_0^{\tau }$

   2. MAS(uno,doli,X19,X5)$MAS(uno,doli,X19,X5)$ y P(uno) $P\left(uno\right)$son terminos de tipo τ$\tau$ ya que pertenecen a Tτ1$T_1^{\tau }$ (por que?)

   3. Las palabras P(P(uno))     MAS(P(X4),doli,X19,X5)$$P\left(P\right(uno\left)\right)MAS\left(P\right(X4),doli,X19,X5)$$ son terminos de tipo τ$\tau$ ya que pertenecen a Tτ2$T_2^{\tau }$

   4. P(MAS(P(X4),MAS(X1,X2,X3,X4),X19,X5))$P\left(MAS\right(P\left(X4\right),MAS(X1,X2,X3,X4),X19,X5\left)\right)$ es un termino ya que pertenece a Tτ3$T_3^{\tau }$

   5. uno$uno$, doli$doli$, P(uno)$P\left(uno\right)$ y MAS(uno,doli,doli,doli)$MAS(uno,doli,doli,doli)$ son terminos cerrados de tipo τ$\tau$

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

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

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

Observacion importante: Notar que los terminos de tipo τ$\tau$ son un modelo matematico de los terminos elementales puros de tipo τ$\tau$, 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$k$.

CASO k=1$k=1$: Es directo ya que por definicion Tτ1=Var∪C∪{f(t1,...,tn):f∈Fn, n≥1 y t1,...,tn∈Tτ0}.$$T_1^{\tau }=Var\cup C\cup \left\{f\right(t_1,...,t_n):f\in F_n\text{,}n\ge 1\text{y}{t}_1,...,t_n\in T_0^{\tau }\}.$$

CASO k⇒k+1$k\Rightarrow k+1$: Sea t∈Tτk+1$t\in T_{k+1}^{\tau }$. Por definicion de Tτk+1$T_{k+1}^{\tau }$ tenemos que t∈Tτk$t\in T_k^{\tau }$ o t=f(t1,...,tn)$t=f(t_1,...,t_n)$ con f∈Fn$f\in F_n$, n≥1$n\ge 1$ y t1,...,tn∈Tτk$t_1,...,t_n\in T_k^{\tau }$. Si se da que t∈Tτk$t\in T_k^{\tau }$, entonces podemos aplicar hipotesis inductiva y usar que Tτk−1⊆Tτk$T_{k-1}^{\tau }\subseteq T_k^{\tau }$. 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τ$t\in T^{\tau }$ es tal que en t$t$ ocurre el simbolo )$)$, entonces t=f(t1,...,tn)$t=f(t_1,...,t_n)$ con f∈Fn$f\in F_n$, n≥1$n\ge 1$ y t1,...,tn∈Tτ$t_1,...,t_n\in T^{\tau }$.

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

3. - Si t∈Tτ$t\in T^{\tau }$ comienza con X$X$ entonces t∈Var$t\in Var$

4. - Si t∈Tτ$t\in T^{\tau }$ y [t]i=)${\left[t\right]}_i=)$, con i<|t|$i<\left|t\right|$, entonces [t]i+1=${\left[t\right]}_{i+1}=$ ,$,$ o [t]i+1=${\left[t\right]}_{i+1}=$ )$)$

5. - Si t∈Tτ$t\in T^{\tau }$, entonces |t|(=|t|)${\left|t\right|}_{(}={\left|t\right|}_{)}$.

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)$\tau =(\varnothing ,\{glp\},\varnothing ,a)$, con a(glp)=1$a\left(glp\right)=1$, la palabra α=glp((X133)$\alpha =glp\left(\right(X133)$ no es un termino ya que |α|(≠|α|)${\left|\alpha \right|}_{(}\ne {\left|\alpha \right|}_{)}$.

7.7.2.1 Unicidad de la lectura de terminos

Definamos conjuntos Balk$Ba{l}_k$, con k≥1$k\ge 1$ de la siguiente manera: Bal1={()}Balk+1=Balk∪{(b1...bn):b1,...,bn∈Balk,n≥1}.$$\begin{array}{cc}Ba{l}_1& =\left\{\right(\left)\right\}\\ Ba{l}_{k+1}& =Ba{l}_k\cup \left\{\right(b_1...b_n):b_1,...,b_n\in Ba{l}_k,n\ge 1\}.\end{array}$$ Sea Bal=⋃k≥1Balk$$Bal=\bigcup _{k\ge 1}Ba{l}_k$$ Recordemos que β$\beta$ es un tramo inicial (propio) de α$\alpha$ si hay una palabra γ$\gamma$ tal que α=βγ$\alpha =\beta \gamma$ (y β∉{ε,α}$\beta \notin \{\epsilon ,\alpha \}$). En forma similar se define tramo final (propio).

Proof. Probaremos por induccion en k$k$, que valen (1), (2) y (3) para cada b∈Balk$b\in Ba{l}_k$. El caso k=1$k=1$ es trivial. Supongamos b∈Balk+1$b\in Ba{l}_{k+1}$. Si b∈Balk$b\in Ba{l}_k$, se aplica directamente HI. Supongamos entonces que b=(b1...bn)$b=(b_1...b_n)$, con b1,...,bn∈Balk$b_1,...,b_n\in Ba{l}_k$, n≥1$n\ge 1$. Por HI, b1,...,bn$b_1,...,b_n$ cumplen (1) por lo cual b$b$ cumple (1). Veamos que b$b$ cumple (2). Sea x$x$ un tramo inicial propio de b$b$. Notese que x$x$ es de la forma x=(b1...bix1$x=(b_1...b_i{x}_1$ con 0≤i≤n−1$0\le i\le n-1$ y x1$x_1$ un tramo inicial de bi+1$b_{i+1}$ (en el caso i=0$i=0$ interpretamos b1...bi=ε)$b_1...b_i=\epsilon )$. Pero entonces ya que |x|(−|x|)=1+(i∑j=1|bj|(−|bj|))+|x1|(−|x1|)$${\left|x\right|}_{(}-{\left|x\right|}_{)}=1+(\sum _{j=1}^i{\left|b_j\right|}_{(}-{\left|b_j\right|}_{)})+{\left|x_1\right|}_{(}-{\left|x_1\right|}_{)}$$ tenemos que por HI, se da que |x|(−|x|)>0${\left|x\right|}_{(}-{\left|x\right|}_{)}>0$. En forma analoga se puede ver que b$b$ cumple (3).  

Dado un alfabeto Σ$\Sigma$ tal que ($($ y )$)$ pertenecen a Σ$\Sigma$, definamos del:Σ∗→Σ∗$del:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$, de la siguiente manera del(ε)=εdel(αa)=del(α)a, si a∈{(,)}del(αa)=del(α), si a∈Σ−{(,)}$$\begin{array}{cc}del\left(\epsilon \right)& =\epsilon \\ del\left(\alpha a\right)& =del\left(\alpha \right)a\text{, si}a\in \left\{\right(,\left)\right\}\\ del\left(\alpha a\right)& =del\left(\alpha \right)\text{, si}a\in \Sigma -\left\{\right(,\left)\right\}\end{array}$$

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$c$ sea un tramo inicial propio de otro nombre de cte d$d$. Mas formalmente puede suceder que haya palabras x,y,z$x,y,z$, las tres distintas de ε$\epsilon$ tales que c=xy$c=xy$ y d=yz$d=yz$. En tal caso solemos decir que las palabras c$c$ y d$d$ se mordizquean. Por ejemplo si τ=({uno$\tau =\left(\right\{uno$,noli},∅,∅,∅)$noli\},\varnothing ,\varnothing ,\varnothing )$, es facil ver que τ$\tau$ es un tipo y que uno$uno$ y noli$noli$ se mordizquean. El lema siguiente nos dice que este es el unico caso de mordizqueo de terminos.

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

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)$$t=f(t_1,...,t_n)=g(s_1,...,s_m)$$ con n,m≥1,f∈Fn$n,m\ge 1,f\in F_n$, g∈Fm$g\in F_m$, t1,...,tn,s1,...,sm∈Tτ$t_1,...,t_n,s_1,...,s_m\in T^{\tau }$. Notese que f=g$f=g$. O sea que n=m=a(f)$n=m=a\left(f\right)$. Notese que t1$t_1$ es tramo inicial de s1$s_1$ o s1$s_1$ es tramo inicial de t1$t_1$, lo cual por el lema anterior nos dice que t1=s1$t_1=s_1$. Con el mismo razonamiento podemos probar que debera suceder t2=s2,...,tn=sn$t_2=s_2,...,t_n=s_n$.  

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

1. - F(c)=c$F\left(c\right)=c$, para cada c∈C$c\in C$

2. - F(v)=v$F\left(v\right)=v$, para cada v∈Var$v\in Var$

3. - F(f(t1,...,tn))=f(F(t1),...,F(tn))$F\left(f\right(t_1,...,t_n\left)\right)=f\left(F\right(t_1),...,F(t_n\left)\right)$, si f∈Fn$f\in F_n$, con n≠2$n\ne 2$

4. - F(f(t1,t2))=f(t2,t1)$F\left(f\right(t_1,t_2\left)\right)=f(t_2,t_1)$, si f∈F2.$f\in F_2.$

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$F$ en termino t$t$ estaria dependiendo de cual descomposicion tomemos para t$t$.

Ocurrencias de una palabra en otra

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

Notese que una palabra α$\alpha$ puede ocurrir en β$\beta$, a partir de i$i$, y tambien a partir de j$j$, con i≠j$i\ne j$. En virtud de esto, hablaremos de las distintas ocurrencias de α$\alpha$ en β$\beta$. Por ejemplo hay dos ocurrencias de la palabra aba$aba$ en la palabra cccccccabaccccabaccccc$$cccccccabaccccabaccccc$$ y tambien hay dos ocurrencias de la palabra aba$aba$ en la palabra cccccccababacccccccccc$$cccccccababacccccccccc$$ En el primer caso diremos que dichas ocurrencias de aba$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$ab$ en babbbfabcccfabccc$babbbfabcccfabccc$ esta contenida en la primer ocurrencia de fabc$fabc$ en babbbfabcccfabccc$babbbfabcccfabccc$.