19.8: Salvia

Sage tiene soporte tanto para conjuntos parcialmente ordenados (“posets”) como para celosías, y hace un excelente trabajo al proporcionar representaciones visuales de ambos.

Creación de conjuntos parcialmente ordenados

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

Un enfoque para crear la relación es especificar cada instancia donde un elemento es comparable al otro. Entonces construimos una lista de pares, donde cada par contiene elementos comparables, con el menor primero. Este es el conjunto de relaciones.

Construimos el poset dando al constructor del Poset una lista que contiene los elementos y las relaciones. Entonces podemos obtener fácilmente una “trama” del poset. Observe que la trama solo muestra las “relaciones de cobertura”, un conjunto mínimo de comparaciones que la suposición de transitividad se expandiría en el conjunto de todas las relaciones.

Otro enfoque para crear un Poset es dejar que el constructor poset recorra todos los pares de elementos, y todo lo que hacemos es darle al constructor una forma de probar si dos elementos son comparables. Nuestra función de comparación debe esperar dos elementos y luego devolver Verdadero o Falso. Una función “lambda” es una forma de construir rápidamente una función de este tipo. Esta puede ser una idea nueva para ti, pero dominar las funciones lambda puede ser una gran comodidad. Observe que “lambda” es una palabra reservada solo para este propósito (así, por ejemplo, lambda es una mala elección para el nombre de un valor propio de una matriz). Hay otras formas de hacer funciones en Sage, pero una función lambda es más rápida cuando la función es simple.

Sage también tiene una colección de posets de stock. Algunas son construcciones de un solo disparo, mientras que otras son miembros de familias parametrizadas. Use la terminación de pestañas en Posets. para ver la lista completa. Aquí hay algunos ejemplos.

Una construcción de un solo disparo. Quizás lo que se esperaría, aunque podría haber otras alternativas, igualmente plausibles.

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

Y posets aleatorios. Estos pueden ser útiles para probar y experimentar, pero es poco probable que exhiban casos especiales que pueden ser importantes. Puede ejecutar el siguiente comando muchas veces y variar el segundo argumento, que es un límite superior aproximado en la probabilidad de que dos elementos sean comparables. Recuerda que la trama solo muestra las relaciones de portada. Cuantos más elementos sean comparables, más “estirada verticalmente” será la trama.

Propiedades de un Poset

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

Observe que 6 y 8 no son comparables en este poset (es un orden parcial). Los métodos .is_gequal () y .is_greater_than () funcionan de manera similar, pero devuelve True si el primer elemento es mayor (o igual).

Podemos encontrar los elementos más grandes y pequeños de un poset. Este es un poset aleatorio construido con un 10% de probabilidad, pero copiado aquí para que sea repetible.

Los elementos de un poset se pueden dividir en conjuntos de niveles. En las parcelas de posets, los elementos del mismo nivel se trazan verticalmente a la misma altura. Cada conjunto de niveles se obtiene eliminando todos los conjuntos de niveles anteriores y luego tomando los elementos mínimos del resultado.

Si hacemos dos elementos en R comparables cuando no habían sido previamente, se trata de una extensión de R. Considere todas las extensiones posibles de un poset —podemos hacer un poset a partir de todos estos, donde la inclusión de conjuntos es la relación. Una extensión lineal es un elemento máximo en este poset de posets. De manera informal, estamos agregando tantas relaciones nuevas como sea posible, consistentes con el poset original y para que el resultado sea un orden total. Es decir, hay un orden de los elementos que es consistente con el orden en el poset. Podemos construir tal cosa, pero la salida es solo una lista de los elementos en el orden lineal. Un informático se inclinaría a llamar a esto un “tipo topológico”.

Podemos construir citatorios dando un conjunto de elementos para inducir el nuevo poset. Aquí tomamos aproximadamente la “mitad inferior” del poset aleatorio P induciendo el citatorio en una unión de algunos de los conjuntos de niveles.

El dual de un poset conserva el mismo conjunto de elementos, pero invierte cualquier comparación.

Tomando el dual del poset de divisibilidad de Ejemplo\(19.6\) sería como cambiar la relación a “es un múltiplo de”.

Celosías

Cada celosía es un poset, por lo que todos los comandos anteriores funcionarán igualmente bien para una celosía. Pero, ¿cómo se crea una celosía? Simple: primero cree un poset y luego aliméntelo en el constructor LatticEposet (). Pero date cuenta que solo porque le das un poset a este constructor, no significa que una celosía siempre volverá a salir. Solo si el poset ya es una celosía se actualizará de un poset a un enrejado para los propósitos de Sage, y obtendrás un ValueError si la actualización no es posible. Por último, observe que algunos de los posets constructos de Sage ya son reconocidos como celosías, como el prototípico BooleanLattice.

Una composición entera de\(n\) es una lista de enteros positivos que suman a\(n\text{.}\) Una composición\(C_1\) cubre una composición\(C_2\) si se\(C_2\) puede formar a partir de la adición\(C_1\) de 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\) es un poset que también es una celosía.

Un encuentro o una unión es una operación fundamental en una celosía.

Una vez que un poset se actualiza al estado de celosía, los comandos adicionales estarán disponibles, o el carácter de sus resultados cambia.

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

Un ejemplo de esto último es el método.top (). Lo que tu texto llama un elemento más grande y un elemento más pequeño de una celosía, Sage llama un top y un bottom. Para un poset, .top () y .bottom () pueden devolver un elemento o no (devolviendo None), pero para una celosía se garantiza que devolverá exactamente un elemento.

Observe que los valores devueltos son todos elementos de la celosía, en este caso listas ordenadas de enteros sumando a\(5\text{.}\)

Los complementos ahora tienen sentido en una celosía. El resultado del método .complementos () es un diccionario que utiliza elementos de la celosía como claves. Decimos que el diccionario está “indexado” por los elementos de la celosía. El resultado es una lista de los complementos del elemento. A esto lo llamamos el “valor” del par clave-valor. (Puede que conozcas a los diccionarios como “matrices asociativas”, pero en realidad son solo funciones elegantes).

La celosía de composiciones enteras es una celosía complementada, como podemos ver por el resultado que cada elemento tiene un único complemento (único), evidenciado por las listas de longitud\(1\) en los valores del diccionario. O simplemente podemos preguntar a Sage vía .is_complementado (). Los diccionarios no tienen un orden inherente, por lo que puede obtener diferentes resultados cada vez que inspeccione el diccionario.

Hay muchos más comandos que se aplican a los posets y celosías, así que construye algunos y usa la finalización de pestañas generosamente para explorar. Hay más por descubrir de lo que podemos cubrir en un solo capítulo, pero ahora tienes las herramientas básicas para estudiar provechosamente posets y celosías en Sage.