Tal como vimos en el Capítulo Estructuras y su Lenguaje Elemental, el concepto de prueba elemental dependía del tipo de estructura en cuestión y además de tener fijado un conjunto de sentencias elementales que llamábamos 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 hipotéticos elementos dentro del argumento de la prueba misma. Además cuando hacíamos una prueba elemental teníamos en mente una estructura genérica de la cual solo sabíamos que satisfacía los axiomas, es decir solo podíamos usar la información particular que dichos axiomas nos proveían y pasos elementales obvios de los cuales nadie dudaría. Esto nos inspira a hacer las siguientes dos definiciones.
Una teoría elemental será 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)\) será una estructura de tipo \(\tau\) la cual haga verdaderos a todos los elementos de \(\Sigma\). Veamos algunos ejemplos:
adhocprefix(E1)adhocsufix La teoría elemental de los posets es el par \((\Sigma,\tau)\), donde \(\tau=(\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\) y \(\Sigma\) es el conjunto formado por las siguientes tres sentencias elementales de tipo \(\tau\):
adhocprefixadhocsufix \(\forall x\ \mathrm{\leq}(x,x)\)
adhocprefixadhocsufix \(\forall x\forall y\forall z\;((\mathrm{\leq}(x,y)\wedge\mathrm{\leq}(y,z))\rightarrow\mathrm{\leq}(x,z))\)
adhocprefixadhocsufix \(\forall x\forall y((\mathrm{\leq}(x,y)\wedge\mathrm{\leq}(y,x))\rightarrow x=y)\)
Nótese que los modelos de esta teoría elemental son exactamente aquellas estructuras de tipo \(\tau\) las cuales son "esencialmente" posets.
adhocprefix(E2)adhocsufix La teoría elemental de los reticulados terna es el par \((\Sigma,\tau)\), donde \(\tau=(\emptyset,\{\mathsf{s},\mathsf{i}\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2)\})\) y \(\Sigma\) es el conjunto formado por las siguientes sentencias elementales de tipo \(\tau\):
adhocprefixadhocsufix \(\forall x\forall y\ (\mathsf{s}(x,x)=x)\)
adhocprefixadhocsufix \(\forall x\forall y\ (\mathsf{i}(x,x)=x)\)
adhocprefixadhocsufix \(\forall x\forall y\ (\mathsf{s}(x,y)=\mathsf{s}(y,x))\)
adhocprefixadhocsufix \(\forall x\forall y\ (\mathsf{i}(x,y)=\mathsf{i}(y,x))\)
adhocprefixadhocsufix \(\forall x\forall y\forall z\ (\mathsf{s}(\mathsf{s}(x,y),z)=\mathsf{s}(x,\mathsf{s}(y,z)))\)
adhocprefixadhocsufix \(\forall x\forall y\forall z\ (\mathsf{i}(\mathsf{i}(x,y),z)=\mathsf{i}(x,\mathsf{i}(y,z)))\)
adhocprefixadhocsufix \(\forall x\forall y\ \mathsf{s}(x,\mathsf{i}(x,y))=x)\)
adhocprefixadhocsufix \(\forall x\forall y\ \mathsf{i}(x,\mathsf{s}(x,y))=x)\)
Nótese que los modelos de esta teoría elemental son exactamente aquellas estructuras de tipo \(\tau\) las cuales son "esencialmente" reticulados terna.
adhocprefix(E3)adhocsufix La teoría elemental de los reticulados cuaterna es el par \((\Sigma,\tau)\), donde \(\tau=(\emptyset,\{\mathsf{s},\mathsf{i}\},\{\leq\},\{(\mathsf{s},2),(\mathsf{i},2),(\leq,2)\})\) y \(\Sigma\) es el conjunto formado por las siguientes sentencias elementales de tipo \(\tau\):
adhocprefixadhocsufix \(\mathrm{A}_{\leq R}=\forall x\ \mathrm{\leq}(x,x)\)
adhocprefixadhocsufix \(\mathrm{A}_{\leq T}=\forall x\forall y\forall z\;((\mathrm{\leq}(x,y)\wedge\mathrm{\leq}(y,z))\rightarrow\mathrm{\leq}(x,z))\)
adhocprefixadhocsufix \(\mathrm{A}_{\leq A}=\forall x\forall y\ ((\mathrm{\leq}(x,y)\wedge\mathrm{\leq}(y,x))\rightarrow x=y)\)
adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{s}esC}=\forall x\forall y\;(\mathrm{\leq}(x,\mathsf{s}(x,y))\wedge\mathrm{\leq}(y,\mathsf{s}(x,y)))\)
adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{s}\leq C}=\forall x\forall y\forall z\;\left((\mathrm{\leq}(x,z)\wedge\mathrm{\leq}(y,z))\rightarrow\mathrm{\leq}(\mathsf{s}(x,y),z\right))\)
adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{i}esC}=\forall x\forall y\;(\mathrm{\leq}(\mathsf{i}(x,y),x)\wedge\mathrm{\leq}(\mathsf{i}(x,y),y))\)
adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{i}\geq C}=\forall x\forall y\forall z\;\left((\mathrm{\leq}(z,x)\wedge\mathrm{\leq}(z,y))\rightarrow\mathrm{\leq}(z,\mathsf{i}(x,y))\right)\)
Nótese que los modelos de esta teoría elemental son exactamente aquellas estructuras de tipo \(\tau\) las cuales son "esencialmente" reticulados cuaterna.
adhocprefix(E4)adhocsufix La teoría elemental de los grafos es el par \((\Sigma,\tau)\), donde \(\tau=(\emptyset,\emptyset,\{r\},\{(r,2)\})\) y \(\Sigma\) es el conjunto formado por las siguientes sentencias elementales de tipo \(\tau\):
adhocprefixadhocsufix \(\forall x\lnot r(x,x)\)
adhocprefixadhocsufix \(\forall x\forall y(r(x,y)\rightarrow r(y,x))\)
Nótese que los modelos de esta teoría elemental son exactamente aquellas estructuras de tipo \(\tau\) las cuales son "esencialmente" grafos.
adhocprefix(E5)adhocsufix La teoría elemental de los grafos bicoloreados es el par \((\Sigma,\tau)\), donde \(\tau=(\emptyset,\emptyset,\{r,R\},\{(r,2),(R,1)\})\) y \(\Sigma\) es el conjunto formado por las siguientes sentencias elementales de tipo \(\tau\):
adhocprefixadhocsufix \(\forall x\lnot r(x,x)\)
adhocprefixadhocsufix \(\forall x\forall y(r(x,y)\rightarrow r(y,x))\)
adhocprefixadhocsufix \(\forall x\forall y(r(x,y)\rightarrow((R(x)\wedge\lnot R(y))\vee(\lnot R(x)\wedge R(y))))\)
Nótese que los modelos de esta teoría elemental son exactamente aquellas estructuras de tipo \(\tau\) las cuales son "esencialmente" grafos bicoloreados.
adhocprefix(E6)adhocsufix La teoría elemental de las median algebras es el par \((\Sigma,\tau)\), donde \(\tau=(\emptyset,\{M\},\emptyset,\{(M,3)\})\) y \(\Sigma\) es el conjunto formado por las siguientes sentencias elementales de tipo \(\tau\):
adhocprefixadhocsufix \(\forall x\forall y\forall z(M(x,y,z)=M(x,z,y))\)
adhocprefixadhocsufix \(\forall x\forall y\forall z(M(x,y,z)=M(y,z,x))\)
adhocprefixadhocsufix \(\forall x\forall y(M(x,x,y)=x)\)
adhocprefixadhocsufix \(\forall x\forall y\forall z\forall u\forall v(M(M(x,y,z),u,v))=M(x,M(y,u,v),M(z,u,v)))\)
Es muy importante notar que una teoría elemental \((\Sigma,\tau)\) es en algún sentido un objeto esencialmente sintáctico ya que \(\Sigma\), \(\mathcal{C}\), \(\mathcal{F}\) y \(\mathcal{R}\) son conjuntos de palabras y los elementos de \(\Sigma\) también son palabras. Los modelos de \((\Sigma,\tau)\) constituyen la semántica de la teoría.
Las anteriores son las teorías elementales que se corresponden con los tipos de estructuras consideradas en el Capítulo Estructuras y su Lenguaje Elemental pero nuestra definición de teoría elemental es muy general y nos permite considerar una gran diversidad de teorías. Veamos otros ejemplos de teorías elementales interesantes:
adhocprefix(E7)adhocsufix Consideremos la teoría elemental \((\Sigma,\tau)\), donde \(\tau=(\{\mathrm{ex}\},\{\mathrm{F}\},\emptyset,\{(\mathrm{F},1)\})\) y \(\Sigma\) es el conjunto formado por las siguientes dos sentencias elementales:
adhocprefixadhocsufix \(\forall x\forall y\ (\lnot(x=y)\rightarrow\lnot(\mathrm{F}(x)=\mathrm{F}(y)))\)
adhocprefixadhocsufix \(\forall x\ \lnot(\mathrm{F}(x)=\mathrm{ex})\)
Nótese que una estructura \(\mathbf{A}=(A,i)\) de tipo \(\tau\) es un modelo de \((\Sigma,\tau)\) si y solo si \(i(\mathrm{F})\) es inyectiva y \(i(\mathrm{ex})\notin\mathrm{Im}(i(\mathrm{F}))\). Esto obviamente nos dice que el universo de cada modelo de esta teoría es infinito. Un modelo de la teoría es por ejemplo \((\omega,\{(\mathrm{ex},0),(\mathrm{F},Suc)\})\)
adhocprefix(E8)adhocsufix Sea \(\tau=(\emptyset,\{\times\},\{\mathrm{Com}\},\{(\times,2),(\mathrm{Com},1)\})\) y sea \(\Sigma\) el conjunto formado por las siguientes sentencias elementales de tipo \(\tau\):
adhocprefixadhocsufix \(\forall x\forall y\forall z\ (\times(\times(x,y),z)=\times(x,\times(y,z)))\)
adhocprefixadhocsufix \(\forall z\ (\mathrm{Com}(z)\rightarrow\forall x\ (\times(x,z)=\times(z,x)))\)
adhocprefixadhocsufix \(\forall x\exists z\ (x=\times(z,z)\wedge\mathrm{Com}(z))\)
Supongamos \(\mathbf{A}=(A,i)\) es un modelo de la teoría \((\Sigma,\tau)\). Nótese que el primer axioma nos dice que \(i(\times)\) es una operación binaria asociativa, esto se ve mas fácilmente si escribimos dicho axioma con la notación 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(\mathrm{Com})\), entonces \(a\ i(\times)\ b=b\ i(\times)\ a\), cualesquiera sea \(b\in A\). O sea nos dice que los elementos de \(i(\mathrm{Com})\) conmutan con todos los otros elementos relativo a la operación \(i(\times)\). El tercer axioma nos dice que cualquiera sea \(a\in A\), debe haber un \(b\in i(\mathrm{Com})\) tal que \(b\ i(\times)\ b=a\). En algún sentido nos dice que todo elemento de \(A\) tiene en el conjunto \(i(\mathrm{Com})\) una "raíz cuadrada" relativo a la operación \(i(\times)\). Ejemplos de modelos de esta teoría son:
adhocprefix-adhocsufix \((\{r\in\mathbf{R}:r\geq0\},i)\), con \(i(\times)=\) operación producto usual de \(\mathbf{R}\) restringida a \(\{r\in\mathbf{R}:r\geq0\}^{2}\) y \(i(\mathrm{Com})=\{r\in\mathbf{R}:r\geq0\}\)
adhocprefix-adhocsufix \((\mathbf{R},i)\), con \(i(\times)=\max\) y \(i(\mathrm{Com})=\mathbf{R}\)
adhocprefix-adhocsufix \((\mathbf{R},i)\), con \(i(\times)=\min\) y \(i(\mathrm{Com})=\mathbf{R}\)
adhocprefix-adhocsufix \((\mathcal{P}(\{1,2,3\}),i)\), con \(i(\times)=\cup\) y \(i(\mathrm{Com})=\mathcal{P}(\{1,2,3\})\)
adhocprefix(E9)adhocsufix La teoría elemental de los reticulados cuaterna distributivos es el par \((\Sigma,\tau)\), donde \(\tau=(\emptyset,\{\mathsf{s},\mathsf{i}\},\{\leq\},\{(\mathsf{s},2),(\mathsf{i},2),(\leq,2)\})\) y \(\Sigma\) es el conjunto formado por los axiomas de la teoría elemental de los reticulados cuaterna junto con el axioma
adhocprefixadhocsufix \(\forall x\forall y\forall z\ (\mathsf{i}(x,\mathsf{s}(y,z))=\mathsf{s}(\mathsf{i}(x,y),\mathsf{i}(x,z)))\)
Nótese que los modelos de esta teoría elemental son exactamente aquellas estructuras de tipo \(\tau\) las cuales son "esencialmente" reticulados cuaterna distributivos
adhocprefix(E10)adhocsufix La teoría elemental de los reticulados terna distributivos es el par \((\Sigma,\tau)\), donde \(\tau=(\emptyset,\{\mathsf{s},\mathsf{i}\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2)\})\) y \(\Sigma\) es el conjunto formado por los axiomas de la teoría elemental de los reticulados terna junto con el axioma
adhocprefixadhocsufix \(\forall x\forall y\forall z\ (\mathsf{i}(x,\mathsf{s}(y,z))=\mathsf{s}(\mathsf{i}(x,y),\mathsf{i}(x,z)))\)
Nótese que los modelos de esta teoría elemental son exactamente aquellas estructuras de tipo \(\tau\) las cuales son "esencialmente" reticulados terna distributivos
adhocprefix(E11)adhocsufix La teoría elemental de los reticulados cuaterna Booleanos es el par \((\Sigma,\tau)\), donde \(\tau=(\{0,1\},\{\mathsf{s},\mathsf{i},c\},\{\leq\},\{(\mathsf{s},2),(\mathsf{i},2),(\leq,2),(c,1)\})\) y \(\Sigma\) es el conjunto formado por los axiomas de la teoría elemental de reticulados cuaterna junto con las siguientes sentencias elementales de tipo \(\tau\):
adhocprefixadhocsufix \(\forall x\;\leq(x,1)\)
adhocprefixadhocsufix \(\forall x\;\leq(0,x)\)
adhocprefixadhocsufix \(\forall x\ (\mathsf{i}(x,c(x))=0\wedge\mathsf{s}(x,c(x))=1)\)
adhocprefixadhocsufix \(\forall x\forall y\forall z\ (\mathsf{i}(x,\mathsf{s}(y,z))=\mathsf{s}(\mathsf{i}(x,y),\mathsf{i}(x,z)))\)
Nótese que los modelos de esta teoría elemental son exactamente aquellas estructuras \((A,i)\) de tipo \(\tau\) tales que \((A,i(\mathsf{s}),i(\mathsf{i}),i(c),i(0),i(1))\) es un álgebra de Boole cuyo orden asociado es \(i(\leq)\).
Podemos generalizar el concepto de prueba elemental, introducido en el Capítulo Estructuras y su Lenguaje Elemental, a cualquier teoría elemental. Dada una teoría elemental \((\Sigma,\tau)\) y una sentencia elemental pura \(\varphi\) de tipo \(\tau\), una prueba elemental de \(\varphi\) en \((\Sigma,\tau)\) será una prueba de \(\varphi\) que posea las siguientes características:
adhocprefix(1)adhocsufix En la prueba se parte de una estructura de tipo \(\tau\), fija pero arbitraria en el sentido que lo único que sabemos es que ella es una estructura que satisface los axiomas de \(\Sigma\) (o sea esta es la única información particular que podemos usar).
adhocprefix(2)adhocsufix Las deducciones en la prueba son muy simples y obvias de justificar con mínimas frases en castellano.
adhocprefix(3)adhocsufix En la escritura de la prueba lo concerniente a la matemática misma se expresa usando solo sentencias elementales de tipo \(\tau\)
Nótese que los puntos (1) y (2) nos garantizan que una prueba elemental de \(\varphi\) en \((\Sigma,\tau)\) es una forma solida de justificar que cualquier estructura de tipo \(\tau\) que satisfaga los axiomas de \((\Sigma,\tau)\) también satisfacera \(\varphi\). Por supuesto el concepto de prueba elemental en una teoría \((\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 matemáticos.
Veamos algunos ejemplos:
adhocprefix(E1)adhocsufix Consideremos la teoría elemental del ejemplo (E7) de teorías elementales. Sea \[\varphi=\exists x\exists y\exists z\ (\lnot(x=y)\wedge\lnot(x=z)\wedge\lnot(y=z))\] (\(\varphi\) dice que el universo tiene al menos tres elementos.) Tenemos la siguiente:
adhocprefixPrueba elemental de \(\varphi\) en \((\Sigma,\tau)\):adhocsufix Por el segundo axioma de \((\Sigma,\tau)\) tenemos que \(\lnot(\mathrm{F}(\mathrm{ex})=\mathrm{ex})\). Obviamente entonces tenemos que
1. \(\lnot(\mathrm{ex}=\mathrm{F}(\mathrm{ex}))\)
Por el segundo axioma de \((\Sigma,\tau)\) también tenemos que \(\lnot(\mathrm{F}(\mathrm{F}(\mathrm{ex}))=\mathrm{ex})\) por lo que
2. \(\lnot(\mathrm{ex}=\mathrm{F}(\mathrm{F}(\mathrm{ex})))\)
Ya que se da 1. el primer axioma de \((\Sigma,\tau)\) nos dice que
3. \(\lnot(\mathrm{F}(\mathrm{ex})=\mathrm{F}(\mathrm{F}(\mathrm{ex})))\)
Poniendo 1. 2. y 3. juntos tenemos que \[\lnot(\mathrm{ex}=\mathrm{F}(\mathrm{ex}))\wedge\lnot(\mathrm{ex}=\mathrm{F}(\mathrm{F}(\mathrm{ex})))\wedge\lnot(\mathrm{F}(\mathrm{ex})=\mathrm{F}(\mathrm{F}(\mathrm{ex})))\] de lo cual es obvio que vale \(\varphi\).
adhocprefix(E2)adhocsufix Consideremos la teoría elemental del ejemplo (E8) de teorías elementales. A continuación daremos una prueba elemental de \(\varphi=\forall x\forall y\ (\times(x,y)=\times(y,x))\) en la teoría \((\Sigma,\tau)\). Para facilitar la lectura usaremos la notación clásica para operaciones binarias, es decir escribiremos \(x\times y\) en lugar de \(\times(y,x)\), etc.
adhocprefixPrueba elemental de \(\varphi\) en \((\Sigma,\tau)\):adhocsufix Sean \(a,b\in A\), fijos pero arbitrarios. Por el tercer axioma de \((\Sigma,\tau)\) tenemos que
1. \(\exists z\ (a=z\times z\wedge\mathrm{Com}(z))\)
Sea \(c\) tal que
2. \(a=c\times c\wedge\mathrm{Com}(c)\)
Nuevamente, por el tercer axioma de \((\Sigma,\tau)\) tenemos que
3. \(\exists z\ (b=z\times z\wedge\mathrm{Com}(z))\)
Sea \(d\) tal que
4. \(b=d\times d\wedge\mathrm{Com}(d)\)
Ya que vale \(\mathrm{Com}(c)\), el segundo axioma de \((\Sigma,\tau)\) 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 de \((\Sigma,\tau)\) (asociatividad) tenemos que
7. \((c\times c)\times(d\times d)=c\times(c\times(d\times d))\)
Pero por 5. tenemos que
8. \(c\times(c\times(d\times d))=c\times((d\times d)\times c)\)
Por asociatividad
9. \(c\times((d\times d)\times c)=(c\times(d\times d))\times c\)
Por 5. tenemos que
10. \((c\times(d\times d))\times c=((d\times d)\times c)\times c\)
Por asociatividad tenemos que
11. \(((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 y\ x\times y=y\times x\)