Conjuntos parcialmente ordenados (Posets) en Sage

En los dos cursos hemos oido mucho sobre los "conjuntos parcialmente ordenados" o "posets". Los posets estan implementados en Sage, vamos hacer unos ejemplos y ver si podemos reproducir los ejemplos de las clases.

Hay varias opciones para construir un poset en Sage.

Primero, hay que dar un "diccionario".



In [1]:

    
d = {1:[2,3], 2:[4], 3:[4]}
P = Poset(d); P

Para cada elemento $x$ en el poset, hay que dar listas de $y$ tal que $x$ esta cubierto por $y$.

Si das relaciones que no son "relaciones minimas" ( $x < y$ y no hay un $z$ tal que $x<z<y$ ), aun as\'i funciona.



In [2]:

    
d = {1:[2,3,4], 2:[4], 3:[4]}
PP = Poset(d); PP

Otra manera es dar una función de comparación de elementos.



In [3]:

    
D = list(divisors(12))
P1 = Poset([D, lambda i,j : i.divides(j)]); P1

Para declarar la función, utilice la palabra clave lambda luego $x$ y $y$ son elementos del poset y escriba una expresión que es True (verdadera) si $x \leq y$ en el poset. En el ejemplo de arriba, $x \leq y$ si y solo si $x$ divide a $y$.

Usted tambien puede dar una función que describe las relaciones mínimas.



In [4]:

    
D = list(divisors(12))
P1 = Poset([D, lambda i,j : i.divides(j) and (j//i).is_prime()], cover_relations=True); P1

Otra manera de describirlo es dar una lista de elementos y una lista de relaciones. Por ejemplo



In [2]:

    
P1 = Poset([list(divisors(12)), [(1,2),(1,3),(2,4),(2,6),(3,6),(4,12),(6,12)]])
P1

Si las relaciones que usted da crean un *ciclo: (que quiere decir que el poset ya no es antisimétrico), esto da un error.



In [1]:

    
P2 = Poset([[1,2,3], [(1,2),(2,3),(3,1)]])

Una vez el poset esta creado, usted puede ver los métdos disponibles escribiendo P1. + tecla tab.



In [ ]:

    
P1. # ponga el cursor despues del punto y presione la tecla Tab

Por ejemplo, puede revisar que el poset sea un lattice.



In [8]:

    
P1.is_lattice()

O que el poset es ranqueado.



In [9]:

    
P1.is_ranked()

Hasta puede obtener la función de rango.



In [5]:

    
f = P1.rank_function()



In [9]:

    
f(1)



In [10]:

    
f(2)



In [11]:

    
f(3)



In [12]:

    
f(4)



In [13]:

    
f(6)



In [14]:

    
f(12)

El poset de subconjuntos

Sage puede construir todos los subconjuntos de un conjunto.



In [16]:

    
Sub4 = Subsets([1,2,3,4])
Sub4



In [18]:

    
list(Sub4)

Puede crear un conjunto dado de la siguiente manera:



In [24]:

    
s1 = Sub4({1,2})
s2 = Sub4({2,3,4})

Puede ensayar si un subconjunto está incluido en otro utilizando el siguiente método:



In [28]:

    
s1.issubset(s2)



In [29]:

    
s3 = Sub4({1})
s3.issubset(s1)

Exercisio Cree el poset de subconjuntos de $2^{[4]}$.



In [17]:

¿Es este poset un lattice? (Permita que Sage le diga)



In [18]:

¿Está el poset graduado?



In [19]:

Calcule la función de rango del subconjunto \lbrace 1,2,3 \rbrace



In [20]:

Use Sage para calcular el número de elementos de cada rango y verifique las propiedades vistas en la clase (por ejemplo, la propiedad de suma alternante)



In [22]:

¡Hágamos cocientes!

Sage sabe sobre los grupos de permutación. El siguiente ejemplo da el grupo generado por el ciclo $(1,2,3,4)$.



In [34]:

    
p = PermutationGroupElement([(1,2,3,4)]) # create the cyclic permutation



In [35]:

    
G = PermutationGroup([p]) # create the group generated by that element
G



In [31]:

    
list(G)

Si usted tiene un subconjunto, puede calcular sus imagenes bajo un elemento del grupo.



In [38]:

    
s = Sub4({1,2})
orbit = []
for p in G:
    orbit.append(Sub4({p(i) for i in s}))
print orbit

Podemos crear una lista de sus órbitas.



In [47]:

    
Orbits = []
S = set(Sub4) # we compute all the elements
while len(S) > 0:
    s = S.pop() # we take one element out
    orbit = set()
    for p in G:
        orbit.add(Sub4({p(i) for i in s})) # we add the image to the orbit
    S.difference_update(orbit) # we remote the elements of the orbit from the initial set
    Orbits.append(tuple(orbit)) # note : we transform them into type "tuple" so that they are "immutable" 
Orbits

Ejercisio Complete el código de la siguiente función y compare las órbitas.



In [48]:

    
def orbit_comp(o1, o2):
    """
    Return true if at least one element of o1 is smaller than one elements of o2
    """
    # edit here

Esto funciona?



In [49]:

    
orbit_comp(Orbits[0], Orbits[1]) # should say True



In [50]:

    
orbit_comp(Orbits[0], Orbits[2]) # should say False



In [51]:

    
POrbits = Poset([Orbits, lambda x,y: orbit_comp(x,y)])
POrbits

Utilizando métodos similares, construya el poset de $2^{[6]}$ tomando el cociente con el grupo cíclico. Luego verifique las propiedades que hemos visto en la clase.



In [ ]:



In [53]:



In [ ]: