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.