Order Theory

Parition of Binary Relationship

A binary relationship \(R\) can be partitioned into two disjoint components: symmetric part \(I_R\) and asymmetric part \(P_R\) according to the following definition:

\[ \begin{align}\begin{aligned}I_R = \{(x,y) \in R \mid (x,y) \in R \text{ and } (y,x) \in R \}\\P_R = \{(x,y) \in R \mid (x,y) \in R \text{ and } (y,x) \notin R \}\end{aligned}\end{align} \]

Below are APIs that implement this partition.

calcpy.binrel.sym_part(r, /)

Get the symmetric part of a binary relationship.

Returns r(a, b) and r(b, a) for relationship r(a, b).

Parameters:

r (Callable[[Any, Any], bool]) – binary relationship, a callable that accepts two positional arguments and returns a bool.

Return type:

Callable[[Any, Any], bool]

Examples

>>> def fracle(a, b):  # <= on fractional part
...     return (a % 1) <= (b % 1)
>>> fraceq = sym_part(fracle)   # == on fractional part
>>> fraceq(0.5, 1.5)
True
>>> fraceq(0.1, 2.3)
False

calcpy.binrel.asym_part(r, /)

Get the asymmetric part of a binary relationship.

Returns r(a, b) and not r(b, a) for relationship r(a, b).

Parameters:

r (Callable[[Any, Any], bool]) – binary relationship, a callable that accepts two positional arguments and returns a bool.

Return type:

Callable[[Any, Any], bool]

Examples

>>> def fracle(a, b):  # <= on fractional part
...     return (a % 1) <= (b % 1)
>>> fraclt = asym_part(fracle)   # == on fractional part
>>> fraclt(0.5, 1.5)
False
>>> fraclt(0.1, 2.3)
True

See also:

https://www.columbia.edu/~md3405/DT_Order_15.pdf

Maximials and Minimals of Posets

Below are APIs to find maximials and minimals of a poset. They have the keyword lt for less-than relationship. If you have less-than-or-equal-to relationship, you can use calcpy.binrel.asym_part() to convert it to less-than relationship.

calcpy.maximal(values, *, lt)

Returns the maximal elements of a poset.

Parameters:

• values (iterable) – Values to find the maximal elements.

• lt (Callable[[Any, Any], bool]) – Less-than checker.

Returns:

Maximal elements.

Return type:

list

Examples

>>> def isproperfactor(a, b):
...     return (b % a == 0) and (a != b)
>>> maximal([2, 3, 4, 5, 6, 7, 8, 9], lt=isproperfactor)
[5, 6, 7, 8, 9]

calcpy.minimal(values, *, lt)

Returns the minimal elements of a poset.

Parameters:

• values (iterable) – Values to find the minimal elements.

• lt (Callable[[Any, Any], bool]) – Less-than checker.

Returns:

Minimal elements.

Return type:

list

Examples

>>> def isproperfactor(a, b):
...     return (b % a == 0) and (a != b)
>>> minimal([2, 3, 4, 5, 6, 7, 8, 9], lt=isproperfactor)
[2, 3, 5, 7]