En esta seccion introduciremos un nuevo tipo de estructura que llamaremos reticulado cuaterna, pero nuestra intencion aqui no sera hacer teoremas similares a los hechos con las estructuras ya estudiadas. De hecho ya lo hicimos en detalle tantas veces que el lector no tendria problema si quisiera definir los conceptos de subestructura, subuniverso, homomorfismo, etc para los reticulados cuaterna. Nuestra intencion aqui sera delimitar en forma intuitiva un lenguaje muy elemental con el cual se pueden enunciar muchas propiedades matematicas de los reticulados cuaterna y tambien con el cual se pueden hacer muchas pruebas interesantes sin salirse de dicho lenguaje elemental (a las cuales llamaremos pruebas elementales). Comencemos con la definicion matematica 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 vacio, \(\mathsf{s}\) e \(\mathsf{i}\) son operaciones binarias sobre \(L\), \(\leq\) es una relacion 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. Ademas notese 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\}\). Ademas notese que (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 garaniza 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 Dedeking 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 ultimo resultado es un teorema y no la definicion 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 numeros reales
adhocprefix-adhocsufix \((\{A\subseteq\mathbf{N}:A\) es finito\(\},\cup,\cap,\subseteq)\)
adhocprefixConvencion Notacional:adhocsufix 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 maximo, 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.
En lo que sigue comensaremos a definir en forma intuitiva el lenguaje elemental de los reticulados cuaterna. Lo que debe quedar claro es que no nos interesa dar definiciones matematicas rigurosas de estos conceptos sino mas bien dejar bien desarrollada nuestra intuicion respecto de los mismos.
Son palabras que se construyen usando simbolos de la siguiente lista
adhocprefix-adhocsufix Parentesis: \((\;\;)\)
adhocprefix-adhocsufix Variables: \(x,y,z,w,...\)
adhocprefix-adhocsufix Nombres de elementos fijos: \(a,b,c,d,...\)
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 terminos elementales de reticulados cuaterna son palabras, es decir \(Ti(t)=\mathrm{PALABRA}\), cada ves que \(t\) es un termino elemental de reticulado cuaterna. Por ejemplo el termino elemental dado en el primer ejemplo arriba es una palabra de longitud 5 (los espacios no cuentan y son para hacerla mas “lejible”) 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 traera problemas para el manejo intuitivo que haremos del tema.
Las siguientes reglas constructivas nos aproximan razonablemente al concepto de termino elemental de reticulado cuaterna (aunque no sean una definicion matematica precisa).
adhocprefix-adhocsufix Cada variable es un termino elemental de reticulados cuaterna
adhocprefix-adhocsufix Cada nombre de elemento fijo es un termino elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(t\) y \(s\) son terminos elementales de reticulados cuaterna, entonces \((t\;\mathsf{s\;}s)\) es un termino elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(t\) y \(s\) son terminos elementales de reticulados cuaterna, entonces \((t\;\mathsf{i\;}s)\) es un termino elemental de reticulados cuaterna
adhocprefix-adhocsufix Una palabra es un termino elemental de reticulados cuaterna si y solo si se puede construir usando las clausulas anteriores
Deberia 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 termino 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 termino 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 \(mcm(200,300)=100\)).
adhocprefix-adhocsufix En el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\), el termino 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 termino 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 termino 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 termino elemental con el valor que asume en un reticulado cuaterna dado para alguna asignacion de valores a sus variables y nombres de elementos fijos. Por ejemplo los terminos 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 asignacion de valores que tomemos para las variables \(x\) e \(y\).
Un termino elemental de reticulados cuaterna sera llamado puro cuando en el no ocurran nombres de elementos fijos.
Las formulas elementales de reticulados cuaterna son palabras que se construyen usando simbolos 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 alla de que no daremos una definicion matematica rigurosa del concepto de formula elemental de reticulados cuaterna, es importante entender que son meras palabras, es decir \(Ti(\varphi)=\mathrm{PALABRA}\), cada ves que \(\varphi\) es una formula elemental de reticulado cuaterna. Antes de dar una descripcion 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 comun que una formula elemental tenga a terminos elementales como subpalabras aunque los terminos elementales tienen un distinto significado que las formulas elementales ya que ellos representan elementos y las formulas elementales son palabras que cuando las interpretamos adecuadamente se vuelven verdaderas o falsas. Las siguientes reglas constructivas nos aproximan razonablemente al concepto de formula elemental de reticulado cuaterna (aunque no sean una definicion matematica precisa):
adhocprefix-adhocsufix Si \(t\) y \(s\) son terminos elementales de reticulados cuaterna, entonces la palabra \((t=s)\) es una formula elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(t\) y \(s\) son terminos elementales de reticulados cuaterna, entonces la palabra \((t\leq s)\) es una formula elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales de reticulados cuaterna, entonces \((\varphi_{1}\wedge\varphi_{2})\) es una formula elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales de reticulados cuaterna, entonces \((\varphi_{1}\vee\varphi_{2})\) es una formula elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales de reticulados cuaterna, entonces \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una formula elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales de reticulados cuaterna, entonces \((\varphi_{1}\rightarrow\varphi_{2})\) es una formula elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(\varphi\) es una formula elemental de reticulados cuaterna, entonces \(\lnot\varphi\) es una formula elemental de reticulados cuaterna
adhocprefix-adhocsufix Si \(\varphi\) es una formula elemental de reticulados cuaterna, entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son formulas elementales de reticulados cuaterna
adhocprefix-adhocsufix Si \(\varphi\) es una formula elemental de reticulados cuaterna, entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son formulas elementales de reticulados cuaterna
adhocprefix-adhocsufix Una palabra es una formula elemental de reticulados cuaterna si y solo si se puede construir usando las clausulas anteriores
Deberia 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\). Notese que siempre "cuantificamos por delante", es decir que la palabra \((x\leq a)\forall x\) NO es una formula 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 formula elemental.
adhocprefixObservacion importante:adhocsufix Notese que segun los items (7), (8) y (9) de la definicion de formula cuando “negamos” y cuando “cuantificamos”, no agregamos parentesis. Solo agregamos parentesis cuando “nexamos” un par de formulas. Esto hay que tenerlo en cuenta para leer las formulas. Por ejemplo la formula \((\exists z(a\leq z)\wedge(b\leq z))\) debe leerse como la conjuncion de las formulas \(\exists z(a\leq z)\) y \((b\leq z)\) y no pensarse como una formula que dice “\(\exists z\text{ tal que }(a\leq z)\wedge(b\leq z)\)”. Sucede algo similar con la negacion. Es decir si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales entonces la formula elemental \((\lnot\varphi_{1}\wedge\varphi_{2})\) debe leerse como la conjuncion de \(\lnot\varphi_{1}\) y \(\varphi_{2}\) y no pensarse como una formula que dice “no es verdad que \(\varphi_{1}\wedge\varphi_{2}\)”. O sea, los cuantificadores y la negacion tienen precedencia sobre los nexos logicos.
Una formula elemental de reticulados cuaterna sera llamada pura cuando en ella no ocurran nombres de elementos fijos. Notese que en particular los terminos que ocurran en una formula elemental pura seran tambien puros.
Para que una formula elemental se vuelva verdadera o falsa tenemos que tener un reticulado cuaterna concreto \((L,\mathsf{s},\mathsf{i},\leq)\) y ademas asignar valores concretos de \(L\) a las variables libres y a los nombres de elementos fijos que ocurren en dicha formula. Tambien 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 formula 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 relacion \(|\) y \(6\text{ divide a }36\)
adhocprefix-adhocsufix La formula elemental \(((a\;\mathsf{s\;}y=y)\vee(y\;\mathsf{s\;}a=a))\) tiene a \(y\) como su unica 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 formula es verdadera en el reticulado cuaterna \((\mathbf{N},max,min,\leq)\) para cualquier asignacion de valores a \(a\) y a \(y\).
adhocprefix-adhocsufix La formula elemental \(\exists y((y\leq x)\wedge\lnot(y=x))\) tiene a \(x\) como su unica 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 formula 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 formula elemental es pura, su valor de verdad en un reticulado cuaterna dado solo depende de que valores asignemos a sus variables libres. Tambien es bueno pensar que
adhocprefix-adhocsufix La formula elemental \(\forall y(x\leq y)\) "dice" \(x\) es un elemento minimo de \((L,\mathsf{s},\mathsf{i},\leq)\), en el sentido que ella sera verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si le asignamos a \(x\) un elemento minimo de \((L,\mathsf{s},\mathsf{i},\leq)\).
adhocprefix-adhocsufix La formula elemental \(\forall y(y\leq b)\) "dice" \(b\) es un elemento maximo de \((L,\mathsf{s},\mathsf{i},\leq)\), en el sentido que ella sera verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si le asignamos a \(b\) un elemento maximo de \((L,\mathsf{s},\mathsf{i},\leq)\).
adhocprefix-adhocsufix La formula elemental \(((x\leq y)\wedge\lnot(y=x))\) "dice" \(x\) es menor que \(y\) en \((L,\mathsf{s},\mathsf{i},\leq)\)
adhocprefix-adhocsufix La formula 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 formula elemental de reticulados cuaterna no tiene variables libres diremos que es una sentencia elemental de reticulados cuaterna. Algunos ejemplos de sentencias:
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))\)
Notese que en tal caso sera 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 \((\{A\subseteq\mathbf{N}:A\text{ es finito}\},\cup,\cap,\subseteq)\) cuando le asignamos a \(a\) el valor \(\emptyset\)
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 deberiamos notar que si una variable ocurre varias veces en una formula, entonces algunas de aquellas ocurrencias seran libres y otras no. Por ejemplo
adhocprefix-adhocsufix En la formula \(((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 formula es ya sea libre o acotada. Por ejemplo, en la formula \[(((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 formula elemental \(\varphi\) nos estaremos refiriendo a que la variable \(x\) ocurre al menos una ves libremente en \(\varphi\), aunque tambien puede ocurrir acotadamente en \(\varphi\). Por ejemplo:
adhocprefix-adhocsufix \(x\) es una variable libre de la formula \(((x\leq a)\wedge\forall x(b\leq x))\) (aunque ocurre acotadamente)
adhocprefix-adhocsufix Las variables libres de la formula \[(((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 sera una palabra formada por alguno de los simbolos \[\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 formulas elementales es que siempre que un cuantificador ocurra en una formula elemental, seguido a dicha ocurrencia ocurrira una formula elemental (la cual ademas es unica). Ejemplos:
adhocprefix-adhocsufix En la formula \[(((x\leq y)\wedge\forall y\lnot(y=a))\rightarrow\forall y(z\leq y))\] seguido a la segunda ocurrencia del cuantificador \(\forall y\) ocurre la formula \((z\leq y)\) y seguido a la primer ocurrencia del cuantificador \(\forall y\) ocurre la formula \(\lnot(y=a)\).
adhocprefix-adhocsufix En la formula \[\forall x\forall y((x\leq y)\vee(y\leq x))\] seguido a la unica ocurrencia del cuantificador \(\forall y\) ocurre la formula \(((x\leq y)\vee(y\leq x))\) y seguido a la unica ocurrencia del cuantificador \(\forall x\) ocurre la formula \(\forall y((x\leq y)\vee(y\leq x))\)
Llamaremos a esta formula elemental unica 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 formula \[((((x\leq y)\wedge\forall y\underline{\lnot(y=a)})\rightarrow\forall y(z\leq y))\vee(x\leq z))\] hemos subrayado el alcance de la primer ocurrencia del cuantificador \(\forall y\).
adhocprefix-adhocsufix En la formula \[\forall x\underline{\forall y((x\leq y)\vee(y\leq x))}\] hemos subrayado el alcance de la unica ocurrencia del cuantificador \(\forall x\).
adhocprefix-adhocsufix En la formula \[(((x\leq z)\vee\exists x\underline{\forall y((a\leq x)\wedge(y\leq x))})\rightarrow\exists x(x\leq y))\] hemos subrayado el alcance de la primer ocurrencia del cuantificador \(\exists x\).
Es importante notar que no tiene sentido hablar del alcance de un cuantificador en una formula ya que el mismo cuantificador puede ocurrir varias veces en dicha formula 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 formula \[((((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 \(\forall y(z\leq y)\)
Notese que una ocurrencia de una variable \(v\) en una formula elemental \(\varphi\) sera acotada si y solo si ella sucede dentro de una ocurrencia en \(\varphi\) de una formula de la forma \(Qv\psi\), con \(Q\in\{\forall,\exists\}\) y \(\psi\) una formula elemental.
Ademas deberia quedar claro que el roll jugado por una variable \(v\) en sus ocurrencias acotadas dentro de una ocurrencia en \(\varphi\) de una formula de la forma \(Qv\psi\) es "mudo" o "impersonal" en el sentido que podriamos reemplazar dichas ocurrencias de \(v\) por una variable \(w\) que no figure en la formula \(\psi\) y el significado de la formula resultante seria el mismo que el significado de \(\varphi\). Por ejemplo la formula \[\varphi=(\lnot(x=a)\wedge\forall y((x\leq y)\wedge(x\leq y)))\] nos "dice" que \(x\) es distinto a \(a\) y que \(x\) es comparable con todo otro elemento; y si reemplazamos cada ocurrencia de \(y\) en el bloque \(\forall y((x\leq y)\wedge(x\leq y))\) por la variable \(z\), obtenemos \[(\lnot(x=a)\wedge\forall z((x\leq z)\wedge(x\leq z)))\] la cual claramente dice lo mismo acerca de \(x\) y \(a\).
adhocprefixAviso importante:adhocsufix Ya tenemos una intuicion bien clara del concepto de formula elemental y en esta etapa no nos interesa ser puntillosos en la escritura por lo cual muchas veces para hacer mas dinamica la exposicion suprimiremos algunos parentesis. Por ejemplo en lugar de escribir \(((x\leq y)\wedge(y\leq z))\) escribiremos \((x\leq y\wedge y\leq z)\) o tambien por ejemplo 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)\) ya que obviamente ambas formulas tienen el mismo significado.
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 aqui el problema es que \(n\) hace referencia a algun natural que puede variar y no podemos reemplazarlo por uno concreto ya que entonces la sentencia solo valdria en los reticulados cuaterna con a lo sumo esa candidad de elementos. Es decir las formulas elementales en general no pueden expresar la existencia de una sucesion 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 algun 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.
Notese 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\;\text{\ensuremath{\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 relacion \(\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 elejidos en forma analoga.
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 justificacion de \(\rho\) usa la expresion \(\mathrm{sup}\{x,y\}\), la cual no forma parte de las formulas elementales. Nos interesa dar una prueba muy especial de \(\rho\) en el sentido que se cumplan las siguientes caracteristicas
adhocprefix(1)adhocsufix En la prueba se parte de una estructura \((L,\mathsf{s},\mathsf{i},\leq)\) fija pero arbitraria en el sentido que 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}\) (o sea esta es la unica informacion particular que podemos usar).
adhocprefix(2)adhocsufix Las deducciones de la prueba son muy simples y obvias de justificar con minimas fraces en castellano
adhocprefix(3)adhocsufix En la escritura de la prueba lo concerniente a la matematica misma se expresa usando solo sentencias elementales de reticulados cuaterna.
Llamaremos a las pruebas que tengan estas caracteristicas, pruebas elementales de reticulados cuaterna. Veamos una prueba de \(\rho\) con estas caracteristicas. 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 arbitarrios. 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\] Ademas 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\;\text{\ensuremath{\mathsf{s\;}}}b\leq b\;\mathsf{s}\;a\right)\] O sea que de las ultimas dos sentencias obtenemos trivialmente que \[a\;\text{\ensuremath{\mathsf{s\;}}}b\leq b\;\mathsf{s}\;a\] En forma analoga se puede probar que \[b\;\mathsf{s}\;a\leq a\;\text{\ensuremath{\mathsf{s\;}}}b\] Lo cual nos dice trivialmente que \[a\;\text{\ensuremath{\mathsf{s\;}}}b\leq b\;\mathsf{s}\;a\wedge b\;\mathsf{s}\;a\leq a\;\text{\ensuremath{\mathsf{s\;}}}b\] Pero el axioma \(\mathrm{A}_{\leq A}\) nos dice que \[(a\;\text{\ensuremath{\mathsf{s\;}}}b\leq b\;\mathsf{s}\;a\wedge b\;\mathsf{s}\;a\leq a\;\text{\ensuremath{\mathsf{s\;}}}b)\rightarrow a\;\text{\ensuremath{\mathsf{s\;}}}b=b\;\mathsf{s}\;a\] De lo cual obviamente obtenemos que \[a\;\text{\ensuremath{\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 analoga se puede probar que \(b\;\mathsf{s}\;a\leq a\;\mathsf{s\;}\)\(b\)" deberiamos 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 justificacion “en forma analoga se puede probar ...” no es lo suficientemente simple y obvia).
Muchas de las pruebas dadas en la seccion de reticulados par pueden adaptarse naturalmente para ser pruebas elementales de reticulados cuaterna. Para hacer esta adaptacion notese que el axioma \(\mathrm{A}_{\leq A}\) puede ser usado en lugar de aplicar la regla Igualdad en Posets (asi lo hicimos en la prueba de recien) 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 Menor o Igual que un Infimo.
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. [Prueba elemental de \(\mu\):] 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\;\text{\ensuremath{\mathsf{s\;}}}b\leq b\right)\] Pero por el axioma \(\mathrm{A}_{\leq R}\) tenemos que \(b\leq b\) y por hipotesis 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\). Ademas 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 habiamos 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 implicacion 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)\]
adhocprefixConsejos importantes:adhocsufix Por favor contengan a su escarabajo interior...
Cuando queramos hacer una prueba elemental de alguna sentencia elemental pura es importante no perder nuestro roll de matematicos y creer que porque debemos realizar la prueba escribiendo las cosas con sentencias elementales debemos dejar de pensar como matematicos y volvernos escarabajos sintacticos mecanicos 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 guias anteriores pero agregando la consigna de que a la matematica 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 matematica sin fijarse demaciado si es elemental o no. Es decir partir de la suposicion de que tenemos un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) fijo (pero arbitrario) e intentar (como matematicos) probar que entonces en \((L,\mathsf{s},\mathsf{i},\leq)\) se cumple \(\varphi\). Una ves que hayamos hecho nuestra prueba como matematicos, intentar tunearla para que se vuelva una prueba elemental.
Es decir debemos ser el mismo matematico de siempre solo que haciendo pruebas de un estilo muy particular.