Posets¶

class sage.categories.posets.Posets[source]¶

Bases: Category

The category of posets i.e. sets with a partial order structure.

EXAMPLES:

Sage

sage: Posets()
Category of posets
sage: Posets().super_categories()
[Category of sets]
sage: P = Posets().example(); P
An example of a poset: sets ordered by inclusion

Python

>>> from sage.all import *
>>> Posets()
Category of posets
>>> Posets().super_categories()
[Category of sets]
>>> P = Posets().example(); P
An example of a poset: sets ordered by inclusion

The partial order is implemented by the mandatory method le():

Sage

sage: x = P(Set([1,3])); y = P(Set([1,2,3]))
sage: x, y
({1, 3}, {1, 2, 3})
sage: P.le(x, y)
True
sage: P.le(x, x)
True
sage: P.le(y, x)
False

Python

>>> from sage.all import *
>>> x = P(Set([Integer(1),Integer(3)])); y = P(Set([Integer(1),Integer(2),Integer(3)]))
>>> x, y
({1, 3}, {1, 2, 3})
>>> P.le(x, y)
True
>>> P.le(x, x)
True
>>> P.le(y, x)
False

The other comparison methods are called lt(), ge(), gt(), following Python’s naming convention in operator. Default implementations are provided:

Sage

sage: P.lt(x, x)
False
sage: P.ge(y, x)
True

Python

>>> from sage.all import *
>>> P.lt(x, x)
False
>>> P.ge(y, x)
True

Unless the poset is a facade (see Sets.Facade), one can compare directly its elements using the usual Python operators:

Sage

sage: D = Poset((divisors(30), attrcall("divides")), facade = False)
sage: D(3) <= D(6)
True
sage: D(3) <= D(3)
True
sage: D(3) <= D(5)
False
sage: D(3) < D(3)
False
sage: D(10) >= D(5)
True

Python

>>> from sage.all import *
>>> D = Poset((divisors(Integer(30)), attrcall("divides")), facade = False)
>>> D(Integer(3)) <= D(Integer(6))
True
>>> D(Integer(3)) <= D(Integer(3))
True
>>> D(Integer(3)) <= D(Integer(5))
False
>>> D(Integer(3)) < D(Integer(3))
False
>>> D(Integer(10)) >= D(Integer(5))
True

At this point, this has to be implemented by hand. Once Issue #10130 will be resolved, this will be automatically provided by this category:

Sage

sage: # not implemented
sage: x < y
True
sage: x < x
False
sage: x <= x
True
sage: y >= x
True

Python

>>> from sage.all import *
>>> # not implemented
>>> x < y
True
>>> x < x
False
>>> x <= x
True
>>> y >= x
True

class ElementMethods[source]¶: Bases: object

Finite[source]¶: alias of FinitePosets

class ParentMethods[source]¶

Bases: object

CartesianProduct[source]¶: alias of CartesianProductPoset

directed_subset(elements, direction)[source]¶

Return the order filter or the order ideal generated by a list of elements.

If direction is 'up', the order filter (upper set) is being returned.

If direction is 'down', the order ideal (lower set) is being returned.

INPUT:

elements – list of elements
direction – 'up' or 'down'

EXAMPLES:

Sage

sage: B = posets.BooleanLattice(4)
sage: B.directed_subset([3, 8], 'up')
[3, 7, 8, 9, 10, 11, 12, 13, 14, 15]
sage: B.directed_subset([7, 10], 'down')
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]

Python

>>> from sage.all import *
>>> B = posets.BooleanLattice(Integer(4))
>>> B.directed_subset([Integer(3), Integer(8)], 'up')
[3, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> B.directed_subset([Integer(7), Integer(10)], 'down')
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]

ge(x, y)[source]¶

Return whether \(x \ge y\) in the poset self.

INPUT:

x, y – elements of self

This default implementation delegates the work to le().

EXAMPLES:

Sage

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.ge( 6, 3 )
True
sage: D.ge( 3, 3 )
True
sage: D.ge( 3, 5 )
False

Python

>>> from sage.all import *
>>> D = Poset((divisors(Integer(30)), attrcall("divides")))
>>> D.ge( Integer(6), Integer(3) )
True
>>> D.ge( Integer(3), Integer(3) )
True
>>> D.ge( Integer(3), Integer(5) )
False

gt(x, y)[source]¶

Return whether \(x > y\) in the poset self.

INPUT:

x, y – elements of self

This default implementation delegates the work to lt().

EXAMPLES:

Sage

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.gt( 3, 6 )
False
sage: D.gt( 3, 3 )
False
sage: D.gt( 3, 5 )
False

Python

>>> from sage.all import *
>>> D = Poset((divisors(Integer(30)), attrcall("divides")))
>>> D.gt( Integer(3), Integer(6) )
False
>>> D.gt( Integer(3), Integer(3) )
False
>>> D.gt( Integer(3), Integer(5) )
False

is_antichain_of_poset(o)[source]¶

Return whether an iterable o is an antichain of self.

INPUT:

o – an iterable (e. g., list, set, or tuple) containing some elements of self

OUTPUT:

True if the subset of self consisting of the entries of o is an antichain of self, and False otherwise.

EXAMPLES:

Sage

sage: P = Poset((divisors(12), attrcall("divides")),
....:           facade=True, linear_extension=True)
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_antichain_of_poset([1, 3])
False
sage: P.is_antichain_of_poset([3, 1])
False
sage: P.is_antichain_of_poset([1, 1, 3])
False
sage: P.is_antichain_of_poset([])
True
sage: P.is_antichain_of_poset([1])
True
sage: P.is_antichain_of_poset([1, 1])
True
sage: P.is_antichain_of_poset([3, 4])
True
sage: P.is_antichain_of_poset([3, 4, 12])
False
sage: P.is_antichain_of_poset([6, 4])
True
sage: P.is_antichain_of_poset(i for i in divisors(12)
....:                         if (2 < i and i < 6))
True
sage: P.is_antichain_of_poset(i for i in divisors(12)
....:                         if (2 <= i and i < 6))
False

sage: Q = Poset({2: [3, 1], 3: [4], 1: [4]})
sage: Q.is_antichain_of_poset((1, 2))
False
sage: Q.is_antichain_of_poset((2, 4))
False
sage: Q.is_antichain_of_poset((4, 2))
False
sage: Q.is_antichain_of_poset((2, 2))
True
sage: Q.is_antichain_of_poset((3, 4))
False
sage: Q.is_antichain_of_poset((3, 1))
True
sage: Q.is_antichain_of_poset((1, ))
True
sage: Q.is_antichain_of_poset(())
True

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(12)), attrcall("divides")),
...           facade=True, linear_extension=True)
>>> sorted(P.list())
[1, 2, 3, 4, 6, 12]
>>> P.is_antichain_of_poset([Integer(1), Integer(3)])
False
>>> P.is_antichain_of_poset([Integer(3), Integer(1)])
False
>>> P.is_antichain_of_poset([Integer(1), Integer(1), Integer(3)])
False
>>> P.is_antichain_of_poset([])
True
>>> P.is_antichain_of_poset([Integer(1)])
True
>>> P.is_antichain_of_poset([Integer(1), Integer(1)])
True
>>> P.is_antichain_of_poset([Integer(3), Integer(4)])
True
>>> P.is_antichain_of_poset([Integer(3), Integer(4), Integer(12)])
False
>>> P.is_antichain_of_poset([Integer(6), Integer(4)])
True
>>> P.is_antichain_of_poset(i for i in divisors(Integer(12))
...                         if (Integer(2) < i and i < Integer(6)))
True
>>> P.is_antichain_of_poset(i for i in divisors(Integer(12))
...                         if (Integer(2) <= i and i < Integer(6)))
False

>>> Q = Poset({Integer(2): [Integer(3), Integer(1)], Integer(3): [Integer(4)], Integer(1): [Integer(4)]})
>>> Q.is_antichain_of_poset((Integer(1), Integer(2)))
False
>>> Q.is_antichain_of_poset((Integer(2), Integer(4)))
False
>>> Q.is_antichain_of_poset((Integer(4), Integer(2)))
False
>>> Q.is_antichain_of_poset((Integer(2), Integer(2)))
True
>>> Q.is_antichain_of_poset((Integer(3), Integer(4)))
False
>>> Q.is_antichain_of_poset((Integer(3), Integer(1)))
True
>>> Q.is_antichain_of_poset((Integer(1), ))
True
>>> Q.is_antichain_of_poset(())
True

An infinite poset:

Sage

sage: from sage.categories.examples.posets import FiniteSetsOrderedByInclusion
sage: R = FiniteSetsOrderedByInclusion()
sage: R.is_antichain_of_poset([R(set([3, 1, 2])),
....:                          R(set([1, 4])), R(set([4, 5]))])
True
sage: R.is_antichain_of_poset([R(set([3, 1, 2, 4])),
....:                          R(set([1, 4])), R(set([4, 5]))])
False

Python

>>> from sage.all import *
>>> from sage.categories.examples.posets import FiniteSetsOrderedByInclusion
>>> R = FiniteSetsOrderedByInclusion()
>>> R.is_antichain_of_poset([R(set([Integer(3), Integer(1), Integer(2)])),
...                          R(set([Integer(1), Integer(4)])), R(set([Integer(4), Integer(5)]))])
True
>>> R.is_antichain_of_poset([R(set([Integer(3), Integer(1), Integer(2), Integer(4)])),
...                          R(set([Integer(1), Integer(4)])), R(set([Integer(4), Integer(5)]))])
False

is_chain_of_poset(o, ordered=False)[source]¶

Return whether an iterable o is a chain of self, including a check for o being ordered from smallest to largest element if the keyword ordered is set to True.

INPUT:

o – an iterable (e. g., list, set, or tuple) containing some elements of self
ordered – a Boolean (default: False); decides whether the notion of a chain includes being ordered

OUTPUT:

If ordered is set to False, the truth value of the following assertion is returned: The subset of self formed by the elements of o is a chain in self.

If ordered is set to True, the truth value of the following assertion is returned: Every element of the list o is (strictly!) smaller than its successor in self. (This makes no sense if ordered is a set.)

EXAMPLES:

Sage

sage: P = Poset((divisors(12), attrcall("divides")),
....:           facade=True, linear_extension=True)
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_chain_of_poset([1, 3])
True
sage: P.is_chain_of_poset([3, 1])
True
sage: P.is_chain_of_poset([1, 3], ordered=True)
True
sage: P.is_chain_of_poset([3, 1], ordered=True)
False
sage: P.is_chain_of_poset([])
True
sage: P.is_chain_of_poset([], ordered=True)
True
sage: P.is_chain_of_poset((2, 12, 6))
True
sage: P.is_chain_of_poset((2, 6, 12), ordered=True)
True
sage: P.is_chain_of_poset((2, 12, 6), ordered=True)
False
sage: P.is_chain_of_poset((2, 12, 6, 3))
False
sage: P.is_chain_of_poset((2, 3))
False

sage: Q = Poset({2: [3, 1], 3: [4], 1: [4]})
sage: Q.is_chain_of_poset([1, 2], ordered=True)
False
sage: Q.is_chain_of_poset([1, 2])
True
sage: Q.is_chain_of_poset([2, 1], ordered=True)
True
sage: Q.is_chain_of_poset([2, 1, 1], ordered=True)
False
sage: Q.is_chain_of_poset([3])
True
sage: Q.is_chain_of_poset([4, 2, 3])
True
sage: Q.is_chain_of_poset([4, 2, 3], ordered=True)
False
sage: Q.is_chain_of_poset([2, 3, 4], ordered=True)
True

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(12)), attrcall("divides")),
...           facade=True, linear_extension=True)
>>> sorted(P.list())
[1, 2, 3, 4, 6, 12]
>>> P.is_chain_of_poset([Integer(1), Integer(3)])
True
>>> P.is_chain_of_poset([Integer(3), Integer(1)])
True
>>> P.is_chain_of_poset([Integer(1), Integer(3)], ordered=True)
True
>>> P.is_chain_of_poset([Integer(3), Integer(1)], ordered=True)
False
>>> P.is_chain_of_poset([])
True
>>> P.is_chain_of_poset([], ordered=True)
True
>>> P.is_chain_of_poset((Integer(2), Integer(12), Integer(6)))
True
>>> P.is_chain_of_poset((Integer(2), Integer(6), Integer(12)), ordered=True)
True
>>> P.is_chain_of_poset((Integer(2), Integer(12), Integer(6)), ordered=True)
False
>>> P.is_chain_of_poset((Integer(2), Integer(12), Integer(6), Integer(3)))
False
>>> P.is_chain_of_poset((Integer(2), Integer(3)))
False

>>> Q = Poset({Integer(2): [Integer(3), Integer(1)], Integer(3): [Integer(4)], Integer(1): [Integer(4)]})
>>> Q.is_chain_of_poset([Integer(1), Integer(2)], ordered=True)
False
>>> Q.is_chain_of_poset([Integer(1), Integer(2)])
True
>>> Q.is_chain_of_poset([Integer(2), Integer(1)], ordered=True)
True
>>> Q.is_chain_of_poset([Integer(2), Integer(1), Integer(1)], ordered=True)
False
>>> Q.is_chain_of_poset([Integer(3)])
True
>>> Q.is_chain_of_poset([Integer(4), Integer(2), Integer(3)])
True
>>> Q.is_chain_of_poset([Integer(4), Integer(2), Integer(3)], ordered=True)
False
>>> Q.is_chain_of_poset([Integer(2), Integer(3), Integer(4)], ordered=True)
True

Examples with infinite posets:

Sage

sage: from sage.categories.examples.posets import FiniteSetsOrderedByInclusion
sage: R = FiniteSetsOrderedByInclusion()
sage: R.is_chain_of_poset([R(set([3, 1, 2])),
....:                      R(set([1, 4])),
....:                      R(set([4, 5]))])
False
sage: R.is_chain_of_poset([R(set([3, 1, 2])),
....:                      R(set([1, 2])),
....:                      R(set([1]))], ordered=True)
False
sage: R.is_chain_of_poset([R(set([3, 1, 2])),
....:                      R(set([1, 2])), R(set([1]))])
True

sage: from sage.categories.examples.posets import PositiveIntegersOrderedByDivisibilityFacade
sage: T = PositiveIntegersOrderedByDivisibilityFacade()
sage: T.is_chain_of_poset((T(3), T(4), T(7)))
False
sage: T.is_chain_of_poset((T(3), T(6), T(3)))
True
sage: T.is_chain_of_poset((T(3), T(6), T(3)), ordered=True)
False
sage: T.is_chain_of_poset((T(3), T(3), T(6)))
True
sage: T.is_chain_of_poset((T(3), T(3), T(6)), ordered=True)
False
sage: T.is_chain_of_poset((T(3), T(6)), ordered=True)
True
sage: T.is_chain_of_poset((), ordered=True)
True
sage: T.is_chain_of_poset((T(3),), ordered=True)
True
sage: T.is_chain_of_poset((T(q) for q in divisors(27)))
True
sage: T.is_chain_of_poset((T(q) for q in divisors(18)))
False

Python

>>> from sage.all import *
>>> from sage.categories.examples.posets import FiniteSetsOrderedByInclusion
>>> R = FiniteSetsOrderedByInclusion()
>>> R.is_chain_of_poset([R(set([Integer(3), Integer(1), Integer(2)])),
...                      R(set([Integer(1), Integer(4)])),
...                      R(set([Integer(4), Integer(5)]))])
False
>>> R.is_chain_of_poset([R(set([Integer(3), Integer(1), Integer(2)])),
...                      R(set([Integer(1), Integer(2)])),
...                      R(set([Integer(1)]))], ordered=True)
False
>>> R.is_chain_of_poset([R(set([Integer(3), Integer(1), Integer(2)])),
...                      R(set([Integer(1), Integer(2)])), R(set([Integer(1)]))])
True

>>> from sage.categories.examples.posets import PositiveIntegersOrderedByDivisibilityFacade
>>> T = PositiveIntegersOrderedByDivisibilityFacade()
>>> T.is_chain_of_poset((T(Integer(3)), T(Integer(4)), T(Integer(7))))
False
>>> T.is_chain_of_poset((T(Integer(3)), T(Integer(6)), T(Integer(3))))
True
>>> T.is_chain_of_poset((T(Integer(3)), T(Integer(6)), T(Integer(3))), ordered=True)
False
>>> T.is_chain_of_poset((T(Integer(3)), T(Integer(3)), T(Integer(6))))
True
>>> T.is_chain_of_poset((T(Integer(3)), T(Integer(3)), T(Integer(6))), ordered=True)
False
>>> T.is_chain_of_poset((T(Integer(3)), T(Integer(6))), ordered=True)
True
>>> T.is_chain_of_poset((), ordered=True)
True
>>> T.is_chain_of_poset((T(Integer(3)),), ordered=True)
True
>>> T.is_chain_of_poset((T(q) for q in divisors(Integer(27))))
True
>>> T.is_chain_of_poset((T(q) for q in divisors(Integer(18))))
False

is_order_filter(o)[source]¶

Return whether o is an order filter of self, assuming self has no infinite ascending path.

INPUT:

o – list (or set, or tuple) containing some elements of self

EXAMPLES:

Sage

sage: P = Poset((divisors(12), attrcall("divides")),
....:           facade=True, linear_extension=True)
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_order_filter([4, 12])
True
sage: P.is_order_filter([])
True
sage: P.is_order_filter({3, 4, 12})
False
sage: P.is_order_filter({3, 6, 12})
True

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(12)), attrcall("divides")),
...           facade=True, linear_extension=True)
>>> sorted(P.list())
[1, 2, 3, 4, 6, 12]
>>> P.is_order_filter([Integer(4), Integer(12)])
True
>>> P.is_order_filter([])
True
>>> P.is_order_filter({Integer(3), Integer(4), Integer(12)})
False
>>> P.is_order_filter({Integer(3), Integer(6), Integer(12)})
True

is_order_ideal(o)[source]¶

Return whether o is an order ideal of self, assuming self has no infinite descending path.

INPUT:

o – list (or set, or tuple) containing some elements of self

EXAMPLES:

Sage

sage: P = Poset((divisors(12), attrcall("divides")),
....:           facade=True, linear_extension=True)
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_order_ideal([1, 3])
True
sage: P.is_order_ideal([])
True
sage: P.is_order_ideal({1, 3})
True
sage: P.is_order_ideal([1, 3, 4])
False

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(12)), attrcall("divides")),
...           facade=True, linear_extension=True)
>>> sorted(P.list())
[1, 2, 3, 4, 6, 12]
>>> P.is_order_ideal([Integer(1), Integer(3)])
True
>>> P.is_order_ideal([])
True
>>> P.is_order_ideal({Integer(1), Integer(3)})
True
>>> P.is_order_ideal([Integer(1), Integer(3), Integer(4)])
False

le(x, y)[source]¶

Return whether \(x \le y\) in the poset self.

INPUT:

x, y – elements of self

EXAMPLES:

Sage

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.le( 3, 6 )
True
sage: D.le( 3, 3 )
True
sage: D.le( 3, 5 )
False

Python

>>> from sage.all import *
>>> D = Poset((divisors(Integer(30)), attrcall("divides")))
>>> D.le( Integer(3), Integer(6) )
True
>>> D.le( Integer(3), Integer(3) )
True
>>> D.le( Integer(3), Integer(5) )
False

lower_covers(x)[source]¶

Return the lower covers of \(x\), that is, the elements \(y\) such that \(y<x\) and there exists no \(z\) such that \(y<z<x\).

EXAMPLES:

Sage

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.lower_covers(15)
[3, 5]

Python

>>> from sage.all import *
>>> D = Poset((divisors(Integer(30)), attrcall("divides")))
>>> D.lower_covers(Integer(15))
[3, 5]

lt(x, y)[source]¶

Return whether \(x < y\) in the poset self.

INPUT:

x, y – elements of self

This default implementation delegates the work to le().

EXAMPLES:

Sage

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.lt( 3, 6 )
True
sage: D.lt( 3, 3 )
False
sage: D.lt( 3, 5 )
False

Python

>>> from sage.all import *
>>> D = Poset((divisors(Integer(30)), attrcall("divides")))
>>> D.lt( Integer(3), Integer(6) )
True
>>> D.lt( Integer(3), Integer(3) )
False
>>> D.lt( Integer(3), Integer(5) )
False

order_filter(elements)[source]¶

Return the order filter generated by a list of elements.

A subset \(I\) of a poset is said to be an order filter if, for any \(x\) in \(I\) and \(y\) such that \(y \ge x\), then \(y\) is in \(I\).

This is also called the upper set generated by these elements.

EXAMPLES:

Sage

sage: B = posets.BooleanLattice(4)
sage: B.order_filter([3,8])
[3, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Python

>>> from sage.all import *
>>> B = posets.BooleanLattice(Integer(4))
>>> B.order_filter([Integer(3),Integer(8)])
[3, 7, 8, 9, 10, 11, 12, 13, 14, 15]

order_ideal(elements)[source]¶

Return the order ideal in self generated by the elements of an iterable elements.

A subset \(I\) of a poset is said to be an order ideal if, for any \(x\) in \(I\) and \(y\) such that \(y \le x\), then \(y\) is in \(I\).

This is also called the lower set generated by these elements.

EXAMPLES:

Sage

sage: B = posets.BooleanLattice(4)
sage: B.order_ideal([7,10])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]

Python

>>> from sage.all import *
>>> B = posets.BooleanLattice(Integer(4))
>>> B.order_ideal([Integer(7),Integer(10)])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]

order_ideal_toggle(I, v)[source]¶

Return the result of toggling the element v in the order ideal I.

If \(v\) is an element of a poset \(P\), then toggling the element \(v\) is an automorphism of the set \(J(P)\) of all order ideals of \(P\). It is defined as follows: If \(I\) is an order ideal of \(P\), then the image of \(I\) under toggling the element \(v\) is

the set \(I \cup \{ v \}\), if \(v \not\in I\) but every element of \(P\) smaller than \(v\) is in \(I\);
the set \(I \setminus \{ v \}\), if \(v \in I\) but no element of \(P\) greater than \(v\) is in \(I\);
\(I\) otherwise.

This image always is an order ideal of \(P\).

EXAMPLES:

Sage

sage: P = Poset({1: [2,3], 2: [4], 3: []})
sage: I = Set({1, 2})
sage: I in P.order_ideals_lattice()                                     # needs sage.modules
True
sage: P.order_ideal_toggle(I, 1)
{1, 2}
sage: P.order_ideal_toggle(I, 2)
{1}
sage: P.order_ideal_toggle(I, 3)
{1, 2, 3}
sage: P.order_ideal_toggle(I, 4)
{1, 2, 4}
sage: P4 = Posets(4)
sage: all(all(all(P.order_ideal_toggle(P.order_ideal_toggle(I, i), i) == I          # needs sage.modules
....:               for i in range(4))
....:          for I in P.order_ideals_lattice(facade=True))
....:     for P in P4)
True

Python

>>> from sage.all import *
>>> P = Poset({Integer(1): [Integer(2),Integer(3)], Integer(2): [Integer(4)], Integer(3): []})
>>> I = Set({Integer(1), Integer(2)})
>>> I in P.order_ideals_lattice()                                     # needs sage.modules
True
>>> P.order_ideal_toggle(I, Integer(1))
{1, 2}
>>> P.order_ideal_toggle(I, Integer(2))
{1}
>>> P.order_ideal_toggle(I, Integer(3))
{1, 2, 3}
>>> P.order_ideal_toggle(I, Integer(4))
{1, 2, 4}
>>> P4 = Posets(Integer(4))
>>> all(all(all(P.order_ideal_toggle(P.order_ideal_toggle(I, i), i) == I          # needs sage.modules
...               for i in range(Integer(4)))
...          for I in P.order_ideals_lattice(facade=True))
...     for P in P4)
True

order_ideal_toggles(I, vs)[source]¶

Return the result of toggling the elements of the list (or iterable) vs (one by one, from left to right) in the order ideal I.

See order_ideal_toggle() for a definition of toggling.

EXAMPLES:

Sage

sage: P = Poset({1: [2,3], 2: [4], 3: []})
sage: I = Set({1, 2})
sage: P.order_ideal_toggles(I, [1,2,3,4])
{1, 3}
sage: P.order_ideal_toggles(I, (1,2,3,4))
{1, 3}

Python

>>> from sage.all import *
>>> P = Poset({Integer(1): [Integer(2),Integer(3)], Integer(2): [Integer(4)], Integer(3): []})
>>> I = Set({Integer(1), Integer(2)})
>>> P.order_ideal_toggles(I, [Integer(1),Integer(2),Integer(3),Integer(4)])
{1, 3}
>>> P.order_ideal_toggles(I, (Integer(1),Integer(2),Integer(3),Integer(4)))
{1, 3}

principal_lower_set(x)[source]¶

Return the order ideal generated by an element x.

This is also called the lower set generated by this element.

EXAMPLES:

Sage

sage: B = posets.BooleanLattice(4)
sage: B.principal_order_ideal(6)
[0, 2, 4, 6]

Python

>>> from sage.all import *
>>> B = posets.BooleanLattice(Integer(4))
>>> B.principal_order_ideal(Integer(6))
[0, 2, 4, 6]

principal_order_filter(x)[source]¶

Return the order filter generated by an element x.

This is also called the upper set generated by this element.

EXAMPLES:

Sage

sage: B = posets.BooleanLattice(4)
sage: B.principal_order_filter(2)
[2, 3, 6, 7, 10, 11, 14, 15]

Python

>>> from sage.all import *
>>> B = posets.BooleanLattice(Integer(4))
>>> B.principal_order_filter(Integer(2))
[2, 3, 6, 7, 10, 11, 14, 15]

principal_order_ideal(x)[source]¶

Return the order ideal generated by an element x.

This is also called the lower set generated by this element.

EXAMPLES:

Sage

sage: B = posets.BooleanLattice(4)
sage: B.principal_order_ideal(6)
[0, 2, 4, 6]

Python

>>> from sage.all import *
>>> B = posets.BooleanLattice(Integer(4))
>>> B.principal_order_ideal(Integer(6))
[0, 2, 4, 6]

principal_upper_set(x)[source]¶

Return the order filter generated by an element x.

This is also called the upper set generated by this element.

EXAMPLES:

Sage

sage: B = posets.BooleanLattice(4)
sage: B.principal_order_filter(2)
[2, 3, 6, 7, 10, 11, 14, 15]

Python

>>> from sage.all import *
>>> B = posets.BooleanLattice(Integer(4))
>>> B.principal_order_filter(Integer(2))
[2, 3, 6, 7, 10, 11, 14, 15]

upper_covers(x)[source]¶

Return the upper covers of \(x\), that is, the elements \(y\) such that \(x<y\) and there exists no \(z\) such that \(x<z<y\).

EXAMPLES:

Sage

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.upper_covers(3)
[6, 15]

Python

>>> from sage.all import *
>>> D = Poset((divisors(Integer(30)), attrcall("divides")))
>>> D.upper_covers(Integer(3))
[6, 15]

example(choice=None)[source]¶

Return examples of objects of Posets(), as per Category.example().

EXAMPLES:

Sage

sage: Posets().example()
An example of a poset: sets ordered by inclusion

sage: Posets().example("facade")
An example of a facade poset:
 the positive integers ordered by divisibility

Python

>>> from sage.all import *
>>> Posets().example()
An example of a poset: sets ordered by inclusion

>>> Posets().example("facade")
An example of a facade poset:
 the positive integers ordered by divisibility

super_categories()[source]¶

Return a list of the (immediate) super categories of self, as per Category.super_categories().

EXAMPLES:

Sage

sage: Posets().super_categories()
[Category of sets]

Python

>>> from sage.all import *
>>> Posets().super_categories()
[Category of sets]