7.5 Teorias elementales y pruebas elementales

Tal como vimos en el capitulo Estructuras y su Lenguaje Elemental, el concepto de prueba elemental dependia del tipo de estructura en cuestion y ademas de tener fijado un conjunto de sentencias elementales que llamabamos axiomas y eran el punto de partida de dichas pruebas. Cabe destacar que dichos axiomas eran sentencias elementales puras, i.e. sin nombres de elementos fijos, ya que estos se usaban solo en las pruebas elementales para denotar hipoteticos elementos dentro del argumento de la prueba misma. Ademas cuando haciamos una prueba elemental teniamos en mente una estructura generica de la cual solo sabiamos que satisfacia los axiomas, es decir solo podiamos usar la informacion particular que dichos axiomas nos proveian y pasos elementales obvios de los cuales nadie dudaria. Esto nos inspira a hacer las siguientes dos definiciones.

Una teoria elemental sera un par $(\Sigma ,\tau )$ tal que $\tau$ es un tipo cualquiera y $\Sigma$ es un conjunto de sentencias elementales puras de tipo $\tau$. Un modelo de $(\Sigma ,\tau )$ sera una estructura de tipo $\tau$ la cual haga verdaderos a todos los elementos de $\Sigma$. Veamos algunos ejemplos:

1. (E1) La teoria elemental de los posets es el par $(\Sigma ,\tau )$, donde $\tau =(\varnothing ,\varnothing ,\{\le \},\{(\le ,2)\left\}\right)$ y $\Sigma$ es el conjunto formado por las siguientes tres sentencias elementales de tipo $\tau$:

   1. $\forall x\le (x,x)$

   2. $\forall x\forall y\forall z\left(\right(\le (x,y)\wedge \le (y,z))\to \le (x,z\left)\right)$

   3. $\forall x\forall y\left(\right(\le (x,y)\wedge \le (y,x))\to x=y)$

   Notese que los modelos de esta teoria elemental son exactamente aquellas estructuras de tipo $\tau$ las cuales son "esencialmente" posets.

2. (E2) La teoria elemental de los reticulados terna es el par $(\Sigma ,\tau )$, donde $\tau =(\varnothing ,\{s,i\},\varnothing ,\{(s,2),(i,2)\left\}\right)$ y $\Sigma$ es el conjunto formado por las siguientes sentencias elementales de tipo $\tau$:

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

   2. $\forall x\forall y\left(i\right(x,x)=x)$

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

   4. $\forall x\forall y\left(i\right(x,y)=i(y,x\left)\right)$

   5. $\forall x\forall y\forall z\left(s\right(s(x,y),z)=s(x,s(y,z)\left)\right)$

   6. $\forall x\forall y\forall z\left(i\right(i(x,y),z)=i(x,i(y,z)\left)\right)$

   7. $\forall x\forall ys(x,i(x,y\left)\right)=x)$

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

   Notese que los modelos de esta teoria elemental son exactamente aquellas estructuras de tipo $\tau$ las cuales son "esencialmente" reticulados terna.

3. (E3) La teoria elemental de los reticulados cuaterna es el par $(\Sigma ,\tau )$, donde $\tau =(\varnothing ,\{s,i\},\{\le \},\{(s,2),(i,2),(\le ,2)\left\}\right)$ y $\Sigma$ es el conjunto formado por las siguientes sentencias elementales de tipo $\tau$:

   1. $A_{\le R}=\forall x\le (x,x)$

   2. $A_{\le T}=\forall x\forall y\forall z\left(\right(\le (x,y)\wedge \le (y,z))\to \le (x,z\left)\right)$

   3. $A_{\le A}=\forall x\forall y\left(\right(\le (x,y)\wedge \le (y,x))\to x=y)$

   4. $A_{sesC}=\forall x\forall y\left(\le \right(x,s(x,y))\wedge \le (y,s(x,y)\left)\right)$

   5. $A_{s\le C}=\forall x\forall y\forall z\left(\right(\le (x,z)\wedge \le (y,z))\to \le (s(x,y),z))$

   6. $A_{iesC}=\forall x\forall y\left(\le \right(i(x,y),x)\wedge \le (i(x,y),y\left)\right)$

   7. $A_{i\ge C}=\forall x\forall y\forall z\left(\right(\le (z,x)\wedge \le (z,y))\to \le (z,i(x,y)\left)\right)$

   Notese que los modelos de esta teoria elemental son exactamente aquellas estructuras de tipo $\tau$ las cuales son "esencialmente" reticulados cuaterna.

4. (E4) La teoria elemental de los grafos es el par $(\Sigma ,\tau )$, donde $\tau =(\varnothing ,\varnothing ,\{r\},\{(r,2)\left\}\right)$ y $\Sigma$ es el conjunto formado por las siguientes sentencias elementales de tipo $\tau$:

   1. $\forall x\neg r(x,x)$

   2. $\forall x\forall y\left(r\right(x,y)\to r(y,x\left)\right)$

   Notese que los modelos de esta teoria elemental son exactamente aquellas estructuras de tipo $\tau$ las cuales son "esencialmente" grafos.

5. (E5) La teoria elemental de los grafos bicoloreados es el par $(\Sigma ,\tau )$, donde $\tau =(\varnothing ,\varnothing ,\{r,R\},\{(r,2),(R,1)\left\}\right)$ y $\Sigma$ es el conjunto formado por las siguientes sentencias elementales de tipo $\tau$:

   1. $\forall x\neg r(x,x)$

   2. $\forall x\forall y\left(r\right(x,y)\to r(y,x\left)\right)$

   3. $\forall x\forall y\left(r\right(x,y)\to (\left(R\right(x)\wedge \neg R(y\left)\right)\vee \left(\neg R\right(x)\wedge R(y\left)\right)\left)\right)$

   Notese que los modelos de esta teoria elemental son exactamente aquellas estructuras de tipo $\tau$ las cuales son "esencialmente" grafos bicoloreados.

6. (E6) La teoria elemental de las median algebras es el par $(\Sigma ,\tau )$, donde $\tau =(\varnothing ,\{M\},\varnothing ,\{(M,3)\left\}\right)$ y $\Sigma$ es el conjunto formado por las siguientes sentencias elementales de tipo $\tau$:

   1. $\forall x\forall y\forall z\left(M\right(x,y,z)=M(x,z,y\left)\right)$

   2. $\forall x\forall y\forall z\left(M\right(x,y,z)=M(y,z,x\left)\right)$

   3. $\forall x\forall y\left(M\right(x,x,y)=x)$

   4. $\forall x\forall y\forall z\forall u\forall v\left(M\right(M(x,y,z),u,v\left)\right)=M(x,M(y,u,v),M(z,u,v\left)\right))$

Es muy importante notar que una teoria elemental $(\Sigma ,\tau )$ es en algun sentido un objeto esencialmente sintactico ya que $\Sigma$, $C$, $F$ y $R$ son conjuntos de palabras y los elementos de $\Sigma$ tambien son palabras. Los modelos de $(\Sigma ,\tau )$ constituyen la semantica de la teoria.

Las anteriores son las teorias elementales que se corresponden con los tipos de estructuras consideradas en el capitulo Estructuras y su Lenguaje Elemental pero nuestra definicion de teoria elemental es muy general y nos permite considerar una gran diversidad de teorias. Veamos otros ejemplos de teorias elementales interesantes:

1. (E7) Consideremos la teoria elemental $(\Sigma ,\tau )$, donde $\tau =\left(\right\{ex\},\{F\},\varnothing ,\{(F,1)\left\}\right)$ y $\Sigma$ es el conjunto formado por las siguientes dos sentencias elementales:

   1. $\forall x\forall y\left(\neg \right(x=y)\to \neg (F\left(x\right)=F\left(y\right)\left)\right)$

   2. $\forall x\neg \left(F\right(x)=ex)$

   Notese que una estructura $A=(A,i)$ de tipo $\tau$ es un modelo de $(\Sigma ,\tau )$ si y solo si $i\left(F\right)$ es inyectiva y $i\left(ex\right)\notin \mathrm{Im}\left(i\right(F\left)\right)$. Esto obviamente nos dice que el universo de cada modelo de esta teoria es infinito. Un modelo de la teoria es por ejemplo $(\omega ,\{(ex,0),(F,Suc)\left\}\right)$

2. (E8) Sea $\tau =(\varnothing ,\{\times \},\{Com\},\{(\times ,2),(Com,1)\left\}\right)$ y sea $\Sigma$ el conjunto formado por las siguientes sentencias elementales de tipo $\tau$:

   1. $\forall x\forall y\forall z(\times (\times (x,y),z)=\times (x,\times (y,z)\left)\right)$

   2. $\forall z\left(Com\right(z)\to \forall x(\times (x,z)=\times (z,x)\left)\right)$

   3. $\forall x\exists z(x=\times (z,z)\wedge Com(z\left)\right)$

   Supongamos $A=(A,i)$ es un modelo de la teoria $(\Sigma ,\tau )$. Notese que el primer axioma nos dice que $i(\times )$ es una operacion binaria asociativa, esto se ve mas facilmente si escribimos dicho axioma con la notacion mas usual para operaciones: $$\forall x\forall y\forall z(x\times y)\times z=x\times (y\times z)$$

   El segundo axioma nos dice que si $a\in i\left(Com\right)$, entonces $ai(\times )b=bi(\times )a$, cualesquiera sea $b\in A$. O sea nos dice que los elementos de $i\left(Com\right)$ conmutan con todos los otros elementos relativo a la operacion $i(\times )$. El tercer axioma nos dice que cualquiera sea $a\in A$, debe haber un $b\in i\left(Com\right)$ tal que $bi(\times )b=a$. En algun sentido nos dice que todo elemento de $A$ tiene en el conjunto $i\left(Com\right)$ una "raiz cuadrada" relativo a la operacion $i(\times )$. Ejemplos de modelos de esta teoria son:

   1. $\left(\right\{r\in R:r\ge 0\},i)$, con $i(\times )=$ operacion producto usual de $R$ restringida a $\{r\in R:r\ge 0{\}}^2$ y $i\left(Com\right)=\{r\in R:r\ge 0\}$

   2. $(R,i)$, con $i(\times )=max$ y $i\left(Com\right)=R$

   3. $(R,i)$, con $i(\times )=min$ y $i\left(Com\right)=R$

   4. $\left(P\right(\{1,2,3\}),i)$, con $i(\times )=\cup$ y $i\left(Com\right)=P\left(\right\{1,2,3\left\}\right)$

3. (E9) La teoria elemental de los reticulados cuaterna distributivos es el par $(\Sigma ,\tau )$, donde $\tau =(\varnothing ,\{s,i\},\{\le \},\{(s,2),(i,2),(\le ,2)\left\}\right)$ y $\Sigma$ es el conjunto formado por los axiomas de la teoria elemental de los reticulados cuaterna junto con el axioma

   1. $\forall x\forall y\forall z\left(i\right(x,s(y,z))=s(i(x,y),i(x,z)\left)\right)$

   Notese que los modelos de esta teoria elemental son exactamente aquellas estructuras de tipo $\tau$ las cuales son "esencialmente" reticulados cuaterna distributivos

4. (E10) La teoria elemental de los reticulados terna distributivos es el par $(\Sigma ,\tau )$, donde $\tau =(\varnothing ,\{s,i\},\varnothing ,\{(s,2),(i,2)\left\}\right)$ y $\Sigma$ es el conjunto formado por los axiomas de la teoria elemental de los reticulados terna junto con el axioma

   1. $\forall x\forall y\forall z\left(i\right(x,s(y,z))=s(i(x,y),i(x,z)\left)\right)$

   Notese que los modelos de esta teoria elemental son exactamente aquellas estructuras de tipo $\tau$ las cuales son "esencialmente" reticulados terna distributivos

5. (E11) La teoria elemental de los reticulados cuaterna Booleanos es el par $(\Sigma ,\tau )$, donde $\tau =\left(\right\{0,1\},\{s,i,c\},\{\le \},\{(s,2),(i,2),(\le ,2),(c,1)\left\}\right)$ y $\Sigma$ es el conjunto formado por los axiomas de la teoria elemental de reticulados cuaterna junto con las siguientes sentencias elementales de tipo $\tau$:

   1. $\forall x\le (x,1)$

   2. $\forall x\le (0,x)$

   3. $\forall x\left(i\right(x,c\left(x\right))=0\wedge s(x,c\left(x\right))=1)$

   4. $\forall x\forall y\forall z\left(i\right(x,s(y,z))=s(i(x,y),i(x,z)\left)\right)$

   Notese que los modelos de esta teoria elemental son exactamente aquellas estructuras $(A,i)$ de tipo $\tau$ tales que $(A,i(s),i(i),i(c),i(0),i(1\left)\right)$ es un algebra de Boole cuyo orden asociado es $i(\le )$.

7.5.1 Pruebas elementales en una teoria elemental $(\Sigma ,\tau )$

Podemos generalizar el concepto de prueba elemental, introducido en el capitulo Estructuras y su Lenguaje Elemental, a cualquier teoria elemental. Dada una teoria elemental $(\Sigma ,\tau )$ y una sentencia elemental pura $\phi$ de tipo $\tau$, una prueba elemental de $\phi$ en $(\Sigma ,\tau )$ sera una prueba de $\phi$ que posea las siguientes caracteristicas:

1. (1) En la prueba se parte de una estructura de tipo $\tau$, fija pero arbitraria en el sentido que lo unico que sabemos es que ella satisface los axiomas de $\Sigma$ (i.e. es un modelo de $(\Sigma ,\tau )$) y ademas esta es la unica informacion particular que podemos usar.

2. (2) Las deducciones en la prueba son muy simples y obvias de justificar con minimas fraces en castellano.

3. (3) En la escritura de la prueba lo concerniente a la matematica misma se expresa usando solo sentencias elementales de tipo $\tau$

Notese que el punto (1) nos garantiza que una prueba elemental de $\phi$ en $(\Sigma ,\tau )$ es una forma solida de justificar que cualquier estructura de tipo $\tau$ que satisfaga los axiomas de $(\Sigma ,\tau )$ tambien satisfacera $\phi$. Por supuesto el concepto de prueba elemental en una teoria $(\Sigma ,\tau )$ no es un concepto definido en forma precisa sino mas bien una idea basada en ciertos ejemplos de la vida real de los matematicos.

Veamos algunos ejemplos:

1. (E1) Consideremos la teoria elemental del ejemplo (E7) de teorias elementales. Sea $$\phi =\exists x\exists y\exists z\left(\neg \right(x=y)\wedge \neg (x=z)\wedge \neg (y=z\left)\right)$$

   ($\phi$ dice que el universo tiene al menos tres elementos.) Tenemos la siguiente:

   1. Prueba elemental de $\phi$ en $(\Sigma ,\tau )$: Por el segundo axioma tenemos que $\neg \left(F\right(ex)=ex)$. Obviamente entonces tenemos que

      (1) $\neg (ex=F(ex\left)\right)$

      Por el segundo axioma tambien tenemos que $\neg \left(F\right(F\left(ex\right))=ex)$ por lo que

      (2) $\neg (ex=F(F\left(ex\right)\left)\right)$

      Ya que se da (1), el primer axioma nos dice que

      (3) $\neg \left(F\right(ex)=F(F\left(ex\right)\left)\right)$

      Poniendo (1), (2) y (3) juntos tenemos que $$\neg (ex=F(ex\left)\right)\wedge \neg (ex=F(F\left(ex\right)\left)\right)\wedge \neg \left(F\right(ex)=F(F\left(ex\right)\left)\right)$$ de lo cual es obvio que vale $\phi$.

2. (E2) Consideremos la teoria elemental del ejemplo (E8) de teorias elementales. A continuacion daremos una prueba elemental de $\phi =\forall x\forall y(\times (x,y)=\times (y,x\left)\right)$ en la teoria $(\Sigma ,\tau )$. Para facilitar la lectura usaremos la notacion clasica para operaciones binarias, es decir escribiremos $x\times y$ en lugar de $\times (y,x)$, etc.

   1. Prueba elemental de $\phi$ en $(\Sigma ,\tau )$: Sean $a,b\in A$, fijos pero arbitrarios. Por el tercer axioma tenemos que

      1. $\exists z(a=z\times z\wedge Com(z\left)\right)$

      Sea $c$ tal que

      2. $a=c\times c\wedge Com\left(c\right)$

      Nuevamente, por el tercer axioma tenemos que

      3. $\exists z(b=z\times z\wedge Com(z\left)\right)$

      Sea $d$ tal que

      4. $b=d\times d\wedge Com\left(d\right)$

      Ya que vale $Com\left(c\right)$, el segundo axioma nos dice que

      5. $\forall x(x\times c=c\times x)$

      Ya que $a=c\times c$ y $b=d\times d$, tenemos que

      6. $a\times b=(c\times c)\times (d\times d)$

      Pero por el primer axioma (asociatividad) tenemos que

      7. $(c\times c)\times (d\times d)=c\times (c\times (d\times d\left)\right)$

      Pero por 5. tenemos que

      8. $c\times (c\times (d\times d\left)\right)=c\times \left(\right(d\times d)\times c)$

      Por asociatividad

      9. $c\times \left(\right(d\times d)\times c)=(c\times (d\times d\left)\right)\times c$

      Por 5. tenemos que

      10. $(c\times (d\times d\left)\right)\times c=\left(\right(d\times d)\times c)\times c$

      Por asociatividad tenemos que

      11. $\left(\right(d\times d)\times c)\times c=(d\times d)\times (c\times c)$

      Ya que $a=c\times c$ y $b=d\times d$, tenemos que

      12. $(d\times d)\times (c\times c)=b\times a$.

      Siguiendo la cadena de igualdades desde 6. hasta 12. tenemos que

      13. $a\times b=b\times a$.

      Ya que $a$ y $b$ eran elementos arbitrarios, hemos probado que $\forall x\forall yx\times y=y\times x$