Wednesday, August 21, 2013

Set producing functions

A wide variety of preordering relations can be derived from set producing functions such as the relations of connectivity, reachability, and targeting on any binary relation and the orderings of closure and reachability of any binary operation among others:
  • Reachability: the set of nodes reachable from any node produces a preordering relation parent to any binary relation.
  • Targets: the set of targets of any node also produces a preordering relation for any binary relation. This preordering relation can also be used to reason about certain simple graphs like threshold graphs unlike the reachability relation which is primarily useful for non-strongly-connected components.
  • Closure: the closure ordering on any binary operation produces a preorder which in the case of monoids is the ordering of cyclic submonoids.
Such preordering relations derived from set producing functions appear all over the place in mathematics. Similar concepts can be defined for rings and other related algebraic structures.

No comments:

Post a Comment