Picturing Finite Relations as Graphs

On the previous post about Algebraic Path Finding, I made some figures illustrating how a finite relation can be viewed a graph. This got me thinking about how certain usual notions on relations would translate to this graph world.

This is a mostly visual post illustrating the graphs for many common kinds of relations.

Common Properties

• Reflexivity: Every vertex has a self-edge.

• Transitivity: Connected vertices are also adjacent.

• Symmetry: the graph is undirected.

• Antisymmetry: All cycles are self-edges.

• Connected: there is an edge between all vertices (no matter the direction)

• Strict: no self-edges.

• Totality: Every vertex has an outgoing edge.

• Deterministic: Each vertex has at most one outgoing edge.

Common Relations

Equality

Possibly the most famous relation among all is equality. An element is only equal to itself, meaning that there are only self-edges.

Equivalence Relations

Transitive, Reflexive and Symmetric.

Sometimes it is too strong to require equality of objects. It may be more interesting to look at things that are equivalent.

In an equivalence relation, the vertices are clustered into equivalence classes. An edge exists if and only if the vertices are on the same class.

Preorders

Transitive and Reflexive.

These are graphs where every path corresponds to an edge. That is, if two vertices are connected, then there is an edge between them.

Preorders contain all self-edges and composite edges. Thus, in order to reduce all the noise created by edges that must be there anyway, it is common to only picture the essential edges that cannot be generated from other paths. This is called the relation’s transitive reduction or its Hasse Diagram.

Partial Orders

Transitive, Reflexive and Antisymmetric.

By disallowing cycles in a preorder, what get what is called a partial order. These graphs flow in a certain direction, since a path cannot pass through the same vertices twice.

Again, to prevent all the noise, it is useful to look at the Hasse Diagram.

Total Orders

Transitive, Reflexive, Antisymmetric and Connected.

For these orders, there is also the requirement of existing and (undirected) edge between any pair of vertices.

They are also called Linear Orders because their Hasse Diagram consists of a single path.

Functions

Deterministic and Total.

How could I end this post without illustrating the most pervasive kind of relation in the entire field of mathematics? I’m so used to looking at functions as maps that I even forget that they are relations.

Functions are graphs where all vertices have a unique outgoing edge.