Orders

We can let a binary relation provide a notion of order within a set.

Let X be a set and R ⊆ S × S any subset.

Preorder

If (s, s') ⊆ R, write s ⩽ s'. R is a preorder if for all s, s', s'' in S, we have:

• Reflexivity: s ⩽ s, and
• Transitivity: if s ⩽ s′ and s′ ⩽ s″, then s ⩽ s″.

Discrete preorder

The smallest preorder relation that can be put on S is to let a ⩽ b iff a = b.

Indiscrete preorder

The largest relation that can be put on S is to connect everything:

a ⩽ b for all a, b ∈ S

Partial order

A preorder, but an additional property of antisymmetry holds for any two elements in S:

• Antisymmetry: If s ⩽ s′ and s′ ⩽ s, then s = s′.

Linear Order

A partial order, but the property of comparability holds for any two elements in S:

• Comparability: Either s ⩽ s′ or s′ ⩽ s.

Graph Interpretation of orders

Let G be a graph.

• A preorder on the vertices arises by letting an arrow from a to b indicate a ⩽ b.
• If there are no loops in the graph, then there is a partial order on the vertices.
• If there is a path between any two vertices a and b in G, then there is a linear order on the vertices.

Generated preorders

In the same way that every relation generates an equivalence relation that is minimal in some sense, every relation generates a preorder.

R-Paths

Instead of intersecting all equivalence relations containing relation R to get the generated equivalence relation, we instead augment an existing graph with additional arrows:

Let Rg be the generated relation from an existing relation realized from paths in graph G:

• Containment. If (x, y) ∈ R, then (x,y) ∈ Rg. That is, R ⊆ Rg.
• Reflexivity. For all x ∈ X, we have (x,x) ∈ Rg (add self loops).
• Transitivity. For all x, y, z ∈ X, if (x,y) ∈ Rg and (y,z) ∈ Rg , then (x,z) ∈ Rg (add straight-shot connections).

Algorithmically, one can imagine stepping up from R-Paths of length 0 through R-Paths of length n, adding relevant paths as you go in order to satisfy the three rules above. This process will give you a preorder on the graph G which started with connections specified by relation R. One terminates the process when a given level n yields no new arrows.

Cliques

A clique is a subset S′ ⊆ S such that for each a, b ∈ S′, one has a ⩽ b.

In the graph interpretation of cliques, we have a partial order prohibiting nontrivial cliques: a partial order on a graph's vertices means there are no loops with more than two vertices. Imagining arrows as meaning is friends with, we have a clique representing vertices who are all friends with one another (anyone vertex can go out for a beer with any other vertex without other vertices tagging along).

Meets and Joins

A meet is a greatest lower bound and a join is a least upper bound of two elements t and s in preorder (S, ⩽ ).

Meet and join are generalized intersection and union operations, respectively. One can imagine a meet being analogous to taking the intersection of subsets generated from the Powerset of some set X. The "less than" relation among the subsets comes from the natural subset relation ⊆. For example:

meet({1, 2, 3}, {2, 3, 5}) yields {2, 3}
join({1, 2, 3}, {2, 3, 5}) yields {1, 2, 3, 5}

In the join operation above, it would clearly not be the "least upper bound" if we were to say it yields {1, 2, 3, 4, 5, 9, 47}. The join is the least element (subset) which is greater than (contains) the two elements (subsets) being joined.

Monoid structures on meets and joins

If we let the set S be the power-set of some set X, then we can create monoid structures based on meet and join "multiplications":

Meet monoid

Let the Meet monoid be (power-set(X), X, intersect). The unit element is necessarily all of X, so we can ensure that:

intersect(s, X) = s

Let the Join monoid be (power-set(X), {}, union). Similarly, we are guaranteeing that the unit element "does nothing":

union(s, {}) = s

Trees as orders

A tree (let the root be the largest node) is a partial order. This is because antisymmetry exists due to the strict arrows go "downwards" rule. However, trees are usually not linear orders because they are usually not a boring chain. Different nodes at the same level are not comparable, yet they are not equal to one another.

The join operation for two nodes finds the union, which is the least upper bound. This is the closest mutual ancestor for two nodes in the tree.

Opposite orders

Basically, it's easiest to define everything that has been defined up to this point using the less-than symbol. This plays nicely with the efforts taken to generalize intersections and unions of subsets created by the power-set function. The opposite order* reverses the order everything. Meets become joins, and joins become meets.

Morphisms of Orders

A structure preserving function on orders (preorder, partial, or linear).

A function f:S→S′ such that:

For every pair of elements s1, s2 ∈ S, if s1 ⩽ s2, then f(s1) ⩽′ f(s2).