En esta sección introduciremos un nuevo tipo de estructura que llamaremos reticulado cuaterna, pero nuestra intención aquí no será hacer teoremas similares a los hechos con las estructuras ya estudiadas. De hecho ya lo hicimos en detalle tantas veces que el lector no tendría problema si quisiera definir los conceptos de subestructura, subuniverso, homomorfismo, etc para los reticulados cuaterna. Nuestra intención aquí será delimitar en forma intuitiva un lenguaje muy elemental con el cual se pueden enunciar muchas propiedades matemáticas de los reticulados cuaterna y también con el cual se pueden hacer muchas pruebas interesantes sin salirse de dicho lenguaje elemental (a las cuales llamaremos pruebas elementales). Comencemos con la definición matemática de este nuevo tipo de estructura.
Por un reticulado cuaterna entenderemos una \(4\)-upla \((L,\mathsf{s},\mathsf{i},\leq)\) tal que \(L\) es un conjunto no vacío, \(\mathsf{s}\) e \(\mathsf{i}\) son operaciones binarias sobre \(L\), \(\leq\) es una relación binaria sobre \(L\) y se cumplen las siguientes propiedades:
adhocprefix(1)adhocsufix \(x\leq x\), cualesquiera sea \(x\in L\)
adhocprefix(2)adhocsufix \(x\leq y\text{ y }y\leq z\text{ implican }x\leq z\), cualesquiera sean \(x,y,z\in L\)
adhocprefix(3)adhocsufix \(x\leq y\text{ y }y\leq x\text{ implican }x=y\), cualesquiera sean \(x,y\in L\)
adhocprefix(4)adhocsufix \(x\leq x\;\mathsf{s}\;y\text{ y }y\leq x\;\mathsf{s}\;y\), cualesquiera sean \(x,y\in L\)
adhocprefix(5)adhocsufix \(x\leq z\text{ y }y\leq z\text{ implican }x\;\mathsf{s}\;y\leq z\), cualesquiera sean \(x,y,z\in L\)
adhocprefix(6)adhocsufix \(x\;\mathsf{i}\;y\leq x\text{ y }x\;\mathsf{i}\;y\leq y\), cualesquiera sean \(x,y\in L\)
adhocprefix(7)adhocsufix \(z\leq x\text{ y }z\leq y\text{ implican }z\leq x\;\mathsf{i}\;y\), cualesquiera sean \(x,y,z\in L\)
Obviamente (1), (2) y (3) nos garantizan que \((L,\leq)\) es un poset. Nótese que (4) nos dice que cualesquiera sean \(x,y\in L\) se tiene que \(x\;\mathsf{s}\;y\) es cota superior del conjunto \(\{x,y\}\). Además (5) nos dice que cualesquiera sean los elementos \(x,y\in L\), se tiene que \(x\;\mathsf{s}\;y\leq z\), cada vez que \(z\) es cota superior del conjunto \(\{x,y\}\). Por supuesto esto nos garantiza que \(x\;\mathsf{s}\;y=\mathrm{sup}(\{x,y\})\), cualesquiera sean \(x,y\in L\). Similarmente (6) y (7) garantizan que \(x\;\mathsf{s}\;y=\inf(\{x,y\})\), cualesquiera sean \(x,y\in L\).
O sea que, en virtud del Teorema de Dedekind y de los resultados sobre reticulados par probados anteriormente, tenemos que un reticulado cuaterna no es ni mas ni menos que una \(4\)-upla \((L,\mathsf{s},\mathsf{i},\leq)\) tal que \((L,\mathsf{s},\mathsf{i})\) es un reticulado terna y \(\leq\) es su orden parcial asociado. Pero debe quedar claro que este último resultado es un teorema y no la definición de reticulado cuaterna.
Algunos ejemplos de reticulados cuaterna:
adhocprefix-adhocsufix \((\mathbf{N},mcm,mcd,|)\)
adhocprefix-adhocsufix \((\mathbf{R},max,min,\leq)\), donde \(\leq\) es el orden usual de los números reales
adhocprefix-adhocsufix \((\{A\subseteq\mathbf{N}:A\) es finito\(\},\cup,\cap,\subseteq)\)
Convención Notacional: Muchos conceptos definidos para posets o reticulados terna los usaremos referidos a un reticulado cuaterna. Por ejemplo, si decimos que \((L,\mathsf{s},\mathsf{i},\leq)\) es totalmente ordenado, esto significara que el poset \((L,\leq)\) lo es. Si decimos que \((L,\mathsf{s},\mathsf{i},\leq)\) tiene elemento máximo, esto significara que el poset \((L,\leq)\) lo tiene. Si decimos que en \((L,\mathsf{s},\mathsf{i},\leq)\) el elemento \(a\) cubre al elemento \(b\), esto significara que eso sucede en el poset \((L,\leq)\). Otro ejemplo, si decimos que \((L,\mathsf{s},\mathsf{i},\leq)\) es distributivo, nos estaremos refiriendo a que \((L,\mathsf{s},\mathsf{i})\) es distributivo. También hablaremos del diagrama de Hasse de \((L,\mathsf{s},\mathsf{i},\leq)\) en referencia al diagrama de Hasse de su poset asociado \((L,\leq)\).
En lo que sigue comenzaremos a definir en forma intuitiva el lenguaje elemental de los reticulados cuaterna. Lo que debe quedar claro es que no nos interesa dar definiciones matemáticas rigurosas de estos conceptos sino mas bien dejar bien desarrollada nuestra intuición respecto de los mismos.
Son palabras que se construyen usando símbolos de la siguiente lista
adhocprefix-adhocsufix Paréntesis: \((\;\;)\)
adhocprefix-adhocsufix Variables: \(x,y,z,w,...\)
adhocprefix-adhocsufix Nombres de elementos fijos: \(a,b,c,d,...\)
adhocprefix-adhocsufix Los símbolos: \(\mathsf{s}\text{ }\) \(\text{ }\mathsf{i}\)
Intuitivamente hablando son palabras que representan el resultado de aplicar a las variables y a los nombres de elementos fijos las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) cierta cantidad de veces (posiblemente 0 veces). Algunos ejemplos:
adhocprefix-adhocsufix \((x\;\mathsf{s\;}y)\)
adhocprefix-adhocsufix \(((a\mathsf{\;i\;}y)\;\mathsf{s}\;z)\)
adhocprefix-adhocsufix \(((x\mathsf{\;s\;}y)\;\mathsf{s}\;((x\mathsf{\;s\;}y)\;\mathsf{s}\;z))\)
adhocprefix-adhocsufix \((x\mathsf{\;i\;}(x\mathsf{\;i\;}(b\mathsf{\;i\;}x)))\)
adhocprefix-adhocsufix \(x\)
adhocprefix-adhocsufix \(a\)
Es muy importante entender que los términos elementales de reticulados cuaterna son palabras, es decir \(Ti(t)=\mathrm{PALABRA}\), cada vez que \(t\) es un término elemental de reticulado cuaterna. Por ejemplo el término elemental dado en el primer ejemplo arriba es una palabra de longitud 5 (los espacios no cuentan y son para hacerla mas “legible”) el del quinto ejemplo es una palabra de longitud 1 (la letra \(x\)), etc. No precisaremos bien la lista de variables y la de nombres de elementos fijos pero esto no traerá problemas para el manejo intuitivo que haremos del tema.
Las siguientes reglas constructivas nos aproximan razonablemente al concepto de término elemental de reticulado cuaterna (aunque no sean una definición matemática precisa):
adhocprefix(1)adhocsufix Cada variable es un término elemental de reticulados cuaterna
adhocprefix(2)adhocsufix Cada nombre de elemento fijo es un término elemental de reticulados cuaterna
adhocprefix(3)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados cuaterna, entonces la palabra \((t\;\mathsf{s\;}s)\) es un término elemental de reticulados cuaterna
adhocprefix(4)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados cuaterna, entonces la palabra \((t\;\mathsf{i\;}s)\) es un término elemental de reticulados cuaterna
adhocprefix(5)adhocsufix Una palabra es un término elemental de reticulados cuaterna si y solo si se puede construir usando las clausulas anteriores
Debería quedar claro que arriba \((t\;\mathsf{s\;}s)\) denota el resultado de concatenar las 5 siguientes palabras \[(\;\;\;\;\;\;t\;\;\;\;\;\;\;\;\;\mathsf{s\;}\;\;\;\;\;\;\;s\;\;\;\;\;\;\;\;\;)\] es decir que \((t\;\mathsf{s\;}s)\) es una palabra de longitud \(\left|t\right|+\left|s\right|+3\).
Para que un término elemental \(t\) represente o asuma un valor debemos tener un reticulado cuaterna concreto y asignarle valores a las variables y a los nombres de elementos fijos que ocurren en \(t\). Algunos ejemplos:
adhocprefix-adhocsufix En el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\), el término elemental \(((x\mathsf{\;i\;}b))\), cuando le asignamos a \(x\) el valor \(200\) y a \(b\) el valor \(300\), asume el valor 100 (ya que \(mcd(200,300)=100\)).
adhocprefix-adhocsufix En el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\), el término elemental \(z\), cuando le asignamos a \(z\) el valor \(200\) asume el valor 200.
adhocprefix-adhocsufix En el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\), el término elemental \(((x\mathsf{\;i\;}y)\;\mathsf{s}\;z)\), cuando le asignamos a \(x\) el valor \(20\) a \(y\) el valor 12 y a \(z\) el valor 100, asume el valor 100 (ya que \(mcm(mcd(20,12),100)=100\)).
adhocprefix-adhocsufix En el reticulado cuaterna \((\{A\subseteq\mathbf{N}:A\text{ es finito}\},\cup,\cap,\subseteq)\), el término elemental \(((x\mathsf{\;i\;}y)\mathsf{\;i\;}z)\), cuando le asignamos a \(x\) el valor \(\{1,5,9\}\) a \(y\) el valor \(\{5,6,9,1000\}\) y a \(z\) el valor \(\{9\}\), asume el valor \(\{9\}\) (ya que \((\{1,5,9\}\cap\{5,6,9,1000\})\cap\{9\}=\{9\}\)).
Es muy importante no confundir un término elemental con el valor que asume en un determinado reticulado cuaterna, para alguna asignación de valores a sus variables y nombres de elementos fijos. Por ejemplo los términos elementales \((x\mathsf{\;i\;}y)\) y \((y\mathsf{\;i\;}x)\) son distintos y sin embargo asumen siempre el mismo valor cualquiera sea el reticulado cuaterna que consideremos y cualquiera sea la asignación de valores que tomemos para las variables \(x\) e \(y\).
Un término elemental de reticulados cuaterna será llamado puro cuando en el no ocurran nombres de elementos fijos.
Las fórmulas elementales de reticulados cuaterna son palabras que se construyen usando símbolos de la siguiente lista:
adhocprefix-adhocsufix \(\forall\ \exists\;\lnot\;\vee\;\wedge\;\rightarrow\;\leftrightarrow\;(\;)\;=\;\mathsf{s\;}\mathsf{i\;}\leq\)
adhocprefix-adhocsufix Variables: \(x,y,z,w,...\)
adhocprefix-adhocsufix Nombres de elementos fijos: \(a,b,c,d,...\)
Es decir que, mas allá de que no daremos una definición matemática rigurosa del concepto de fórmula elemental de reticulados cuaterna, es importante entender que son meras palabras, es decir \(Ti(\varphi)=\mathrm{PALABRA}\), cada ves que \(\varphi\) es una fórmula elemental de reticulado cuaterna. Antes de dar una descripción mas completa del concepto, veamos algunos ejemplos concretos:
adhocprefix-adhocsufix \((x\leq y)\)
adhocprefix-adhocsufix \((x=y)\)
adhocprefix-adhocsufix \(((x\;\mathsf{s\;}y)=a)\)
adhocprefix-adhocsufix \(((a\;\mathsf{s\;}z)\;\mathsf{i\;}x)=((x\;\mathsf{i\;}y)\;\mathsf{s\;}x))\)
adhocprefix-adhocsufix \((((a\leq z)\wedge(x=y))\wedge\lnot(x=y))\)
adhocprefix-adhocsufix \(\lnot\exists y((x\;\mathsf{s\;}y=y)\wedge\lnot(x=y))\)
adhocprefix-adhocsufix \(\forall x\forall y\forall z(((x\leq y)\wedge(y\leq z))\rightarrow(x\leq z))\)
adhocprefix-adhocsufix \(\forall x\exists y((x\;\mathsf{s\;}y)=a)\)
adhocprefix-adhocsufix \(\forall x\forall y\forall z\forall w(((x\leq z)\wedge(y\leq w))\rightarrow((x\;\mathsf{s}\ y)\leq(z\;\mathsf{s}\ w)))\)
Como puede notarse es muy común que una fórmula elemental tenga a términos elementales como subpalabras aunque los términos elementales tienen un distinto significado que las fórmulas elementales ya que ellos representan elementos y las fórmulas elementales son palabras que cuando las interpretamos adecuadamente se vuelven verdaderas o falsas. Las siguientes reglas constructivas nos aproximan razonablemente al concepto de fórmula elemental de reticulado cuaterna (aunque no sean una definición matemática precisa):
adhocprefix(1)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados cuaterna, entonces la palabra \((t=s)\) es una fórmula elemental de reticulados cuaterna
adhocprefix(2)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados cuaterna, entonces la palabra \((t\leq s)\) es una fórmula elemental de reticulados cuaterna
adhocprefix(3)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados cuaterna, entonces la palabra \((\varphi_{1}\wedge\varphi_{2})\) es una fórmula elemental de reticulados cuaterna
adhocprefix(4)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados cuaterna, entonces la palabra \((\varphi_{1}\vee\varphi_{2})\) es una fórmula elemental de reticulados cuaterna
adhocprefix(5)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados cuaterna, entonces la palabra \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una fórmula elemental de reticulados cuaterna
adhocprefix(6)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados cuaterna, entonces la palabra \((\varphi_{1}\rightarrow\varphi_{2})\) es una fórmula elemental de reticulados cuaterna
adhocprefix(7)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados cuaterna, entonces la palabra \(\lnot\varphi\) es una fórmula elemental de reticulados cuaterna
adhocprefix(8)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados cuaterna, entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son fórmulas elementales de reticulados cuaterna
adhocprefix(9)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados cuaterna, entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son fórmulas elementales de reticulados cuaterna
adhocprefix(10)adhocsufix Una palabra es una fórmula elemental de reticulados cuaterna si y solo si se puede construir usando las clausulas anteriores
Debería quedar claro que, por ejemplo, arriba \((\varphi_{1}\wedge\varphi_{2})\) denota el resultado de concatenar las 5 siguientes palabras \[(\;\;\;\;\;\;\varphi_{1}\;\;\;\;\;\;\;\;\;\wedge\;\;\;\;\;\;\;\varphi_{2}\;\;\;\;\;\;\;\;\;)\] es decir que \((\varphi_{1}\wedge\varphi_{2})\) es una palabra de longitud \(\left|\varphi_{1}\right|+\left|\varphi_{2}\right|+3\). Nótese que siempre "cuantificamos por delante", es decir que la palabra \((x\leq a)\forall x\) NO es una fórmula elemental de reticulados cuaterna. Tampoco se cuantificaran los nombres de elementos fijos, es decir solo cuantificamos variables. O sea que \(\forall a(a=x)\) no es una fórmula elemental.
Observación Importante: Nótese que según los items (7), (8) y (9), cuando “negamos” y cuando “cuantificamos”, no agregamos paréntesis. Solo agregamos paréntesis cuando “nexamos” un par de fórmulas. Esto hay que tenerlo en cuenta para leer las fórmulas. Por ejemplo la fórmula \((\exists z(a\leq z)\wedge(b\leq z))\) debe leerse como la conjunción de las fórmulas \(\exists z(a\leq z)\) y \((b\leq z)\) y no pensarse como una fórmula que dice “\(\exists z\text{ tal que }(a\leq z)\wedge(b\leq z)\)”. Sucede algo similar con la negación. Es decir si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales entonces la fórmula elemental \((\lnot\varphi_{1}\wedge\varphi_{2})\) debe leerse como la conjunción de \(\lnot\varphi_{1}\) y \(\varphi_{2}\) y no pensarse como una fórmula que dice “no es verdad que \(\varphi_{1}\wedge\varphi_{2}\)”. O sea, los cuantificadores y la negación tienen precedencia sobre los nexos lógicos.
Una fórmula elemental de reticulados cuaterna será llamada pura cuando en ella no ocurran nombres de elementos fijos. Nótese que en particular los términos que ocurran en una fórmula elemental pura serán también puros.
Para que una fórmula elemental se vuelva verdadera o falsa tenemos que tener un reticulado cuaterna concreto \((L,\mathsf{s},\mathsf{i},\leq)\) y además asignar valores concretos de \(L\) a las variables libres y a los nombres de elementos fijos que ocurren en dicha fórmula. También cabe destacar que los cuantificadores siempre ranguean sobre \(L\), es decir \(\forall x\) se interpretara como \(\forall x\in L\) y \(\exists x\) se interpretara como \(\exists x\in L\). Veamos algunos ejemplos concretos:
adhocprefix-adhocsufix La fórmula elemental \((x\leq y)\) tiene a las variables \(x\) e \(y\) libres y en el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\) es verdadera cuando le asignamos a \(x\) el valor \(6\) y a \(y\) el valor \(36\). Esto es ya que interpretamos a \(\leq\) como la relación \(|\) y \(6\text{ divide a }36\)
adhocprefix-adhocsufix La fórmula elemental \((((a\;\mathsf{s\;}y)=y)\vee((y\;\mathsf{s\;}a)=a))\) tiene a \(y\) como su única variable libre y en el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\) es falsa cuando le asignamos a \(a\) el valor \(5\) y a \(y\) el valor \(11\) y verdadera cuando le asignamos a \(a\) el valor \(5\) y a \(y\) el valor \(10\). Esta fórmula es verdadera en el reticulado cuaterna \((\mathbf{N},max,min,\leq)\) para cualquier asignación de valores a \(a\) y a \(y\).
adhocprefix-adhocsufix La fórmula elemental \(\exists y((y\leq x)\wedge\lnot(y=x))\) tiene a \(x\) como su única variable libre y en el reticulado cuaterna \((\{A\subseteq\mathbf{N}:A\text{ es finito}\},\cup,\cap,\subseteq)\) es verdadera cuando le asignamos a \(x\) cualquier valor distinto de \(\emptyset\) y es falsa cuando le asignamos a \(x\) el valor \(\emptyset\)
adhocprefix-adhocsufix La fórmula elemental \(((\lnot(x=y)\wedge\lnot(x=z))\wedge\lnot(y=z))\) es verdadera en un reticulado cuaterna si y solo si los valores que le asignamos a las variables \(x\), \(y\) y \(z\) son distintos entre si.
Por supuesto, cuando la fórmula elemental es pura, su valor de verdad en un reticulado cuaterna dado solo depende de que valores asignemos a sus variables libres. También es bueno pensar que
adhocprefix-adhocsufix La fórmula elemental \(\forall y(x\leq y)\) dice \[x\text{ es un elemento minimo de }(L,\mathsf{s},\mathsf{i},\leq)\] en el sentido que ella será verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si el valor asignado a \(x\) es un elemento mínimo de \((L,\mathsf{s},\mathsf{i},\leq)\).
adhocprefix-adhocsufix La fórmula elemental \(\forall y(y\leq b)\) dice \[b\text{ es un elemento maximo de }(L,\mathsf{s},\mathsf{i},\leq)\] en el sentido que ella será verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo el valor asignado a \(b\) es un elemento máximo de \((L,\mathsf{s},\mathsf{i},\leq)\).
adhocprefix-adhocsufix La fórmula elemental \(((x\leq y)\wedge\lnot(y=x))\) dice \(x\) es menor que \(y\) en \((L,\mathsf{s},\mathsf{i},\leq)\)
adhocprefix-adhocsufix La fórmula elemental \(\lnot\exists z((x\leq z)\wedge\lnot(z=x))\) dice \(x\) es un elemento maximal de \((L,\mathsf{s},\mathsf{i},\leq)\)
Cuando una fórmula elemental de reticulados cuaterna no tiene variables libres diremos que es una sentencia elemental de reticulados cuaterna. Algunos ejemplos de sentencias elementales de reticulados cuaterna:
adhocprefix-adhocsufix \(\forall x(a\leq x)\)
adhocprefix-adhocsufix \(\exists x\exists y\lnot(x=y)\)
adhocprefix-adhocsufix \(\forall x\forall y((x\leq y)\vee(y\leq x))\)
adhocprefix-adhocsufix \(\exists x\exists y((((a\;\mathsf{s\;}x)=(a\;\mathsf{s\;}y))\wedge\lnot(x\leq y))\wedge\lnot(y\leq x))\)
Nótese que una sentencia elemental de reticulados cuaterna será verdadera o falsa en \((L,\mathsf{s},\mathsf{i},\leq)\) dependiendo solo de los valores que tomen los nombres de elementos fijos que ocurren en ella. Y si ella es pura (i.e. no ocurren en ella nombres de elementos fijos), entonces dado un reticulado cuaterna concreto, la sentencia resulta verdadera o falsa. Por ejemplo:
adhocprefix-adhocsufix La sentencia elemental \(\forall x(a\leq x)\) es verdadera en el reticulado cuaterna \((\{A\subseteq\mathbf{N}:A\text{ es finito}\},\cup,\cap,\subseteq)\) cuando le asignamos a \(a\) el valor \(\emptyset\) y falsa cuando le asignamos cualquier otro valor de \(\{A\subseteq\mathbf{N}:A\text{ es finito}\}\)
adhocprefix-adhocsufix La sentencia elemental pura \(\exists x\exists y\lnot(x=y)\) es verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si \(L\) tiene al menos dos elementos distintos.
adhocprefix-adhocsufix La sentencia elemental pura \(\forall x\forall y((x\leq y)\vee(y\leq x))\) es verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si el poset \((L,\leq)\) es un conjunto totalmente ordenado
adhocprefix-adhocsufix La sentencia elemental \[\exists x\exists y((((a\;\mathsf{s\;}x)=(a\;\mathsf{s\;}y))\wedge\lnot(x\leq y))\wedge\lnot(y\leq x))\] es verdadera en el reticulado cuaterna \((\mathcal{P}(\{0,1,2\}),\cup,\cap,\subseteq)\) cuando le asignamos a \(a\) el valor \(\{0,1\}\) y es falsa cuando le asignamos a \(a\) el valor \(\{0\}\) o el valor \(\emptyset\)
Ya que el tema de cuando una variable es libre o no, es bastante delicado, nos explayaremos un poco mas. Primero deberíamos notar que si una variable ocurre varias veces en una fórmula, entonces algunas de aquellas ocurrencias serán libres y otras no. Por ejemplo
adhocprefix-adhocsufix En la fórmula \(((x\leq a)\wedge\forall x(b\leq x))\) la primer ocurrencia de \(x\) es libre y las otras dos ocurrencias de \(x\) no son libres
Como es usual a las ocurrencias que no son libres las llamaremos acotadas. O sea que toda ocurrencia de una variable en una fórmula es ya sea libre o acotada. Por ejemplo, en la fórmula \[(((a\;\mathsf{s\;}b)\leq y)\wedge\forall y((z\;\mathsf{s\;}b)\leq y))\] la variable \(y\) ocurre tres veces, la primera ocurrencia es libre y la segunda y tercera son acotadas.
Cuando digamos que \(x\) es una variable libre de una fórmula elemental \(\varphi\) nos estaremos refiriendo a que la variable \(x\) ocurre al menos una ves libremente en \(\varphi\), aunque también puede ocurrir acotadamente en \(\varphi\). Por ejemplo:
adhocprefix-adhocsufix \(x\) es una variable libre de la fórmula \(((x\leq a)\wedge\forall x(b\leq x))\) (aunque ocurre acotadamente)
adhocprefix-adhocsufix Las variables libres de la fórmula \[(((x\leq z)\vee\exists x\forall y((a\leq x)\wedge(y\leq x)))\rightarrow\forall y(z\leq y))\] son \(x\) y \(z\). Las dos ocurrencias de \(z\) son libres, todas las ocurrencias de \(y\) son acotadas, la primer ocurrencia de \(x\) es libre y las otras tres ocurrencias de \(x\) son acotadas.
Un cuantificador será una palabra formada por alguno de los símbolos \[\forall\ \ \ \ \exists\] seguido de una variable. Es decir \[\exists x\ \ \ \forall x\ \ \ \exists y\ \ \ \forall y\ \ \ \exists z\ \ \ \forall z\ \ \ldots\] son los cuantificadores.
Una propiedad importante de las fórmulas elementales es que siempre que un cuantificador ocurra en una fórmula elemental, seguido a dicha ocurrencia ocurrirá una fórmula elemental (la cual además es única). Ejemplos:
adhocprefix-adhocsufix En la fórmula \[(((x\leq y)\wedge\forall y\lnot(y=a))\rightarrow\forall y((z\;\mathsf{s\;}y)\leq y))\] seguido a la segunda ocurrencia del cuantificador \(\forall y\) ocurre la fórmula \(((z\;\mathsf{s\;}y)\leq y)\) y seguido a la primer ocurrencia del cuantificador \(\forall y\) ocurre la fórmula \(\lnot(y=a)\).
adhocprefix-adhocsufix En la fórmula \[\forall x\forall y((x\leq y)\vee(y\leq x))\] seguido a la única ocurrencia del cuantificador \(\forall y\) ocurre la fórmula \(((x\leq y)\vee(y\leq x))\) y seguido a la única ocurrencia del cuantificador \(\forall x\) ocurre la fórmula \(\forall y((x\leq y)\vee(y\leq x))\)
Llamaremos a esta fórmula elemental única que sigue a la ocurrencia de un cuantificador el alcance de dicha ocurrencia. En los siguientes ejemplos subrayaremos algunos alcances de ocurrencias de cuantificadores.
adhocprefix-adhocsufix En la fórmula \[((((x\leq y)\wedge\forall y\underline{\lnot(y=a)})\rightarrow\forall y((z\;\mathsf{i\;}y)\leq y))\vee(x\leq z))\] hemos subrayado el alcance de la primer ocurrencia del cuantificador \(\forall y\).
adhocprefix-adhocsufix En la fórmula \[\forall x\underline{\forall y((x\leq y)\vee(y\leq x))}\] hemos subrayado el alcance de la única ocurrencia del cuantificador \(\forall x\).
adhocprefix-adhocsufix En la fórmula \[(((x\leq z)\vee\exists x\underline{\forall y((a\leq(x\;\mathsf{i\;}b))\wedge(y\leq x))})\rightarrow\exists x(x\leq(y\;\mathsf{i\;}c)))\] hemos subrayado el alcance de la primer ocurrencia del cuantificador \(\exists x\).
Es importante notar que no tiene sentido hablar a secas del alcance de un cuantificador en una fórmula ya que el mismo cuantificador puede ocurrir varias veces en dicha fórmula y tener distintos alcances cada una de las distintas ocurrencias. Es decir el concepto de alcance es relativo a una ocurrencia de un cuantificador. Por ejemplo
adhocprefix-adhocsufix En la fórmula \[((((x\leq y)\wedge\forall y\lnot(y=a))\rightarrow\forall y(z\leq y))\vee(x\leq z))\] el alcance de la primer ocurrencia del cuantificador \(\forall y\) es \(\lnot(y=a)\) y el alcance de la segunda ocurrencia de \(\forall y\) es \((z\leq y)\).
Nótese que una ocurrencia de una variable \(v\) en una fórmula elemental \(\varphi\) será acotada si y solo si ella sucede dentro de una ocurrencia en \(\varphi\) de una fórmula de la forma \(Qv\psi\), con \(Q\in\{\forall,\exists\}\) y \(\psi\) una fórmula elemental.
Además debería quedar claro que el rol jugado por una variable \(v\) en sus ocurrencias acotadas dentro de una ocurrencia en \(\varphi\) de una fórmula de la forma \(Qv\psi\) es "mudo" o "impersonal" en el sentido que podríamos reemplazar dichas ocurrencias de \(v\) por una variable \(w\) que no figure en la fórmula \(\psi\) y el significado de la fórmula resultante seria el mismo que el significado de \(\varphi\). Por ejemplo la fórmula \[\varphi=(\lnot(x=a)\wedge\forall y((x\leq y)\vee(y\leq x)))\] nos "dice" que \(x\) es distinto a \(a\) y que \(x\) es comparable con todo elemento de \(L\); y si reemplazamos cada ocurrencia de \(y\) en el bloque \(\forall y((x\leq y)\vee(y\leq x))\) por la variable \(z\), obtenemos \[(\lnot(x=a)\wedge\forall z((x\leq z)\vee(z\leq x)))\] la cual claramente dice lo mismo acerca de \(x\) y \(a\).
Aviso Importante: Ya tenemos una intuición bien clara del concepto de fórmula elemental y en esta etapa no nos interesa ser puntillosos en la escritura por lo cual muchas veces para hacer mas dinámica la exposición suprimiremos algunos paréntesis. Algunos ejemplos:
En lugar de escribir \(((x\leq y)\wedge(y\leq z))\) escribiremos \(x\leq y\wedge y\leq z\)
En lugar de escribir \(((x\leq y)\wedge(y\leq z))\vee(a=b))\) escribiremos \((x\leq y\wedge y\leq z)\vee a=b\)
En lugar de escribir \(((a\leq b)\wedge(x\leq y))\wedge(z=c))\) escribiremos \(a\leq b\wedge x\leq y\wedge z=c\)
En lugar de escribir \((a\leq(x\;\mathsf{i\;}b))\) escribiremos \(a\leq x\;\mathsf{i\;}b\)
En lugar de escribir \(((a\;\mathsf{s\;}x)=(a\;\mathsf{s\;}y))\) escribiremos \(a\;\mathsf{s\;}x=a\;\mathsf{s\;}y\)
Hay muchas propiedades de los reticulados cuaterna que no se pueden “decir” usando sentencias elementales puras. Por ejemplo no hay una sentencia elemental pura 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. Por supuesto esto lo podemos “decir” de la siguiente manera \[\exists x_{1}\exists x_{2}...\exists x_{n}\forall z((z=x_{1})\vee(z=x_{2})\vee...\vee(z=x_{n}))\] pero aquí el problema es que \(n\) hace referencia a algún natural que puede variar y no podemos reemplazarlo por uno concreto ya que entonces la sentencia solo valdría en los reticulados cuaterna con a lo sumo esa cantidad de elementos. Es decir las fórmulas elementales en general no pueden expresar la existencia de una sucesión finita de elementos, solo la existencia de una cantidad concreta fija de elementos. O sea se puede “decir” existen tres elementos tales que ... o “decir” existen 10 elementos tales que ... pero no se puede “decir” existen \(n\) elementos tales que ... , pensando que \(n\) es algún natural. Una prueba de esta imposibilidad de “decir” con una sentencia elemental que el universo de \((L,\mathsf{s},\mathsf{i},\leq)\) es finito es consecuencia directa del Teorema de Compacidad que veremos mas adelante.
Nótese que las propiedades (1), ... ,(7) que definen reticulado cuaterna pueden ser escritas como sentencias elementales puras 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)\)
Llamaremos a estas sentencias elementales puras los axiomas elementales de reticulados cuaterna. El nombre \(\mathrm{A}_{\leq R}\) hace referencia a que esta sentencia “dice” que la relación \(\leq\) es reflexiva. El nombre \(\mathrm{A}_{\mathsf{s}esC}\) hace referencia a que esta sentencia “dice” que \(x\;\mathsf{s}\;y\) es cota superior del conjunto \(\{x,y\}\). El nombre \(\mathrm{A}_{\mathsf{s}\leq C}\) hace referencia a que esta sentencia “dice” que \(x\;\mathsf{s}\;y\) es menor o igual a cualquier cota superior del conjunto \(\{x,y\}\). Los otros nombres fueron elegidos en forma análoga.
Muchas propiedades que son ciertas en todos los reticulados cuaterna se pueden escribir usando sentencias elementales puras de reticulados cuaterna. Por ejemplo la sentencia elemental pura \(\rho=\forall x\forall y(x\;\mathsf{s}\;y=y\;\mathsf{s}\;x)\) es cierta en cada reticulado cuaterna. Esto nosotros lo sabemos ya que en un reticulado cuaterna los axiomas \(\mathrm{A}_{\mathsf{s}esC}\) y \(\mathrm{A}_{\mathsf{s}\leq C}\) nos garantizan que \(x\;\mathsf{s}\;y=\mathrm{sup}\{x,y\}\) y obviamente \(\mathrm{sup}\{x,y\}=\mathrm{sup}\{y,x\}\). Pero esta prueba o justificación de \(\rho\) usa la expresión \(\mathrm{sup}\{x,y\}\), la cual no forma parte de las fórmulas elementales. Nos interesa dar una prueba muy especial de \(\rho\) en el sentido que se cumplan las siguientes características
adhocprefix(1)adhocsufix En la prueba se parte de una estructura \((L,\mathsf{s},\mathsf{i},\leq)\) fija pero arbitraria en el sentido lo único que sabemos de ella es:
adhocprefix-adhocsufix \(L\) es un conjunto no vacío
adhocprefix-adhocsufix \(\mathsf{s}\) e \(\mathsf{i}\) son operaciones binarias sobre \(L\)
adhocprefix-adhocsufix \(\leq\) es una relación binaria sobre \(L\)
adhocprefix-adhocsufix \((L,\mathsf{s},\mathsf{i},\leq)\) satisface los axiomas \(\mathrm{A}_{\leq R}\), \(\mathrm{A}_{\leq A}\), \(\mathrm{A}_{\leq T}\), \(\mathrm{A}_{\mathsf{s}esC}\), \(\mathrm{A}_{\mathsf{s}\leq C}\), \(\mathrm{A}_{\mathsf{i}esC}\) , \(\mathrm{A}_{\mathsf{i}\geq C}\)
(O sea esta es la única información particular de \((L,\mathsf{s},\mathsf{i},\leq)\) que podemos usar).
adhocprefix(2)adhocsufix Las deducciones de 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 reticulados cuaterna.
Llamaremos a las pruebas que tengan estas características, pruebas elementales de reticulados cuaterna. Veamos una prueba de \(\rho\) con estas características. Recordemos que en la prueba partiremos de una estructura \((L,\mathsf{s},\mathsf{i},\leq)\) fija de la cual solo sabemos que satisface los axiomas \(\mathrm{A}_{\leq R}\), \(\mathrm{A}_{\leq A}\), \(\mathrm{A}_{\leq T}\), \(\mathrm{A}_{\mathsf{s}esC}\), \(\mathrm{A}_{\mathsf{s}\leq C}\), \(\mathrm{A}_{\mathsf{i}esC}\) , \(\mathrm{A}_{\mathsf{i}\geq C}\).
Proof. Sean \(a,b\in L\) elementos fijos pero arbitrarios. Por el axioma \(\mathrm{A}_{\mathsf{s}esC}\) (instanciado haciendo \(x=b\) y \(y=a\)) tenemos que \[b\leq b\;\mathsf{s}\;a\wedge a\leq b\;\mathsf{s}\;a\] De lo cual sacamos obviamente que \[a\leq b\;\mathsf{s}\;a\wedge b\leq b\;\mathsf{s}\;a\] Además el axioma \(\mathrm{A}_{\mathsf{s}\leq C}\) (instanciado haciendo \(x=a\), \(y=b\) y \(z=b\;\mathsf{s}\;a\)) nos dice que \[\left((a\leq b\;\mathsf{s}\;a\wedge b\leq b\;\mathsf{s}\;a)\rightarrow a\;\mathsf{s}\;b\leq b\;\mathsf{s}\;a\right)\] O sea que de las últimas dos sentencias obtenemos trivialmente que \[a\;\mathsf{s}\;b\leq b\;\mathsf{s}\;a\] En forma análoga se puede probar que \[b\;\mathsf{s}\;a\leq a\;\mathsf{s}\;b\] Lo cual nos dice trivialmente que \[a\;\mathsf{s}\;b\leq b\;\mathsf{s}\;a\wedge b\;\mathsf{s}\;a\leq a\;\mathsf{s}\;b\] Pero el axioma \(\mathrm{A}_{\leq A}\) nos dice que \[(a\;\mathsf{s}\;b\leq b\;\mathsf{s}\;a\wedge b\;\mathsf{s}\;a\leq a\;\mathsf{s}\;b)\rightarrow a\;\mathsf{s}\;b=b\;\mathsf{s}\;a\] De lo cual obviamente obtenemos que \[a\;\mathsf{s}\;b=b\;\mathsf{s}\;a\] Ya que \(a,b\) eran elementos fijos pero arbitrarios, hemos probado que \[\forall x\forall y(x\;\mathsf{s}\;y=y\;\mathsf{s}\;x)\]
Por supuesto, en la parte de la prueba en la que decimos "En forma análoga se puede probar que \(b\;\mathsf{s}\;a\leq a\;\mathsf{s\;}\)\(b\)" deberíamos poner las lineas que corresponden para obtener realmente la prueba elemental (si no lo hacemos la prueba no es una prueba elemental ya que la justificación “en forma análoga se puede probar ...” no es lo suficientemente simple y obvia).
Muchas de las pruebas dadas en la Sección de Reticulados Par pueden adaptarse naturalmente para ser pruebas elementales de reticulados cuaterna. Para hacer esta adaptación nótese que el axioma \(\mathrm{A}_{\leq A}\) puede ser usado en lugar de aplicar la regla Igualdad en Posets (así lo hicimos en la prueba de recién) y similarmente los axiomas \(\mathrm{A}_{\mathsf{s}\leq C}\) y \(\mathrm{A}_{\mathsf{i}\geq C}\) se pueden usar en lugar de las reglas Superar un Supremo y Ser \(\leq\) que un Ínfimo.
Ahora daremos una prueba elemental de la sentencia elemental pura \(\mu=\forall x\forall y(x\leq y\leftrightarrow x\;\mathsf{s}\;y=y)\). Obviamente sabemos que \(\mu\) es verdadera en cada reticulado cuaterna pero queremos una prueba elemental. Recordemos que en la prueba partiremos de una estructura \((L,\mathsf{s},\mathsf{i},\leq)\) fija de la cual solo sabemos que satisface los axiomas \(\mathrm{A}_{\leq R}\), \(\mathrm{A}_{\leq A}\), \(\mathrm{A}_{\leq T}\), \(\mathrm{A}_{\mathsf{s}esC}\), \(\mathrm{A}_{\mathsf{s}\leq C}\), \(\mathrm{A}_{\mathsf{i}esC}\) , \(\mathrm{A}_{\mathsf{i}\geq C}\) .
Proof. Sean \(a,b\in L\) elementos fijos. Supongamos que \(a\leq b\). Probaremos que \(a\;\mathsf{s}\;b=b\). Por el axioma \(\mathrm{A}_{\mathsf{s}\leq C}\) tenemos que \[\left((a\leq b\wedge b\leq b)\rightarrow a\;\mathsf{s}\;b\leq b\right)\] Pero por el axioma \(\mathrm{A}_{\leq R}\) tenemos que \(b\leq b\) y por hipótesis tenemos que \(a\leq b\) por lo cual \[a\leq b\wedge b\leq b\] Obviamente esto nos dice que \(a\;\mathsf{s\;}\)\(b\leq b\). Además por el axioma \(\mathrm{A}_{\mathsf{s}esC}\) tenemos que \[b\leq a\;\mathsf{s}\;b\] O sea que hemos probado \[a\;\mathsf{s\;}b\leq b\wedge b\leq a\;\mathsf{s\;}b\] Lo cual por el axioma \(\mathrm{A}_{\leq A}\) nos dice que \(a\;\mathsf{s}\;b=b\). Ya que habíamos asumido que \(a\leq b\) en realidad hemos probado que \[a\leq b\rightarrow a\;\mathsf{s}\;b=b\] Supongamos ahora que \(a\;\mathsf{s}\;b=b\). Por el axioma \(\mathrm{A}_{\mathsf{s}esC}\) tenemos que \(a\leq a\;\mathsf{s}\;b\). Ya que \(a\;\mathsf{s}\;b=b\) obtenemos que \(a\leq b\). O sea que realmente hemos probado que \[a\;\mathsf{s}\;b=b\rightarrow a\leq b\] Lo cual por la otra implicación probada nos dice que \[a\leq b\leftrightarrow a\;\mathsf{s}\;b=b\] Ya que \(a,b\) eran elementos fijos pero arbitrarios, hemos probado que \[\forall x\forall y(x\leq y\leftrightarrow x\;\mathsf{s}\;y=y)\]
Consejos Importantes: Por favor contengan a su escarabajo interior...
Cuando queramos hacer una prueba elemental de alguna sentencia elemental pura es importante no perder nuestro rol de matemáticos y creer que porque debemos realizar la prueba escribiendo las cosas con sentencias elementales debemos dejar de pensar como matemáticos y volvernos escarabajos sintácticos mecánicos que solo usan reglas y van encadenando sentencias elementales sin pensar e imaginar. Es decir, debemos hacer la prueba a lo mariposa pensando, imaginando. Tal como lo venimos haciendo en las guías anteriores pero agregando la consigna de que a la matemática involucrada la escribamos usando sentencias elementales.
Una buena manera de hacer una prueba elemental de una sentencia elemental pura \(\varphi\) es primero hacer la prueba matemática sin fijarse demasiado si es elemental o no. Es decir partir de la suposición de que tenemos un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) fijo (pero arbitrario) e intentar (como matemáticos) probar que entonces en \((L,\mathsf{s},\mathsf{i},\leq)\) se cumple \(\varphi\). Una ves que hayamos hecho nuestra prueba como matemáticos, intentar tunearla para que se vuelva una prueba elemental.
Es decir debemos ser el mismo matemático de siempre solo que haciendo pruebas de un estilo muy particular.