Ordering relations

The nodes a preorder can be partitioned into sets of equivalence classes such that for any ordered pair of nodes in an equivalence class there is a path between the two nodes. Every preorder is determined up to isomorphism by a partial ordering of its equivalence classes. Here are several types of preorder relations:

• Equivance relation: the partial ordering relation is empty
• Partial order: every equivalence class is trivial

If the partial ordering relation doesn't contain any undirected cycles that are greater then size two then it forms a tree. It is relatively easy to canonize directed trees and equivalence relations up to isomorphism by describing their shape. However, canonizing ordering relations that contain oriented cycles like the reachability partial order on {A -> B, A -> C, B -> D, C -> D} is a relatively complicated process.

Every relation has a reachability relation associated with it that preorders all nodes in terms of rather or not there is a path between them. Functions have a reachability relation between elements that is a tree of equivalence classes, and since permutations are the union of disjoint cycles their reachability relation is an equivalence relation.