
$R$ is asymmetric when there is at most one directed edge between any two vertices, and there are no self-loops:
$\forall x, \ y \in A. \ x \ R \ y \implies \neg(y \ R \ x)$


$R$ is antisymmetric when there is at most one directed edge between any two distinct vertices, but there may be self-loops:
$\forall x \neq y \in A. \ x \ R \ y \implies \neg(y \ R \ x)$
that is,
$\forall x, \ y \in A. \ (x \ R \ y \land y \ R \ x) \implies x = y$


$R$ is transitive if there is a positive length path from $u$ to $v$ , then there is an edge from $u$ to $v$ :
$\forall x, \ y, \ z \in A. \ (x \ R \ y \land y \ R \ z) \implies x \ R \ z$


$R$ is linear when given any two vertices, there is an edge between them in one direction or the other:
$\forall x \neq y \in A. \ (x \ R \ y \lor y \ R \ x)$

Let's now define what is called a strict partial order:

A relation that is transitive and irreflexive is called a strict partial order.

Transitivity says that merging a walk from $u$ to $v$ with a walk from $v$ to $w$ gives a walk from $u$ to $w$ .

Irreflexivity says that there is no positive length walk from a vertex to itself.

We defined them using graph terminology, but we can even think of an example for a strict partial order that has nothing to do with graphs at all. Imagine the "less than" operation:
If $x \lt y$ and $y \lt z$ , then $x \lt z$ . It is transitive.
Since $x \nless x$ implies irreflexivity, we can say that the "less than" operation is both transitive and irreflexive.

One distinction to note is that in asymmetry, self-loops are never allowed; it is antisymmetry that allows it. Since asymmetry implies irreflexivity, we can now better define strict partial orders:

A binary relation $R$ on a set $A$ is a strict partial order iff it is transitive and asymmetric.

Aside from strict partial orders, there are also weak partial orders. They allow self-loops:

A binary relation on a set is a weak partial order iff it is transitive, reflexive, and antisymmetric.

If you have two different numbers, one will be larger than the other. Partial orders with this property are called linear orders. They are also called total orders.

An equivalence relation is a relation that is reflexive, transitive, and symmetric.

A trivial example of an equivalence relation is equality ( $=$ ). It's reflexive, transitive, and symmetric.

One thing to note that if there is a walk from $u$ to $v$ , and a walk from $v$ to $u$ (the symmetry property), it is also said that $u$ and $v$ are strongly connected.

The strong connectedness relation in a digraph is an equivalence relation.

There are also equivalence classes:

The equivalence classes of an equivalence relation on a set $A$ are the blocks of a partition of $A$ .

Note: We mentioned partition briefly in the previous section.

Graphs with the same connections are called isomorphic.
When there is an edge-preserving bijection between two graphs, it means that they are isomorphic.

Bite-Sized Mathematics for Computer Science

Notes on MIT's 6.042J

Partial Orders and Equivalence