En la Sección de Reticulados Cuaterna del capítulo anterior desarrollamos a manera intuitiva un tipo de fórmulas y pruebas muy particulares asociadas con los reticulados cuaterna. Les llamamos fórmulas elementales y pruebas elementales por lo básicas y simples que son. En este capítulo haremos lo mismo con las otras estructuras que venimos trabajando y con algunas nuevas. Esto dejara el terreno listo para hacer en el capítulo siguiente un tratamiento general del concepto de estructura y su lenguaje elemental.
Tal como para el caso de los reticulados cuaterna, nuestras definiciones de fórmula elemental y prueba elemental para estos otros tipos de estructuras no serán del todo precisas matemáticamente hablando. Esto no nos afectará ya que en esta etapa lo que nos importa es manejar en forma intuitiva dichos conceptos.
Las estructuras que hemos estudiado en el Capítulo Estructuras Algebraicas Ordenadas son todas de un formato similar, a saber uplas formadas por una primera coordenada que es un conjunto no vacío (llamado el universo de la estructura) y luego ciertas relaciones, operaciones y elementos distinguidos, dependiendo del caso. Otra cosa importante a notar es que para cada tipo de estructura hay ciertos símbolos fijos que usamos en forma genérica para denotar sus relaciones, operaciones y elementos distinguidos. Por ejemplo:
adhocprefix-adhocsufix Para los posets usamos el símbolo \(\leq\) para denotar su relación binaria de orden parcial en un sentido genérico (este tipo de estructuras no tiene operaciones ni elementos distinguidos).
adhocprefix-adhocsufix Para el caso de los reticulados terna usamos en forma genérica los símbolos \(\mathsf{s}\) e \(\mathsf{i}\) para denotar sus operaciones binarias de supremo e ínfimo (este tipo de estructuras no tiene relaciones ni elementos distinguidos).
adhocprefix-adhocsufix Para el caso de los reticulados acotados usamos en forma genérica los símbolos \(\mathsf{s}\) e \(\mathsf{i}\) para denotar sus operaciones binarias de supremo e ínfimo y los numerales \(0\) y \(1\) para denotar sus elementos distinguidos, a saber mínimo y máximo respectivamente.
adhocprefix-adhocsufix Para el caso de los reticulados complementados usamos en forma genérica los símbolos \(\mathsf{s}\) e \(\mathsf{i}\) para denotar sus operaciones binarias de supremo e ínfimo, el símbolo \(c\) para denotar su operación unaria de complementación y los numerales \(0\) y \(1\) para denotar sus elementos distinguidos, a saber mínimo y máximo respectivamente.
adhocprefix-adhocsufix Para el caso de los reticulados cuaterna usamos en forma genérica los símbolos \(\mathsf{s}\) e \(\mathsf{i}\) para denotar sus operaciones binarias de supremo e ínfimo y el símbolo \(\leq\) para denotar su relación binaria de orden parcial.
En el caso de los reticulados cuaterna, estos símbolos genéricos \(\mathsf{s}\), \(\mathsf{i}\) y \(\leq\) son justamente los que intervienen (aparte de ciertos símbolos clásicos) en la construcción de las fórmulas elementales. Es decir que para dar nuestra definición de fórmula elemental para alguno de estos otros tipos de estructura, usaremos la misma idea, es decir serán aquellas fórmulas que se pueden construir (de forma adecuada) usando solo los símbolos genéricos del tipo de estructura en cuestión mas símbolos de la siguiente lista de símbolos clásicos:
adhocprefix-adhocsufix \(\forall\ \exists\;\lnot\;\vee\;\wedge\;\rightarrow\;\leftrightarrow\;(\;,\;)\;=\)
adhocprefix-adhocsufix \(x,y,z,w,...\)
adhocprefix-adhocsufix \(a,b,c,d,...\)
A continuación iremos viendo los distintos casos (algunos quedaran como ejercicios) y agregaremos también tres tipos de estructuras mas para hacer mas general aun nuestra perspectiva del tema.
Ya que no tenemos en los posets operaciones ni elementos distinguidos, solo una la relación binaria denotada genéricamente con el símbolo \(\leq\), los términos elementales de posets serán las variables y los nombres de elementos fijos. Por analogía con lo hecho para reticulados cuaterna, aquellos términos elementales de posets en los que no ocurren nombres de elementos fijos serán llamados puros. O sea que solo las variables serán términos elementales puros de posets.
Las fórmulas elementales de posets se definen con las siguientes clausulas:
adhocprefix(1)adhocsufix Si \(t\) y \(s\) son términos elementales de posets, entonces la palabra \((t=s)\) es una fórmula elemental de posets
adhocprefix(2)adhocsufix Si \(t\) y \(s\) son términos elementales de posets, entonces la palabra \((t\leq s)\) es una fórmula elemental de posets
adhocprefix(3)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de posets, entonces la palabra \((\varphi_{1}\wedge\varphi_{2})\) es una fórmula elemental de posets
adhocprefix(4)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de posets, entonces la palabra \((\varphi_{1}\vee\varphi_{2})\) es una fórmula elemental de posets
adhocprefix(5)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de posets, entonces la palabra \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una fórmula elemental de posets
adhocprefix(6)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de posets, entonces la palabra \((\varphi_{1}\rightarrow\varphi_{2})\) es una fórmula elemental de posets
adhocprefix(7)adhocsufix Si \(\varphi\) es una fórmula elemental de posets, entonces la palabra \(\lnot\varphi\) es una fórmula elemental de posets
adhocprefix(8)adhocsufix Si \(\varphi\) es una fórmula elemental de posets, entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son fórmulas elementales de posets
adhocprefix(9)adhocsufix Si \(\varphi\) es una fórmula elemental de posets, entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son fórmulas elementales de posets
adhocprefix(10)adhocsufix Una palabra es una fórmula elemental de posets si y solo si se puede construir usando las clausulas anteriores
Cabe destacar que esta definición de fórmula elemental de poset no es una definición matemática precisa.
Similarmente a lo hecho para reticulados cuaterna, aquellas fórmulas elementales de posets en las que no ocurren nombres de elementos fijos serán llamadas puras.
Nótese que cada fórmula elemental de posets es una fórmula elemental de reticulados cuaterna pero obviamente no al revés.
Ya que en estas estructuras tenemos tres operaciones distinguidas, denotadas genéricamente con \(\mathsf{s}\), \(\mathsf{i}\) y \(c\) y además tenemos dos elementos distinguidos, denotados genéricamente con los numerales \(0\) y \(1\), los términos elementales de reticulados complementados serán dados por las siguientes clausulas
adhocprefix(1)adhocsufix Los numerales \(0\) y \(1\) son términos elementales de reticulados complementados
adhocprefix(2)adhocsufix Cada variable es un término elemental de reticulados complementados
adhocprefix(3)adhocsufix Cada nombre de elemento fijo es un término elemental de reticulados complementados
adhocprefix(4)adhocsufix Si \(t\) es un término elemental de reticulados complementados, entonces la palabra \(c(t)\) es un término elemental de reticulados complementados
adhocprefix(5)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados complementados, entonces la palabra \((t\;\mathsf{s\;}s)\) es un término elemental de reticulados complementados
adhocprefix(6)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados complementados, entonces la palabra \((t\;\mathsf{i\;}s)\) es un término elemental de reticulados complementados
adhocprefix(7)adhocsufix Una palabra es un término elemental de reticulados complementados si y solo si se puede construir usando las clausulas anteriores
Debería quedar claro que arriba \(c(t)\) denota el resultado de concatenar las 4 siguientes palabras \[c\;\;\;\;\;\;(\;\;\;\;\;\;\;\;\;t\;\;\;\;\;\;\;\;\;)\] es decir que \(c(t)\) es una palabra de longitud \(\left|t\right|+3\). Algunos ejemplos:
adhocprefix-adhocsufix \((0\;\mathsf{s\;}c(y))\)
adhocprefix-adhocsufix \(c(0)\)
adhocprefix-adhocsufix \(c((x\mathsf{\;s\;}y)\;\mathsf{s}\;z))\)
adhocprefix-adhocsufix \((c(a)\;\mathsf{s\;}z)\;\mathsf{i\;}x)\)
adhocprefix-adhocsufix \(c(c(c(b)))\)
Cabe destacar que esta definición de término elemental de reticulados complementados no es una definición matemática precisa.
Las siguientes clausulas definen el concepto de fórmula elemental de reticulados complementados
adhocprefix(1)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados complementados, entonces la palabra \((t=s)\) es una fórmula elemental de reticulados complementados
adhocprefix(2)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados complementados, entonces la palabra \((\varphi_{1}\wedge\varphi_{2})\) es una fórmula elemental de reticulados complementados
adhocprefix(3)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados complementados, entonces la palabra \((\varphi_{1}\vee\varphi_{2})\) es una fórmula elemental de reticulados complementados
adhocprefix(4)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados complementados, entonces la palabra \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una fórmula elemental de reticulados complementados
adhocprefix(5)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados complementados, entonces la palabra \((\varphi_{1}\rightarrow\varphi_{2})\) es una fórmula elemental de reticulados complementados
adhocprefix(6)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados complementados, entonces la palabra \(\lnot\varphi\) es una fórmula elemental de reticulados complementados
adhocprefix(7)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados complementados, entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son fórmulas elementales de reticulados complementados
adhocprefix(8)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados complementados, entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son fórmulas elementales de reticulados complementados
adhocprefix(9)adhocsufix Una palabra es una fórmula elemental de reticulados complementados si y solo si se puede construir usando las clausulas anteriores
Nótese que por ejemplo la palabra \((x\leq y)\) no es una fórmula elemental de reticulados complementados. Esto es debido a que en la definición de reticulado complementado solo intervienen las operaciones \(\mathsf{s},\mathsf{i},c\) y los elementos distinguidos \(0,1\).
Cabe destacar que esta definición de fórmula elemental de reticulados complementados no es una definición matemática precisa.
Por supuesto, los términos o fórmulas elementales de reticulados complementados en los cuales no ocurran nombres de elementos fijos serán llamados puros.
Dejamos al lector dar las definiciones de fórmula elemental de reticulado terna y de fórmula elemental de reticulado acotado. A continuación analizaremos las fórmulas elementales de otros tres tipos de estructuras.
Un grafo es un par \((G,r)\) donde \(G\) es un conjunto no vacío y \(r\) es una relación binaria sobre \(G\) tal que:
adhocprefix-adhocsufix \((x,x)\notin r\), cualesquiera sea \(x\in G\)
adhocprefix-adhocsufix Si \((x,y)\in r\), entonces \((y,x)\in r\), cualesquiera sean \(x,y\in G\) (es decir, \(r\) es simétrica con respecto a \(G\))
Hay varias presentaciones del concepto de grafo no dirigido pero el lector no tardara en darse cuenta que estas estructuras son equivalentes a las que el haya estudiado bajo el nombre de grafos no dirigidos. Los elementos de \(G\) son llamados los vértices de \((G,r)\). Cuando \((x,y)\in r\) diremos que \(x\) e \(y\) son adyacentes o están conectados.
Dado que no hay operaciones distinguidas ni elementos distinguidos en este tipo de estructuras, los términos elementales de grafos serán las variables y los nombres de elementos fijos. Dado un grafo \((G,r)\), escribiremos \(r(x,y)\) para expresar que \((x,y)\in r\). Con esta convención las fórmulas elementales de grafos se definen con las siguientes clausulas:
adhocprefix(1)adhocsufix Si \(t\) y \(s\) son términos elementales de grafos, entonces la palabra \((t=s)\) es una fórmula elemental de grafos
adhocprefix(2)adhocsufix Si \(t\) y \(s\) son términos elementales de grafos, entonces la palabra \(r(t,s)\) es una fórmula elemental de grafos
adhocprefix(3)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de grafos, entonces la palabra \((\varphi_{1}\wedge\varphi_{2})\) es una fórmula elemental de grafos
adhocprefix(4)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de grafos, entonces la palabra \((\varphi_{1}\vee\varphi_{2})\) es una fórmula elemental de grafos
adhocprefix(5)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de grafos, entonces la palabra \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una fórmula elemental de grafos
adhocprefix(6)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de grafos, entonces la palabra \((\varphi_{1}\rightarrow\varphi_{2})\) es una fórmula elemental de grafos
adhocprefix(7)adhocsufix Si \(\varphi\) es una fórmula elemental de grafos, entonces la palabra \(\lnot\varphi\) es una fórmula elemental de grafos
adhocprefix(8)adhocsufix Si \(\varphi\) es una fórmula elemental de grafos, entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son fórmulas elementales de grafos
adhocprefix(9)adhocsufix Si \(\varphi\) es una fórmula elemental de grafos, entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son fórmulas elementales de grafos
adhocprefix(10)adhocsufix Una palabra es una fórmula elemental de grafos si y solo si se puede construir usando las clausulas anteriores
Debería quedar claro que arriba \(r(t,s)\) denota el resultado de concatenar las 6 siguientes palabras \[r\;\;\;\;\;\;(\;\;\;\;\;\;t\;\;\;\;\;\;,\;\;\;\;\;\;s\;\;\;\;\;\;)\] es decir que \(r(t,s)\) es una palabra de longitud \(\left|t\right|+\left|s\right|+4\).
Cabe destacar que esta definición de fórmula elemental de grafos no es una definición matemática precisa.
Por supuesto, los términos o fórmulas elementales de grafos en los cuales no ocurran nombres de elementos fijos serán llamados puros. O sea que en este caso solo las variables serán términos elementales puros de grafos.
Veamos algunas definiciones básicas de grafos. Dado un grafo \((G,r)\) y \(x\in G\) la valencia de \(x\) es el cardinal del conjunto \(\{y:(x,y)\in r\}\). Diremos que un subconjunto \(S\subseteq G\) es una clique cuando se dé que \((x,y)\in r\) cada ves que \(x,y\) sean elementos distintos de \(S\). Dado \(n\geq2\), un \(n\)-ciclo de \((G,r)\) será una sucesión \(x_{1},x_{2},...,x_{n}\) la cual cumpla que
adhocprefix-adhocsufix \(x_{i}\text{ es distinto de }x_{j}\), siempre que \(i\text{ sea distinto de }j\)
adhocprefix-adhocsufix \((x_{i},x_{i+1})\in r\), para \(i=1,...,n-1\)
adhocprefix-adhocsufix \((x_{n},x_{1})\in r\)
Dejamos al lector que se ejercite intentando dar:
adhocprefix-adhocsufix Una fórmula elemental pura de grafos que tenga a \(x\) como su única variable libre la cual "diga" \(x\) tiene valencia 3
adhocprefix-adhocsufix Una sentencia elemental pura de grafos que sea verdadera en un grafo \((G,r)\) si y solo si \((G,r)\) no tiene cliques de cardinal 4
adhocprefix-adhocsufix Una sentencia elemental pura de grafos que sea verdadera en un grafo \((G,r)\) si y solo si \((G,r)\) no tiene 4-ciclos
Recordemos que dado un grafo \((G,r)\), un coloreo de \((G,r)\) es una asignación de colores a cada elemento de \(G\) de manera que nunca dos elementos de \(G\) que estén relacionados tengan el mismo color. En el caso en que el coloreo solo usa dos colores, le llamamos un bicoloreo de \((G,r)\). Nótese que un bicoloreo puede ser representado con un subconjunto de \(G\). Por ejemplo si el bicoloreo coloreaba a los elementos de \(G\) con dos colores, verde y rojo, podemos tomar \(R=\{g\in G:g\) es rojo\(\}\) y esto determina nuestro bicoloreo ya que \(G-R\) será justamente el conjunto de elementos verdes. O sea que matemáticamente hablando podemos dar la siguiente definición. Un bicoloreo de \((G,r)\) es un subconjunto \(R\) de \(G\) el cual cumple:
adhocprefix-adhocsufix Cualesquiera sean \(x,y\in G\) se tiene que si \((x,y)\in r\), entonces se da alguna de las siguientes condiciones:
adhocprefix(i)adhocsufix \(x\in R\) y \(y\notin R\)
adhocprefix(ii)adhocsufix \(x\notin R\) y \(y\in R\)
Esto nos inspira para dar la definición de un nuevo tipo de estructura.
Un grafo bicoloreado es una terna \((G,r,R)\), donde \((G,r)\) es un grafo y \(R\) es un bicoloreo de \((G,r)\). Algunos ejemplos:
adhocprefix-adhocsufix \((\{1,2\},\{(1,2),(2,1)\},\{1\})\) es un grafo bicoloreado
adhocprefix-adhocsufix Tomemos \[\begin{aligned} G & =\omega\\ r & =\{(x,x+1):x\in\omega\}\cup\{(x+1,x):x\in\omega\}\\ R & =\{x\in\omega:x\text{ es par}\} \end{aligned}\] Entonces \((G,r,R)\) es un grafo bicoloreado
adhocprefix-adhocsufix \((\{1,2,3,4\},\emptyset,R)\) es un grafo bicoloreado, cualesquiera sea \(R\subseteq\{1,2,3,4\}\)
Para escribir las fórmulas elementales de grafos bicoloreados, pensaremos a \(R\) como una "relación unaria" y escribiremos \(R(x)\) para expresar que \(x\in R\). Así como cuando escribimos \(r(x,y)\) pensamos "\(x\) e \(y\) están conectados", cuando escribamos \(R(x)\) pensaremos "\(x\) es rojo". Ya que no tenemos en los grafos bicoloreados operaciones ni elementos distinguidos, solo una relación unaria denotada genéricamente con el símbolo \(R\) y una relación binaria denotada genéricamente con el símbolo \(r\), los términos elementales de grafos bicoloreados serán las variables y los nombres de elementos fijos. Dejamos al lector la definición de fórmulas elementales de grafos bicoloreados.
Algunos ejemplos de fórmulas elementales de grafos bicoloreados:
adhocprefix-adhocsufix \((R(a)\wedge r(x,y))\)
adhocprefix-adhocsufix \(\exists z(r(a,z)\rightarrow R(z))\)
adhocprefix-adhocsufix \(\forall yr(a,y)\)
adhocprefix-adhocsufix \(\forall x\forall y((R(x)\wedge R(y))\rightarrow(x=y))\)
adhocprefix-adhocsufix \(\exists x\forall z(\lnot R(z)\rightarrow r(x,z))\)
adhocprefix-adhocsufix \(\forall x\forall y(r(x,y)\rightarrow(R(x)\leftrightarrow\lnot R(y)))\)
adhocprefix-adhocsufix \(\forall x\forall y\forall z\;(((x=y)\wedge(y=z))\rightarrow(x=z))\)
Debería quedar claro que el primero de los ejemplos de fórmula elemental de grafos bicoloreados de arriba, como objeto matemático, es simplemente una palabra de longitud 13, el segundo una palabra de longitud 15, etc.
Una median algebra es un par \((A,M)\) donde \(A\) es un conjunto no vacío, \(M\) es una operación \(3\)-aria sobre \(A\) (i.e. \(M:A^{3}\rightarrow A\)) y se cumplen:
adhocprefix-adhocsufix \(M(x,y,z)=M(x,z,y)\), cualesquiera sean \(x,y,z\in A\)
adhocprefix-adhocsufix \(M(x,y,z)=M(y,z,x)\), cualesquiera sean \(x,y,z\in A\)
adhocprefix-adhocsufix \(M(x,x,y)=x\), cualesquiera sean \(x,y\in A\)
adhocprefix-adhocsufix \(M(M(x,y,z),u,v)=M(x,M(y,u,v),M(z,u,v))\), cualesquiera sean \(x,y,z,u,v\in A\)
Por ejemplo si tomamos un reticulado terna \((L,\mathsf{s},\mathsf{i})\) y definimos \(M(x,y,z)=(x\;\mathsf{i\;}y)\;\mathsf{s\;}(x\;\mathsf{i\;}z)\;\mathsf{s\;}(y\;\mathsf{i\;}z)\), para cada \(x,y,z\in L\), entonces \((L,M)\) es una median algebra. Estas estructuras han sido extensivamente estudiadas y tienen un rol importante en la informática teórica.
Ya que hay una única operación distinguida la cual denotamos genéricamente con la letra \(M\), los términos elementales de median algebras serán dados por las siguientes clausulas
adhocprefix(1)adhocsufix Cada variable es un término elemental de median algebras
adhocprefix(2)adhocsufix Cada nombre de elemento fijo es un término elemental de median algebras
adhocprefix(3)adhocsufix Si \(t_{1},t_{2},t_{3}\) son términos elementales de median algebras, entonces la palabra \(M(t_{1},t_{2},t_{3})\) es un término elemental de median algebras
adhocprefix(4)adhocsufix Una palabra es un término elemental de median algebras si y solo si se puede construir usando las clausulas anteriores
Debería quedar claro que arriba \(M(t_{1},t_{2},t_{3})\) denota el resultado de concatenar las 8 siguientes palabras \[M\;\;\;\;\;\;(\;\;\;\;\;\;t_{1}\;\;\;\;\;\;,\;\;\;\;\;\;t_{2}\;\;\;\;\;\;,\;\;\;\;\;\;t_{3}\;\;\;\;\;\;)\] es decir que \(M(t_{1},t_{2},t_{3})\) es una palabra de longitud \(\left|t_{1}\right|+\left|t_{2}\right|+\left|t_{3}\right|+5\).
Cabe destacar que esta definición de términos elementales de median algebras no es una definición matemática precisa. Algunos ejemplos:
adhocprefix-adhocsufix \(M(x,y,z)\)
adhocprefix-adhocsufix \(M(M(a,a,a),a,a)\)
adhocprefix-adhocsufix \(M(a,b,M(M(M(x,y,z),u,v),x,a)\)
adhocprefix-adhocsufix \(x\)
adhocprefix-adhocsufix \(a\)
Ahora seguramente el lector no tendrá problema para definir las fórmulas elementales de median algebras. Algunos ejemplos:
adhocprefix-adhocsufix \(\exists x\exists y(M(x,y,z)=z)\)
adhocprefix-adhocsufix \(\forall x\forall y\forall z((M(x,y,a)=M(x,y,b))\rightarrow(a=b))\)
adhocprefix-adhocsufix \(\forall x\forall y(M(x,y,y)=y)\)
Dejamos al lector que defina el concepto de fórmula elemental de median algebras
Ya tenemos una buena cantidad de tipos de estructuras y para cada tipo hemos definido el concepto de fórmula 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 Sección de Reticulados Cuaterna. 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 continuación daremos para cada tipo de estructura un conjunto de axiomas. El lector no tendrá problemas en corroborar que dichos conjuntos de axiomas caracterizan en cada caso al tipo de estructura en cuestión.
Axiomas elementales de posets
adhocprefixadhocsufix \(\forall x(x\leq x)\)
adhocprefixadhocsufix \(\forall x\forall y\forall z((x\leq y\wedge y\leq z)\rightarrow x\leq z)\)
adhocprefixadhocsufix \(\forall x\forall y((x\leq y\wedge y\leq x)\rightarrow x=y)\)
Axiomas elementales de reticulados terna
adhocprefixadhocsufix \(\forall x(x\;\mathsf{s}\;x=x)\)
adhocprefixadhocsufix \(\forall x(x\mathsf{\;i\;}x=x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;s\;}y=y\;\mathsf{s}\;x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;i\;}y=y\mathsf{\;i\;}x)\)
adhocprefixadhocsufix \(\forall x\forall y\forall z((x\mathsf{\;s\;}y)\;\mathsf{s}\;z=x\;\mathsf{s}\;(y\;\mathsf{s}\;z))\)
adhocprefixadhocsufix \(\forall x\forall y\forall z((x\mathsf{\;i\;}y)\mathsf{\;i\;}z=x\mathsf{\;i\;}(y\mathsf{\;i\;}z))\)
adhocprefixadhocsufix \(\forall x\forall y(x\;\mathsf{s}\;(x\mathsf{\;i\;}y)=x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x)\)
Axiomas elementales de reticulados ternaAxiomas elementales de reticulados acotados
adhocprefixadhocsufix \(\forall x(x\;\mathsf{s}\;x=x)\)
adhocprefixadhocsufix \(\forall x(x\mathsf{\;i\;}x=x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;s\;}y=y\;\mathsf{s}\;x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;i\;}y=y\mathsf{\;i\;}x)\)
adhocprefixadhocsufix \(\forall x\forall y\forall z((x\mathsf{\;s\;}y)\;\mathsf{s}\;z=x\;\mathsf{s}\;(y\;\mathsf{s}\;z))\)
adhocprefixadhocsufix \(\forall x\forall y\forall z((x\mathsf{\;i\;}y)\mathsf{\;i\;}z=x\mathsf{\;i\;}(y\mathsf{\;i\;}z))\)
adhocprefixadhocsufix \(\forall x\forall y(x\;\mathsf{s}\;(x\mathsf{\;i\;}y)=x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x)\)
adhocprefixadhocsufix \(\forall x(0\mathsf{\;s\;}x=x)\)
adhocprefixadhocsufix \(\forall x(x\mathsf{\;s\;}1=1)\)
Axiomas elementales de reticulados complementados
adhocprefixadhocsufix \(\forall x(x\;\mathsf{s}\;x=x)\)
adhocprefixadhocsufix \(\forall x(x\mathsf{\;i\;}x=x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;s\;}y=y\;\mathsf{s}\;x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;i\;}y=y\mathsf{\;i\;}x)\)
adhocprefixadhocsufix \(\forall x\forall y\forall z((x\mathsf{\;s\;}y)\;\mathsf{s}\;z=x\;\mathsf{s}\;(y\;\mathsf{s}\;z))\)
adhocprefixadhocsufix \(\forall x\forall y\forall z((x\mathsf{\;i\;}y)\mathsf{\;i\;}z=x\mathsf{\;i\;}(y\mathsf{\;i\;}z))\)
adhocprefixadhocsufix \(\forall x\forall y(x\;\mathsf{s}\;(x\mathsf{\;i\;}y)=x)\)
adhocprefixadhocsufix \(\forall x\forall y(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x)\)
adhocprefixadhocsufix \(\forall x(0\mathsf{\;s\;}x=x)\)
adhocprefixadhocsufix \(\forall x(x\mathsf{\;s\;}1=1)\)
adhocprefixadhocsufix \(\forall x(x\mathsf{\;s\;}c(x)=1)\)
adhocprefixadhocsufix \(\forall x(x\mathsf{\;i\;}c(x)=0)\)
Axiomas elementales de reticulados cuaterna
adhocprefixadhocsufix \(\mathrm{A}_{\leq R}=\forall x(x\leq x)\)
adhocprefixadhocsufix \(\mathrm{A}_{\leq T}=\forall x\forall y\forall z((x\leq y\wedge y\leq z)\rightarrow x\leq z)\)
adhocprefixadhocsufix \(\mathrm{A}_{\leq A}=\forall x\forall y((x\leq y\wedge y\leq x)\rightarrow x=y)\)
adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{s}esC}=\forall x\forall y(x\leq x\;\mathsf{s}\;y\wedge y\leq x\;\mathsf{s}\;y)\)
adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{s}\leq C}=\forall x\forall y\forall z((x\leq z\wedge y\leq z)\rightarrow x\;\mathsf{s}\;y\leq z)\)
adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{i}esC}=\forall x\forall y(x\;\mathsf{i}\;y\leq x\wedge x\;\mathsf{i}\;y\leq y)\)
adhocprefixadhocsufix \(\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)\)
Axiomas elementales de grafos
adhocprefixadhocsufix \(\forall x\neg r(x,x)\)
adhocprefixadhocsufix \(\forall x\forall y(r(x,y)\rightarrow r(y,x))\)
Axiomas elementales de grafos bicoloreados
adhocprefixadhocsufix \(\forall x\neg 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))))\)
Axiomas elementales de median algebras
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)))\)
Ahora que tenemos para cada tipo de estructura sus axiomas elementales podemos describir el concepto de prueba elemental, relativo a un tipo de estructura. Las pruebas elementales deberán poseer las siguientes características:
adhocprefix(1)adhocsufix El enunciado a probar debe ser una sentencia elemental pura del tipo de estructura en cuestión.
adhocprefix(2)adhocsufix En la prueba se parte de una estructura del tipo en cuestión, fija pero arbitraria en el sentido que lo único que sabemos es que ella satisface los axiomas elementales correspondientes (o sea esta es la única información particular que podemos usar).
adhocprefix(3)adhocsufix Las deducciones en la prueba son muy simples y obvias de justificar con mínimas frases en castellano.
adhocprefix(4)adhocsufix En la escritura de la prueba lo concerniente a la matemática misma se expresa usando solo sentencias elementales del tipo de estructura en cuestión
Dado que en una prueba se parte de una estructura fija de la que solo se asume que satisface los axiomas elementales y dado que las deducciones en una prueba elemental son muy simples y obvias de justificar, la sentencia elemental pura probada debe ser verdadera en todas las estructuras del tipo en cuestión.
A continuación 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)\] Nótese 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 máximos, entonces \(x=y\). Veamos una prueba elemental de posets de \(\mu\). Notar que, tal como lo aclara el ítem (2) arriba, debemos partir de un poset \((P,\leq)\), fijo pero arbitrario y solo usar la información 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
adhocprefix-adhocsufix \((\exists x\exists y\ \lnot(x=y)\rightarrow\exists x\exists y\ \lnot(x\leq y))\)
adhocprefix-adhocsufix \(\forall x\forall y\forall z\ ((x\leq y\wedge y\leq z\wedge x=z)\rightarrow x=y)\)
adhocprefix-adhocsufix \((\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 continuación 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 ítem (2) de la descripción de prueba elemental, debemos partir de un reticulado terna \((L,\mathsf{s},\mathsf{i})\), fijo pero arbitrario y solo usar la información 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 habíamos 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)\).
Nótese que las sentencias elementales de reticulados terna son sentencias elementales de reticulados cuaterna también. Sin embargo la prueba elemental de reticulados terna de arriba no es una prueba elemental de reticulados cuaterna (por que?).
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 tendrá problema para obtener de la prueba del Lema 1.24 las ideas para hacer una prueba elemental de reticulados terna de la sentencia elemental \((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 además no podemos escribir el símbolo \(\leq\). Podemos escribir \(t\;\mathsf{s}\;s=s\) en lugar de \(t\leq s\) y de esta manera simular en nuestras fórmulas elementales de reticulados terna al símbolo \(\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 ínfimo respecto del orden dado por la ecuación \(x\;\mathsf{s}\;y=y\). Esto puede ser resuelto si nos inspiramos en la prueba del Teorema de Dedekind que prueba justamente eso usando solo los axiomas elementales de los reticulados terna. Es decir, la prueba de dicho teorema parte de un reticulado terna fijo pero arbitrario y luego usando solo esta información prueba que la relación dada por “\(x\;\mathsf{s}\;y=y\)” es un orden parcial respecto del cual las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) son supremo e ínfimo. Podríamos usar las ideas de dicha demostración para dar pruebas elementales de reticulados terna de las siguientes sentencias \[\begin{aligned} & \forall x\forall y((x\mathsf{\;s\;}y=y\wedge y\mathsf{\;s\;}x=x)\rightarrow x=y)\\ & \forall x\forall y\forall z((x\mathsf{\;s\;}y=y\wedge y\mathsf{\;s\;}z=z)\rightarrow x\;\mathsf{s}\;z=z) \end{aligned}\] las cuales esencialmente dicen que la relación dada por “\(x\;\mathsf{s}\;y=y\)” es antisimétrica y transitiva. También podríamos extraer de dicha prueba las ideas para probar las sentencias elementales \[\begin{aligned} & \forall x\forall y(x\mathsf{\;s\;}(x\;\mathsf{s}\;y)=x\;\mathsf{s}\;y\wedge y\;\mathsf{s}\;(x\;\mathsf{s}\;y)=x\;\mathsf{s}\;y)\\ & \forall x\forall y\forall z((x\mathsf{\;s\;}z=z\wedge y\mathsf{\;s\;}z=z)\rightarrow(x\mathsf{\;s\;}y)\mathsf{\;s\;}z=z) \end{aligned}\] las cuales se corresponden con los axiomas \(\mathrm{A}_{\mathsf{s}esC}\) y \(\mathrm{A}_{\mathsf{s}\leq C}\) vía “escribir \(t\;\mathsf{s}\;s=s\) en lugar de \(t\leq s\)”. Dejamos esto como ejercicio opcional.
También tenemos el problema de no poder escribir el símbolo \(\leq\) en las pruebas elementales de reticulados acotados y también el escollo de que los axiomas no hacen referencia obvia a que las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) sean operaciones supremo e ínfimo respecto del orden dado por la ecuación \(x\;\mathsf{s}\;y=y\). Por supuesto que podemos hacer el truco hecho para los reticulados terna y ganar poder expresivo. Notar que toda prueba elemental de reticulados terna es también 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 ítem (2) de la descripción de prueba elemental, debemos partir de un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\), fijo pero arbitrario y solo usar la información 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 justificación simple y obvia (de hecho dicho teorema podría ser muy difícil 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 inspirándose en el Lema 1.25 de una prueba elemental de reticulados acotados de la sentencia elemental pura: \[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)\]
También tenemos el problema de no poder escribir el símbolo \(\leq\) en las pruebas elementales de reticulados acotados y también el escollo de que los axiomas no hacen referencia obvia a que las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) sean operaciones supremo e ínfimo respecto del orden dado por la ecuación \(x\;\mathsf{s}\;y=y\). Por supuesto que podemos hacer el truco hecho para los reticulados terna y ganar poder expresivo. Notar que toda prueba elemental de reticulados terna o de reticulados acotados es también una prueba elemental de reticulados complementados, por lo cual tenemos ya varias pruebas elementales de este tipo de estructuras.
Dejamos al lector que inspirándose en los resultados probados en la Sección de Reticulados Complementados de pruebas elementales de reticulados complementados de las siguientes sentencias elementales puras:
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(c(c(x))=x)\)
adhocprefix-adhocsufix \(Dis_{1}\rightarrow\forall x\forall y(c(x\mathsf{\;i\;}y)=c(x)\mathsf{\;s\;}c(y))\)
adhocprefix-adhocsufix \(Dis_{1}\rightarrow\forall x\forall y(c(x\mathsf{\;s\;}y)=c(x)\mathsf{\;i\;}c(y))\)
adhocprefix-adhocsufix \(Dis_{1}\rightarrow\forall x\forall y(x\mathsf{\;i\;}y=0\leftrightarrow y\mathsf{\;s\;}c(x)=c(x))\)
adhocprefix-adhocsufix \(Dis_{1}\rightarrow\forall x\forall y(x\mathsf{\;s\;}y=y\leftrightarrow c(y)\mathsf{\;s\;}c(x)=c(x))\)
Es difícil 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 fisonomía 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 análisis 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 geométrica y simple. Veamos un ejemplo. Supongamos que tenemos dos sucesiones \(x_{1},x_{2},...,x_{n}\) y \(y_{1},y_{2},...,y_{n}\) de vértices 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 algún \(i\in\{2,...,n-1\}\)
Entonces haciendo un dibujo uno rápidamente 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 todavía no esta escrita en forma de sentencia elemental y si quisiéramos hacerlo nos toparíamos 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 podríamos hacer una prueba elemental de grafos que pruebe dicha sentencia elemental.
También es difícil 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 ítem (2) de la descripción de prueba elemental, debemos partir de una median algebra \((A,M)\), fija pero arbitraria y solo usar la información 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 arbitrarios, 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 arbitrarios. 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 se observó que para el caso de los reticulados cuaterna 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 común que no se pueda decir cierta propiedad por medio de una fórmula o sentencia elemental. Esto habla en algún sentido del poco poder expresivo que tienen las fórmulas elementales lo cual es razonable por lo “elementales” y en algún sentido “finitarias” que son. Veamos algunos ejemplos mas de limitaciones del poder expresivo de las fórmulas elementales:
adhocprefix(E1)adhocsufix No hay una fórmula elemental pura \(\varphi\) de grafos la cual tenga a \(x\) e \(y\) como sus únicas 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:
adhocprefix-adhocsufix \(\varphi\) es verdadera en \((G,r)\) cuando asignamos a \(x\) el valor \(g_{1}\) y a \(y\) el valor \(g_{2}\)
adhocprefix-adhocsufix \(g_{1}\) y \(g_{2}\) están en la misma componente conexa de \((G,r)\)
Es decir no hay una fórmula elemental pura \(\varphi\) de grafos la cual “diga” \(x\) e \(y\) están en la misma componente conexa
adhocprefix(E2)adhocsufix No hay una fórmula elemental pura \(\varphi\) de posets la cual tenga a \(x\) e \(y\) como sus únicas 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:
adhocprefix-adhocsufix \(\varphi\) es verdadera en \((P,\leq)\) cuando asignamos a \(x\) el valor \(p_{1}\) y a \(y\) el valor \(p_{2}\)
adhocprefix-adhocsufix El intervalo \(\{p\in P:p_{1}\leq p\leq p_{2}\}\) es un conjunto finito
Es decir no hay una fórmula elemental pura \(\varphi\) de posets (la cual tenga a \(x\) e \(y\) como sus únicas variables libres) la cual “diga” el intervalo \([x,y]\) es finito.
adhocprefix(E3)adhocsufix Los reticulados terna \((\mathbf{R},max,min)\) y \((\mathbf{Q},max,min)\) son indistinguibles usando sentencias elementales, i.e. si \(\varphi\) es una sentencia elemental pura de reticulados terna, entonces \(\varphi\) es veradera en \((\mathbf{R},max,min)\) si y solo si \(\varphi\) es veradera en \((\mathbf{Q},max,min)\).
adhocprefix(E4)adhocsufix No hay una sentencia elemental pura \(\varphi\) 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 \((\mathbf{R},max,min)\). Esto se puede deducir del ejemplo anterior ya que \((\mathbf{R},max,min)\) y \((\mathbf{Q},max,min)\) no pueden ser isomorfos porque no existe una biyeccion entre \(\mathbf{R}\) y \(\mathbf{Q}\).
Lo mas común es que si una propiedad involucra infinitos chequeos no se pueda “decir” por medio de una fórmula elemental. Las imposibilidades dadas en (E1) y (E2) pueden ser justificadas usando el Teorema de Compacidad que veremos mas adelante. (E3) puede ser probado via un razonamiento inductivo pero requiere cierta destreza.
Supongamos tenemos una cuatrupla \((A,f,g,R)\) tal que \(A\) es un conjunto no vacío, \(f\) y \(g\) son operaciones binarias sobre \(A\) y \(R\) es una relación binaria sobre \(A\), pero no sabemos nada acerca de estas operaciones \(f\) y \(g\) ni de la relación \(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 fórmula elemental de reticulados cuaterna es verdadera en \((A,f,g,R)\) para una asignación 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 fórmula interpretando además sus variables libres y nombres de elementos fijos según la asignación dada. Dicho en pocas palabras, las fórmulas elementales de reticulados cuaterna se pueden interpretar no solo en los reticulados cuaterna sino también en cualquier “estructura del mismo tipo”.
Veamos algunos ejemplos:
adhocprefix(E1)adhocsufix La fórmula 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 relación \(\{(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(E2)adhocsufix La fórmula 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 operación \(+\).
adhocprefix(E3)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(E4)adhocsufix La fórmula elemental de reticulados cuaterna \(((a\;\mathsf{s\;}y)=(a\;\mathsf{i\;}y))\) es verdadera en la estructura \((\mathbf{N},+,+,|)\) cualquiera sea la asignación de valores a \(a\) y a \(y\).
adhocprefix(E5)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(E6)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 generalización 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 vacío cualquiera y \(R\) es una relación binaria sobre \(A\) (cualquier relación binaria, no necesariamente un orden parcial) podemos hablar de cuando una fórmula elemental de posets es verdadera en \((A,R)\) para una asignación de valores de \(A\) a sus variables libres y sus nombres de elementos fijos. Simplemente debemos interpretar a \(\leq\) como \(R\) y “leer” dicha fórmula interpretando además sus variables libres y nombres de elementos fijos según la asignación dada. Algunos ejemplos
adhocprefix(E7)adhocsufix La fórmula 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 relación \(\mathbf{R}\times\omega\). Cabe destacar que \((\mathbf{R},\mathbf{R}\times\omega)\) no es un poset (por que?)
adhocprefix(E8)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(E9)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 operación \(-\) sobre los reales y a \(c\) como la función \(\{(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 número real \(x\) hay un número real \(y\) tal que \(y-y=x^{2}\), lo cual sabemos que es falso.
adhocprefix(E10)adhocsufix La fórmula 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 relación binaria \(\{(1,1),(3,4)\}\) y a \(R\) como la relación 1-aria \(\{5,6,7,8,9,10\}\).
adhocprefix(E11)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 operación \(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\). Nótese 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.