Posets¶
-
class
sage.categories.posets.
Posets
(s=None)¶ 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 inoperator
. Default implementations are provided:sage: P.lt(x, x) False sage: 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: 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()
-
class
ElementMethods
¶
-
Posets.
Finite
¶ alias of
FinitePosets
-
class
Posets.
ParentMethods
¶ -
directed_subset
(elements, direction)¶ 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 – a list of elements.
- direction – ‘up’ or ‘down’.
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]
-
ge
(x, y)¶ Return whether
in the poset
self
.INPUT:
x
,y
– elements ofself
.
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
-
gt
(x, y)¶ Return whether
in the poset
self
.INPUT:
x
,y
– elements ofself
.
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
-
is_antichain_of_poset
(o)¶ Return whether an iterable
o
is an antichain ofself
.INPUT:
o
– an iterable (e. g., list, set, or tuple) containing some elements ofself
OUTPUT:
True
if the subset ofself
consisting of the entries ofo
is an antichain ofself
, andFalse
otherwise.EXAMPLES:
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
An infinite poset:
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
-
is_chain_of_poset
(o, ordered=False)¶ Return whether an iterable
o
is a chain ofself
, including a check foro
being ordered from smallest to largest element if the keywordordered
is set toTrue
.INPUT:
o
– an iterable (e. g., list, set, or tuple) containing some elements ofself
ordered
– a Boolean (default:False
) which decides whether the notion of a chain includes being ordered
OUTPUT:
If
ordered
is set toFalse
, the truth value of the following assertion is returned: The subset ofself
formed by the elements ofo
is a chain inself
.If
ordered
is set toTrue
, the truth value of the following assertion is returned: Every element of the listo
is (strictly!) smaller than its successor inself
. (This makes no sense ifordered
is a set.)EXAMPLES:
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
Examples with infinite posets:
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
-
is_order_filter
(o)¶ Return whether
o
is an order filter ofself
, assumingself
has no infinite ascending path.INPUT:
o
– a list (or set, or tuple) containing some elements ofself
EXAMPLES:
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
-
is_order_ideal
(o)¶ Return whether
o
is an order ideal ofself
, assumingself
has no infinite descending path.INPUT:
o
– a list (or set, or tuple) containing some elements ofself
EXAMPLES:
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
-
le
(x, y)¶ Return whether
in the poset
self
.INPUT:
x
,y
– elements ofself
.
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
-
lower_covers
(x)¶ 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]
-
lower_set
(elements)¶ Return the order ideal in
self
generated by the elements of an iterableelements
.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]
-
lt
(x, y)¶ Return whether
in the poset
self
.INPUT:
x
,y
– elements ofself
.
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
-
order_filter
(elements)¶ 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]
-
order_ideal
(elements)¶ Return the order ideal in
self
generated by the elements of an iterableelements
.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]
-
order_ideal_toggle
(I, v)¶ Return the result of toggling the element
v
in the order idealI
.If
is an element of a poset
, then toggling the element
is an automorphism of the set
of all order ideals of
. It is defined as follows: If
is an order ideal of
, then the image of
under toggling the element
is
- the set
, if
but every element of
smaller than
is in
;
- the set
, if
but no element of
greater than
is in
;
otherwise.
This image always is an order ideal of
.
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(facade=True)) ....: for P in P4) True
- the set
-
order_ideal_toggles
(I, vs)¶ Return the result of toggling the elements of the list (or iterable)
vs
(one by one, from left to right) in the order idealI
.See
order_ideal_toggle()
for a definition of toggling.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}
-
principal_lower_set
(x)¶ 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]
-
principal_order_filter
(x)¶ 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]
-
principal_order_ideal
(x)¶ 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]
-
principal_upper_set
(x)¶ 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]
-
upper_covers
(x)¶ 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]
-
upper_set
(elements)¶ 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]
-
-
Posets.
example
(choice=None)¶ Return examples of objects of
Posets()
, as perCategory.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
-
Posets.
super_categories
()¶ Return a list of the (immediate) super categories of
self
, as perCategory.super_categories()
.EXAMPLES:
sage: Posets().super_categories() [Category of sets]
-
class