El concepto de reticulado puede ser abordado en dos formas distintas, una geométrica, vía posets, la cual daremos ahora y la otra algebraica, vía estructuras algebraicas definidas ecuacionalmente, la cual daremos en la sección 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 ínfimo 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 ínfimo y supremo del conjunto \(\{A,B\}\) en \((\mathcal{P}(\omega),\leq)\)
Recordemos que dado un conjunto \(A\), por una operación binaria sobre \(A\) entenderemos una función 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 continuación 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 matemático maduro, la cual será crucial a la hora de hacer lógica ya que la lógica estudia (modeliza) matemáticamente el funcionar de un matemático y será muy práctico que cada uno cuente con un matemático 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 definición de \(\mathsf{s}\) tenemos que \(a\) \(\mathsf{s}\) \(b=\sup(\{a,b\})\). O sea que por definición 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 definición 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\}\). Además es claro que si \(z\) es cota superior de \(\{a\}\), entonces \(z\geq a\). O sea que por definición 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 absorción (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 definición 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 básicas de los reticulados par daremos tres reglas que serán de suma utilidad para encontrar pruebas. Dejamos al lector justificar matemáticamente 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:
Probar que \(x\leq y\)
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:
Probar que \(z\geq x\)
Probar que \(z\geq y\)
Regla Ser Menor o Igual que un Ínfimo: 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:
Probar que \(z\leq x\)
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 también 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 nótese 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 análoga 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 (Monotonía). 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\) nótese que \(a\leq c\) (por hipótesis) 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 fácilmente 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. ínfimos) da supremos (resp. ínfimos), es decir:
5.8. Sea \((L,\leq)\) un reticulado par y sean \(x_{1},...,x_{n}\in L\), con \(n\geq2\). 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}\]
Proof. Haremos sólo el caso del supremo. Lo probaremos usando la Regla de Inducción desde 2. Para cada \(n\geq2\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:
adhocprefix\(\mathrm{Enu}_{n}\):adhocsufix Sea \((L,\leq)\) un reticulado par y sean \(x_{1},...,x_{n}\in L\). Se tiene que \[\begin{aligned} (...(x_{1}\;\mathsf{s\;}x_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}x_{n} & =\sup(\{x_{1},...,x_{n}\}) \end{aligned}\]
Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(2\).
Prueba de que \(\mathrm{Enu}_{2}\) es verdadero. Por definición de la operación \(\mathsf{s}\).
Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\). Sea \((L,\leq)\) un reticulado par y sean \(a_{1},...,a_{n+1}\in L\), fijos. Ya que \(\mathrm{Enu}_{k}\) es verdadero 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 fácil 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 también 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 \(\mathrm{Enu}_{n+1}\).
Dado que la distribución de paréntesis en una expresión 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 paréntesis.
Una regla que hemos usado constantemente es la siguiente:
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:
Probar que \(x\) es cota superior de \(S\)
Probar que si \(z\) es una cota superior de \(S\), entonces \(x\leq z\)
Concluimos la sección con una regla que es una de las mas usadas por los matemáticos:
Regla del Director de Cine Generoso: Si Ud esta en el medio de una prueba y puede introducir un nuevo actor, hágalo!
Obviamente esta regla necesita explicación. La cosa es así, muchas veces en el desarrollo de una demostración probamos que existe al menos un objeto con cierta propiedad \(P.\) Por supuesto que en general puede haber varios objetos con dicha propiedad \(P.\) Entonces la Regla del Director de Cine Generoso nos dice que introduzcamos un nuevo objeto en nuestro discurso diciendo “sea \(a\) un elemento fijo tal que cumple \(P\)”. Este nuevo actor \(a\) muchas veces nos ayuda a seguir con la demostración. Cabe destacar que la Regla Pertenecer a la Imagen dada al final de la sección anterior es un caso particular de la Regla del Director de Cine Generoso (por que?). A medida que vayamos haciendo mas pruebas y vayamos madurando como matemáticos iremos entendiendo mas el nombre de esta regla ya que en algún sentido una demostración es una película que parte de un escenario inicial fijo y ficticio (i.e. las hipótesis) y a lo largo de la demostración van sucediendo cosas que nos conducen dentro de esa ficción a un escenario distinto al que teníamos al comienzo (i.e. la conclusión de la demostración). Obviamente el matemático que realiza la demostración es el director de esta “película” ya que es quien decide que cosas van sucediendo a lo largo de la prueba. Por ejemplo en la prueba del Lema 5.7 el escenario inicial es un reticulado par \((L,\leq)\) el cual obviamente es ficticio (i.e. no es uno concreto) aunque lo pensamos como un objeto fijo, concreto (tal como cuando comenzamos a ver una película). Luego se introducen en la escena tres elementos \(a,b,c\) de \(L\) (actores nuevos en la película) y sigue la trama hasta obtener la conclusión de que \((L,\leq)\) cumple que \((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\) (este es el escenario final de esta corta película).
Las seis reglas consideradas están muy vinculadas al concepto de inteligencia artificial ya que si quisiéramos hacer un probador automático del tipo de teoremas hechos en esta sección, claramente estas reglas le darían una alternativa de búsqueda que podría (y de hecho en muchos casos lo hace) dar el camino adecuado para obtener la prueba de un enunciado dado.