Algebra AbstractaTeoría y Aplicaciones

SubsecciónCreando Conjuntos Parcialmente Ordenados

El Ejemplo 19.6 en el texto, es un buen ejemplo para repetirlo como demostración de comandos Sage. Primero definimos los elementos del conjunto \(X\text{.}\)

Una posibilidad para crear la relación es especificando cada instancia donde un elemento es comparable con otro. Para ello construimos una lista de pares, donde cada par contiene elementos comparables, con el menor primero. Este es el conjunto de relaciones.

Construimos el conjunto parcialmente ordenado entregándole al constructor Poset una lista con todos los elementos y las relaciones. Luego podemos obtener una visualización del conjunto parcialmente ordenado. Notemos que el método plot solo muestra las “relaciones de cobertura” — un conjunto minimal de comparaciones que por transitividad permiten recuperar todas las relaciones.

Otra posibilidad para crear un conjunto parcialmente ordenado es dejar que el constructor de conjuntos parcialmente ordenados recorra todos los pares de elementos, y lo único que le debemos entregar al constructor es una forma de comprobar si dos elementos son comparables. Nuestra función de comparación debe requerir dos elementos y devolver True o False. Una función “lambda” es una forma de construir una tal función rápidamente. Esta puede ser una idea nueva para usted, pero el dominio de las funciones lambda puede ser muy conveniente. Notemos que “lambda” es una palabra erservada precisamente para este propósito (así, por ejemplo, lambda es una elección prohibida para el valor propio de una matriz). Hay otras maneras de definir funciones en Sage, pero una función lambda es lo más rápido cuando la función es simple.

Sage ya tiene una colección de conjuntos parcialmente ordenados. Algunos se construyen directamente, mientras otros pertenecen a familias parametrizadas. Use completación con TAB en Posets. para ver la lista completa. Acá hay algunos ejemplo.

Ahora una familia parametrizada. Este es un ejemplo clásico donde los elementos son subconjuntos de un conjunto de \(n\) elementos y la relación es “subconjunto de.”

Y conjuntos parcialmente ordenados aleatorios. Estos pueden ser útiles para experimentos o comprobciones, pero es poco probable que aparezcan con propiedades especiales que pueden ser importantes. Puede intentar el siguiente comando varias veces, variando el segundo argumento que es una cota superior para la probabilidad de que dos elementos cualquiera sean comparables. Recuerde que plot solo muestra las relaciones de cobertura. Mientras más elementos comparables haya, más “estirado verticalmente” será el gráfico.

SubsecciónPropiedades de un conjunto parcialmente ordenado

Una vez que tenemos un conjunto parcialmente ordenado, ¿qué podemos hacer con él? Volvamos a nuestro primer ejemplo, D. Por supuesto podemos determinar si un elemento es menor a otro, que es la estructura fundamental de un conjunto parcialmente ordenado.

Notemos que 6 y 8 no son comparables en este conjunto parcialmente ordenado (es un orden parcial). Los métodos .is_gequal() y .is_greater_than() funcionan de forma similar, pero devuelven True si el primer eleemento es mayor (o igual).

Podemo encontrar elementos maximales o minimales de un conjunto parcialmente ordenado. Este es un conjunto parcialmente ordenado aleatorio construido con una probabilidad de 10%, pero copiado acá para ser repetible.

Los elementos de un conjunto parcialmente ordenado pueden ser particionados en conjuntos de nivel. En las gráficas de los conjuntos parcialmente ordenados, los elementos del mismo nivel se muestran a la misma altura. Cada leverl se obtiene removiendo todos los elementos de los niveles anteriores y escogiendo los elementos minimales del resultado.

Si hacemos que dos elementos de R sean comparables cuando antes no lo eran, eso constituye una extensión de R. Consideremos todas las posibles extensiones de un conjunto parcialmente ordenado — podemos construir un conjunto parcialmente ordenado a partir de tas ellas, donde la relación es la de inclusión conjuntista. Una extensión lineal es un elemento maximal en este conjunto parcialmente ordenado de conjuntos parcialmente ordenados. Informalmente, estamos agregando tantas relaciones como sea posible, de manera consistente con el conjunto parcialmente ordenado original y tal que el resultado es un orden total. En otras palabra, hay un orden de los elementos que es consistente con el orden en el conjunto parcialmente ordenado. Podemos construir una cosa así, pero la salida no es más que una lista de elementos en el orden lineal. Un informático se inclinaría por llamar a esto un “ordenamiento topológico.”

Podemos construir subposets a partir de un subconjunto de los elementos con el orden inducido para producir un conjunto parcialmente ordenado nuevo. Acá tomamos aproximadamente la “mitad inferior” del conjunto parcialmente ordenado aleatorio P induciendo el orden en ĺa unión de algunos de los conjuntos de nivel.

El dual de un conjunto parcialmente ordenado mantiene todos sus elementos e invierte sus comparaciones.

El dual del conjunto parcialmente ordenado de divisibilidad del Ejemplo 19.6 es como cambiar la relación por “es múltiplo de.”

SubsecciónReticulados

Cada reticulado es conjunto parcialmente ordenado, de manera que todos los comandos de arriba funcionan igualmente bien para un reticulado. Pero, ¿cómo se construye un reticulado? Fácil — primero creamos un conjunto parcialmente ordenado y luego lo pasamos al constructor LatticePoset(). Pero nos daremos cuenta que simplemente por darle un conjunto parcialmente ordenado a este constructor, no significa que lo que salga sea un reticulado. Solo si el conjunto parcialmente ordenado ya es un reticulado el resultado será un reticulado para Sage y obtendremos el error ValueError si el cambio de estatus es imposible. Finalmente, notemos que algunos de los conjuntos parcialmente ordenados que construye Sage ya son reconocidos como reticulados, tal como el prototípico BooleanLattice.

Una composición entera de \(n\) es una lista de enteros positivos que suman \(n\text{.}\) Una composición \(C_1\) cubre a una composición \(C_2\) si \(C_2\) se puede formar a partir de \(C_1\) sumando partes consecutivas. Por ejemplo, \(C_1 = [2, 1, 2] \succeq [3, 2] = C_2\text{.}\) Con esta relación, el conjunto de todas las composiciones enteras de un entero fijo \(n\) en un conjunto parcialmente ordenado que también es un reticulado.

El ínfimo (meet) y el supremo (join) son operaciones fundamentales en un reticulado.

Una vez que un conjunto parcialmente ordenado adquiere el estatus de reticulado, disponemos de comandos adicionales, o cambian las características de sus resultados.

Un ejemplo de lo primero es el método .is_distributive().

Un ejemplo de lo segundo es el método .top(). Lo que en el texto se llama elemento máximo y elemento mínimo, Sage los llama top y bottom. Para un conjunto parcialmente ordenado, .top() y .bottom() pueden entregar un elemento o no (devolviendo None), pero para un reticulado se garantiza la obtención de exactamente un elemento.

Notemos que los valores retornados son todos elementos del reticulado, es este caso listas ordenadas de enteros que suman \(5\text{.}\)

Los complementos tienen sentido en un reticulado. El resultado del método .complements() es un diccionario que tiene elementos del reticulado como índices (keys). Decimos que el diccionario está “indexado” por los elementos del reticulado. El resultado es una lista de complementos del elemento. A esto lo llamamos el “valor” del par índice-valor. (Puede que conozca los diccionarios como “arreglos asociativos”, pero en realidad no son más que funciones sofisticadas.)

El reticulado de composiciones enteras es un reticulado complementado, como podemos observar por el hecho de que cada elemento tiene un complemento único, evidenciado por las listas de largo \(1\) en los valores del diccionario. O podemos preguntarle a Sage por medio de .is_complemented(). Los diccionarios no tienen un orden inherente, de manera que es posible obtener una salida distinta cada vez que se inspeccione el diccionario.

Hay muchos más comandos para conjuntos parcialmente ordenados y erticulados. Construya algunos y use completación con TAB para explorar las posibilidades. Hay mucho más de lo que podemos cubrir en un solo capítulo, pero ya tenemos las herramientas básicas para estudiar conjuntos parcialmente ordenados y reticulados en Sage.