7.4 Formulas elementales de tipo $\tau$

Recordemos que cada uno de los tipos de estructuras consideradas en el capitulo Estructuras y su Lenguaje Elemental tiene su tipo asociado. Es decir: $$\begin{array}{cc}\text{Tipo de los posets}& =(\varnothing ,\varnothing ,\{\le \},\{(\le ,2)\left\}\right)\\ \text{Tipo de los ret. ternas}& =(\varnothing ,\{s,i\},\varnothing ,\{(s,2),(i,2)\left\}\right)\\ \text{Tipo de los ret. acotados}& =\left(\right\{0,1\},\{s,i\},\varnothing ,\{(s,2),(i,2)\left\}\right)\\ \text{Tipo de los ret. comp.}& =\left(\right\{0,1\},\{s,i,c\},\varnothing ,\{(s,2),(i,2),(c,1)\left\}\right)\\ \text{Tipo de los ret. cuaternas}& =(\varnothing ,\{s,i\},\{\le \},\{(s,2),(i,2),(\le ,2)\left\}\right)\\ \text{Tipo de las median algebras}& =(\varnothing ,\{M\},\varnothing ,\{(M,3)\left\}\right)\\ \text{Tipo de los grafos}& =(\varnothing ,\varnothing ,\{r\},\{(r,2)\left\}\right)\\ \text{Tipo de los grafos bicoloreados}& =(\varnothing ,\varnothing ,\{r,R\},\{(r,2),(R,1)\left\}\right)\end{array}$$ Notese que en cada uno de los casos anteriores los simbolos de $C\cup F\cup R$ son los que se usan (junto con los simbolos logicos, las variables y los nombres de elementos fijos) para formar sus correspondientes terminos y formulas elementales. Es decir, lo particular de los terminos y las formulas elementales de cada tipo de estructura estaba dado por los correspondientes simbolos de $C\cup F\cup R$. Esto nos permite generalizar nuestros conceptos intuitivos de termino elemental y formula elemental, para el caso de cualquier tipo $\tau$ de estructuras. Primero definamos dado un tipo $\tau =(C,F,R,a)$ los terminos elementales de tipo $\tau$ por las siguientes clausulas:

1. - Cada palabra de $C$ es un termino elemental de tipo $\tau$

2. - Las variables $x,y,z,w,...$ son terminos elementales de tipo $\tau$

3. - Los nombres de elementos fijos $a,b,c,d,...$ son terminos elementales de tipo $\tau$

4. - Si $f\in F_n$, con $n\ge 1$ y $t_1,...,t_n$ son terminos elementales de tipo $\tau$, entonces $f(t_1,...,t_n)$ es un termino elemental de tipo $\tau$

5. - Una palabra es un termino elemental de tipo $\tau$ si y solo si se puede construir usando las clausulas anteriores

Deberia quedar claro que un termino elemental de tipo $\tau$ como objeto matematico es una palabra. Tambien deberia quedar claro que arriba $f(t_1,...,t_n)$ denota el resultado de concatenar las $n+(n-1)+3$ siguientes palabras $$f(t_1,t_2,...,t_n)$$ es decir que $f(t_1,...,t_n)$ es una palabra de longitud $\left|f\right|+\left|t_1\right|+...+\left|t_n\right|+(n-1)+2$ (notar que $n-1$ cuenta la cantidad de comas). Veamos algunos ejemplos:

1. (E1) Si $\tau$ es el tipo $$\left(\right\{un,0\},\{MAS,P,+\},\{Verde\},\{(MAS,4),(P,1),(+,2),(Verde,1)\left\}\right)$$ entonces las siguientes palabras son terminos elementales de tipo $\tau$:

   1. $un$

   2. $0$

   3. $x$

   4. $a$

   5. $MAS(a,b,un,z)$

   6. $P\left(P\right(z\left)\right)$

   7. $+(+(0,x),P(z\left)\right)$

   8. $MAS\left(P\right(0),+(0,b),un,MAS(x,x,x,x\left)\right)$

   Por supuesto las aridades de los nombres de $F$ son importantes y deben ser respetadas. Por ejemplo $$P(x,y)MAS(a,b)+(x,y,z)$$ no son terminos elementales de tipo $\tau$.

2. (E2) Si $\tau$ es el tipo de los reticulados complementados $$\left(\right\{0,1\},\{s,i,c\},\varnothing ,\{(s,2),(i,2),(c,1)\left\}\right)$$ entonces las siguientes palabras son terminos elementales de tipo $\tau$:

   1. $s(x,y)$

   2. $a$

   3. $s\left(i\right(x,0),z)$

   4. $c\left(s\right(i(x,0),c\left(z\right)\left)\right)$

   5. $c\left(s\right(i(0,0),0\left)\right)$

   Notese que no coinciden con los terminos elementales de reticulados complementados definidos en el capitulo Estructuras y su Lenguaje Elemental ya que aqui usamos un formato mas general y usamos $s(x,y)$ en lugar de $\left(xsy\right)$, etc. Obviamente esto no cambia mucho las cosas y es hecho a los fines de homogeneisar la escritura y no hacer un uso distinto para los nombres de funcion de aridad 2.

3. (E3) Si $\tau$ es tal que $F=\varnothing$ entonces los terminos elementales de tipo $\tau$ son las variables, los nombres de elementos fijos y los elementos de $C$

4. (E4) Si $\tau$ es el tipo $$\left(\right\{1,er\},\{+,s\},\varnothing ,\{(+,5),(s,3)\left\}\right)$$ entonces las siguientes palabras son terminos elementales de tipo $\tau$:

   1. $s(x,z,1)$

   2. $+(1,1,1,1,1)$

   3. $s(+(er,er,z,a,a),er,s(x,x,x\left)\right)$

5. (E5) Tal como lo aclaramos anteriormente la definicion de tipo es muy libre en lo que respecta a que palabras componen los conjuntos $C$, $F$ y $R$, es decir salvo por ciertas restricciones leves, ellas pueden ser cualquier palabra aunque a veces resulte chocante la eleccion de las mismas debido al uso y costumbre de los matematicos. Por ejemplo si tomamos $\tau =\left(\right\{\le \},\{1\},\varnothing ,\{(1,3)\left\}\right)$, obtenemos un tipo en el cual $\le$ es un nombre de constante y el numeral $1$ es un nombre de funcion $3$-aria (lo cual nos dice que en una estructura de tipo $\tau$ el simbolo $\le$ debera interpretarse como un elemento del universo y el simbolo $1$ debera interpretarse como una operacion $3$-aria). Algunos terminos elementales de este tipo $\tau$ son:

   1. $x$

   2. $\le$

   3. $1(z,z,z)$

   4. $1(x,a,1(\le ,\le ,\le \left)\right)$

Terminos elementales puros de tipo $\tau$

Un termino elemental de tipo $\tau$ sera llamado puro cuando en el no ocurran nombres de elementos fijos.

Ahora si usando el concepto de termino elemental de tipo $\tau$ podemos definir las formulas elementales de tipo $\tau$ con las siguientes clausulas:

1. - Si $t$ y $s$ son terminos elementales de tipo $\tau$, entonces la palabra $(t=s)$ es una formula elemental de tipo $\tau$

2. - Si $r\in R_n$, con $n\ge 1$ y $t_1,...,t_n$ son terminos elementales de tipo $\tau$, entonces $r(t_1,...,t_n)$ es una formula elemental de tipo $\tau$

3. - Si ${\phi }_1$ y ${\phi }_2$ son formulas elementales de tipo $\tau$, entonces $({\phi }_1\wedge {\phi }_2)$ es una formula elemental de tipo $\tau$

4. - Si ${\phi }_1$ y ${\phi }_2$ son formulas elementales de tipo $\tau$, entonces $({\phi }_1\vee {\phi }_2)$ es una formula elemental de tipo $\tau$

5. - Si ${\phi }_1$ y ${\phi }_2$ son formulas elementales de tipo $\tau$, entonces $({\phi }_1\leftrightarrow {\phi }_2)$ es una formula elemental de tipo $\tau$

6. - Si ${\phi }_1$ y ${\phi }_2$ son formulas elementales de tipo $\tau$, entonces $({\phi }_1\to {\phi }_2)$ es una formula elemental de tipo $\tau$

7. - Si $\phi$ es una formula elemental de tipo $\tau$, entonces $\neg \phi$ es una formula elemental de tipo $\tau$

8. - Si $\phi$ es una formula elemental de tipo $\tau$, entonces las palabras $$\forall x\phi \forall y\phi \forall z\phi ...$$ son formulas elementales de tipo $\tau$

9. - Si $\phi$ es una formula elemental de tipo $\tau$, entonces las palabras $$\exists x\phi \exists y\phi \exists z\phi ...$$ son formulas elementales de tipo $\tau$

10. - Una palabra es una formula elemental de tipo $\tau$ si y solo si se puede construir usando las clausulas anteriores.

Deberia quedar claro que una formula elemental de tipo $\tau$ como objeto matematico es una palabra. Tambien deberia quedar claro que arriba $r(t_1,...,t_n)$ denota el resultado de concatenar las $n+(n-1)+3$ siguientes palabras $$r(t_1,t_2,...,t_n)$$ es decir que $f(t_1,...,t_n)$ es una palabra de longitud $\left|r\right|+\left|t_1\right|+...+\left|t_n\right|+(n-1)+2$ (notar que $n-1$ cuenta la cantidad de comas).

Tambien deberia quedar claro que el concepto de formula elemental de tipo $\tau$ no es un concepto definido en forma matematica precisa sino mas bien una idea basada en ciertos ejemplos de la vida real de los matematicos. Veamos algunos ejemplos

1. (E1) Si $\tau$ es el tipo $$\left(\right\{un,0\},\{MAS,P\},\{Her,Verde\},\{(MAS,4),(P,1),(Her,3),(Verde,1)\left\}\right)$$ entonces las siguientes son formulas elementales de tipo $\tau$:

   1. $Her(x,y,z)$

   2. $Verde\left(x\right)$

   3. $Verde\left(MAS\right(a,b,un,z\left)\right)$

   4. $Her(0,MAS(a,b,un,z),P(P\left(z\right)\left)\right))$

   5. $(un=P(z\left)\right)$

   6. $\left(Verde\right(MAS(a,b,un,z))\wedge (un=P\left(0\right)\left)\right)$

   7. $\left(MAS\right(a,b,un,z)=b)$

   8. $\left(MAS\right(a,b,un,P\left(z\right))=P(P\left(P\right(z\left)\right)\left)\right)$

   9. $\exists z\left(MAS\right(a,b,un,z)=b)$

   10. $\forall x\forall yHer(0,y,P(P\left(x\right)\left)\right)$

   11. $\forall y\left(\right(P\left(P\right(z\left)\right)=x)\to \exists z(Verde\left(z\right)\wedge Her(x,y,z)\left)\right)$

   Por supuesto las aridades de los nombres de $F\cup R$ son importantes y deben ser respetadas. Por ejemplo $$\left(P\right(x,y)=x)Her(x,y)Verde(x,y)$$ no son formulas elementales de tipo $\tau$.

2. (E2) Si $\tau$ es el tipo $$\left(\right\{0,1\},\{s,△\},\{\le ,r\},\{(s,2),(△,5),(\le ,2),(r,2)\left\}\right)$$ entonces las siguientes son formulas elementales de tipo $\tau$:

   1. $r(x,z)$

   2. $\le (x,y)$

   3. $\le (△(x,y,z,0,0),s(x,x\left)\right)$

   4. $\left(s\right(a,b)=△(x,y,z,0,0\left)\right)$

   5. $(△(x,y,z,0,0)=△(1,1,0,x,z\left)\right)$

   6. $\left(s\right(△(x,y,z,0,0),z)=1)$

   7. $\neg r(x,s(a,s(a,b)\left)\right)$

   8. $\neg \forall y\left(s\right(x,y)=x)$

   9. $\exists z\forall x\left(r\right(x,s(z,z)\wedge \neg \le (x,z))$

   10. $\forall x\forall y\forall z\left(\right(r(x,y)\wedge r(y,z))\to r(x,z\left)\right)$

   Notese que hay algunas pequeñas diferencias con las formulas elementales de las estructuras clasicas definidas en el capitulo Estructuras y su Lenguaje Elemental ya que aqui respondemos a un formato mas general. Por ejemplo hemos escrito $\le (x,y)$ en lugar de $x\le y$ y $s(x,y)$ en lugar de $\left(xsy\right)$. Esto es a los fines de homogeneisar la escritura y no hacer un uso distinto para los nombres de funcion y de relacion de aridad 2.

   Por supuesto las aridades de los nombres de $F\cup R$ son importantes y deben ser respetadas. Por ejemplo $$(+(x,y,z)=x)r(x,y,z)\le (x,y,z)$$ no son formulas elementales de tipo $\tau$.

3. (E3) Si $\tau$ es el tipo $$\left(\right\{er\},\{+\},\{\le \},\{(+,4),(\le ,5)\left\}\right)$$ entonces las siguientes son formulas elementales de tipo $\tau$:

   1. $\le (x,y,er,er,er)$

   2. $\le (+(x,y,z,er),+(x,x,er,x),a,b,z)$

   3. $\exists z(+(x,z,x,+(x,x,x,x))=z)$

4. (E4) Si $\tau$ es el tipo $$\left(\right\{er\},\{\le \},\{+\},\{(\le ,3),(+,2)\left\}\right)$$ entonces las siguientes son formulas elementales de tipo $\tau$:

   1. $\left(\le \right(x,y,er)=x)$

   2. $+(z,er)$

   3. $\exists z\neg +(z,er)$

   (aqui hay que tener en cuenta que $\le$ es un nombre de funcion de aridad 3 y que $+$ es un nombre de relacion de aridad 2, lo cual es inusual pero perfectamente posible en nuestra muy general definicion de tipo)

5. (E5) Si $\tau$ es el tipo $$\left(\right\{\le \},\{+\},\varnothing ,\{(+,3)\left\}\right)$$ entonces las siguientes son formulas elementales de tipo $\tau$:

   1. $(\le =x)$

   2. $(+(z,\le ,a)=\le )$

   3. $(+(+(z,\le ,\le ),x,a)=b)$

   (aqui hay que tener en cuenta que $\le$ es un nombre de constante, lo cual es inusual pero perfectamente posible)

Formulas elementales puras de tipo $\tau$

Una formula elemental de tipo $\tau$ sera llamada pura cuando en ella no ocurran nombres de elementos fijos. Notese que en particular los terminos elementales de tipo $\tau$ que ocurran en una formula elemental pura de tipo $\tau$ seran tambien puros.

7.4.1 Variables libres, acotadas y alcance de un cuantificador

Estos conceptos se definen para una formula elemental $\phi$ de un tipo $\tau$ cualquiera, de la misma manera que lo hicimos en la Seccion de Reticulados Cuaterna para las formulas elementales de reticulados cuaterna. Dejamos al lector que los repace. Recordemos que una variable libre de una formula elemental era una que al menos una vez ocurria libremente (aunque tambien pudiera ocurrir acotadamente en dicha formula elemental). Cuando una formula elemental de tipo $\tau$ no tenga variables libres, diremos que es una sentencia elemental de tipo $\tau$.

7.4.2 Valores de terminos y formulas para una estructura dada

Dada una estructura $(A,i)$ de tipo $\tau$ y un termino elemental $t$ de tipo $\tau$, para que $t$ represente un valor de $A$, tenemos que asignarles valores concretos de $A$ a las variables y a los nombres de elementos fijos que ocurren en $t$. Los nombres de funcion que ocurren en $t$ obviamente se interpretaran segun manda la funcion $i$. Similarmente dada una estructura $(A,i)$ de tipo $\tau$ y una formula elemental $\phi$ de tipo $\tau$, para que $\phi$ sea verdadera o falsa tenemos que asignarle valores concretos de $A$ a las variables libres de $\phi$ y a los nombres de elementos fijos que ocurren en $\phi$ y luego, a los nombres de $C\cup F\cup R$, debemos interpretarlos usando la funcion $i$. Notemos que si $\phi$ es una sentencia elemental pura de tipo $\tau$, entonces $\phi$ sera verdadera o falsa en cada estructura de tipo $\tau$, sin necesidad de hacer asignaciones de valores a sus variables.

Algunos ejemplos:

1. (E1) Sea $\tau$ el tipo $$\left(\right\{un,0\},\{MAS,P\},\{Her,Verde\},\{(MAS,4),(P,1),(Her,3),(Verde,1)\left\}\right)$$ y sea $(A,i)$ la estructura de tipo $\tau$ dada por:

   1. - $A=R$, $i\left(un\right)=\pi$, $i\left(0\right)=0$ (ojo que aqui el primer cero es un simbolo y el segundo un numero real!)

   2. - $$\begin{array}{cc}& \begin{array}{ccc}i\left(MAS\right):R^4& \to & R\\ (x,y,z,w)& \to & x.y\end{array}\\ & \begin{array}{ccc}i\left(P\right):R& \to & R\\ x& \to & x^2\end{array}\end{array}$$ $$\begin{array}{cc}i\left(Her\right)& =\left\{\right(x,y,z)\in R^3:x.y.z=9\}\\ i\left(Verde\right)& =Q\end{array}$$

   Entonces:

   1. El termino elemental $un$ asume o representa el valor $\pi$

   2. El termino elemental $P\left(z\right)$ asume o representa el valor $25$ cuando le asignamos a $z$ el valor $5$.

   3. El termino elemental $MAS(a,b,un,z)$ asume o representa el valor $2$ cuando le asignamos a $a$ el valor $\sqrt{2}$, a $b$ el valor $\sqrt{2}$ y a $z$ el valor $16$ (o cualquier otro valor)

   4. La formula elemental $Her(x,y,z)$ es verdadera en $(A,i)$ cuando le asignamos a $x$ el valor $9$, a $y$ el valor $1$ y a $z$ el valor $1$

   5. $Verde\left(x\right)$ es falsa en $(A,i)$ cuando le asignamos a $x$ el valor $\sqrt{2}$

   6. $Verde\left(MAS\right(a,b,un,z\left)\right)$ es verdadera en $(A,i)$ cuando le asignamos a $a$ el valor $\sqrt{2}$, a $b$ el valor $\sqrt{2}$ y a $z$ el valor $16$ (o cualquier otro valor)

   7. La formula elemental $\exists y\exists zHer(a,y,z))$ es una sentencia ya que no tiene variables libres y es veradera en $(A,i)$ cuando a $a$ le asignamos un valor no nulo

   8. La formula elemental $\exists y\exists zHer(x,y,z))$ es verdadera en $(A,i)$ cuando a $x$ le asignamos un valor no nulo

   9. La formula elemental $\forall x\left(\neg \right(x=0)\to \exists y\exists zHer(x,y,z\left)\right)$ es una sentencia elemental ya que no tiene variables libres y es veradera en $(A,i)$

   10. La formula elemental $\forall x\forall y\left(\right(Verde\left(x\right)\wedge Verde\left(y\right))\to Verde(MAS(x,y,un,z)\left)\right)$ es verdadera en $(A,i)$ independientemente de que valor le asignemos a $z$, ya que el producto de racionales es racional

   11. La formula elemental $\exists y\left(MAS\right(z,z,y,un)=P(z\left)\right)$ es veradera en $(A,i)$ cualquiera sea el valor que le asignemos a $z$

   12. Error frecuente: En la estructura anterior hay varios elementos que tienen su notacion clasica en la matematica, por ejemplo, con la letra griega $\pi$ denotamos la cantidad de veces que entra el diametro en la circunferencia o con el numeral $3$ denotamos al numero entero tres. Esto no debe confundirnos y pensar que por ejemplo las palabras $$\neg Verde\left(\pi \right)\exists yHer(3,3,y)$$ son formulas elementales de tipo $\tau$ (aunque es claro que son verdaderas en la estructura $(A,i)$)

2. (E2) Sea $\tau$ el tipo $$\left(\right\{er\},\{+\},\{\le \},\{(+,4),(\le ,5)\left\}\right)$$ y sea $(A,i)$ la estructura de tipo $\tau$ dada por:

   1. - $A=\{1,2,3,4,5\}$, $i\left(er\right)=4$

   2. - $$\begin{array}{ccc}i(+):A^4& \to & A\\ (x,y,z,w)& \to & max\{x,y,z,w\}\end{array}$$ $$i(\le )=\left\{\right(x,y,z,u,v)\in A^5:x+y+z+u+v\ge 17\}$$

   Entonces:

   1. El termino elemental $er$ asume o representa el valor $4$

   2. El termino elemental $+(x,x,x,a)$ asume o representa el valor $4$ cuando le asignamos a $x$ el valor $2$ y a $a$ el valor $4$.

   3. $\le (er,er,er,er,er)$ es una sentencia elemental verdadera en $(A,i)$

   4. $\le (x,y,er,er,er)$ es verdadera en $(A,i)$ cuando le asignamos a las variables $x$ e $y$ valores que sumados den al menos $5$

   5. $\forall x\exists y\le (x,x,x,x,y)$ es una sentencia elemental pura la cual es falsa en $(A,i)$, ya que la formula elemental $\exists y\le (x,x,x,x,y)$ es falsa en $(A,i)$ cuando le asignamos a $x$ el valor $1$

   6. La sentencia elemental pura $\forall x\exists z\le (x,x,x,x,+(x,x,x,z\left)\right)$ es falsa en $(A,i)$

3. (E3) Sea $\tau$ el tipo $$\left(\right\{epa\},\{\le ,r\},\varnothing ,\{(\le ,1),(r,1)\left\}\right)$$ y sea $(A,i)$ la estructura de tipo $\tau$ dada por:

   1. - $A=\omega$, $i\left(epa\right)=71$

   2. - $$\begin{array}{cc}& \begin{array}{ccc}i\left(\le \right):\omega & \to & \omega \\ x& \to & x^2\end{array}\\ & \begin{array}{ccc}i\left(r\right):\omega & \to & \omega \\ x& \to & \lfloor \sqrt{x}\rfloor \end{array}\end{array}$$ (Notese que aqui contrario al uso estandard en la matematica, el simbolo $\le$ se interpreta como una funcion.)

   3. El termino elemental $\le \left(x\right)$ asume el valor $100$ cuando a $x$ le asignamos el valor $10$

   4. El termino elemental $r\left(\le \right(b\left)\right)$ asume el valor $11$ cuando a $b$ le asignamos el valor $11$

   5. El termino elemental $\le \left(r\right(b\left)\right)$ asume el valor $9$ cuando a $b$ le asignamos el valor $11$

   6. $\left(\le \right(epa)=x)$ es veradera en $(A,i)$ cuando le asignamos a la variable $x$ el valor ${71}^2$ y falsa en caso contrario

   7. La sentencia elemental pura $\exists z\left(\le \right(z)=x)$ es verdadera en $(A,i)$ cuando le asignamos a $x$ el valor $16$

   8. La sentencia elemental pura $\forall x\left(r\right(\le \left(x\right))=x)$ es verdadera en $(A,i)$

   9. La sentencia elemental pura $\exists x\neg \left(\le \right(r\left(x\right))=x)$ es verdadera en $(A,i)$