El concepto de reticulado puede ser abordado en dos formas distintas, una geometrica, via posets, la cual daremos ahora y la otra algebraica, via estructuras algebraicas definidas ecuacionalmente, la cual daremos en la seccion siguiente. Como veremos mas adelante ambas definiciones son equivalentes.
Por un reticulado par entenderemos un poset \((P,\leq)\) el cual cumple que para todo \(a,b\in P\), existen (en \((P,\leq)\)) \(\sup(\{a,b\})\) e \(\inf(\{a,b\})\). Algunos ejemplos:
adhocprefix(E1)adhocsufix El poset \((\mathbf{N},D)\) es un reticulado par (\(D=\{(x,y)\in\mathbf{N}^{2}:x|y\}\)) ya que dados \(x,y\in\mathbf{N}\), hemos visto que \(mcd(x,y)\) y \(mcm(x,y)\) son infimo y supremo del conjunto \(\{x,y\}\) en \((\mathbf{N},D)\)
adhocprefix(E2)adhocsufix El poset \((\mathcal{P}(\omega),\leq)\) es un reticulado par (\(\mathrm{\leq}=\{(A,B)\in\mathcal{P}(\omega)^{2}:A\subseteq B\}\)) ya que dados \(A,B\in\mathcal{P}(\omega)\), hemos visto que \(A\cap B\) y \(A\cup B\) son infimo y supremo del conjunto \(\{A,B\}\) en \((\mathcal{P}(\omega),\leq)\)
Recordemos que dado un conjunto \(A\), por una operacion binaria sobre \(A\) entenderemos una funcion cuyo dominio es \(A^{2}\) y cuya imagen esta contenida en \(A\). En un reticulado par \((P,\leq)\) tenemos dos operaciones binarias naturalmente definidas: \[\begin{array}{rcl} \mathsf{s}:P^{2} & \rightarrow & P\\ (a,b) & \rightarrow & \sup(\{a,b\}) \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rcl} \mathsf{i}:P^{2} & \rightarrow & P\\ (a,b) & \rightarrow & \inf(\{a,b\}) \end{array}\] Escribiremos \(a\mathsf{\;s\;}b\) en lugar de \(\mathsf{s}(a,b)\) y \(a\mathsf{\;i\;}b\) en lugar de \(\mathsf{i}(a,b)\).
A continuacion nos dedicaremos a probar varias propiedades agradables que se cumplen en un reticulado par. Recomendamos al lector que en algunos casos practique encontrando pruebas perfectas. Esto lo entrenara en su capacidad de ser un matematico maduro, la cual sera crucial a la hora de hacer logica ya que la logica estudia (modeliza) matematicamente el funcionar de un matematico y sera muy practico que cada uno cuente con un matematico maduro en su propia mente.
5.2. Dado un reticulado par \((L,\leq)\) se cumplen las siguientes.
adhocprefix(1)adhocsufix \(x\leq x\) \(\mathsf{s}\) \(y\), cualesquiera sean \(x,y\in L\)
adhocprefix(2)adhocsufix \(x\;\mathsf{i\;}y\leq x\), cualesquiera sean \(x,y\in L\)
adhocprefix(3)adhocsufix \(x\;\mathsf{s}\;x=x\), cualesquiera sean \(x\in L\)
adhocprefix(4)adhocsufix \(x\mathsf{\;i\;}x=x\), cualesquiera sean \(x\in L\)
adhocprefix(5)adhocsufix \(x\;\mathsf{s}\;y=y\;\mathsf{s}\;x\), cualesquiera sean \(x,y\in L\)
adhocprefix(6)adhocsufix \(x\mathsf{\;i\;}y=y\mathsf{\;i\;}x\), cualesquiera sean \(x,y\in L\)
Proof. Prueba perfecta de (1). Sean \(a,b\in L\), fijos. Por definicion de \(\mathsf{s}\) tenemos que \(a\) \(\mathsf{s}\) \(b=\sup(\{a,b\})\). O sea que por definicion de supremo de un conjunto tenemos que \(a\) \(\mathsf{s}\) \(b\) es cota superior del conjunto \(\{a,b\}\) en \((L\leq)\). O sea que \(a\leq a\) \(\mathsf{s}\) \(b\). Ya que \(a,b\) eran arbitrarios, hemos probado que vale (1).
Prueba perfecta de (3). Sea \(a\in L\), fijo. Por definicion de \(\mathsf{s}\) tenemos que \(a\) \(\mathsf{s}\) \(a=\sup(\{a,a\})=\sup(\{a\})\). O sea que debemos probar que \(a=\sup(\{a\})\). Es claro que \(a\) es cota superior de \(\{a\}\). Ademas es claro que si \(z\) es cota superior de \(\{a\}\), entonces \(z\geq a\). O sea que por definicion de supremo de un conjunto tenemos que \(a=\sup(\{a\})\). O sea que hemos probado que \(a\mathsf{\;s\;}a=a\). Ya que \(a\) era arbitrario, hemos probado que vale (3).
Dejamos al lector completar la prueba.
5.3. Dado un reticulado par \((L,\leq)\) se tiene que:
adhocprefix(1)adhocsufix \(x\leq y\) si y solo si \(x\;\mathsf{s}\;y=y\), cualesquiera sean \(x,y\in L\)
adhocprefix(2)adhocsufix \(x\leq y\) si y solo si \(x\;\mathsf{i}\;y=x\), cualesquiera sean \(x,y\in L\)
Proof. Ejercicio
Las siguientes dos propiedades son conocidas como leyes de absorcion (por que?)
5.4. Dado un reticulado par \((L,\leq)\), se tiene que:
adhocprefix(1)adhocsufix \(x\;\mathsf{s}\;(x\mathsf{\;i\;}y)=x\), cualesquiera sean \(x,y\in L\)
adhocprefix(2)adhocsufix \(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x\), cualesquiera sean \(x,y\in L\)
Proof. (1). Sean \(a,b\in L\), fijos. Por definicion de \(\mathsf{i}\) debemos probar que \(\sup(\{a,a\mathsf{\;i\;}b\})=a\). O sea debemos probar que \(a\) es la menor cota superior de \(\{a,a\mathsf{\;i\;}b\}\). Por un lema anterior tenemos que \(a\mathsf{\;i\;}b\leq a\) y obviamente se da \(a\leq a\), lo cual nos dice que \(a\) es cota superior de \(\{a,a\mathsf{\;i\;}b\}\). Es claro que es menor o igual que cualquier otra cota superior. O sea que hemos probado que \(a\;\mathsf{s}\;(a\mathsf{\;i\;}b)=a\), lo cual ya que \(a,b\) eran elementos arbitrarios nos dice que vale (1).
(2) es dejada al lector.
Antes de seguir dando propiedades basicas de los reticulados par daremos tres reglas que seran de suma utilidad para encontrar pruebas. Dejamos al lector justificar matematicamente la validez de dichas reglas.
Regla Igualdad en Posets
Si ud esta intentando probar que en un poset \((P,\leq)\) dos elementos \(x,y\) son iguales, desdoble su tarea en las dos tareas siguientes:
adhocprefix-adhocsufix Probar que \(x\leq y\)
adhocprefix-adhocsufix Probar que \(y\leq x\)
Regla Superar un Supremo
Si ud esta intentando probar que en un reticulado par \((L,\leq)\) se da que \(z\geq x\;\mathsf{s}\;y\), desdoble su tarea en las dos tareas siguientes:
adhocprefix-adhocsufix Probar que \(z\geq x\)
adhocprefix-adhocsufix Probar que \(z\geq y\)
Regla Ser Menor o Igual que un Infimo
Si ud esta intentando probar que en un reticulado par \((L,\leq)\) se da que \(z\leq x\;\mathsf{i}\;y\), desdoble su tarea en las dos tareas siguientes:
adhocprefix-adhocsufix Probar que \(z\leq x\)
adhocprefix-adhocsufix Probar que \(z\leq y\)
Ambas operaciones \(\mathsf{s}\) e \(\mathsf{i}\) son asociativas, es decir:
5.5. Dado un reticulado par \((L,\leq)\), se tiene que:
adhocprefix(1)adhocsufix \((x\;\mathsf{s}\;y)\;\mathsf{s}\;z=x\;\mathsf{s}\;(y\;\mathsf{s}\;z)\), cualesquiera sean \(x,y,z\in L\)
adhocprefix(2)adhocsufix \((x\mathsf{\;i\;}y)\mathsf{\;i\;}z=x\mathsf{\;i\;}(y\mathsf{\;i\;}z)\), cualesquiera sean \(x,y,z\in L\)
Proof. (1) Sean \(a,b,c\in L\), fijos. Usaremos la regla Igualdad en Posets. Primero probaremos \((a\;\mathsf{s}\;b)\;\mathsf{s}\;c\leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\). Para esto usaremos la regla Superar un Supremo. Es decir que debemos probar que \[\begin{aligned} (a\;\mathsf{s}\;b) & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\\ c & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c) \end{aligned}\] Para la primer desigualdad usaremos tambien la regla Superar un Supremo, por lo cual deberemos probar \[\begin{aligned} a & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\\ b & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c) \end{aligned}\] O sea que en suma debemos probar las siguientes desigualdades \[\begin{aligned} a & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\\ b & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\\ c & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c) \end{aligned}\] La primera es directa de un lema anterior, y para la segunda notese que el mismo lema nos dice que \[b\leq(b\;\mathsf{s}\;c)\text{ y }(b\;\mathsf{s}\;c)\leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\] por lo cual solo resta usar que \(\leq\) es transitiva. La tercera es completamente analoga a la segunda.
En forma similar se prueba que \(a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\leq(a\;\mathsf{s}\;b)\;\mathsf{s}\;c\). Es decir que por la regla Igualdad en Posets tenemos que \(a\;\mathsf{s}\;(b\;\mathsf{s}\;c)=(a\;\mathsf{s}\;b)\;\mathsf{s}\;c\). Ya que \(a,b,c\) eran elementos arbitrarios hemos probado que vale (1).
(2) es dejada como ejercicio.
El siguiente lema prueba que en un reticulado par las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) preservan el orden.
5.6. Dado un reticulado par \((L,\leq)\), se tiene que:
adhocprefix(1)adhocsufix \(x\leq z\) e \(y\leq w\) implica \(x\;\mathsf{s}\ y\leq z\;\mathsf{s}\ w\), cualesquiera sean \(x,y,z,w\in L\)
adhocprefix(2)adhocsufix \(x\leq z\) e \(y\leq w\) implica \(x\mathsf{\;i\;}y\leq z\mathsf{\;i\;}w\), cualesquiera sean \(x,y,z,w\in L\)
Proof. (1) Sean \(a,b,c,d\in L\), elementos fijos. Supongamos que \(a\leq c\) e \(b\leq d\). Probaremos que entonces \(a\;\mathsf{s}\ b\leq c\;\mathsf{s}\ d\). Por la regla Superar un Supremo basta con probar que \[\begin{aligned} a & \leq c\;\mathsf{s}\;d\\ b & \leq c\;\mathsf{s}\;d \end{aligned}\] Para ver que \(a\leq c\;\mathsf{s}\;d\) notese que \(a\leq c\) (por hipotesis) y \(c\leq c\;\mathsf{s}\;d\), por lo cual podemos usar que \(\leq\) es transitiva. La desigualdad \(b\leq c\;\mathsf{s}\;d\) se prueba en forma similar. O sea que hemos probado que \[a\leq c\text{ y }b\leq d\text{ implica }a\;\mathsf{s}\ b\leq c\;\mathsf{s}\ d\] Ya que \(a,b,c,d\) eran elementos arbitrarios hemos probado que vale (1).
(2) es dejada al lector
5.7. Dado un reticulado par \((L,\leq)\), se tiene que:
adhocprefix-adhocsufix \((x\mathsf{\;i\;}y)\;\mathsf{s}\;(x\mathsf{\;i\;}z)\leq x\mathsf{\;i\;}(y\;\mathsf{s}\;z)\), cualesquiera sean \(x,y,z\in L\)
Proof. Sean \(a,b,c\in L\), elementos fijos. Por la regla Superar un Supremo, basta con probar que \[\begin{aligned} a\mathsf{\;i\;}b & \leq a\mathsf{\;i\;}(b\;\mathsf{s}\;c)\\ a\mathsf{\;i\;}c & \leq a\mathsf{\;i\;}(b\;\mathsf{s}\;c) \end{aligned}\] Pero estas dos desigualdades pueden ser facilmente probadas aplicando (2) del lema anterior. O sea que \((a\mathsf{\;i\;}b)\;\mathsf{s}\;(a\mathsf{\;i\;}c)\leq a\mathsf{\;i\;}(b\;\mathsf{s}\;c)\), de lo cual se deduce nuestro lema ya que \(a,b,c\) eran elementos arbitrarios.
Iterar supremos (resp. infimos) da supremos (resp. infimos), es decir:
5.8. Sea \((L,\leq)\) un reticulado par. Se tiene que \[\begin{aligned} (...(x_{1}\;\mathsf{s\;}x_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}x_{n} & =\sup(\{x_{1},...,x_{n}\})\\ (...(x_{1}\mathsf{\;i\;}x_{2})\mathsf{\;i\;}...)\mathsf{\;i\;}x_{n} & =\inf(\{x_{1},...,x_{n}\}) \end{aligned}\] cualesquiera sean los elementos \(x_{1},...,x_{n}\in L\), con \(n\geq2\).
Proof. Por induccion en \(n\). Claramente el resultado vale para \(n=2\). Supongamos vale para \(n\) y veamos entonces que vale para \(n+1\). Sean \(a_{1},...,a_{n+1}\in L\), fijos. Por hipotesis inductiva tenemos que
adhocprefix(1)adhocsufix \((...(a_{1}\;\mathsf{s}\;a_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}a_{n}=\sup(\{a_{1},...,a_{n}\})\)
Veamos entonces que
adhocprefix(2)adhocsufix \(((...(a_{1}\;\mathsf{s\;}a_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}a_{n})\;\mathsf{s\;}a_{n+1}=\sup(\{a_{1},...,a_{n+1}\})\)
Usando (1), es facil ver que \(((...(a_{1}\;\mathsf{s\;}a_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}a_{n})\;\mathsf{s\;}a_{n+1}\) es cota superior de \(\{a_{1},...,a_{n+1}\}\). Supongamos que \(z\) es otra cota superior. Ya que \(z\) es tambien cota superior del conjunto \(\{a_{1},...,a_{n}\}\), por (1) tenemos que \[(...(a_{1}\;\mathsf{s\;}a_{2})\;\mathsf{s}\;...)\;\mathsf{s\;}a_{n}\leq z\] Pero entonces ya que \(a_{n+1}\leq z\), tenemos que \[((...(a_{1}\;\mathsf{s\;}a_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}a_{n})\;\mathsf{s\;}a_{n+1}\leq z\] con lo cual hemos probado (2). Ya que \(a_{1},...,a_{n+1}\in L\) eran elementos arbitrarios, hemos probado que vale el enunciado del lema para \(n+1\).
Dado que la distribucion de parentesis en una expresion de la forma \[(...(x_{1}\;\mathsf{s\;}x_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}x_{n}\] es irrelevante (ya que\(\;\mathsf{s\;}\)es asociativa), en general suprimiremos los parentesis.
Concluimos esta subseccion enunciando una regla que hemos usado constantemente:
Regla Igualar un Supremo
Si ud esta intentando probar que en un poset \((P,\leq)\) se da que \(x=\sup(S)\), desdoble su tarea en las dos tareas siguientes:
adhocprefix-adhocsufix Probar que \(x\) es cota superior de \(S\)
adhocprefix-adhocsufix Probar que si \(z\) es una cota superior de \(S\), entonces \(x\leq z\)
Las cinco reglas consideradas estan muy vinculadas al concepto de inteligencia artificial ya que si quisieramos hacer un probador automatico del tipo de teoremas hechos en esta seccion, claramente estas reglas le darian una alternativa de busqueda que podria (y de hecho lo hace) dar el camino adecuado para obtener la prueba de un enunciado dado.