Preorders and Reflexive-Transitive Closure

Preorders

Definition

A relation $R$ on $A$ is a preorder if it is:

1. Reflexive: $\forall a \in A. aRa$
2. Transitive: $\forall a, b, c \in A. (aRb \land bRc \Rightarrow aRc)$

A preorder captures a notion of “being related through a chain of steps” with the base case of being related to oneself.

Examples

• $\leq$ on $\mathbb{R}$: reflexive and transitive
• $\subseteq$ on $\mathcal{P}(X)$: reflexive and transitive
• Reachability in a directed graph: always a preorder
• Divisibility $\mid$ on $\mathbb{Z}^+$: reflexive and transitive

Partial Orders

Definition

A partial order is a preorder that is also antisymmetric:

$aRb \land bRa \Rightarrow a = b$

Preorder vs Partial Order

A preorder may have distinct elements $a \neq b$ with $aRb$ and $bRa$.

Example: ”$x$ and $y$ live in the same country” is a preorder but not a partial order.

Example: Divisibility on $\mathbb{Z}$ is a preorder: $-1 \mid 1$ and $1 \mid -1$, but $-1 \neq 1$.

Quotient to Partial Order

Every preorder $R$ induces an equivalence relation:

$a \sim b \iff aRb \land bRa$

On the quotient $A / {\sim}$, the induced relation is a partial order.

Operations on Preorders

Intersection

If $R$ and $S$ are preorders on $A$, then $R \cap S$ is a preorder.

Proof: Reflexive since $aRa$ and $aSa$, so $a(R \cap S)a$. Transitive since if $a(R \cap S)b$ and $b(R \cap S)c$, then $aRb \land aSb$ and $bRc \land bSc$, so $aRc \land aSc$.

Composition

If $R$ and $S$ are preorders, $R \circ S$ need not be a preorder.

Example: Let $R = \text{id}$ and $S$ be any preorder. Then $R \circ S = S$ is a preorder. But for other relations, composition can fail transitivity.

Reflexive-Transitive Closure

Definition

For any relation $R$ on $A$, the reflexive-transitive closure is:

$R^{\circ *} = \bigcup_{n \geq 0} R^{\circ n}$

where $R^{\circ 0} = \text{id}_A$ and $R^{\circ (n+1)} = R \circ R^{\circ n}$.

Alternative Definition

$R^{\circ *} = \bigcap \{P : R \subseteq P, P \text{ is a preorder}\}$

This is the intersection of all preorders containing $R$.

Examinable Proof: Equivalence of Definitions

Theorem: The two definitions of $R^{\circ *}$ coincide.

Proof:

Step 1: $R^{\circ *}$ as defined by union is a preorder containing $R$.

• $R \subseteq R^{\circ *}$: Clear since $R^{\circ 1} = R$.
• Reflexive: $R^{\circ 0} = \text{id} \subseteq R^{\circ *}$.
• Transitive: If $a R^{\circ *} b$ and $b R^{\circ *} c$, there exist $m, n$ with $a R^{\circ m} b$ and $b R^{\circ n} c$. Then $a R^{\circ (m+n)} c$.

Step 2: $R^{\circ *}$ is contained in every preorder containing $R$.

Let $P$ be a preorder with $R \subseteq P$. By induction, $R^{\circ n} \subseteq P$ for all $n$.

• Base: $R^{\circ 0} = \text{id} \subseteq P$ by reflexivity.
• Step: $R^{\circ (n+1)} = R \circ R^{\circ n} \subseteq P \circ P \subseteq P$ by transitivity.

Thus $R^{\circ *} \subseteq P$.

Step 3: Since $R^{\circ *}$ is a preorder containing $R$ and is contained in all such preorders, it equals their intersection.

Transitive Closure

The transitive closure $R^{\circ +}$ is defined similarly but without reflexivity:

$R^{\circ +} = \bigcup_{n \geq 1} R^{\circ n}$

This is the smallest transitive relation containing $R$.

Relationship

$R^{\circ *} = \text{id} \cup R^{\circ +}$

Computing Closure via Matrix

For an $n$-vertex graph with adjacency matrix $M$:

$M^* = I \oplus M \oplus M^{\otimes 2} \oplus \cdots \oplus M^{\otimes (n-1)}$

This computes $R^{\circ *}$ efficiently.

---

Summary

• A preorder is reflexive and transitive
• A partial order is a preorder that is also antisymmetric
• $R^{\circ *} = \bigcup_{n \geq 0} R^{\circ n}$ is the reflexive-transitive closure
• $R^{\circ *}$ is the smallest preorder containing $R$