Ya tenemos una buena cantidad de tipos de estructuras y para cada tipo hemos definido el concepto de formula elemental. Ahora definiremos el concepto de prueba elemental asociado a cada tipo de estructura. Obviamente nos inspiraremos en nuestro concepto de prueba elemental de reticulados cuaterna, ya definido y trabajado en la seccion de reticulados cuaterna del capitulo anterior. Primero es importante notar que para hablar del concepto de prueba elemental relativo a un tipo de estructura debemos tener un conjunto de sentencias elementales puras las cuales axiomaticen a tal tipo de estructura. A continuacion daremos para cada tipo de estructura un conjunto de axiomas. El lector no tendra problemas en corroborar que dichos conjuntos de axiomas caracterizan en cada caso al tipo de estructura en cuestion.
\(\forall x(x\leq x)\)
\(\forall x\forall y\forall z((x\leq y\wedge y\leq z)\rightarrow x\leq z)\)
\(\forall x\forall y((x\leq y\wedge y\leq x)\rightarrow x=y)\)
\(\forall x(x\;\mathsf{s}\;x=x)\)
\(\forall x(x\mathsf{\;i\;}x=x)\)
\(\forall x\forall y(x\mathsf{\;s\;}y=y\;\mathsf{s}\;x)\)
\(\forall x\forall y(x\mathsf{\;i\;}y=y\mathsf{\;i\;}x)\)
\(\forall x\forall y\forall z((x\mathsf{\;s\;}y)\;\mathsf{s}\;z=x\;\mathsf{s}\;(y\;\mathsf{s}\;z))\)
\(\forall x\forall y\forall z((x\mathsf{\;i\;}y)\mathsf{\;i\;}z=x\mathsf{\;i\;}(y\mathsf{\;i\;}z))\)
\(\forall x\forall y(x\;\mathsf{s}\;(x\mathsf{\;i\;}y)=x)\)
\(\forall x\forall y(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x)\)
\(\forall x(x\;\mathsf{s}\;x=x)\)
\(\forall x(x\mathsf{\;i\;}x=x)\)
\(\forall x\forall y(x\mathsf{\;s\;}y=y\;\mathsf{s}\;x)\)
\(\forall x\forall y(x\mathsf{\;i\;}y=y\mathsf{\;i\;}x)\)
\(\forall x\forall y\forall z((x\mathsf{\;s\;}y)\;\mathsf{s}\;z=x\;\mathsf{s}\;(y\;\mathsf{s}\;z))\)
\(\forall x\forall y\forall z((x\mathsf{\;i\;}y)\mathsf{\;i\;}z=x\mathsf{\;i\;}(y\mathsf{\;i\;}z))\)
\(\forall x\forall y(x\;\mathsf{s}\;(x\mathsf{\;i\;}y)=x)\)
\(\forall x\forall y(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x)\)
\(\forall x(0\mathsf{\;s\;}x=x)\)
\(\forall x(x\mathsf{\;s\;}1=1)\)
\(\forall x(x\;\mathsf{s}\;x=x)\)
\(\forall x(x\mathsf{\;i\;}x=x)\)
\(\forall x\forall y(x\mathsf{\;s\;}y=y\;\mathsf{s}\;x)\)
\(\forall x\forall y(x\mathsf{\;i\;}y=y\mathsf{\;i\;}x)\)
\(\forall x\forall y\forall z((x\mathsf{\;s\;}y)\;\mathsf{s}\;z=x\;\mathsf{s}\;(y\;\mathsf{s}\;z))\)
\(\forall x\forall y\forall z((x\mathsf{\;i\;}y)\mathsf{\;i\;}z=x\mathsf{\;i\;}(y\mathsf{\;i\;}z))\)
\(\forall x\forall y(x\;\mathsf{s}\;(x\mathsf{\;i\;}y)=x)\)
\(\forall x\forall y(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x)\)
\(\forall x(0\mathsf{\;s\;}x=x)\)
\(\forall x(x\mathsf{\;s\;}1=1)\)
\(\forall x(x\mathsf{\;s\;}c(x)=1)\)
\(\forall x(x\mathsf{\;i\;}c(x)=0)\)
\(\mathrm{A}_{\leq R}=\forall x(x\leq x)\)
\(\mathrm{A}_{\leq T}=\forall x\forall y\forall z((x\leq y\wedge y\leq z)\rightarrow x\leq z)\)
\(\mathrm{A}_{\leq A}=\forall x\forall y((x\leq y\wedge y\leq x)\rightarrow x=y)\)
\(\mathrm{A}_{\mathsf{s}esC}=\forall x\forall y(x\leq x\;\mathsf{s}\;y\wedge y\leq x\;\mathsf{s}\;y)\)
\(\mathrm{A}_{\mathsf{s}\leq C}=\forall x\forall y\forall z((x\leq z\wedge y\leq z)\rightarrow x\;\text{\ensuremath{\mathsf{s\;}}}y\leq z)\)
\(\mathrm{A}_{\mathsf{i}esC}=\forall x\forall y(x\;\mathsf{i}\;y\leq x\wedge x\;\mathsf{i}\;y\leq y)\)
\(\mathrm{A}_{\mathsf{i}\geq C}=\forall x\forall y\forall z((z\leq x\wedge z\leq y)\rightarrow z\leq x\;\mathsf{i}\;y)\)
\(\forall x\neg r(x,x)\)
\(\forall x\forall y(r(x,y)\rightarrow r(y,x))\)
\(\forall x\neg r(x,x)\)
\(\forall x\forall y(r(x,y)\rightarrow r(y,x))\)
\(\forall x\forall y(r(x,y)\rightarrow((R(x)\wedge\lnot R(y))\vee(\lnot R(x)\wedge R(y))))\)
\(\forall x\forall y\forall z(M(x,y,z)=M(x,z,y))\)
\(\forall x\forall y\forall z(M(x,y,z)=M(y,z,x))\)
\(\forall x\forall y(M(x,x,y)=x)\)
\(\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)))\)
Ahora que tenemos para cada tipo de estructura sus axiomas elementales podemos describir el concepto de prueba elemental relativo a un tipo de estructura. Por supuesto las pruebas elementales prueban cierta sentencia elemental pura de dicho tipo, la cual debera obviamente ser verdadera en todas las estructuras de tal tipo. Deberan poseer ademas las siguientes caracteristicas:
adhocprefix(1)adhocsufix El enunciado a probar debe ser una sentencia elemental pura del tipo en cuestion.
adhocprefix(2)adhocsufix En la prueba se parte de una estructura del tipo en cuestion, fija pero arbitraria en el sentido que lo unico que sabemos es que ella satisface los axiomas elementales correspondientes (o sea esta es la unica informacion particular que podemos usar).
adhocprefix(3)adhocsufix Las deducciones en la prueba son muy simples y obvias de justificar con minimas fraces en castellano
adhocprefix(4)adhocsufix En la escritura de la prueba lo concerniente a la matematica misma se expresa usando solo sentencias elementales del tipo de estructura en cuestion
Dado que en una prueba se parte de una estructura fija de la que solo se asume que satisface los axiomas elementales, la sentencia elemental pura probada debe ser verdadera en todas las estructuras del tipo en cuestion.
A continuacion damos ejemplos para cada uno de los tipos de estructuras analizados previamente.
Sea \[\mu=\forall x\forall y\left((\forall z\ z\leq x\wedge\forall z\ z\leq y)\rightarrow x=y\right)\] Notese que \(\mu\) es una sentencia elemental pura de posets la cual se cumple en todos los posets ya que ella expresa que si en un poset \(x\) e \(y\) son elementos maximos, entonces \(x=y\). Veamos una prueba elemental de posets de \(\mu\). Notar que, tal como lo aclara el item (2) arriba, debemos partir de un poset \((P,\leq)\), fijo pero arbitrario y solo usar la informacion que nos brindan los axiomas.
Proof. Sean \(a,b\in P\) fijos pero arbitrarios. Supongamos \[(\forall z\ z\leq a\wedge\forall z\ z\leq b)\] En particular \(\forall z\ z\leq b\) nos dice que \(a\leq b\) y \(\forall z\ z\leq a\) nos dice que \(b\leq a\), por lo cual tenemos que \[a\leq b\wedge b\leq a\] Pero el axioma \[\forall x\forall y((x\leq y\wedge y\leq x)\rightarrow x=y)\] nos dice que \[(a\leq b\wedge b\leq a)\rightarrow a=b\] obteniendo de esta forma que \(a=b\). O sea que hemos probado que \[(\forall z\ z\leq a\wedge\forall z\ z\leq b)\rightarrow a=b\] Como \(a\) y \(b\) eran elementos fijos pero arbitrarios, obtenemos que vale \(\mu\).
adhocprefixEjercicio:adhocsufix De pruebas elementales de posets de las siguientes sentencias
\(\exists x\exists y\ (\lnot(x=y))\rightarrow\exists x\exists y\ (\lnot(x\leq y))\)
\(\forall x\forall y\forall z\ (x\leq y\wedge y\leq z\wedge x=z\rightarrow x=y)\)
\((\forall x\exists y(\lnot(x=y)\wedge x\leq y)\rightarrow\exists x\exists y\exists z(\lnot(x=y)\wedge\lnot(x=z)\wedge\lnot(y=z))\)
A continuacion daremos una prueba elemental de reticulados terna de la sentencia \(\eta=\forall x\forall y(x\;\mathsf{s}\;y=y\rightarrow x\;\mathsf{i}\;y=x)\). Notar que, tal como lo aclara el item (2) de la descripcion de prueba elemental, debemos partir de un reticulado terna \((L,\mathsf{s},\mathsf{i})\), fijo pero arbitrario y solo usar la informacion que nos brindan los axiomas.
Proof. Sean \(a,b\in L\) fijos pero arbitrarios. Supongamos \[(a\;\mathsf{s}\;b=b)\] El axioma \[\forall x\forall y(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x)\] nos dice que \[a\mathsf{\;i\;}(a\;\mathsf{s}\;b)=a\] O sea que reemplazando en esta igualdad \(a\;\mathsf{s}\;b\) por \(b\) obtenemos: \[a\mathsf{\;i\;}b=a\] Ya que habiamos supuesto que \(a\;\mathsf{s}\;b=b\) hemos probado en realidad que \[a\;\mathsf{s}\;b=b\rightarrow a\mathsf{\;i\;}b=a\] Como \(a\) y \(b\) eran elementos fijos pero arbitrarios, obtenemos que vale \(\forall x\forall y(x\;\mathsf{s}\;y=y\rightarrow x\;\mathsf{i}\;y=x)\).
Notese que las sentencias elementales de reticulados terna son sentencias elementales de reticulados cuaterna tambien. Por que la prueba elemental de reticulados terna de arriba no es una prueba elemental de reticulados cuaterna?
Recordemos que \[\begin{aligned} Dis_{1} & =\forall x\forall y\forall z(x\mathsf{\;i\;}(y\;\mathsf{s}\;z)=(x\mathsf{\;i\;}y)\;\mathsf{s}\;(x\mathsf{\;i\;}z))\\ Dis_{2} & =\forall x\forall y\forall z(x\;\mathsf{s}\;(y\mathsf{\;i\;}z)=(x\mathsf{\;s\;}y)\mathsf{\;i\;}(x\;\mathsf{s}\;z)) \end{aligned}\] El lector no tendra problema para obtener de la prueba del Lema 5.24 las ideas para hacer una prueba elemental de reticulados terna de la sentencia elemental de reticulados terna \((Dis_{1}\rightarrow Dis_{2})\).
Encontrar pruebas elementales de reticulados terna tiene cierta dificultad ya que solo podemos usar los axiomas de reticulados terna y ademas no podemos escribir el simbolo \(\leq\). Podemos escribir \(t\;\mathsf{s}\;s=s\) en lugar de \(t\leq s\) y de esta manera simular en nuestras formulas elementales de reticulados terna al simbolo \(\leq\). De todas maneras el escollo que tendremos es que de los axiomas de reticulados terna no es obvio que las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) sean supremo e infimo respecto del orden dado por la ecuacion \(x\;\mathsf{s}\;y=y\). Esto puede ser resuelto si nos inspiramos en la prueba del Teorema de Dedeking (que prueba justamente eso usando solo el lenguaje elemental de los reticulados terna) pero de todas maneras las pruebas se complican un poco en su escritura.
Tambien tenemos el problema de no poder escribir el simbolo \(\leq\) en las pruebas elementales de reticulados acotados y tambien el escollo de que los axiomas no hacen referencia obvia a que las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) sean operaciones supremo e infimo respecto del orden dado por la ecuacion \(x\;\mathsf{s}\;y=y\). Sin envargo muchas pruebas elementales se pueden hacer en forma natural. Por ejemplo, notar que toda prueba elemental de reticulados terna es tambien una prueba elemental de reticulados acotados, por lo cual tenemos pruebas elementales de reticulados acotados de las sentencias \[\begin{aligned} \forall x\forall y(x\;\mathsf{s}\;y & =y\rightarrow x\;\mathsf{i}\;y=x)\\ (Dis_{1} & \rightarrow Dis_{2}) \end{aligned}\] Veamos una prueba elemental de reticulados acotados de la sentencia \(\forall x(x\mathsf{\;i\;}1=x)\). Notar que, tal como lo aclara el item (2) de la descripcion de prueba elemental, debemos partir de un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\), fijo pero arbitrario y solo usar la informacion que nos brindan los axiomas de reticulados acotados.
Proof. Sea \(a\in L\) fijo pero arbitrario. El axioma \[\forall x(x\mathsf{\;s\;}1=1)\] nos dice que \[a\mathsf{\;s\;}1=1\] Ya que \[\forall x\forall y(x\;\mathsf{s}\;y=y\rightarrow x\;\mathsf{i}\;y=x)\] (teorema ya probado) tenemos que \[a\;\mathsf{s}\;1=1\rightarrow a\;\mathsf{i}\;1=a\] O sea que \[a\;\mathsf{i}\;1=a\] Ya que \(a\) era arbitrario, hemos probado que \[\forall x(x\;\mathsf{i}\;1=x)\]
Por supuesto la anterior no es una prueba elemental estrictamente hablando porque en una parte introduce la sentencia \(\forall x\forall y(x\;\mathsf{s}\;y=y\rightarrow x\;\mathsf{i}\;y=x)\) y lo justifica diciendo “teorema ya probado” lo cual no es una justificacion simple y obvia (de hecho dicho teorema podria ser muy dificil de probar). Obviamente esto se soluciona de manera muy simple: agregamos antes de la sentencia \(\forall x\forall y(x\;\mathsf{s}\;y=y\rightarrow x\;\mathsf{i}\;y=x)\) la prueba elemental que ya hicimos de ella. Dejamos al lector que inspirandose en los resultados probados en la seccion de reticulados complementados de pruebas elementales de reticulados complementados de las siguientes sentencias elementales puras:
adhocprefix-adhocsufix \(Dis_{1}\rightarrow\forall x\forall u\forall v((x\mathsf{\;s\;}u=1\wedge x\mathsf{\;i\;}u=0\wedge x\mathsf{\;s\;}v=1\wedge x\mathsf{\;i\;}v=0)\rightarrow u=v)\)
adhocprefix-adhocsufix \(Dis_{1}\rightarrow\forall x\forall u((x\mathsf{\;s\;}u=1\wedge x\mathsf{\;i\;}u=0)\rightarrow u=c(x))\)
adhocprefix-adhocsufix \(Dis_{1}\rightarrow\forall x\forall y(c(x\,\mathsf{i\,}y)=c(x)\,\mathsf{s\,}c(y))\)
Es dificil encontrar pruebas elementales de grafos que no sean complicadas. Aceptando cierto grado de complejidad hay muchas. Un dato interesante es que el conjunto de sentencias elementales de grafos que tienen una prueba elemental es no recursivo, es decir no hay un procedimiento efectivo que decida si una sentencia elemental de grafos dada tiene una prueba elemental. Esto habla acerca de cuan complicada puede ser la estructura o fisonomia de las sentencias elementales de grafos que pueden ser probadas elementalmente. Otro problema para hacer pruebas elementales de grafos es que en general son tediosas ya que suelen involucrar el analisis de muchos casos. De todas maneras muchas veces aunque la prueba sea tediosa por la cantidad de casos, la idea de la sentencia a probar es bastante geometrica y simple. Veamos un ejemplo. Supongamos que tenemos dos suceciones \(x_{1},x_{2},...,x_{n}\) y \(y_{1},y_{2},...,y_{n}\) de vertices de un grafo \((G,r)\), con \(n\geq3\) tales que
adhocprefix-adhocsufix \(x_{i}\text{ es distinto de }x_{j}\), siempre que \(i\text{ sea distinto de }j\)
adhocprefix-adhocsufix \(y_{i}\text{ es distinto de }y_{j}\), siempre que \(i\text{ sea distinto de }j\)
adhocprefix-adhocsufix \((x_{i},x_{i+1}),(y_{i},y_{i+1})\in r\), para \(i=1,...,n-1\)
adhocprefix-adhocsufix \(x_{1}=y_{1}\) y \(x_{n}=y_{n}\)
adhocprefix-adhocsufix \(x_{i}\text{ es distinto de }y_{i}\), para algun \(i\in\{2,...,n-1\}\)
Entonces haciendo un dibujo uno rapidamente se convence que en \((G,r)\) debe haber un \(k\)-ciclo, con \(k\) tal que \(2n-2\geq k\geq4\). Por supuesto esta verdad acerca de los grafos todavia no esta escrita en forma de sentencia elemental y si quisieramos hacerlo nos topariamos con el problema que \(n\) es variable en el enunciado de dicho resultado. Sin embargo para el caso de un \(n\) concreto, digamos \(n=10\), con un poco de trabajo, podemos hacer una sentencia elemental que simule el enunciado anterior. Y con bastante mas trabajo podriamos hacer una prueba elemental de grafos que pruebe dicha sentencia elemental.
Tambien es dificil encontrar pruebas elementales de median algebras que no sean complicadas. Veamos una prueba elemental de median algebras de la sentencia \(\forall x\forall y(M(x,y,y)=y)\). Notar que, tal como lo aclara el item (2) de la descripcion de prueba elemental, debemos partir de una median algebra \((A,M)\), fija pero arbitraria y solo usar la informacion que nos brindan los axiomas de median algebras.
Proof. Sean \(a,b\in A\) fijos pero arbitrarios. Por el axioma \(\forall x\forall y\forall z(M(x,y,z)=M(y,z,x))\) tenemos que \[M(a,b,b)=M(b,b,a)\] Por el axioma \(\forall x\forall y(M(x,x,y)=x)\) tenemos que \[M(b,b,a)=b\] O sea que \[M(a,b,b)=b\] Ya que \(a,b\) eran arbitarios, hemos probado que \(\forall x\forall y(M(x,y,y)=y)\).
Veamos una prueba elemental de grafos bicoloreados de la sentencia \(\forall x\forall y((r(x,y)\wedge R(x))\rightarrow\lnot R(y))\).
Proof. Sean \(a,b\in G\) fijos pero arbitarios. Supongamos \(r(a,b)\wedge R(a)\). En particular tenemos que se da \(r(a,b)\). Por el axioma \(\forall x\forall y(r(x,y)\rightarrow((R(x)\wedge\lnot R(y))\vee(\lnot R(x)\wedge R(y))))\) tenemos que \(r(a,b)\rightarrow((R(a)\wedge\lnot R(b))\vee(\lnot R(a)\wedge R(b)))\), por lo cual tenemos que \(((R(a)\wedge\lnot R(b))\vee(\lnot R(a)\wedge R(b)))\). Pero ya que se da \(R(a)\), tenemos que no puede darse \((\lnot R(a)\wedge R(b))\), por lo cual obtenemos que se da \((R(a)\wedge\lnot R(b))\). Esto en particular nos dice que se da \(\lnot R(b)\). O sea que hemos probado que \((r(a,b)\wedge R(a))\rightarrow\lnot R(b)\). Ya que \(a\) y \(b\) eran arbitrarios tenemos que vale \(\forall x\forall y((r(x,y)\wedge R(x))\rightarrow\lnot R(y))\).
Ya vimos para el caso de los reticulados cuaterna que no hay una sentencia elemental pura \(\varphi\) de reticulados cuaterna la cual cumpla que es verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si \(L\) es un conjunto finito. Lo mismo sucede para todos los otros tipos de estructuras, es decir nunca se puede con una sentencia elemental pura decir que la estructura tenga universo finito. O sea en general es muy comun que no se pueda decir cierta propiedad por medio de una formula o sentencia elemental. Esto habla en algun sentido del poco poder expresivo que tienen las formulas elementales lo cual es razonable por lo “elementales” y en algun sentido “finitarias” que son. Veamos algunos ejemplos mas de limitaciones del poder expresivo de las formulas elementales:
adhocprefix-adhocsufix No hay una formula elemental pura \(\varphi\) de grafos la cual tenga a \(x\) e \(y\) como sus unicas variables libres y la cual cumpla que, dado un grafo cualquiera \((G,r)\) y elementos \(g_{1}\) y \(g_{2}\) de \(G\), sean equivalentes las siguientes propiedades:
\(\varphi\) es verdadera en \((G,r)\) cuando asignamos a \(x\) el valor \(g_{1}\) y a \(y\) el valor \(g_{2}\)
\(g_{1}\) y \(g_{2}\) estan en la misma componente conexa de \((G,r)\)
Es decir no hay una formula elemental pura \(\varphi\) de grafos la cual “diga” \(x\) e \(y\) estan en la misma componente conexa
adhocprefix-adhocsufix No hay una formula \(\varphi\) elemental de posets la cual tenga a \(x\) e \(y\) como sus unicas variables libres y la cual cumpla que, dado un poset cualquiera \((P,\leq)\) y elementos \(p_{1}\) y \(p_{2}\) de \(P\), sean equivalentes las siguientes propiedades:
\(\varphi\) es verdadera en \((P,\leq)\) cuando asignamos a \(x\) el valor \(p_{1}\) y a \(y\) el valor \(p_{2}\)
El intervalo \(\{p\in P:p_{1}\leq p\leq p_{2}\}\) es un conjunto finito
Es decir no hay una formula elemental pura \(\varphi\) de posets la cual “diga” el intervalo \([x,y]\) es finito
adhocprefix-adhocsufix No hay una sentencia \(\varphi\) elemental de reticulados terna la cual sea verdadera en un reticulado terna \((L,\mathsf{s},\mathsf{i})\) si y solo si \((L,\mathsf{s},\mathsf{i})\) es isomorfo al reticulado terna \((\text{\textbf{R}},max,min)\)
Es decir, lo mas comun es que si una propiedad involucra infinitos chequeos no se pueda “decir” por medio de una formula elemental. Las imposibilidades dadas arriba pueden ser justificadas usando el Teorema de Compacidad que veremos mas adelante.
Supongamos tenemos una cuatrupla \((A,f,g,R)\) tal que \(A\) es un conjunto no vacio, \(f\) y \(g\) son operaciones binarias sobre \(A\) y \(R\) es una relacion binaria sobre \(A\), pero no sabemos nada acerca de estas operaciones \(f\) y \(g\) ni de la relacion \(R\). Es decir tenemos una “estructura” del mismo tipo que los reticulados cuaterna pero obviamente no tiene por que ser un reticulado cuaterna. De todas maneras, podemos hablar de cuando una formula elemental de reticulados cuaterna es verdadera en \((A,f,g,R)\) para una asignacion de valores de \(A\) a sus variables libres y sus nombres de elementos fijos. Simplemente debemos interpretar a \(\mathsf{s}\) como \(f\), a \(\mathsf{i}\) como \(g\) y a \(\leq\) como \(R\) y “leer” dicha formula interpretando ademas sus variables libres y nombres de elementos fijos segun la asignacion dada. Dicho en pocas palabras, las formulas elementales de reticulados cuaterna se pueden interpretar no solo en los reticulados cuaterna sino tambien en cualquier estructura del mismo tipo.
Veamos algunos ejemplos:
adhocprefix-adhocsufix La formula elemental de reticulados cuaterna \((x\leq y)\) es verdadera en la estructura \((\mathbf{R},+,-,\{(x,y)\in\mathbf{R}^{2}:x+1=y\})\) cuando le asignamos a \(x\) el valor \(10\) y a \(y\) el valor \(11\). Esto es ya que interpretamos a \(\leq\) como la relacion \(\{(x,y)\in\mathbf{R}^{2}:x+1=y\}\). Cabe destacar que \((\mathbf{R},+,-,\{(x,y)\in\mathbf{R}^{2}:x+1=y\})\) no es un reticulado cuaterna (por que?)
adhocprefix-adhocsufix La formula elemental de reticulados cuaterna \(((x\;\mathsf{s\;}x)=x)\) es falsa en la estructura \((\mathbf{R},+,-,\{(x,y)\in\mathbf{R}^{2}:x+1=y\})\) cuando le asignamos a \(x\) cualquier valor no nulo. Esto es ya que interpretamos a \(\mathsf{s}\) como la operacion \(+\).
adhocprefix-adhocsufix La sentencia elemental de reticulados cuaterna \(\exists y((y\;\mathsf{s\;}y)=y)\) es falsa en la estructura \((\mathbf{N},+,+,|)\) (la cual tampoco es un reticulado cuaterna).
adhocprefix-adhocsufix La formula elemental de reticulados cuaterna \(((a\;\mathsf{s\;}y)=(a\;\mathsf{i\;}y))\) es verdadera en la estructura \((\mathbf{N},+,+,|)\) cualquiera sea la asignacion de valores a \(a\) y a \(y\).
adhocprefix-adhocsufix La sentencia elemental de reticulados cuaterna \(\forall x((x\leq x)\rightarrow\forall z((z\;\mathsf{i\;}x)=x))\) es verdadera en la estructura \((\mathbf{R},+,.,\{(0,0)\})\)
adhocprefix-adhocsufix La sentencia elemental de reticulados cuaterna \(\forall x(\lnot(x=a)\rightarrow\exists y((x\;\mathsf{i\;}y)=b))\) es verdadera en la estructura \((\mathbf{R},+,.,\{(0,0)\})\) cuando le asignamos a \(a\) el valor \(0\) y a \(b\) el valor \(1\).
Por supuesto podemos hacer el mismo tipo de generalizacion para cada uno de los tipos de estructuras que venimos manejando. Por ejemplo si tenemos un par \((A,R)\) tal que \(A\) es un conjunto no vacio cualquiera y \(R\) es una relacion binaria sobre \(A\) (cualquier relacion, no necesariamente un orden parcial) podemos hablar de cuando una formula elemental de posets es verdadera en \((A,R)\) para una asignacion de valores de \(A\) a sus variables libres y sus nombres de elementos fijos. Simplemente debemos interpretar a \(\leq\) como \(R\) y “leer” dicha formula interpretando ademas sus variables libres y nombres de elementos fijos segun la asignacion dada. Algunos ejemplos
adhocprefix-adhocsufix La formula elemental de posets \((x\leq y)\) es falsa en la estructura \((\mathbf{R},\mathbf{R}\times\omega)\) cuando le asignamos a \(x\) el valor \(0\) y a \(y\) el valor \(1/2\). Esto es ya que interpretamos a \(\leq\) como la relacion \(\mathbf{R}\times\omega\). Cabe destacar que \((\mathbf{R},\mathbf{R}\times\omega)\) no es un poset (por que?)
adhocprefix-adhocsufix La sentencia elemental de posets \(\exists y\forall x(x\leq y)\) es verdadera en la estructura \((\mathbf{N},\{(n,5):n\in\mathbf{N}\})\) (la cual tampoco es un poset).
Otros ejemplos para los otros tipos de estructuras:
adhocprefix-adhocsufix La sentencia elemental de reticulados complementados \((\forall x\exists y((y\;\mathsf{s\;}y)=c(x))\) es falsa en la estructura \((\mathbf{R},-,+,\{(x,x^{2}):x\in\mathbf{R}\},5,100)\) (la cual no es un reticulado complementado). Esto es ya que interpretamos a \(\mathsf{s}\) como la operacion \(-\) sobre los reales y a \(c\) como la funcion \(\{(x,x^{2}):x\in\mathbf{R}\}\) y por lo tanto \((\forall x\exists y((y\;\mathsf{s\;}y)=c(x))\) “dice” que para cada numero real \(x\) hay un numero real \(y\) tal que \(y-y=x^{2}\), lo cual sabemos que es falso.
adhocprefix-adhocsufix La formula elemental de grafos bicoloreados \((R(z)\wedge\exists xr(a,x))\) es verdadera en la estructura \((\mathbf{R},\{(1,1),(3,4)\},\{5,6,7,8,9,10\})\) (la cual no es un grafo bicoloreado) cuando le asignamos a \(z\) el valor \(10\) y a \(a\) el valor 3. Esto es ya que interpretamos a \(r\) como la relacion binaria \(\{(1,1),(3,4)\}\) y a \(R\) como la relacion 1-aria \(\{5,6,7,8,9,10\}\).
adhocprefix-adhocsufix Sea \(g:\mathbf{R}^{3}\rightarrow\mathbf{R}\) dada por \(g(x,y,z)=1,\text{ para cada }(x,y,z)\in\mathbf{R^{3}}\). La sentencia elemental de median algebras \(\forall x\exists y\exists z\exists w(M(y,z,w)=x)\) es falsa en la estructura \((\mathbf{R},g)\) (la cual no es una median algebra). Esto es ya que interpretamos a \(M\) como la operacion \(g\) y es claro que entonces \(\forall x\exists y\exists z\exists w(M(y,z,w)=x)\) no se cumple en \((\mathbf{R},g)\) puesto que por ejemplo para \(x=2\) tenemos que no hay \(y,z,w\in\mathbf{R}\) tales que \(g(y,z,w)=x\). Notese que por el tercer axioma de median algebras la sentencia \(\forall x\exists y\exists z\exists w(M(y,z,w)=x)\) es cierta en toda median algebra.