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 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

TESTS:

sage: C = Posets()
sage: TestSuite(C).run()
class ElementMethods
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 x \ge y in the poset self.

INPUT:

  • x, y – elements of self.

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 x > y in the poset self.

INPUT:

  • x, y – elements of self.

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_order_filter(o)

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

INPUT:

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

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
is_order_ideal(o)

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

INPUT:

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

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
le(x, y)

Return whether x \le y in the poset self.

INPUT:

  • x, y – elements of self.

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 x, that is, the elements y such that y<x and there exists no z such that y<z<x.

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 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: 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 x < y in the poset self.

INPUT:

  • x, y – elements of self.

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 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: 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 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: 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 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
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 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}
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 x, that is, the elements y such that x<y and there exists no z such that x<z<y.

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 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: 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 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
Posets.super_categories()

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

EXAMPLES:

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

Previous topic

Partially ordered monoids

Next topic

Pointed sets

This Page