Bases: sage.categories.category.Category
The category of posets i.e. sets with a partial order structure.
EXAMPLES:
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
The partial order is implemented by the mandatory method le():
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
The other comparison methods are called lt(), ge(), gt(), following Python’s naming convention in operator. Default implementations are provided:
sage: P.lt(x, x)
False
sage: P.ge(y, x)
True
Unless the poset is a facade (see Sets.Facades), one can compare directly its elements using the usual Python operators:
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
At this point, this has to be implemented by hand. Once trac ticket #10130 will be resolved, this will be automatically provided by this category:
sage: x < y # todo: not implemented
True
sage: x < x # todo: not implemented
False
sage: x <= x # todo: not implemented
True
sage: y >= x # todo: not implemented
True
See also
TESTS:
sage: C = Posets()
sage: TestSuite(C).run()
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:
EXAMPLES:
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]
Return whether in the poset self.
INPUT:
This default implementation delegates the work to le().
EXAMPLES:
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
Return whether in the poset self.
INPUT:
This default implementation delegates the work to lt().
EXAMPLES:
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
Return whether o is an order filter of self, assuming self has no infinite ascending path.
INPUT:
EXAMPLES:
sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True)
sage: 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
Return whether o is an order ideal of self, assuming self has no infinite descending path.
INPUT:
EXAMPLES:
sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True)
sage: 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
Return whether in the poset self.
INPUT:
EXAMPLES:
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
Return the lower covers of , that is, the elements
such that
and there exists no
such that
.
EXAMPLES:
sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.lower_covers(15)
[3, 5]
Return the order ideal in self generated by the elements of an iterable elements.
A subset of a poset is said to be an order ideal if, for
any
in
and
such that
, then
is in
.
This is also called the lower set generated by these elements.
EXAMPLES:
sage: B = Posets.BooleanLattice(4)
sage: B.order_ideal([7,10])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]
Return whether in the poset self.
INPUT:
This default implementation delegates the work to le().
EXAMPLES:
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
Return the order filter generated by a list of elements.
A subset of a poset is said to be an order filter if, for
any
in
and
such that
, then
is in
.
This is also called the upper set generated by these elements.
EXAMPLES:
sage: B = Posets.BooleanLattice(4)
sage: B.order_filter([3,8])
[3, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Return the order ideal in self generated by the elements of an iterable elements.
A subset of a poset is said to be an order ideal if, for
any
in
and
such that
, then
is in
.
This is also called the lower set generated by these elements.
EXAMPLES:
sage: B = Posets.BooleanLattice(4)
sage: B.order_ideal([7,10])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]
Return the result of toggling the element v in the order ideal I.
EXAMPLES:
sage: P = Poset({1: [2,3], 2: [4], 3: []})
sage: I = Set({1, 2})
sage: I in P.order_ideals_lattice()
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
....: for i in range(4) )
....: for I in P.order_ideals_lattice() )
....: for P in P4 )
True
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.
EXAMPLES:
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}
Return the order ideal generated by an element x.
This is also called the lower set generated by this element.
EXAMPLES:
sage: B = Posets.BooleanLattice(4)
sage: B.principal_order_ideal(6)
[0, 2, 4, 6]
Return the order filter generated by an element x.
This is also called the upper set generated by this element.
EXAMPLES:
sage: B = Posets.BooleanLattice(4)
sage: B.principal_order_filter(2)
[2, 3, 6, 7, 10, 11, 14, 15]
Return the order ideal generated by an element x.
This is also called the lower set generated by this element.
EXAMPLES:
sage: B = Posets.BooleanLattice(4)
sage: B.principal_order_ideal(6)
[0, 2, 4, 6]
Return the order filter generated by an element x.
This is also called the upper set generated by this element.
EXAMPLES:
sage: B = Posets.BooleanLattice(4)
sage: B.principal_order_filter(2)
[2, 3, 6, 7, 10, 11, 14, 15]
Return the upper covers of , that is, the elements
such that
and there exists no
such that
.
EXAMPLES:
sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.upper_covers(3)
[6, 15]
Return the order filter generated by a list of elements.
A subset of a poset is said to be an order filter if, for
any
in
and
such that
, then
is in
.
This is also called the upper set generated by these elements.
EXAMPLES:
sage: B = Posets.BooleanLattice(4)
sage: B.order_filter([3,8])
[3, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Return examples of objects of Posets(), as per Category.example().
EXAMPLES:
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
Return a list of the (immediate) super categories of self, as per Category.super_categories().
EXAMPLES:
sage: Posets().super_categories()
[Category of sets]